FP-Growth¶
Gambaran singkat¶
Apa ini? FP-Growth adalah cara lain dan lebih cepat untuk menemukan itemset sering, memakai struktur pohon.
Analogi
Daripada mencatat ulang setiap struk, Anda menggabungkan struk yang awalnya sama dalam satu cabang pohon sehingga lebih ringkas.
Mengapa penting? Pada data besar, Apriori harus membuat banyak kandidat. FP-Growth menghindarinya dengan memampatkan data lebih dulu, tetapi hasilnya sama.
Yang akan dipelajari, berurutan:
- Ide FP-Growth dan bedanya dari Apriori.
- Mengurutkan barang menurut frekuensi pada FP-tree.
- Membuktikan hasilnya sama dengan Apriori.
Istilah awal:
| Istilah | Arti sederhana |
|---|---|
| FP-tree | Pohon yang memampatkan transaksi berawalan sama |
| Prefix | Awalan yang sama pada beberapa transaksi |
| Kandidat | Kombinasi yang perlu dicek apakah sering |
Tujuan pembelajaran¶
- Menjelaskan ide FP-Growth dan perbedaannya dari Apriori.
- Memahami urutan barang berdasarkan frekuensi pada FP-tree.
- Memastikan bahwa Apriori dan FP-Growth menghasilkan itemset yang sama.
Konsep¶
FP-Growth (Frequent Pattern Growth) menghindari pembentukan kandidat dalam jumlah besar. Prosesnya:
- Pindai data sekali untuk menghitung frekuensi tiap barang; buang yang di bawah
min_support. - Urutkan barang pada tiap transaksi menurut frekuensi menurun.
- Bangun FP-tree, yaitu struktur pohon yang menggabungkan awalan (prefix) transaksi yang sama sehingga data dimampatkan.
- Gali itemset sering dengan menelusuri pohon secara rekursif, tanpa menghasilkan kandidat secara eksplisit.
| Apriori | FP-Growth | |
|---|---|---|
| Strategi | Bangkitkan kandidat, lalu uji | Mampatkan data ke pohon, lalu gali |
| Pemindaian data | Berkali-kali | Dua kali |
| Hasil | Itemset sering yang sama | Itemset sering yang sama |
| Kecenderungan | Lambat dan boros memori pada min_support rendah |
Umumnya lebih cepat pada data besar dan padat |
Perbedaan keduanya hanya pada cara menemukan itemset, bukan pada hasilnya.
Implementasi langkah demi langkah¶
Bagian 1 memperlihatkan langkah 1–2 FP-Growth pada contoh lima transaksi. Bagian 2 membandingkan hasil Apriori dan FP-Growth pada 2000 transaksi sintetis. Program examples/association/fpgrowth.py; program lengkap ada di akhir bagian ini.
Langkah 1: urutan barang menurut frekuensi (persiapan FP-tree)¶
Tujuan. Memahami langkah awal FP-Growth: menghitung frekuensi barang, membuang yang di bawah ambang, dan mengurutkan barang tiap transaksi menurut frekuensi menurun.
| Kode | Penjelasan |
|---|---|
pd.Series([i for t in tiny for i in t]).value_counts() |
Meratakan semua transaksi menjadi satu daftar barang lalu menghitung frekuensi tiap barang. |
counts[counts >= 2].index.tolist() |
Barang dengan frekuensi ≥ 2 (ambang minimal 2 dari 5 transaksi), berurutan menurun; ini urutan header. |
sorted(t, key=order.index) |
Mengurutkan barang dalam satu transaksi menurut posisinya di order (frekuensi tertinggi dulu). |
frekuensi barang: {'roti': 4, 'mentega': 3, 'susu': 2, 'telur': 2}
urutan header (menurun): ['roti', 'mentega', 'susu', 'telur']
transaksi diurutkan: ['roti', 'mentega']
transaksi diurutkan: ['roti', 'susu']
transaksi diurutkan: ['roti', 'mentega', 'telur']
transaksi diurutkan: ['susu', 'telur']
transaksi diurutkan: ['roti', 'mentega']
Interpretasi. Frekuensi roti 4, mentega 3, susu 2, telur 2; dengan ambang minimal 2 transaksi semua barang lolos, dan urutan header menurun adalah roti, mentega, susu, telur. Tiap transaksi diurutkan mengikuti urutan itu (misalnya roti, mentega, telur). Transaksi yang berawalan sama (roti, mentega) akan berbagi cabang pada FP-tree, itulah sebabnya data termampatkan.
Langkah 2: Apriori dan FP-Growth menghasilkan itemset yang sama¶
| Kode | Penjelasan |
|---|---|
fpgrowth(df, min_support=ms, use_colnames=True) |
Antarmuka sama dengan apriori; hanya algoritmanya yang berbeda. |
{frozenset(x): round(s, 10) for x, s in zip(...)} |
Mengubah hasil menjadi kamus {itemset: support} (support dibulatkan agar perbandingan tidak terganggu pembulatan komputer). |
sa == sf |
Membandingkan dua kamus sebagai himpunan pasangan: True bila isinya persis sama. |
min_support=0.05: Apriori 54 itemset | FP-Growth 54 itemset | identik: True
min_support=0.01: Apriori 394 itemset | FP-Growth 394 itemset | identik: True
Hasil. Pada min_support 0,05 dan 0,01, Apriori dan FP-Growth sama-sama menghasilkan 54 dan 394 itemset dengan support yang sama persis (identik: True).
Langkah 3: urutan baris tidak dijamin sama¶
| fpgrowth.py | |
|---|---|
Baris ini membandingkan urutan itemset pada kedua hasil (bukan isinya).
Hasil. False: kedua fungsi tidak menjamin urutan baris yang sama, sehingga bandingkan sebagai himpunan (seperti di Langkah 2), bukan sebagai urutan.
Soal kecepatan
FP-Growth biasanya lebih cepat daripada Apriori ketika min_support rendah dan data besar. Materi ini tidak mengukur waktu (waktu bergantung perangkat dan data); untuk memeriksanya pada data Anda, ukur dengan time.perf_counter() untuk kedua fungsi pada min_support yang sama.
Program lengkap (fpgrowth.py)
Kesalahan umum¶
Hindari
- Mengira FP-Growth menghasilkan aturan yang lebih baik; hasilnya sama, hanya caranya berbeda.
- Membandingkan hasil dengan urutan baris.
- Mengabaikan batas memori pada
min_supportsangat rendah, bahkan dengan FP-Growth. - Mengukur waktu dengan sekali jalan pada data kecil.
Latihan¶
- Ukur waktu
aprioridanfpgrowthpadamin_support0,05; 0,02; 0,01 menggunakantime.perf_counter(). - Gambar FP-tree untuk lima transaksi kecil dengan tangan.
- Bangkitkan 20.000 transaksi (
make_transactions(n=20000)) dan ulangi pengukuran waktu.
Ringkasan¶
FP-Growth menemukan itemset sering yang sama dengan Apriori memakai FP-tree sehingga menghindari kandidat dalam jumlah besar. Pilih berdasarkan skala data, dan jangan membandingkan hasil dengan urutan baris.
Berikutnya: Aturan Asosiasi: Support, Confidence, Lift.