Association Rule Pada Data Mining

A.  Association Rule

Aturan Asosiasi, yang juga dikenal sebagai Association rules, merupakan salah satu teknik dalam data mining yang memiliki kegunaan khusus dalam mengidentifikasi aturan asosiatif terkait dengan suatu set barang. Proses pembentukan aturan asosiasi ini melibatkan analisis pola data yang sering muncul, yang dikenal sebagai Frequent patterns, dengan memanfaatkan parameter Support dan Confidence. Support mencerminkan seberapa sering suatu item muncul dalam suatu basis data, sementara Confidence menunjukkan seberapa sering pernyataan atau asosiasi tersebut benar. Dalam bidang keilmuan data mining, terdapat suatu metode yang dinamakan association rule. Association rule mining adalah suatu prosedur untuk mencari hubungan antar item dalam suatu data set yang ditentukan.

Association rule meliputi dua tahap : 

1. Mencari kombinasi yang paling sering terjadi dari suatu itemset. 

2. Mendefinisikan condition dan result (conditional association rule). 

Dalam menentukan suatu association rule, terdapat suatu interestingness measure (ukuran kepercayaan) yang didapatkan dari hasil pengolahan data dengan perhitungan tertentu. Umumnya ada tiga ukuran , yaitu:  

a) Support: yaitu suatu ukuran yang menunjukkan seberapa besar tingkat dominasi suatu item/ itemset dari keseluruhan transaksi. Ukuran ini akan menentukan apakah suatu item/itemset layak untuk dicari confidence-nya (misal, dari seluruh transaksi yang ada, seberapa besar tingkat dominasi yang menunjukkan bahwa item A dan B dibeli bersamaan) dapat juga digunakan untuk mencari tingkat dominasi item tunggal. Secara umum dapat ditulis seperti persamaan  berikut : 

Rumus Support

b) Confidence: yaitu suatu ukuran yang menunjukkan hubungan antar dua item secara conditional (misal, seberapa sering item B dibeli jika orang membeli item A). Secara umum dapat ditulis seperti persamaan (2) berikut.

Rumus Confidence

3) Improvement: yaitu suatu ukuran yang menunjukan besarnya kemungkinan dua item dapat dibeli secara bersamaan. Lebih jelasnya dapat dilihat pada persamaan (3). 

Rumus Improvement

Ketiga ukuran ini nantinya akan berguna dalam menentukan interesting association rules, yaitu untuk dibandingkan dengan threshold (batasan) yang ditentukan. Batasan tersebut umumnya terdiri dari min_support, min_cofidence, dan min_ improvement. 

Persoalan association rule mining terdiri dari dua sub persoalan : 

1. Menemukan semua kombinasi dari item, disebut dengan frequent itemsets, yang memiliki support yang lebih besar daripada minimum support. 

2. Gunakan frequent itemsets untuk men-generate aturan yang dikehendaki. Semisal, ABCD dan AB adalah frequent, maka didapatkan aturan AB → CD jika rasio dari support (ABCD) terhadap support (AB) sedikitnya sama dengan minimum confidence. Aturan ini memiliki minimum support karena ABCD adalah frequent.

 B.  Algoritma Apriori

Algoritma  Apriori  adalah  suatu  algoritma dasar   yang   diusulkan   oleh   Agrawal   &   Srikant pada   tahun   1994   untuk penentuanfrequent itemsets untuk aturan asosiasi boolean. Algoritma apriori  termasuk  jenis  aturan  asosiasi  pada data mining.Aturan  yang  menyatakan  asosiasi  antara beberapa  atribut  sering  disebut affinity  analysis atau market basket analysis.Analisis  asosiasi  atau association rule miningadalah teknik data  mining untuk    menemukan    aturan    suatu    kombinasi item. 

Algoritma Apriori yang bertujuan untuk menemukan frequent itemsets dijalankan pada sekumpulan data. Pada iterasi ke-k, akan ditemukan semua itemsets yang memiliki k items, disebut dengan k-itemsets. Tiap iterasi berisi dua tahap. Misal Oracle Data Mining Fk merepresentasikan himpunan dari frequent k-itemsets, dan Ck adalah himpunan candidate k-itemsets (yang potensial untuk menjadi frequent itemsets). Tahap pertama adalah men-generate kandidat, dimana himpunan dari semua frequent (k-1) itemsets, Fk-1, ditemukan dalam iterasi ke-(k-1), digunakan untuk mengenerate candidate itemsets Ck. 

Prosedur generate candidate memastikan bahwa Ck adalah superset dari himpunan semua frequent k-itemsets. Struktur data hash-tree digunakan untuk menyimpan Ck. Kemudian data di-scan dalam tahap penghitungan support. Untuk setiap transaksi, candidate dalam Ck diisikan ke dalam transaksi, ditentukan dengan menggunakan struktur data hash-tree dan nilai penghitungan support dinaikkan. Pada akhir dari tahap kedua, nilai Ck diuji untuk menentukan yang mana dari candidate yang merupakan frequent. Kondisi penghitung (terminate condition) dari algoritma ini dicapai pada saat Fk atau Ck+1 kosong .

 C. Contoh kasus

Berikut ada 8 data transaksi keranjang belanja dari sebuah grosir seperti pada tabel berikut.

Data Transaksi

   

Untuk menghasilkan aturan asosiasi setidaknya ada 2 fase yang harus dilakukan terkait penggunaan nilai support dan confident di atas : 

1. Frequent itemset

Fase pertama, adalah menentukan itemset yang frequent, frequent disini maksudnya adalah kombinasi itemset yang sering muncul dalam dataset (data transaksi). sehingga aturan yang dibuat nantinya mampu menghasilkan nilai confident yang tinggi. Kembali ke contoh kasus tersebut, kita akan mulai mencari itemset yang frequent. Dengan melakukan kombinasi itemset yang mungkin berdasarkan k-itemset ( pembangkitan itemset frequent), k disini mengacu pada jumlah item yang akan dikombinasikan.

k-itemset ( k=1)

kita mulai dari pembangkitan itemset k=1, maka itemset yang dapat dibentuk beserta dengan jumlah kemunculan nya dalam seluruh transaksi sebagai berikut :

Beras = 6 Buku=4 Minyak=6 Telur=6 Topi=3

Jelas bahwa dari 8 transaksi pembelian dicontoh, ada 6 transaksi yang membeli item beras, 4 transaksi membeli item buku, 6 transaksi membeli item minyak, 6 transaksi membeli item telur dan 3 transaksi membeli item topi.

k-itemset (k=2) 

lanjut pada tahap iterasi kedua dengan nilai k=2, berarti kita akan membentuk kombinasi dari 2 buah itemset sebagai berikut :

{Beras,Buku} = 2 {Beras,Minyak}=4 {Beras,Telur}=5 {Beras,Topi}=2 {Buku,Minyak}=3 {Buku,Telur}=2 {Buku,Topi}=1 { Telur,Minyak}=5 {Minyak,Topi}=2 {Telur,Topi}=2 Dan seterusnya……

Dari 8 transaksi pembelian pada contoh, setidaknya ada 2 dari 8 transaksi yang membeli item Beras dan Buku bersamaan, 4 transaksi membeli item Beras dan Minyak, 5 Transaksi membeli item Beras dan Telur, dan begitu selanjutnya.

k-itemset (k=3) 

kemudian pada iterasi ketiga dengan nilai k=3, akan dibentuk kombinasi dari 3 buah itemset sebagai berikut :

{Telur,Minyak,Beras}=4 {Telur,Minyak,Buku}=2 {Telur,Minyak,Topi}=2 {Telur,Beras,Buku}=1 {Telur,Beras,Topi}=2 {Beras,Buku,Topi}=0 {Beras,Topi,Minyak}=2 {Beras,Buku,Minyak,}=1 {Buku,Minyak,Topi}=1 Dan seterusnya…….

Dari 8 transaksi pada contoh, terdapat 4 transaksi yang membeli item {telur,minyak dan beras} bersamaan, 2 transaksi yang membeli item {telur,minyak dan buku},2 transaksi yang membeli item {telur,minyak dan topi} dan selanjutnya. 

k-itemset (k=4) 

terakhir pada iterasi keempat dengan nilai k=4, akan dibentuk kombinasi dari 4 buah itemset sebagai berikut :

{Telur,Minyak,Beras,Buku}=1 {Telur,Minyak,Beras,Topi}=2 {Telur,Minyak,Buku,Topi}=0 Dan seterusnya…..

Dari 8 transaksi pada contoh, terdapat 1 transaksi yang membeli item {telur,minyak,beras dan buku} bersamaan, 1 transaksi yang membeli item {telur,minyak,beras dan topi} bersamaan dan selanjutnya. Bisa dibayangkan hanya untuk 8 transaksi dengan maksimal item yang dibeli setiap transaksi adalah 4 item saja bisa menghasilkan 31 kombinasi asosiasi.

2. Ekstraksi Aturan Asosiasi

Setelah didapatkan kombinasi itemset yang frequent, maka fase selanjutnya adalah mengekstrasi aturan asosiasi dari kombinasi itemset yang memiliki nilai confident yang tinggi. Untuk menghitung nilai confident, setidaknya kita juga mesti menghitung nilai supportnya agar terlihat korelasi antara nilai support dan nilai confident tersebut. Sebagai contoh kita akan menghitung nilai support dan confident dari k-itemset (k=2) berikut :

{Beras,Buku} = 2 

s(Beras->Buku) = 2/8 = 0.25 = 25% 

c(Beras->Buku)=2/6 = 0.33 = 33%

 {Beras,Telur}=5 

s(Beras->Telur) = 5/8 = 0.625= 62.5% 

c(Beras->Telur)=5/6 = 0.83 = 83%

dapat dilihat dari contoh perhitungan di atas, hal tersebut akan terus kita lakukan untuk menentukan nilai support dan confident untuk ke 31 kandidat itemset frequent yang lain. Akan memakan waktu sekali, namun coba lihat dari contoh perhitungan di atas. Ada korelasi yang bisa kita tarik hipotesa nya untuk memudahkan kita dalam menentukan aturan asosiasi yang tepat sesuai dengan konsep algoritma Apriori.

3.  Menentukan nilai minimum Support

Misalkan nilai minimum support yang akan kita terapkan adalah minSupport=4 ( setara dengan 4/8 = 0.5 atau 50% ) Maka pada iterasi pertama k-itemset (k=1) akan terbentuk aturan sebagai berikut :

Beras = 6 Buku=4 Minyak=6 Telur=6 Topi=3

Dari kelima itemset tersebut, item topi ( 3/8 = 0.375 atau 37.5%) tidak memenuhi nilai minimum support=50 %. Sehingga pada iterasi kedua k-itemset (k=2). Semua itemset yang mengandung topi juga akan dieliminasi sesuai dengan prinsip algoritma apriori.

{Beras,Buku} = 2 {Beras,Minyak}=4 {Beras,Telur}=5 {Beras,Topi}=2 {Buku,Minyak}=3 {Buku,Telur}=2 {Buku,Topi}=1 { Telur,Minyak}=5 {Minyak,Topi}=3 {Telur,Topi}=3 Dan seterusnya……

Pada k-itemset (k=2) di atas, itemset {Beras,Buku} ( 2/8=0.25 atau 25%), {Buku,Minyak} ( 3/8=0.375 atau 37.5%) dan {Buku,Telur} ( 2/8=25%)  tidak memenuhi nilai minimum support, sehingga itemset tersebut juga dieliminasi. Pada iterasi ketiga k-itemset (k=3) hanya tersisa 1 itemset yang memenuhi minimum nilai support yaitu itemset {Telur,Minyak,Beras} ( 4/8 =0.5 atau 50%)

{Telur,Minyak,Beras}=4 {Telur,Minyak,Buku}=2 {Telur,Minyak,Topi}=2 {Telur,Beras,Buku}=1 {Telur,Beras,Topi}=2 {Beras,Buku,Topi}=0 {Beras,Topi,Minyak}=2 {Beras,Buku,Minyak,}=1 {Buku,Minyak,Topi}=1 Dan seterusnya…….

Berdasarkan algoritma Apriori, maka aturan asosiasi yang berhasil didapatkan adalah sebagai berikut : 

1.      {Beras,Minyak} 

Nilai confident, c(Beras->Minyak) = 4/6 = 0.67 = 67% 

2.     {Beras,Telur} 

Nilai confident, c(Beras->Telur) = 5/6 = 0.83 = 83% 

3.     {Minyak,Telur} 

Nilai confident, c(Minyak->Telur) = 5/6 = 0.83 = 83% 

4.     {Telur,Minyak,Beras} 

Nilai confident, c(Telur,Minyak->Beras) = 4/5 = 0.67 = 80%

Aturan Asosiasi : 

1. If Beras, Maka Minyak

2. If Beras, Maka Telur 

3. If Minyak, Maka telur 

4. If Telur dan Minyak, Maka Beras