Mining Association Rule

Mining Association Rule [email protected] Versi dok: 0.5 / 7 Nov 08 Sebagian isi slide diambil dari presentasi J. Han

Intro • Ass Rule mining: – Menemukan asosiasi atau korelasi yang menarik dari data.

• Contoh: Market Basket Analysis – Jika customer membeli sabun, seberapa mungkin ia juga membeli pasta gigi.

• Aplikasi lain: –

cross-marketing, catalog design, sale campaign analysis, Web log (click stream) analysis dan DNA sequence analysis.

•

Dasar task mining yang lain: –

Cluster, klasifikasi, semantic data compression

Support dan Confidence • Besaran “kemenarikan” (interestingness) dari sebuah pola • Hanya pola yang melewati nilai dan support tertentu saja yang diperhitungkan. • Contoh: – Sabun  Pasta gigi

(Support: 60%, Confidence 70%)

Support dan Confidence (2) Transaction-id

Items bought

10

A, B, D

20

A, C, D

30

A, D, E

40

B, E, F

50

B, C, D, E, F Customer buys both

Customer buys beer

Customer buys diaper

• Itemset X = {x1, …, xk} • Temukan rules X  Y dengan min support and confidence – support, s, probabilitas transaksi mengandung X ∪ Y – confidence, c, conditional probability transaksi memiliki X juga mengandung Y Jika supmin = 50%, confmin = 50% Freq. Pat.: {A:3, B:3, D:4, E:3, AD:3} Association rules: A  D (60%, 100%) D  A (60%, 75%)

Klasifikasi Association Rule • Boolean Association Rule  berdasarkan ada tidaknya item • Quantitavie Association Rule  – Umur(X,”30…39”) DAN penghasilan (X, “90jt – 100jt)  beli (X, TV plasma)

• Multidimensi ass. Rule. – Umur(X,”30…39”)  beli (X, PC) – Umur(X,”30…39”)  beli (X, Laptop)

Mining Single-Dimention Boolean Ass Rule: Apriori • •

Berdasarkan prior knowledge Generate and test

•

Metode – Scan DB untuk mendapat 1-item set lalu ambil kandidat yang frekuensinya memenuhi support count – Bangkitkan k+1 itemset dari itemset yang ada sebelumnya – Buang kandidat yang subsetnya tidak memenuhi support count. – Hitung frekuensinya, ambil kandidat yang frekuesninya memenuhi. – Selesai saat tidak ada kandidat yang memenuhi syarat – Hitung ass. Rule

Contoh Pencarian Freq. Itemset dengan Apriori Database TDB Tid 10 20 30 40

L2

Supmin = 2 C1

Items A, C, D B, C, E A, B, C, E B, E Itemset {A, C} {B, C} {B, E} {C, E}

C3

1st scan C2 sup 2 2 3 2

Itemset {B, C, E}

Itemset {A} {B} {C} {D} {E}

Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}

3rd scan

sup 2 3 3 1 3 sup 1 2 1 2 3 2

L3

L1

Itemset {A} {B} {C} {E}

C2 2nd scan

Itemset {B, C, E}

sup 2

sup 2 3 3 3

Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}

Contoh (lanj) Hitung Confidence • Confidence ( A  B) = P(B|A) = support_count(A U B) / support_count(A) • Itemset yang dihasilkan {B,C,E}, subsetnya {B,C}, {B,E}, {E,C}, {B}, {C}, {E} B ^ C  E : conf = ( 2 / 2 =100 %) B ^ E  C : conf = ( 2 / 3 = 66.6%) C^EB BC^E dst

Meningkatkan Efisiensi Metode Apriori • Teknik Hash-based, mengurangi jumlah itemset. • Transaction Reduction • Partisi data • Sampling • Dynamic itemset counting

Mining Freq. Itemset tanpa mengenerate Kandidat • Masalah apriori: – Dapat menghasilkan jumlah kandidat yang sangat besar. – Harus menscan database berulang kali dengan pattern matching. – Metode tanpa generate kandidat: Frequent Pattern growth  FP-growth • Teknik: compress database ke dalam FP-tree, bagi dalam conditional database, dan mine secara terpisah.

Buat FP-tree TID 100 200 300 400 500 • •

Item yang dibeli (ordered) frequent items {f, a, c, d, g, i, m, p} {f, c, a, m, p} {a, b, c, f, l, m, o} {f, c, a, b, m} {b, f, h, j, o, w} {f, b} {b, c, k, s, p} {c, b, p} {a, f, c, e, l, p, m, n} {f, c, a, m, p}

Scan DB untuk mencari frekuensi 1 itemset Sort dan dijadikan FList

Item frequency f 4 c 4 a 3 b 3 m 3 p 3

min_support = 3

F-list = f-c-a-b-m-p

TID 100 200 300 400 500

FP-Tree

Items bought (ordered) frequent items {f, a, c, d, g, i, m, p} {f, c, a, m, p} {a, b, c, f, l, m, o} {f, c, a, b, m} {b, f, h, j, o, w} {f, b} {b, c, k, s, p} {c, b, p} {a, f, c, e, l, p, m, n} {f, c, a, m, p} {}

Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3

f:4 c:3

c:1 b:1

a:3

b:1 p:1

m:2

b:1

p:2

m:1

Conditional Pattern {}

Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3

f:4 c:3

c:1 b:1

a:3

b:1 p:1

m:2

b:1

p:2

m:1

Conditional pattern item

cond. pattern base

c

f:3

a

fc:3

b

fca:1, f:1, c:1

m

fca:2, fcab:1

p

fcam:2, cb:1

Conditional F-Tree f:4 c:3

c:1 b:1

a:3

b:1 p:1

m:2

b:1

p:2

m:1

m-conditional pattern base: fca:2, fcab:1

f:3 c:3



a:3 m-conditional FP-tree



Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3

{}

{}

frequent patterns terkait dengan m m, fm, cm, am, fcm, fam, cam, fcam

Latihan