Algoritma apriori

Analisis Keranjang Belanja di R

Christopher Bruffaerts

Statistician

Association rule mining

Association rule mining membantu menemukan hubungan menarik antar item dalam basis data transaksional besar.

Tugas ini terbagi dua:

Frequent itemset generation: temukan semua itemset sering dari basis data transaksi besar. Itemset disebut sering jika memenuhi minimum support threshold.
Rule generation: dari itemset sering di atas, buat aturan dengan confidence di atas minimum confidence threshold.

Algoritma apriori adalah algoritma klasik dan cepat dalam keluarga association rule mining.

Gagasan di balik algoritma apriori

Algoritma apriori:

Pendekatan bottom-up
Menghasilkan kandidat itemset dengan memanfaatkan prinsip apriori

Prinsip apriori:

Jika sebuah itemset sering, semua subset-nya juga sering.
- mis. jika {A,B} sering, maka {A} dan {B} juga sering
Untuk itemset yang jarang, semua superset-nya juga jarang.
- mis. jika {A} jarang, maka {A,B}, {A,C}, dan {A,B,C} jarang.

¹ Agrawal dan Srikant (1994)

Contoh: 1-itemset

kisi himpunan item

TID	Transaksi
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Ambang minimum support = 3/7 = 0,42

Contoh: 2-itemset

kisi himpunan item

TID	Transaksi
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Ambang minimum support = 3/7 = 0,42

Contoh: 3-itemset

semua himpunan item

TID	Transaksi
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Ambang minimum support = 3/7 = 0,42

Contoh: itemset sering

kisi himpunan item

Itemset	Hitung	Support
{A}	3	0,42
{B}	6	0,85
{C}	4	0,57
{D}	5	0,71
{A,B}	3	0,42
{B,C}	3	0,42
{B,D}	4	0,57
{C,D}	3	0,42

¹ Ambang minimum support = 3/7 = 0,42

Apriori: pembuatan aturan

Setelah generasi itemset sering yang mahal komputasi, apriori membuat aturan:

Mulai dari aturan ber-confidence tinggi dengan satu anteseden
- mis. {A,C} $\rightarrow$ {B}
Bangun aturan lebih kompleks, dengan lebih banyak item di sisi kanan
- mis. {A,C} $\rightarrow$ {B, D}

Trik: pruning aturan asosiasi

mis.: jika aturan {B,C,D} $\rightarrow$ {A} ber-confidence rendah, semua aturan yang memuat item A pada konsekuennya dapat dibuang (mis. {B,D} $\rightarrow$ {A, C} atau {D} $\rightarrow$ {A,B, C}).

Coba pertama dengan apriori

Data transaksional

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

Panggilan pertama fungsi apriori - itemset sering

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

Keluaran apriori - itemset sering

Itemset sering

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

kisi himpunan item

Ekstraksi aturan dengan fungsi apriori

Parameter: parameter mining mengubah karakteristik itemset atau aturan yang ditambang.

Support = 3/7
Confidence = 60%
Panjang minimum aturan = 2

Panggilan fungsi apriori untuk membuat aturan dengan argumen spesifik

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

Ekstraksi aturan: keluaran

Memeriksa aturan

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

Ayo berlatih!

Analisis Keranjang Belanja di R