Association Rule (Algoritma A Priori)

Algoritma  A  Priori  termasuk  jenis  aturan  asosiasi  pada  data  mining.  Selain a  priori, yang  termasuk  pada golongan ini adalah metode  generalized rule induction  dan  algoritma hash based. Aturan yang menyatakan asosiasi antara beberapa atribut sering disebut affinity analysis atau market basket analysis.

Metodologi dasar analisis asosiasi terbagi menjadi dua tahap:

a. Analisa pola frekuensi tinggi

Tahap ini mencari kombinasi item yang memenuhi syarat minimum dari nilai support dalam database. Nilai support sebuah item diperoleh dengan rumus berikut:

b. Pembentukan aturan assosiatif

Setelah  semua  pola  frekuensi  tinggi  ditemukan,  barulah  dicari  aturan  assosiatif  yang  memenuhi  syarat minimum untuk confidence dengan menghitung confidence aturan assosiatif A ->B

Nilai confidence dari aturan A ->B diperoleh dari rumus berikut:

Contoh, ada transaksi seperti yang dilihat di bawah ini:

Transaksi	Item yang dibeli
1	D, E, C
2	C, A
3	C, B, D
4	A, C, E, D
5	E, D
6	E, C, B
7	B, D, A

1. Pisahkan masing-masing item yang dibeli

Item yang dibeli

A

B

C

D

E

2. Kemudian Buat Tabel seperti di bawah ini dan hitung jumlahnya:

Transaksi	A	B	C	D	E
1	0	0	1	1	1
2	1	0	1	0	0
3	0	1	1	1	0
4	1	0	1	1	1
5	0	0	0	1	1
6	0	1	1	0	1
7	1	1	0	1	0
∑	3	3	5	5	4

3.Tentukan Ф

Misalkan kita tentukan Ф = 3, maka kita dapat menentukan frekuen itemset. Dari tabel di atas diketahui total Ф untuk transaksi k = 1, semuanya lebih besardari Ф. Maka:

F1= {{A}, {B}, {C}, {D}, {E}}

Untuk k = 2 (2 unsur), diperlukan tabel untuk tiap-tiap pasang item. Himpunan yang mungkin terbentuk adalah: {A,B}, {A,C}, {A,D}, {A,E}, {B,C}, {B,D}, {B,E}, {C,D}, {C,E}, {D,E}.

 Tabel-tabel untuk calon 2 item set

T	A	B	f		T	A	C	f		T	A	D	f		T	A	E	f		T	B	C	f
1	0	0	s		1	0	1	s		1	0	1	s		1	0	1	s		1	0	1	S
2	1	0	s		2	1	1	s		2	1	0	s		2	1	0	s		2	0	1	S
3	0	1	s		3	0	1	s		3	0	1	s		3	0	0	s		3	1	1	P
4	1	0	s		4	1	1	p		4	1	1	p		4	1	1	p		4	0	1	S
5	0	0	s		5	0	0	s		5	0	1	s		5	0	1	s		5	0	0	S
6	0	1	s		6	0	1	s		6	0	0	s		6	0	1	s		6	1	1	P
7	1	1	p		7	1	0	s		7	1	1	p		7	1	0	s		7	1	0	S
		∑	1				∑	1				∑	2				∑	1				∑	2
T	B	D	f		T	B	E	f		T	C	D	f		T	C	E	f		T	D	E	f
1	0	1	s		1	0	1	s		1	1	1	p		1	1	1	p		1	1	1	p
2	0	0	s		2	0	0	s		2	1	0	s		2	1	0	s		2	0	0	s
3	1	1	p		3	1	0	s		3	1	1	p		3	1	0	s		3	1	0	s
4	0	1	s		4	0	1	s		4	1	1	p		4	1	1	p		4	1	1	p
5	0	1	s		5	0	1	s		5	0	1	s		5	0	1	s		5	1	1	p
6	1	0	s		6	1	1	p		6	1	0	s		6	1	1	p		6	0	1	s
7	1	1	p		7	1	0	s		7	0	1	s		7	0	0	s		7	1	0	s
		∑	2				∑	1				∑	3				∑	3				∑	3

Dari tabel-tabel 2 unsur di atas, P artinya item-item yang dijual bersamaan, sedangkan S berarti tidak ada item  yang  dijual  bersamaan  atau  tidak  terjadi  transaksi.  Σ  melambangkan  jumlah  Frekuensi  item  set.

Jumlah frekuensi item set harus lebih besar atau sama dengan jumlah Frekuensi item set (Σ >= Ф). Dari

tabel diatas, maka didapat:

F2 = {{C,D},{C,E},{D,E}}

Kombinasi dari itemset dalam F2, dapat kita gabungkan menjadi calon 3-itemset. Itemset-itemset yang dapat digabungkan adalah itemset-itemset yang memiliki kesamaan dalam k-1 item pertama.

Untuk k = 3 (3 unsur), himpunan yang mungkin terbentuk adalah: {C,D,E}

T	C	D	E	f
1	1	1	1	P
2	1	0	0	S
3	1	1	0	S
4	1	1	1	P
5	0	1	1	S
6	1	0	1	S
7	0	1	0	S
			∑	2

Dari tabel-tabel di atas, didapat F3= { }, karena tidak ada Σ >= Ф sehingga F4, F5, F6 dan F7 juga merupakan himpunan kosong.

4.Tentukan (ss-s) sebagai antecedent dan s sebagai consequent dari Fk yang telah didapat

Pada F2 didapat himpunan F2= {{C,D},{C,E},{D,E}}

 Maka dapat disusun:

•  Untuk {C,D}:

-  Jika (ss-s) = C, Jika s = D, Maka →If buy C then buy D

-  Jika (ss-s) = D, Jika s = C, Maka →If buy D then buy C

•  Untuk {C,E}:

-  Jika (ss-s) = C, Jika s = E, Maka →If buy C then buy E

-  Jika (ss-s) = E, Jika s = C, Maka →If buy E then buy C

•  Untuk {D,E}:

-  Jika (ss-s) = D, Jika s = E, Maka →If buy D then buy E

-  Jika (ss-s) = E, Jika s = D, Maka →If buy E then buy D

5. Dari langkah di atas, kita mendapatkan 6 rule yang dapat digunakan, yaitu:

• If buy C then buy D
• If buy D then buy C
• If buy C then buy E
• If buy E then buy C
• If buy D then buy E
• If buy E then buy D

6.       Hitung support dan confidence

Sehingga didapat table sebagai berikut:

If antecedent then consequent	Support	Confidence
If buy C then buy D	(3/7)x100%=42,86%	(3/5)x100%=60%
If buy D then buy C	(3/7)x100%=42,86%	(3/5) x100%=60%
If buy C then buy E	(3/7)x100%=42,86%	(3/5) x100%=60%
If buy E then buy C	(3/7)x100%=42,86%	(3/4) x100%=75%
If buy D then buy E	(3/7)x100%=42,86%	(3/5) x100%=60%
If buy E then buy D	(3/7)x100%=42,86%	(3/4) x100%=75%

7.       Setelah  di  dapat  support  dan  confidence  untuk  masing-masing  kandidat,  lakukan  perkalian  antara support dan confidence, dimana confidence-nya diambil 70% ke atas, sehingga di dapat tabel sbb:

If antecedent then consequent	Support	Confidence	Support x Confidence
If buy E then buy C	42,86%	75%	0.32145
If buy E then buy D	42,86%	75%	0.32145

8.       Setelah  didapat  hasil  perkalian  antara  support  dan  confidence,  pilihlah  yang  hasil  perkaliannya  paling besar.  Hasil  paling  besar  dari  perkalian  perkalian  tersebut  merupakan  rule  yang  dipakai  pada  saat menjual. Karena hasil perkalian dari ke-2 penjualan di atas bernilai sama, maka semuanya bisa dijadikan rule.

-          Jika membeli E maka akan membeli C dengan support 42,86% dan confidence 75%

-          Jika membeli E maka akan membeli D dengan support 42,86% dan confidence 75%