Lewati ke isi

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:

  1. Itemset sering dan min_support.
  2. Prinsip anti-monoton yang memangkas pencarian.
  3. Menjalankan Apriori dengan mlxtend.
  4. 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 mlxtend dan 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:

  1. Hitung support barang tunggal; buang yang di bawah min_support.
  2. Bentuk kandidat pasangan hanya dari barang yang sering; hitung support; buang yang tidak lolos.
  3. 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

apriori.py
import pandas as pd
from mlxtend.frequent_patterns import apriori
from mlxtend.preprocessing import TransactionEncoder

from basket_data import make_transactions

transactions = make_transactions()
te = TransactionEncoder()
df = pd.DataFrame(te.fit(transactions).transform(transactions), columns=te.columns_)
print("transaksi:", len(df), "| barang:", df.shape[1])

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.

apriori.py
# 1. Itemset sering dengan min_support = 0.05 (minimal 5% transaksi)
itemsets = apriori(df, min_support=0.05, use_colnames=True)
itemsets["size"] = itemsets["itemsets"].apply(len)
print("\nitemset sering: %d | menurut ukuran: %s" % (len(itemsets), itemsets["size"].value_counts().sort_index().to_dict()))
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).
transaksi: 2000 | barang: 20

itemset sering: 54 | menurut ukuran: {1: 20, 2: 29, 3: 5}

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
# 2. Itemset berukuran >= 2 dengan support tertinggi
multi = itemsets[itemsets["size"] >= 2].sort_values("support", ascending=False)
multi["itemsets"] = multi["itemsets"].apply(lambda s: " + ".join(sorted(s)))
print("\n" + multi.head(6)[["itemsets", "support"]].round(3).to_string(index=False))

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.

apriori.py
# 3. Sifat anti-monoton: support sebuah itemset tidak pernah melebihi support himpunan bagiannya
sup = {frozenset(r.itemsets): r.support for r in itemsets.itertuples()}
pair = frozenset({"roti", "mentega"})
print("\nsupport {roti}=%.3f, {mentega}=%.3f, {roti, mentega}=%.3f" % (
    sup[frozenset({"roti"})], sup[frozenset({"mentega"})], sup[pair]))

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}.

support {roti}=0.264, {mentega}=0.246, {roti, mentega}=0.220

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

apriori.py
# 4. Pengaruh min_support terhadap jumlah itemset (ledakan kombinatorial)
print("\nmin_support  jumlah itemset sering")
for ms in [0.2, 0.1, 0.05, 0.02, 0.01]:
    print(f"{ms:<12} {len(apriori(df, min_support=ms, use_colnames=True))}")

# 5. Membatasi ukuran itemset dengan max_len
print("\nmin_support=0.01 dengan max_len=2:", len(apriori(df, min_support=0.01, use_colnames=True, max_len=2)))

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)
apriori.py
import pandas as pd
from mlxtend.frequent_patterns import apriori
from mlxtend.preprocessing import TransactionEncoder

from basket_data import make_transactions

transactions = make_transactions()
te = TransactionEncoder()
df = pd.DataFrame(te.fit(transactions).transform(transactions), columns=te.columns_)
print("transaksi:", len(df), "| barang:", df.shape[1])

# 1. Itemset sering dengan min_support = 0.05 (minimal 5% transaksi)
itemsets = apriori(df, min_support=0.05, use_colnames=True)
itemsets["size"] = itemsets["itemsets"].apply(len)
print("\nitemset sering: %d | menurut ukuran: %s" % (len(itemsets), itemsets["size"].value_counts().sort_index().to_dict()))

# 2. Itemset berukuran >= 2 dengan support tertinggi
multi = itemsets[itemsets["size"] >= 2].sort_values("support", ascending=False)
multi["itemsets"] = multi["itemsets"].apply(lambda s: " + ".join(sorted(s)))
print("\n" + multi.head(6)[["itemsets", "support"]].round(3).to_string(index=False))

# 3. Sifat anti-monoton: support sebuah itemset tidak pernah melebihi support himpunan bagiannya
sup = {frozenset(r.itemsets): r.support for r in itemsets.itertuples()}
pair = frozenset({"roti", "mentega"})
print("\nsupport {roti}=%.3f, {mentega}=%.3f, {roti, mentega}=%.3f" % (
    sup[frozenset({"roti"})], sup[frozenset({"mentega"})], sup[pair]))

# 4. Pengaruh min_support terhadap jumlah itemset (ledakan kombinatorial)
print("\nmin_support  jumlah itemset sering")
for ms in [0.2, 0.1, 0.05, 0.02, 0.01]:
    print(f"{ms:<12} {len(apriori(df, min_support=ms, use_colnames=True))}")

# 5. Membatasi ukuran itemset dengan max_len
print("\nmin_support=0.01 dengan max_len=2:", len(apriori(df, min_support=0.01, use_colnames=True, max_len=2)))

Kesalahan umum

Hindari

  • Memakai min_support sangat rendah pada banyak barang tanpa max_len.
  • Menyimpulkan bahwa itemset dengan support tinggi pasti punya asosiasi.
  • Lupa bahwa min_support harus sesuai ukuran data (5% dari 100 transaksi hanya 5 keranjang).
  • Menggunakan barang yang hampir ada di semua keranjang.

Latihan

  1. Naikkan min_support ke 0,15. Itemset apa saja yang tersisa?
  2. Hitung secara manual jumlah kandidat pasangan dari 20 barang dan bandingkan dengan 29 yang lolos.
  3. Hapus kantong_plastik dan air_mineral dari 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.