Association Analysis


Secara umum, terdapat dua tahap dalam melakukan Association Rule Mining yaitu Frequent Itemset Candidate Generation dan Rule Generation. Pada tahap Frequent Itemset Candidate Generation terdapat beberapa kendala yang harus dihadapi untuk memperoleh Frequent Itemset seperti banyaknya jumlah kandidat yang memenuhi minimum support, dan proses perhitungan minimum support dari Frequent Itemset yang harus melakukan scan database berulang-ulang. Pendekatan Apriori sangat membantu dalam mengurangi jumlah kandidat Frequent Itemset.
Apakah mungkin candidate generation ini tidak dilakukan?
Dengan menggunakan FP-growth, kita dapat melakukan Frequent Itemset Mining tanpa melakukan candidate generation. FP-growth menggunakan struktur data FP-tree. Dengan menggunakan cara ini scan database hanya dilakukan dua kali saja, tidak perlu berulang-ulang. Data akan direpresentasikan dalam bentuk FP-tree. Setelah FP-tree terbentuk, digunakan pendekatan divide and conquer untuk memperoleh Frequent Itemset. FP-tree merupakan struktur data yang baik sekali untuk Frequent Pattern mining. Struktur ini memberikan informasi yang lengkap untuk membentuk Frequent Pattern. Item-item yang tidak frequent (infrequent) sudah tidak ada dalam FP-tree.

Referensi :
1. J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. SIGMOD’00.
2. R. Agarwal, C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent itemsets. J. Parallel and Distributed Computing:02.

Iklan

Masalah utama pencarian Frequent Itemset adalah banyaknya jumlah kombinasi itemset yang harus diperiksa apakah memenuhi minimum support atau tidak. Salah satu cara untuk mengatasinya adalah dengan mengurangi jumlah kandidat itemset yang harus diperiksa.
Apriori adalah salah satu pendekatan yang sering digunakan pada Frequent Itemset Mining. Prinsip Apriori adalah jika sebuah itemset infrequent, maka itemset yang infrequent tidak perlu lagi diexplore supersetnya sehingga jumlah kandidat yang harus diperiksa menjadi berkurang.
Kira-kira ilustrasinya seperti ini:

Pada gambar di atas, pencarian Frequent Itemset dilakukan tanpa menggunakan prinsip Apriori. Dengan menggunakan prinsip Apriori, pencarian Frequent Itemset akan menjadi seperti di bawah ini:

Dapat dilihat bahwa dengan menggunakan Apriori, jumlah kandidat yang harus diperiksa cukup banyak berkurang. Apriori sendiri terus dikembangkan untuk meningkatkan efisiensi dan efektivitasnya. Salah satunya adalah dengan memanfaatkan Hash Tree untuk perhitungan support yang efisien (mengurangi Database scan yang berulang-ulang).

Referensi :
1. Agrawal and R. Srikant. Fast algorithms for mining association rules. VLDB’94.
2. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. KDD’94.
3. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. VLDB’95.

Secara umum, Association Rule Mining dapat dibagi menjadi dua tahap:

  1. Pencarian Frequent Itemset
    Pada proses ini dilakukan pencarian Frequent Itemset. Frequent Itemset yang diperoleh harus memenuhi minimum support (lihat post Itemset, Support, dan Confidence).
  2. Rule Generation
    Frequent Itemset yang telah dihasilkan dari proses sebelumnya digunakan untuk membentuk Association Rule. Association Rule yang dihasilkan akan memenuhi minimum support dan minimum confidence.

Masalah utama yang muncul pada pencarian Frequent Itemset adalah banyaknya hasil Frequent Itemset yang memenuhi threshold minimum support. Semakin rendah threshold minimum support, Frequent Itemset yang dihasilkan akan semakin banyak. Jika terdapat d item, maka akan diperoleh 2d-1 kombinasi itemset yang bisa diperoleh. Contoh: 100 item akan menghasilkan kombinasi itemset 2100-1. Jumlah itemset ini sangat banyak untuk dapat disimpan atau diproses pada komputer manapun. Untuk mengatasi hal ini, muncul istilah Closed Frequent Itemset dan Maximal Frequent Itemset.

Ketiga istilah ini sangat penting dalam Association Rule mining.
Seperti yang sudah pernah disebutkan sebelumnya bahwa Association Rule Mining disebut juga Frequent Itemset Mining, karena itu Itemset merupakan fokus utama mining. Itemset merupakan himpunan kelompok item. Itemset dengan jumlah item k disebut k-Itemset. Jika menggunakan contoh transaksi pada post Association Rule Mining, {Milk, Bread, Diaper} merupakan salah satu Itemsetnya.
Association Rule dinyatakan dalam bentuk X => Y, di mana X dan Y merupakan Itemset. Contohnya : {Milk, Diaper} => {Beer}.
Support (s) dan Confidence (c) merupakan metrik yang digunakan pada Association Rule. Support menunjukkan persentasi jumlah transaksi yang berisi X dan Y. Sedangkan Confidence menunjukkan persentasi banyaknya Y pada transaksi yang mengandung X. Bentuk persamaan matematisnya dapat dituliskan seperti ini:

Berikut ini adalah contoh Association Rule :
{Milk, Diaper} => {Beer}

Support menunjukkan persentasi jumlah transaksi yang mengandung item {Milk, Diaper, Beer}.
Confidence menunjukkan persentasi {Beer} yang terdapat pada transaksi yang mengandung item {Milk, Diaper}.
Nilai Support digunakan untuk menentukan Frequent Itemset. Itemset yang nilai Support-nya memenuhi parameter threshold minimum support (min_sup) masuk dalam Frequent Itemset. Sedangkan nilai Confidence digunakan dalam menentukan Strong Association Rule. Association Rule yang nilai Confidence-nya memenuhi parameter threshold minimum confidence (min_conf) termasuk dalam Strong Association Rule.

Association Rule Mining merupakan bagian dari Frequent Pattern Mining. Frequent Pattern Mining merupakan salah satu task data mining yang sangat penting. Kenapa? Task ini mencari hubungan/relasi, assosiasi, dan korelasi dalam data. Pengetahuan yang dihasilkan juga sangat berguna untuk klasifikasi, clustering, dan task data mining yang lain. Selain Association Rule Mining, masih ada Sequential Pattern, dan Structured Pattern yang termasuk dalam Frequent Pattern Mining. Association Rule Mining dapat juga disebut Frequent Itemset Mining karena pola yang dihasilkan adalah pola item yang sering muncul bersamaan dalam sebuah database.
Contoh klasik yang sering digunakan untuk menjelaskan Association Rule Mining adalah market basket analisis. Pada market basket analisis, kita menganalisa kebiasaan customer dalam membeli barang. Misalkan terdapat data transaksi seperti ini.

Contoh pengetahuan yang dapat diperoleh dari data di atas adalah
{Beer} –> {Diaper}
artinya orang yang beli beer biasanya beli diaper juga. Lebih jauh, association rule menjelaskan hubungan korelasi antar item dengan lebih jelas, tidak hanya korelasi kuat atau korelasi lemah saja. Hal ini karena adanya beberapa metrik yang digunakan untuk evaluasi rule.
Term-term berikutnya akan membahas lebih lanjut tentang association rule mining termasuk juga teknik yang biasa digunakan.