Mining Association Rules dalam Basis Data yang Besar S1 Teknik Informatika Fakultas Teknologi Informasi Universitas Kristen Maranatha
Agenda •
Pendahuluan
•
Association Rule Mining • • •
Market Basket Analysis Konsep Dasar Contoh
•
Algoritma Apriori
•
Frequent Pattern Growth (FP Growth)
2
1
Pendahuluan •
Asosiasi atau korelasi hubungan dalam sekumpulan besar data.
•
Pendorong : • •
•
Jumlah data yang dikoleksi dan disimpan oleh industri yang semakin besar. Asosiasi hubungan yang ditemukan dapat menolong dalam pembuatan keputusan bisnis seperti desain katalog dan marketing
Contoh umum : market basket analysis 3
Market Basket Analysis Cust. 1 : milk, bread, cereal Cust. 2 : milk, bread, Sugar, eggs Cust. 3 : milk, bread, butter Market Analis : Item mana yang sering dibeli bersamaan oleh customer saya ?
4
2
Contoh Market Basket Analysis (MBA) •
Sales manager, ingin mengetahui kebiasaan membeli para customernya.
•
Pertanyaan : kelompok atau item mana saja yang biasa dibeli oleh customer pada satu kali waktu belanja ?
•
MBA : diterapkan pada data retail transaksi customer.
•
Hasil dapat digunakan untuk merencanakan strategi marketing atau advertising. 5
Contoh Penggunaan Hasil MBA
•
Untuk menentukan layout toko.
•
Item yang sering dibeli bersamaan ditempatkan berdekatan.
•
Penggambaran pola dapat direpresentasikan dengan association rule.
•
Ex. : computer => software
•
Support = 2%, confidence = 60%
6
3
Contoh Penggunaan Hasil MBA •
Support dan confidence merupakan ukuran tingkat kemenarikan.
•
Keduanya menunjukkan tingkat kegunaan dan keyakinan dari rule yang ada.
•
Support 2% berarti 2% dari seluruh transaksi yang dianalisis menunjukkan bahwa computer dan software dibeli bersamaan.
•
Confidence 60% berarti 60% customer yang membeli computer juga membeli software.
•
Pada umumnya, suatu association rule dianggap menarik jika memenuhi minimum support dan confidence threshold tertentu yang diset oleh user / domain expert.
7
Konsep Dasar : Istilah (1) •
Support({A,B}) : banyaknya transaksi yang mengandung item A dan item B
•
Minimum Support : digunakan untuk membatasi variasi itemset
8
4
Basic concept : Istilah(2) •
Confidence (A=>B): probabilitas (B|A), dihitung sebagai confidence( A => B ) =
•
sup({ A, B}) sup({ A})
Jika rule ini mempunyai confidence 0.33, berarti jika A dan B terjadi dalam satu transaksi, terdapat 33% kemungkinan bahwa B juga terjadi.
9
Basic concept : Istilah (3) •
K-itemset : suatu itemset yang berisi k item. •
Ex. {computer,software} adalah 2-itemset.
•
Frekuensi kejadian / occurrence frequency of itemset : banyaknya transaksi yang berisi itemset. Sering disebut juga sebagai frequency, support count, atau count.
•
Rule disebut strong jika memenuhi min support dan confidence threshold.
10
5
Konsep Dasar : Contoh
Total transaksi : 1000 Hammer : 50 Nails : 80 Lumber : 20 Hammer + nails : 15 Nails + lumber : 10 Hammer + lumber : 10 Hammer, nails, lumber : 5
Support u/ hammer, nails : 1,5% (15/1000) Support u/ hammer, nails, lumber : 0,5% (5/1000) Confidence hammer nails : 30% (15/50) Confidence nails hammer : 19% (15/80) Confidence hammer, nails lumber : 33% (5/15) Confidence lumber hammer, nails : 25% (5/20)
11
Langkah – Langkah dalam Association Rule Mining •
Temukan seluruh frequent itemset •
•
Harus memenuhi minimum support yang telah ditentukan sebelumnya.
Generate association rules yang kuat dari frequent itemset •
Memenuhi confidence threshold
12
6
Frequent Patterns & Association Rules Transaction--id Transaction
Items bought
•
Itemset X = {x1, …, xk}
10
A, B, D
•
20
A, C, D
30
A, D, E
40
B, E, F
50
B, C, D, E, F
Find all the rules X Y with minimum support and confidence • support, s, probability that a transaction contains X ∪Y • confidence, c, conditional probability that a transaction having X also contains Y
Customer buys both
Customer buys A
Customer buys D
confidence ( A => B ) =
sup({ A , B }) sup({ A})
Let supmin = 50%, confmin = 50% Jumlah Transaksi : 5 Freq. Pat.: {A:3, B:3, D:4, E:3, AD:3 } Association rules (support, confidence): A D (60%, 100%) D A (60%, 75%)
13
Kekuatan dan Kelemahan AR •
Kekuatan : • • •
•
Result yang mudah dipahami dengan jelas Mendukung undirected DM Dapat dijalankan pada data yang variable length
Kelemahan : •
• •
Membutuhkan resource komputasi yang besarnya meningkat secara eksponensial sesuai problem yang ada Cukup sulit untuk menentukan itemset yang benar untuk dianalisis Tidak bisa menangani item yang jarang.
14
7
Algoritma Apriori & FP Growth •
Algoritma apriori : •
•
algoritma untuk menemukan frequent itemset dengan candidate generation.
FP Growth : •
metode mining frequent itemset tanpa candidate generation.
15
Apriori: A Candidate Generation-and-Test Approach •
Prinsip apriori pruning: jika terdapat semua itemset yang jarang frekuensinya, superset dari itemset tersebut tidak perlu dibuat / dites ! (Agrawal & Srikant @VLDB’94, Mannila, et al. @ KDD’ 94)
•
Metode: • Awalnya, scan basis data sekali untuk mendapatkan 1-itemset yang sering muncul • Membuat kandidat itemset dengan panjang (k+1) dari itemset k yan gsering muncul • Tes kandidat tersebut terhadap basis data • Berhenti saat tidak ada set atau kandidat yang sering muncul sudah tidak dapat dibuat lagi
16
8
Algoritma Apriori - Contoh 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
Itemset {A} {B} {C} {E}
L1
C2 2nd scan
Itemset {B, C, E}
sup 2 3 3 3
Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}
sup 2
17
Algoritma Apriori •
Pseudo-code: Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = {frequent items}; for (k = 1; Lk !=∅; k++) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do
increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return ∪k Lk;
18
9
Detil penting dari Apriori •
Bagaimana untuk menghasilkan kandidat? • •
Langkah 1: self-joining Lk Langkah 2: pruning
•
Bagaimana cara menghitung support dari para kandidat?
•
Contoh dari cara menghasilkan kandidat • •
L3={abc, abd, acd, ace, bcd} Self-joining: L3*L3 • •
abcd from abc and abd acde from acd and ace
•
Pruning:
•
C4={abcd}
•
acde is removed because ade is not in L3
19
Mining Frequent Patterns Without Candidate Generation •
Menumbuhkan pola – pola yang panjang dari yang pendek dengan item lokal yang sering muncul •
“abc” adalah pola yang sering muncul
•
Mengambil semua transaksi yg mengandung “abc”: DB|abc
•
“d” adalah pola lokal yang sering muncul di DB|abc abcd adalah sebuah pola yang sering muncul
20
10
Konstruksi FP-tree dari sebuah Basis Data Transaksi TID 100 200 300 400 500
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} min_support = 3 {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 1. Scan DB sekali, temukan 1itemset yang sering muncul f:4 c:1 Item frequency head (pola satu item) f 4 2. Urutkan item yang sering c 4 c:3 b:1 b:1 muncul dalam urutan a 3 menurun, f-list b 3 a:3 p:1 3 3. Scan DB lagi, konstruksi FP- m tree p 3 m:2 b:1
F-list=f-c-a-b-m-p
21
p:2
m:1
Menenukan Pola – Pola yang Memiliki P dari DB Kondisional P •
Dimulai dari item yang sering muncul dari FP-tree
•
Runut FP-tree dengan mengikuti setiap link dari setiap item yang sering muncul p
•
Akumulasi setiap transformed prefix path dari item p untuk membentuk basis pola p {}
Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 DM-MA/S1IF/FIT/UKM/2010
Conditional pattern bases f:4 c:3
b:1
a:3
c:1
item
cond. pattern base
b:1
c
f:3
a
fc:3
b
fca:1, f:1, c:1
m
fca:2, fcab:1
p
fcam:2, cb:1
p:1
m:2
b:1
p:2
m:1
22
11
Dari basis Pola Kondisional ke FP-trees Kondisional •
Untuk setiap basis pola • •
Akumulasi count dari setiap item dalam basis Konstruksi FP-tree untuk item yang sering muncul dari basis pola m-conditional pattern base:
Header Table Item frequency head f 4 c 4 a 3 b 3 m 3 p 3
fca:2, fcab:1
{} f:4 c:3
{}
c:1 b:1
a:3
b:1 p:1
m:2
b:1
p:2
m:1
f:3 c:3
All frequent patterns relate to m m, fm, cm, am, fcm, fam, cam, fcam
a:3 m-conditional 23 FP-tree
Keuntungan dari FP-tree Structure •
Lengkap • •
•
Menyimpan informasi yang lengkap dari mining pola yang sering muncul Tidak pernah memutus sebuah pola yang panjang dari setiap transaksi
Padat • • • •
Mengurangi info yang tidak relevan – item yang jarang muncul hilang Item disusun denga urutan menurun: semakin sering muncul, semakin mungkin dibagi dengan yang lain Tidak pernah lebih besar dari DB asal (tidak menghitung nodelinks dan hitungan field) Untuk DB jenis Connect-4, rasio kompresi sampai lebih dari 100
24
12
Latihan •
Diberikan :
Transaction--id Transaction
Items bought
Min_sup = 60%
T100
K, A, B, D
Min_conf = 80%
T200
A, C, D, B, E
T300
C, A, B, E
T400
B, E
T500
B, A, D
•
Carilah semua itemset frequent dengan Apriori dan FP-growth, bandingkan efisiensi keduanya
•
Daftarkan semua strong association rules yang memenuhi :
∀x ∈ transaksi , buys( X , item1) ∧ buys( X , item 2) ⇒ buys ( X , item3) 25
13
