Itemset Sering dan Apriori¶
Gambaran singkat¶
Apa ini? Apriori adalah algoritma untuk menemukan itemset sering, yaitu kombinasi barang yang cukup sering dibeli bersamaan.
Analogi
Mencari pasangan barang yang laris tanpa memeriksa semua kombinasi. Jika roti saja jarang dibeli, tidak perlu mengecek "roti + mentega + selai" karena pasti lebih jarang lagi.
Mengapa penting? Jumlah kombinasi barang meledak sangat cepat. Apriori memangkas pencarian dengan satu prinsip sederhana sehingga tetap bisa dihitung.
Yang akan dipelajari, berurutan:
- Itemset sering dan
min_support. - Prinsip anti-monoton yang memangkas pencarian.
- Menjalankan Apriori dengan
mlxtend. - Memahami ledakan kombinatorial.
Istilah awal:
| Istilah | Arti sederhana |
|---|---|
| Itemset sering | Kombinasi barang dengan support di atas ambang |
min_support |
Batas minimal kemunculan agar dianggap sering |
| Anti-monoton | Jika kombinasi besar sering, bagian-bagiannya pasti sering |
| Kombinatorial | Jumlah kombinasi yang tumbuh sangat cepat |
Tujuan pembelajaran¶
- Menjelaskan itemset sering (frequent itemset) dan
min_support. - Menjelaskan prinsip Apriori (sifat anti-monoton) dan mengapa ia memangkas pencarian.
- Menjalankan Apriori dengan
mlxtenddan memahami ledakan kombinatorial.
Konsep¶
Itemset sering adalah itemset dengan support di atas ambang min_support. Mencari semuanya secara naif berarti memeriksa seluruh kombinasi barang, yang berjumlah \(2^{p}-1\) untuk \(p\) barang, sehingga tidak praktis.
Sifat anti-monoton: jika sebuah itemset sering, semua himpunan bagiannya juga sering. Sebaliknya, jika {A, B} tidak sering, maka {A, B, C} pasti tidak sering. Apriori memanfaatkannya:
- Hitung support barang tunggal; buang yang di bawah
min_support. - Bentuk kandidat pasangan hanya dari barang yang sering; hitung support; buang yang tidak lolos.
- Bentuk kandidat ukuran \(k+1\) dari itemset ukuran \(k\) yang sering (dan pastikan semua himpunan bagiannya sering); ulangi sampai tidak ada kandidat baru.
| Aspek | Keterangan |
|---|---|
| Kelebihan | Sederhana, mudah dipahami, hasil lengkap untuk ambang yang diberikan |
| Keterbatasan | Memindai data berulang kali dan menghasilkan banyak kandidat bila min_support rendah |
| Parameter | min_support, max_len |
Implementasi langkah demi langkah¶
Memakai 2000 transaksi sintetis (penjelasan) dan mlxtend.frequent_patterns.apriori. Program examples/association/apriori.py; program lengkap ada di akhir bagian ini.
Langkah 1: menyiapkan matriks transaksi¶
make_transactions() menghasilkan 2000 keranjang; TransactionEncoder mengubahnya menjadi tabel True/False berukuran 2000 × 20 (lesson sebelumnya). df.shape[1] adalah jumlah kolom = jumlah barang.
Langkah 2: mencari itemset sering¶
Tujuan. Menemukan semua itemset yang muncul pada minimal 5% transaksi.
| Kode | Penjelasan |
|---|---|
apriori(df, min_support=0.05, use_colnames=True) |
Menjalankan Apriori. min_support=0.05 berarti itemset harus ada di ≥ 5% transaksi (≥ 100 dari 2000). use_colnames=True menampilkan nama barang (bukan nomor kolom). Hasilnya tabel berkolom support dan itemsets. |
itemsets["itemsets"].apply(len) |
Jumlah barang tiap itemset; disimpan di kolom size. |
value_counts().sort_index().to_dict() |
Berapa itemset sering untuk tiap ukuran (1, 2, 3). |
Hasil. Ada 54 itemset sering: 20 barang tunggal (seluruh barang masih lolos), 29 pasangan, dan 5 itemset tiga barang.
Langkah 3: itemset dengan support tertinggi¶
| apriori.py | |
|---|---|
Hanya itemset berukuran ≥ 2 diambil dan diurutkan menurut support; " + ".join(sorted(s)) mengubah himpunan barang menjadi teks seperti mentega + roti; .head(6) mengambil enam teratas.
itemsets support
mentega + roti 0.220
gula + kopi 0.126
air_mineral + kantong_plastik 0.119
kantong_plastik + roti 0.118
kantong_plastik + mentega 0.106
mie_instan + telur 0.106
Interpretasi. Pasangan teratas: mentega + roti (0,220), gula + kopi (0,126), air_mineral + kantong_plastik (0,119), kantong_plastik + roti (0,118). Pasangan dengan kantong_plastik muncul sering karena kantong itu sendiri populer (44,8% keranjang), bukan karena ada hubungan khusus; support tinggi belum berarti asosiasi (dibahas di lesson aturan).
Langkah 4: sifat anti-monoton¶
Konsep. Support sebuah itemset tidak pernah melebihi support himpunan bagiannya. Sifat inilah yang memungkinkan Apriori memangkas pencarian.
sup adalah kamus {itemset (frozenset): support}; frozenset adalah himpunan yang tidak dapat diubah sehingga boleh dipakai sebagai kunci kamus. Baris cetak membandingkan support {roti}, {mentega}, dan {roti, mentega}.
Hasil. {roti} = 0,264 dan {mentega} = 0,246, sedangkan {roti, mentega} = 0,220: tidak pernah melebihi himpunan bagiannya.
Langkah 5: ledakan kombinatorial dan max_len¶
Perulangan menjalankan Apriori dengan lima nilai min_support dan mencetak jumlah itemset yang dihasilkan. Baris terakhir memakai max_len=2 untuk membatasi ukuran itemset maksimal dua barang.
min_support jumlah itemset sering
0.2 7
0.1 21
0.05 54
0.02 170
0.01 394
min_support=0.01 dengan max_len=2: 177
Interpretasi. Jumlah itemset sering naik cepat saat min_support turun: 7 (0,2), 21 (0,1), 54 (0,05), 170 (0,02), dan 394 (0,01). Dengan 20 barang saja sudah terlihat; dengan ribuan barang jumlahnya dapat melampaui kemampuan memori. Membatasi itemset maksimal dua barang pada min_support=0,01 memangkas hasil dari 394 menjadi 177.
Program lengkap (apriori.py)
Kesalahan umum¶
Hindari
- Memakai
min_supportsangat rendah pada banyak barang tanpamax_len. - Menyimpulkan bahwa itemset dengan support tinggi pasti punya asosiasi.
- Lupa bahwa
min_supportharus sesuai ukuran data (5% dari 100 transaksi hanya 5 keranjang). - Menggunakan barang yang hampir ada di semua keranjang.
Latihan¶
- Naikkan
min_supportke 0,15. Itemset apa saja yang tersisa? - Hitung secara manual jumlah kandidat pasangan dari 20 barang dan bandingkan dengan 29 yang lolos.
- Hapus
kantong_plastikdanair_mineraldari data. Bagaimana pasangan teratas berubah?
Ringkasan¶
Apriori mencari itemset sering dengan memangkas kandidat berdasarkan sifat anti-monoton. Pilih min_support dan max_len dengan hati-hati karena jumlah itemset dapat meledak.
Berikutnya: FP-Growth.