FP-Growth (Pertumbuhan Pola Frekuen)
- Diperkenalkan oleh
- Jiawei Han, Jian Pei & Yiwen Yin
- Tahun
- 2000
- Jenis
- Frequent-itemset mining algorithm
- Keluarga
- Pattern mining
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
FP-Growth, diperkenalkan oleh Jiawei Han, Jian Pei, dan Yiwen Yin pada tahun 2000, menambang kumpulan item yang sering muncul dari data transaksi tanpa menghasilkan himpunan kandidat, langkah mahal yang memperlambat algoritma Apriori klasik.
Algoritma ini mengompresi basis data menjadi pohon pola frekuen (FP-tree) dalam dua pemindaian, kemudian menumbuhkan pola frekuen secara rekursif dari struktur tersebut, membuatnya jauh lebih cepat daripada Apriori pada kumpulan data yang besar dan padat.
Intuisi di balik metode
Apriori menemukan kumpulan item yang sering muncul dengan berulang kali menghasilkan dan menguji kombinasi kandidat — sebuah proses yang mahal dan banyak pemindaian yang meledak pada data padat. FP-Growth mengambil rute yang berbeda: ia memeras seluruh basis data transaksi ke dalam pohon yang ringkas di mana awalan bersama disimpan sekali, sehingga pola umum tumpang tindih dan terkompresi. Kemudian, alih-alih menghasilkan kandidat, ia membaca pola frekuen langsung dari pohon dengan mengikuti jalur yang mengarah ke setiap item dan secara rekursif menambang pohon 'kondisional' yang lebih kecil. Dua kali pemindaian data dan struktur data yang cerdas menggantikan banyak pemindaian Apriori dan ledakan kandidat kombinatorial.
Sejarah
Han, Pei, dan Yin mempresentasikan FP-Growth di SIGMOD 2000 sebagai alternatif bebas generasi kandidat untuk Apriori, dengan perlakuan yang diperluas dalam artikel Data Mining and Knowledge Discovery mereka tahun 2004. Gagasan pohon pola frekuen — mengompresi transaksi ke dalam struktur awalan bersama dan menambangnya secara rekursif — menjadi teknik fundamental dalam penambangan pola, bersama dengan Apriori (berbasis kandidat) dan ECLAT (format vertikal). Algoritma ini tetap menjadi penambang itemset standar berkinerja tinggi dalam pustaka penambangan data.
Kapan digunakan
Gunakan FP-Growth untuk menambang kumpulan item frekuen (dan, hilir, aturan asosiasi) dari data transaksional — analisis keranjang belanja, penambangan penggunaan web dan aliran klik, rekomendasi, dan ko-okurensi bioinformatika — terutama pada kumpulan data besar atau padat di mana generasi kandidat Apriori terlalu lambat. Algoritma ini hanya memerlukan dua pemindaian basis data dan biasanya berkinerja jauh lebih baik daripada Apriori. Biayanya: FP-tree harus muat di memori (batasan untuk data yang sangat besar atau sangat jarang, di mana pohon terkompresi dengan buruk), rekursi bisa rumit untuk diimplementasikan, dan seperti semua penambangan berbasis dukungan, algoritma ini sensitif terhadap ambang batas dukungan minimum (terlalu rendah meledakkan keluaran, terlalu tinggi melewatkan pola). ECLAT (interseksi tidset vertikal) adalah alternatif; untuk aturan itu sendiri, pasangkan dengan generasi aturan asosiasi.
Batasan dan pertimbangan
- FP-tree harus muat di memori; kumpulan data yang sangat besar mungkin tidak.
- Pada data jarang, pohon terkompresi dengan buruk, mengurangi keuntungannya.
- Konstruksi pohon kondisional rekursif relatif kompleks untuk diimplementasikan.
- Sensitif terhadap ambang batas dukungan minimum, seperti semua penambangan kumpulan item frekuen.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Tanpa generasi kandidat — jauh lebih cepat daripada Apriori pada data besar/padat.
- Hanya dua pemindaian basis data, terlepas dari panjang pola.
- FP-tree mengompresi struktur bersama, menghemat memori dan waktu pada data padat.
- Skalabilitas ke pola frekuen panjang yang mengalahkan metode berbasis kandidat.
Penerapan
- Analisis keranjang belanja dan penambangan asosiasi ritel.
- Penambangan pola penggunaan web dan aliran klik.
- Rekomendasi melalui item yang sering bersama-sama muncul.
- Ko-okurensi bioinformatika dan penemuan motif.
- Tugas kumpulan item frekuen skala besar apa pun di mana Apriori terlalu lambat.
Cara kerjanya
Cara kerjanya
Pemindaian basis data pertama menghitung dukungan setiap item dan membuang item di bawah ambang batas dukungan minimum. Item frekuen yang tersisa diurutkan berdasarkan frekuensi menurun — urutan ini memungkinkan transaksi berbagi awalan pohon dan menjaga FP-tree tetap ringkas.
Rumus
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}Pemindaian kedua memasukkan setiap transaksi (item frekuennya, dalam urutan yang diurutkan) ke dalam FP-tree, menambah hitungan di sepanjang jalur awalan bersama dan menambahkan cabang baru sesuai kebutuhan. Tabel header menghubungkan semua kemunculan setiap item, sehingga pohon secara ringkas mewakili struktur frekuen seluruh basis data.
Rumus
\text{second scan: insert each transaction's frequent items into the FP-tree}Untuk setiap item frekuen (diproses dari yang paling tidak frekuen terlebih dahulu), algoritma mengumpulkan basis pola kondisionalnya — himpunan jalur awalan dalam pohon yang bersama-sama muncul dengan item tersebut, masing-masing diberi bobot berdasarkan hitungannya. Ini menangkap konteks di mana item tersebut muncul secara frekuen.
Rumus
\text{for each item: collect its conditional pattern base (prefix paths)}Dari setiap basis pola kondisional, pohon FP kondisional yang lebih kecil dibangun dan ditambang secara rekursif, menumbuhkan kumpulan item frekuen yang lebih panjang dengan menambahkan item ke pola yang ditemukan di pohon kondisionalnya. Rekursi berakhir pada pohon jalur tunggal, yang kombinasi kumpulan itemnya dihitung secara langsung — menghasilkan semua kumpulan item frekuen tanpa generasi kandidat.
Rumus
\text{build conditional FP-trees recursively to grow frequent patterns}Kesalahan umum
- Menetapkan dukungan minimum terlalu rendah, menghasilkan ledakan kumpulan item.
- Menganggapnya selalu mengalahkan Apriori — pada data kecil atau jarang, peningkatannya sedang.
- Melupakan bahwa kumpulan item frekuen bukanlah aturan; generasi aturan adalah langkah terpisah.
- Mengabaikan batasan memori ketika FP-tree tidak dapat disimpan di RAM.
Pertanyaan yang sering diajukan
Bagaimana FP-Growth lebih cepat dari Apriori?
Apriori berulang kali menghasilkan dan menguji kumpulan item kandidat, memindai basis data berkali-kali. FP-Growth sepenuhnya menghindari generasi kandidat: ia mengompresi data menjadi FP-tree dalam dua pemindaian dan menambang pola secara rekursif darinya. Ini menghilangkan ledakan kandidat kombinatorial, memberikan percepatan besar pada data padat.
Apa itu FP-tree?
Pohon awalan terkompresi dari item frekuen basis data. Transaksi yang berbagi awalan berbagi jalur, dengan hitungan node mencatat dukungan, dan tabel header menghubungkan kemunculan setiap item. Pohon ini menyimpan struktur frekuen basis data secara ringkas sehingga pola dapat dibaca tanpa memindai ulang data.
Bagaimana FP-Growth berhubungan dengan ECLAT dan aturan asosiasi?
FP-Growth, ECLAT, dan Apriori semuanya menemukan kumpulan item frekuen; ECLAT menggunakan pendekatan interseksi tidset vertikal alih-alih pohon. Menemukan kumpulan item frekuen hanyalah tahap pertama — aturan asosiasi (dengan kepercayaan/lift) dihasilkan dari kumpulan item tersebut dalam langkah terpisah.
Metode terkait
Sumber
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
Buka referensi DOIDisalin.Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.
Buka referensi DOIDisalin.