1665 13 association rule

INTNRODUCTION DATA MINING

Proses untuk menemukan dataset baru pada dataset yang sangat besar.

TOPIK

ASSOCIATION RULES (ATURAN ASOSIASI)

ATURAN ASOSIASI Menggunakan algoritme klasik : IF - THEN

ATURAN ASOSIASI Analisis Afinitas = “apa bersama apa”

Bisa digunakan untuk menentukan kebiasaan “ suatu produk apa akan dibeli bersama apa”

Market Basket Analysis

Contoh:

Studi transaksi di supermarket

Jika membeli Susu Bayi makan akan membeli Sabun Mandi

ATURAN ASOSIASI DALAM TRANSAKSIMenemukan asosiasi produk dalam database

transaksi suatu supermarket. (database Market Basket)

Contoh Kasus: Para manajer ingin mengetahui kelompok items apa

yang sering dibeli untuk membuat layout katalog belanja.

Solusi: Gunakan aturan asosiasi dalam hubungan “if-then” atau

“jika-maka”.

Aturan tersebut dihitung dari data yang sifatnya probabilistic berdasarkan data market basket

KASUS

Suatu toko yang menjual pakaian olah raga, sedang melakukan promosi padapenjualan topi. Jika seorang pelanggan membeli lebih dari satu macam topi dari 6 pilihan yang ada akan mendapat diskon.

Manajer toko tersebut ingin melihat warna apa yang dibeli bersama oleh pelanggan, mengumpulkan data dan menyimpan dalam database.

Data items Topi tersebut berupa:• Catatan

transaksipembelian

Transaksi

1 merah putih hijau

2 putih orange

3 putih biru

4 merah putih orange

5 merah biru

6 putih biru

7 putih orange

8 merah putih biru hijau

9 merah putih biru

10 kuning

Warna

Ide dari Aturan Asosiasi:• Periksa semua kemungkinan “IF - THEN”

• Pilih yang paling mungkin (most likely) sebagaiindicator dari hubungan ketergantungan antar item.

• Antecedent =“Jika” dan consequent = “maka”

• Kemungkinan aturan:

– “Jika Merah, maka Putih ”

– {Merah, Putih} = {Biru}

Secara praktis,Hanya kombinasi yang terjadi dengan frekuensi yang sangat tinggi yang akan diperhatikan

itu yang disebut:FREQUENT ITEM SET

FREQUENT ITEM SET Berhubungan dengan SUPPORT

SUPPORT: jumlah transaksi yang mengandung item

Support digunakan untuk mengukur seberapa tingkatdukungan data terhadap validitas aturan yang dikembangkan.

Dinyatakan dalam prosentase (%)

Contoh:

{Merah, Putih} adalah 4/10 atau 40%

Mengukur Aturan yang Kuat

Contoh Confidence Suatu supermarket memiliki

100.000 titik transaksi. Dari jml tersebut ada 1000 transaksi yang mengandung jeruk dan obat flu. Dari 1000 transaksi ada 800 yang mengandung mie instant.

Aturan asosiasi jika jeruk dan obat flu dibeli maka mie instant juga dibeli pada belanja yang bersamaan => Support= 800/100.000

Confidence = 800/1000

SUPPORT: Peluang transaksi yang dipilih secara random dari database akan mengandung semua item dalam antecendent maupun consequent atau P (antecedent dan consequent).

P (consequent | antecedent)

Lift Ratio

Ada beberapa algoritme yang sudah

dikembangkan mengenai aturan asosiasi,

namun ada satu algoritme klasik yang

sering dipakai yaitu algoritma apriori

(Shmueli et al., 2007)

Apriori: A Candidate Generation-and-Test Approach

Apriori pruning principle: If there is any itemset which is

infrequent, its superset should not be generated/tested!

(Agrawal & Srikant @VLDB’94, Mannila, et al. @ KDD’ 94)

Method:

Initially, scan DB once to get frequent 1-itemset

Generate length (k+1) candidate itemsets from length k

frequent itemsets

Test the candidates against DB

Terminate when no frequent or candidate set can be

generated

December 13, 2014 Data Mining: Concepts and Techniques 18

The Apriori Algorithm—An Example

Database TDB

1st scan

C1

L1

L2

C2 C2

2nd scan

C3 L33rd scan

Tid Items

10 A, C, D

20 B, C, E

30 A, B, C, E

40 B, E

Itemset sup

{A} 2

{B} 3

{C} 3

{D} 1

{E} 3

Itemset sup

{A} 2

{B} 3

{C} 3

{E} 3

Itemset

{A, B}

{A, C}

{A, E}

{B, C}

{B, E}

{C, E}

Itemset sup

{A, B} 1

{A, C} 2

{A, E} 1

{B, C} 2

{B, E} 3

{C, E} 2

Itemset sup

{A, C} 2

{B, C} 2

{B, E} 3

{C, E} 2

Itemset

{B, C, E}

Itemset sup

{B, C, E} 2

Supmin = 2