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:
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}}
-
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
-
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
-
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%