Asosiasi Data Mining: Algoritma Apriori dan FP Growth

Asosiasi Data Mining – Algoritma asosiasi data mining merupakan suatu bentuk algoritma yang memberikan informasi tentang hubungan antar item data di dalam database. Salah satu pemanfaatan algoritma asosiasi untuk proses bisnis diantaranya dalam proses penjualan. Terapat dua algoritma dalam asosiasi data mining yakni algoritma apriori dan algoritma FP growth.

Baca Juga Algoritma Clustering dalam Data Mining: Metode Partisi

Apa itu Frequent Pattern Analysis?

Frequent Pattern merupakan sebuah pola (satu set item, berikutnya, substruktur, dll) yang sering terjadi dalam kumpulan data. Pertama kali diusulkan oleh Agrawal, Imielinski, dan Swami [AIS93] dalam konteks frequent itemset dan asosiasi rule mining. Tujuannya yaitu Menemukan keteraturan yang melekat dalam data, seperti:

• Produk apa yang sering dibeli bersama? – Bir dan popok ?!
• Apa pembelian selanjutnya setelah membeli PC?
• Jenis DNA apa yang sensitif terhadap obat baru ini?
• Bisakah kita secara otomatis mengklasifikasikan dokumen web?

Penerapan Frequent Pattern Analysis diantaranya: Analisis data keranjang, cross-marketing (pemasaran silang), desain katalog, analisis kampanye penjualan, analisis log Web (aliran klik), dan analisis urutan DNA.

Mengapa Frequent Pattern Mining itu penting dalam Asosiasi Data Mining?

Frequent Pattern berfungsi untuk menemukan Properti intrinsik dan penting dari dataset. Hal ini menjadi dasar untuk banyak tugas penting data mining seperti:

• Asosiasi, korelasi, dan analisis kausalitas
• Pola berurutan, struktural (mis., Sub-grafik)
• Analisis pola dalam spatiotemporal, multimedia, jadwal waktu, dan aliran data
• Klasifikasi: diskriminatif, analisis pola yang sering
• Analisis kluster: pengelompokan berbasis pola yang sering
• Penyimpanan data: kubus gunung es dan kubus-gradien
• Kompresi data semantik: fasik
• Aplikasi luas

Konsep Dasar Frequent Pattern dalam Asosiasi Data Mining

• itemset: Satu set dar satu item atau lebih.
• k-itemset X = {x1, …, xk}
• support (absolut), atau, jumlah support dari X: Frekuensi atau kemunculan itemset X
• support (relatif), s, adalah fraksi transaksi yang mengandung X (mis., Probabilitas bahwa suatu transaksi mengandung X)
• Itemset X sering terjadi jika dukungan X tidak kurang dari ambang batas minsup
• Temukan semua aturan X → Y dengan dukungan dan kepercayaan minimum
  • support, s, probabilitas bahwa suatu transaksi mengandung X ∪ Y
  • confidence, c, probabilitas bersyarat bahwa transaksi yang memiliki X juga mengandung Y

Misalkan minsup = 50%, minconf = 50%
Frequent Pattern: Beer: 3, Nuts: 3, Diaper: 4, Eggs: 3, {Beer, Diaper}: 3

Association rules: (many more!)

• Beer → Diaper (60%, 100%)
• Diaper → Beer (60%, 75%)

Closed Patterns dan Max-Patterns dalam Asosiasi Data Mining

• Pola panjang berisi sejumlah kombinasi subpola, misalnya {a₁ , …, a₁₀₀} berisi (100¹ ) + (100² ) + … + (₁¹₀⁰₀⁰) = 2¹⁰⁰ – 1 = 1.27*10³⁰ sub -pola!
• Solusi: Tambang closed patterns dan max-patterns sebagai gantinya
• Itemset X ditutup jika X sering dan tidak ada pola super Y כ X, dengan dukungan yang sama seperti X (diusulkan oleh Pasquier, dkk. @ ICDT’99)
• Itemset X adalah max-patterns jika X sering dan tidak ada pola super sering Y כ X (diusulkan oleh Bayardo @ SIGMOD’98)
• Pola tertutup adalah kompresi lossless dari pola yang sering
  • Mengurangi # pola dan aturan

• Latihan. DB = {< a₁ , …, a₁₀₀>, < a₁ , …, a₅₀>}
  • Min_sup = 1.
• Apa himpunan dari closed itemset ?
  • < a₁ , …, a₁₀₀> : 1
  • < a₁ , …, a₅₀> : 2
• Apa himpunan dari max-pattern ?
  • < a₁ , …, a₁₀₀>
• Apa himpunan semua pola?
  • !!

Kompleksitas Komputasi dari Frequent Itemset Mining

• Berapa banyak itemet yang berpotensi dihasilkan dalam kasus terburuk?
  • Jumlah set item yang sering dihasilkan adalah senstive ke ambang menit
  • Ketika menit rendah, ada kemungkinan ada sejumlah item yang eksponensial
  • Kasus terburuk: MN di mana M: # item berbeda, dan N: panjang transaksi maksimum
• Kompleksitas kasus terburuk vs. probabilitas yang diharapkan
• Ex. Misalkan Walmart memiliki 104 jenis produk
  • Kesempatan untuk mengambil satu produk 10-4
  • Kesempatan untuk mengambil satu set 10 produk tertentu: ~ 10-40
  • Berapa peluang 10 set produk ini untuk sering muncul sebanyak 103 kali dalam 109 transaksi?

Baca Juga Persiapan Data Dalam Data Mining: Data Reduction

Metode Frequent Itemset Mining dalam Asosiasi Data Mining

Metode Scalable Frequent Itemset Mining

• Apriori: Pendekatan Pembuatan dan Uji Kandidat
• Meningkatkan Efisiensi Apriori
• FPGrowth: Pendekatan Pola-Pertumbuhan yang Sering
• ECLAT: Frequent Pattern Mining dengan Format Data Vertikal

Metode The Downward Closure Property and Scalable Mining

• The downward closure property dari frequent patterns
  • Setiap subset dari itemset yang sering harus sering
  • Jika {bir, popok, kacang} sering, begitu juga {bir, popok}
  • misalnya, Setiap transaksi yang mengandung {bir, popok, kacang} juga mengandung {bir, popok}
• Scalable Mining Methods: Tiga pendekatan utama
  • Apriori (Agrawal & Srikant @ VLDB’94)
  • Frekuensi. pertumbuhan pola (FPgrowth — Han, Pei & Yin @ SIGMOD’00)
  • Pendekatan format data vertikal (Charm — Zaki & Hsiao @ SDM’02)

Algoritma Apriori: Calon Generasi & Pendekatan Uji

Prinsip pemangkasan Apriori: Jika ada itemet yang jarang terjadi, supersetnya tidak boleh dihasilkan / diuji! (Agrawal & Srikant VLDB’94, Mannila, dkk. @ KDD ’94). Berikut ini langkah-langkah dalam Algoritma Apriori:

1. Mulanya, pindai DB sekali untuk mendapatkan 1-itemet sesering mungkin
2. Hasilkan panjang (k + 1) kandidat itemset dari length k frequent itemset
3. Uji kandidat terhadap DB
4. Hentikan ketika tidak ada kandidat sering atau set dapat dihasilkan

Contoh Algoritma Apriori

Pseudo-Code Algoritma Apriori

Ck: Kandidat itemset ukuran k
Lk: frequent itemset ukuran k

L1 = {frequent items};
for (k = 1; Lk!=; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database do
increment the count of all candidates in Ck+1 that are contained in t
Lk+1 = candidates in Ck+1 with min_support
end
return ∪k Lk;

Implementasi Algoritma Apriori

• Bagaimana cara menghasilkan kandidat?
  • Langkah 1: self-joining Lk
  • Langkah 2: pruning
• contoh dari calon generasi
  • L3={abc, abd, acd, ace, bcd}
  • Self-joining: L3*L3
    • abcd dari abc dan abd
    • acde dari acd dan ace
  • Pruning:
    • acde dihapus karena ade tidak termasuk L3
  • C₄ = {abcd}

Bagaimana Menghitung Support of Candidates?

• Mengapa menghitung dukungan kandidat merupakan masalah?
  • Jumlah total kandidat bisa sangat besar
  • Satu transaksi mungkin mengandung banyak kandidat
• Metode:
  • Kandidat item disimpan di hash-tree
  • Node daun hash-tree berisi daftar itemet dan jumlah
  • Interior node berisi tabel hash
  • Fungsi subset: menemukan semua kandidat yang terkandung dalam transaksi

Menghitung Support of Candidates Menggunakan Hash Tree

Candidate Generation: Implementasi SQL

• Implementasi SQL dari generasi kandidat
  • Misalkan item dalam Lk-1 terdaftar dalam suatu urutan
  • Langkah 1: bergabung sendiri Lk-1
    insert into Ck
    select p.item1 , p.item2 , …, p.itemk-1 , q.itemk-1
    from Lk-1 p, Lk-1 q
    where p.item1=q.item1 , …, p.itemk-2=q.itemk-2 , p.itemk-1 < q.itemk-1
  • Langkah 2: pruning
    forall itemsets c in Ck do
    forall (k-1)-subsets s of c do
    if (s is not in Lk-1) then delete c from Ck
• Gunakan ekstensi objek-relasional seperti fungsi UDF, BLOB, dan Tabel untuk implementasi yang efisien (S. Sarawagi, S. Thomas, dan R. Agrawal. Mengintegrasikan penambangan aturan asosiasi dengan sistem basis data relasional: Alternatif dan implikasi. SIGMOD’98)

Pendekatan Frequent Pattern Growth (FP Growth): Frekuensi Penambangan Pola Tanpa Candidate Generation

• Hambatan pendekatan Apriori
  • Pencarian Breadth-first (mis., Level-wise)
  • Membuat kandidat dan ujian
    • Seringkali menghasilkan sejumlah besar kandidat
• Pendekatan FPGrowth (J. Han, J. Pei, dan Y. Yin, SIGMOD ’00)
  • Pencarian Kedalaman-pertama
  • Hindari pembuatan kandidat secara eksplisit
• Filosofi utama: Tumbuhkan pola panjang dari pola pendek menggunakan item lokal saja
  • “abc” adalah pola yang sering
  • Dapatkan semua transaksi yang memiliki “abc”, mis., Proyeksikan DB pada abc: DB | abc
  • “d” adalah item sering lokal di DB | abc → abcd adalah pola yang sering

Membangun FP-tree dari Database Transaksi

Pola Partisi dan Basis Data

• Pola yang sering dapat dipartisi ke dalam himpunan bagian sesuai dengan daftar-f
  • Daftar-F = f-c-a-b-m-p
  • Pola yang mengandung hal
  • Pola memiliki m tetapi tidak ada hal
  • …
  • Pola memiliki c tetapi tidak a atau b, m, p
  • Pola f
• Kelengkapan dan non-redundensi

Menemukan Pola Memiliki P Dari P-basis data bersyarat

• Mulai dari tabel header item sering di FP-Tree
• Traverse FP-tree dengan mengikuti tautan dari setiap item yang sering, hal
• Akumulasi semua jalur awalan yang diubah dari item p untuk membentuk basis pola bersyarat p

Dari basis pola-kondisional ke FP-tree kondisional

• Untuk setiap basis pola
• Akumulasi hitungan untuk setiap item di pangkalan
• Bangun FP-tree untuk item yang sering dari dasar pola

Recursion: Menambang setiap FP-tree kondisional

Kasus Khusus: Jalur Awalan Tunggal di FP-tree

• Misalkan sebuah (kondisional) FP-tree T memiliki satu path awalan bersama P
• Penambangan dapat diuraikan menjadi dua bagian
  • Pengurangan jalur awalan tunggal menjadi satu simpul
  • Gabungan hasil penambangan dari dua bagian

Keuntungan dari struktur FP-tree

• Kelengkapan
  • Menyimpan informasi lengkap untuk penambangan frequent pattern
  • Jangan sekali-kali merusak pola transaksi yang panjang
• Kekompakan
  • Mengurangi info yang tidak relevan — item yang jarang muncul dihilangkan
  • Item dalam urutan menurun: semakin sering terjadi, semakin besar kemungkinan untuk dibagikan
  • Tidak pernah lebih besar dari database asli (tidak menghitung simpul-tautan dan bidang hitung)

Metode Algoritma Frequent Pattern Growth (FP Growth) Mining

• Konsep: Pertumbuhan pola yang sering
  • Menumbuhkan pola yang sering berdasarkan pola dan partisi basis data
• metode
  1. Untuk setiap item yang sering, buat basis pola kondisionalnya, dan kemudian pohon FP bersyaratnya
  2. Ulangi proses pada setiap pohon-FP bersyarat yang baru dibuat
  3. Sampai pohon-FP yang dihasilkan kosong, atau hanya berisi satu jalur — jalur tunggal akan menghasilkan semua kombinasi dari sub-jalurnya, yang masing-masingnya merupakan pola yang sering

Scaling dalam algoritma FP growth dengan Proyeksi Basis Data

• Bagaimana jika FP-tree tidak dapat memuat memori? Proyeksi DB
• Pertama-tama, partisi sebuah basis data ke dalam satu set DB yang diproyeksikan
• Kemudian membangun dan menambang pohon FP untuk setiap DB yang diproyeksikan
• Teknik proyeksi paralel vs proyeksi partisi
  • Proyeksi paralel
    • Proyeksikan DB secara paralel untuk setiap item yang sering
    • Proyeksi paralel adalah ruang yang mahal
    • Semua partisi dapat diproses secara paralel
  • Proyeksi partisi
    • Partisi DB berdasarkan item yang sering dipesan
    • Melewati bagian yang belum diproses ke partisi selanjutnya

Partition-Based Projection

• Proyeksi paralel membutuhkan banyak ruang disk
• Proyeksi partisi menyimpannya

Algoritma FP Growth vs Apriori: Scalability With the Support Threshold

Keuntungan dari Pendekatan Pattern Growth

• Divide-and-conquer:
  • Menguraikan tugas penambangan dan DB sesuai dengan pola yang sering diperoleh sejauh ini
  • Mengarah ke pencarian fokus pada database yang lebih kecil
• Faktor lain
  • Tidak ada kandidat generasi, tidak ada tes kandidat
  • Database terkompresi: struktur FP-tree
  • Tidak memindai ulang seluruh database
  • Operasi dasar: menghitung item freq lokal dan membangun sub FPtree, tidak ada pencarian pola dan pencocokan
• Implementasi open source dan penyempurnaan FPGrowth yang baik
  • FPGrowth + (Grahne dan J. Zhu, FIMI’03)

Perbaikan Metode Penambangan Lebih Lanjut

• AFOPT (Liu, et al. @ KDD’03)
  • Metode “push-right” untuk menambang pohon pola sering terkondensasi (CFP)
• Carpenter (Pan, dkk. @ KDD’03)
  • Kumpulan data tambang dengan baris kecil tetapi banyak kolom
  • Bangun pohon penghitungan baris untuk penambangan yang efisien
• FPgrowth + (Grahne dan Zhu, FIMI03)
  • Efisien Menggunakan Prefix-Trees di Mining Frequent Itemsets, Proc. ICDM’03 Int. Workshop Implementasi Penambangan Item Frequent (FIMI’03), Melbourne, FL, November 2003
• TD-Close (Liu, et al, SDM’06)

Tambahan dari Metodologi Pattern Growth Mining

• Menambang itemet tertutup yang sering dan max-pola
  • CLOSET (DMKD’00), FPclose, dan FPMax (Grahne & Zhu, Fimi’03)
• Menambang pola berurutan
  • PrefixSpan (ICDE’01), CloSpan (SDM’03), BIDE (ICDE’04)
• Menambang pola grafik
  • gSpan (ICDM’02), CloseGraph (KDD’03)
• Penambangan pola sering berbasis kendala
  • Kendala konversi (ICDE’01), gPrune (PAKDD’03)
• Menghitung data kubus gunung es dengan langkah-langkah kompleks
  • H-tree, H-cubing, dan Star-cubing (SIGMOD’01, VLDB’03)
• Clustering berbasis pola pertumbuhan
  • MaPle (Pei, et al., ICDM’03)
• Klasifikasi Berbasis Pola Pertumbuhan
  • Menambang pola-pola yang sering dan diskriminatif (Cheng, et al, ICDE’07)

Baca Juga: Memahami Konsep Data Mining Beserta Prosesnya

Tahapan dan Contoh Algoritma FP Growth

Berikut ini 9 tahapan dalam Algoritma FP Growth

1. Penyiapan Dataset
2. Pencarian Frequent Itemset (Item yang sering muncul)
3. Dataset diurutkan Berdasarkan Priority
4. Pembuatan FP-Tree Berdasarkan Item yang sudah diurutkan
5. Pembangkitan Conditional Pattern Base
6. Pembangkitan Conditional FP-tree
7. Pembangkitan Frequent Pattern
8. Mencari Support
9. Mencari Confidence

1. Penyiapan Data set

2. Pencarian Frequent Itemset

3. Dataset diurutkan Berdasarkan Priority

4. Pembuatan FP-Tree

5. Pembangkitan Conditional Pattern Base

6. Pembangkitan Conditional FP-tree

7. Pembangkitan Frequent Pattern

Frequent 2 Itemset

8. Mencari Support 2 Itemset

9. Mencari Confidence 2 Itemset