Analisis Asosiasi -Apriori Algorithm- Sistem Informasi | Fakultas Ilmu Komputer 2019
Analisis Asosiasi
Association mining adalah proses mendeteksi kumpulan atribut-atribut yang muncul bersamaan(co-occur) dalam frekuensi yang sering, dan membentuk sejumlah kaidah dari kumpulan-kumpulan tersebut.
Analisa asosiasi berguna untuk menemukan hubungan yang tersembunyi diantara set data yang sangat besar
Pemanfaatan Analisis Asosiasi
Aturan asosiasi yang didefinisikan pada basket data transaksi, dapat digunakan untuk menganalisa data dalam rangka :
• keperluan desain katalog promosi
• pola belanja pelanggan
• cross selling
• market basket analysis.
Analisa Asosiasi• Hubungan antar item berupa aturan asosiasi (association rule).
• Sebagai contoh data transaksi berikut
IDT Item
T1 Buku, minyak, topi
T2 Beras, telur, topi, minyak
T3 Telur, minyak, beras
T4 Beras, buku
{Telur} —> {Minyak}
Aturan yang terbentuk :X —> Y
Algoritma AprioriAlgoritma Apriori merupakan salah satu algoritma yang digunakan dalam memecahkan persoalan association rule mining
•Yang mengolah suatu database transaksi dengan setiap transaksi adalah suatu himpunan item-item.
•Kemudian mencari seluruh kaidah apriori yang memenuhi minimum support dan minimum confidence yang diberikan.
frequent itemset association rules
Pseudo-Code Apriori AlgorithmCk: Kandidate itemset dari ukuran k;
Lk : Frequent itemset dari ukuran k.
L1 = {frequent items};
for (k = 1; Lk !=0; k++) do begin
Ck+1 = {kandidat dibangun
for each transaksi t yang dimuat dalam database do naikkan hitungan dari seluruh kandidat dalam Ck+1 yang dimuat dalam t
Lk+1 = {kandidat dalam Ck+1 dengan min_support}
end
return .k Lk;
Itemset
• Itemset : kumpulan item dal am keranjang belanja dalam jumlah kosong atau lebih
• Jika berisi k-item, maka itemset disebut k-itemset
• contoh : {Minyak} = 1-itemset
{Telur, Beras} = 2-itemset
Support dan Support Count
Supportcount(σ)Jumlahkombinasiitemdalamdbase
σ({Milk,Bread})=3σ({Soda,Chips})=4
Support(s)PersentaseAsosiasiitemsetyangterjadis({Milk,Bread})=(3/8)*100%s({Soda,Chips})=(4/8)*100%
Confidence
Confidenceyaitu kuatnya hubungan antar item dalam rule
aturanX->Y,nilaiconfidenceygtinggimenunjukanYyangmunculdalamtransaksiygberisiX
* Antecedent:jumlahtransaksiyangmembeliXdarihimpunanXUY
Aturan AsosiasiPendefinisian aturan asosiasi :
Diberikan sejumlah transaksi T, cari semua aturan yang memiliki nilai :
dan
• minsup : ambang batas support• minconf : ambang batas confidence
Contoh SoalBerikut ini Contoh dari 4 Transaksi belanja konsumen, akan dicari hubungan asosiasi antar item dengan minimal support 50%, dengan min confidence 75%
No Itemset
1 kopi; gula; apel
2 teh; gula; roti
3 kopi; teh; gula; roti
4 teh; roti
A : kopi C : gula E: roti
B : teh D: apel
Jumlah transaksi 4Min support : 50% (2 dari 4 transaksi)Min confidence : 75%Langkah 1 : L1= {Large 1-itemset}
No Itemset
1 A-kopi; C-gula; D-apel
2 B-teh; C-gula; E-roti
3 A-kopi; B-teh; C-gula; E-roti
4 B-teh; E-roti
Langkah 1
Itemset SupportA 50%B 75%C 75%D 25%E 75%
Langkah 1
Min support : 50% sehingga items yang tidak memenuhi dibuang
Itemset SupportA 50%B 75%C 75%D 25%E 75% Itemset Support
A 50%B 75%C 75%D 25%E 75%
Langkah 2Langkah 2 : Mencari kandidat itemset untuk L2
2.1 Gabungkan itemset pada L1 (algoritma apriori)
2.2 Hapus yang tidak ada dalam itemset
Itemset (L1)
A
B
C
E
Itemset (L2)
AB
AC
AE
BC
BE
CE
ItemsetABCDE
Langkah 3
Langkah 3 : Hitung Support dari tiap kandidat itemset
Itemset (L2) Support
AB 25%
AC 50%
AE 25%
BC 50%
BE 75%
CE 50%
Langkah 4Langkah 4 : L2 {Large 2-itemset}
Itemset (L2) Support
AB 25%
AC 50%
AE 25%
BC 50%
BE 75%
CE 50%
Itemset (L2) Support
AC 50%
BC 50%
BE 75%
CE 50%
Langkah 5Ulangi langkah 2 - langkah 4 :
5.1 Gabungkan itemset pada L2 dan L2 5.2 Hapus yang tidak ada dalam itemset
Itemset (L2) Support
AC 50%
BC 50%
BE 75%
CE 50%
Itemset (L2) Itemset 3AC + BC ABCAC + BE ABC, ABE, ACEAC + CE ACEBC + BE BCEBC + CE BCEBE + CE BEC Itemset (L3)
ABCABEACEBCE
Langkah 6
• Langkah 6 : Hitung Support dari tiap kandidat itemset
• Langkah 7 : L3 {BCE}STOP karena sudah tidak ada lagi kandidat untuk 4-itemset
Itemset (L3) SupportABC 25%ABE 25%ACE 25%BCE 50%
Large Itemset yang terbentuk
Itemset (L3) Support
BCE 50%
Itemset (L2) Support
AC 50%
BC 50%
BE 75%
CE 50%
Itemset (L1) Support
A 50%
B 75%
C 75%
E 75%
Rule yang Terbentuk
Untuk mencari aturan asosiasi diperlukan juga min-conf : 75%
Aturan (x —> y) Support ( x U y ) Support (x) Confidence
BC —> E 50% 50% 100%BE —> C 50% 75% 66,67%CE —> B 50% 50% 100%A —> C 50% 50% 100%C —> A 50% 75% 66,67%B —> C 50% 75% 66,67%C —> B 50% 75% 66,67%B —> E 75% 75% 100%E —> B 75% 75% 100%C —> E 50% 75% 66,67%E —> C 50% 75% 66,67%