ASSOCIATION RULES PADA TEXT MINING

Text dan Web Mining - FTI UKDW - BUDI SUSANTO

ASSOCIATION RULES PADA TEXT MINING Budi Susanto versi 1.4

1


2

Tujuan • Memahami algoritma Apriori dan FP-Growth

• Memahami penerapannya pada penambangan dokumen • Memamahmi algoritma GSP • Memahami penerapannya pada penambangan dokumen


3

Pendahuluan • Analisis aturan asosiasi merupakan tugas dasar pada

data mining. • Tujuannya: • Menemukan hubungan kemunculan bersamaan (asosiasi) diantara

item-item data.

• Aplikasi klasik yang menggunakan metode ini adalah

market basket data analysis. • Tujuannya: menemukan bagaimana item-item barang yang dibeli

oleh pelanggan diasosiasikan.


4

Pendahuluan • Contoh: • Sabun Mandi  Pasta Gigi • [support: 40%, confidence = 80%] • 40% pelanggan membeli Sabun Mandi dan Pasta Gigi bersamaan • 80% pelanggan membeli Sabun Mandi juga membeli Pasta Gigi.

• Dalam text mining, association rules dapat digunakan

untuk menemukan hubungan kemunculan kata.


5

Konsep Dasar Association Rules

I = {i1,i2 ,...,im }

Himpunan item

T = {t1, t2 ,..., tn }

Himpunan transaksi

Ti adalah himpunan item dimana

ti Í I

Bentuk implikasi pada association rules:

X Y, dimana

X Ì I,Y Ì I, X ÇY = 0


6

Ukuran • Support • Seberapa sering aturan yang dihasilkan berlaku pada himpunan transaksi T. • Confidence • Dilihat sebagai probabilitas kondisional terhadap aturan. • Aturan yang terpilih adalah aturan yang memenuhi

minimum support dan minimum confidence


Contoh • Terdapat himpunan transaksi I:

• Chicken, Clothes • Clothes

Milk [sup = 3/7, conf = 3/3] Milk, Chicken [sup = 3/7, conf = 3/3]

7


8

Algoritma Apriori • Terdapat dua tahap utama: • Hasilkan semua frequent itemsets (itemset yang memiliki support > minsupport) • Hasilkan semua aturan asosiasi dari frequent itemsets (confident > minconfident)

• Jumat item dalam sebuah itemset ditentukan, k.


9

Apriori: pembentukan itemset • Apriori menganut prinsip downward closure property • Jika sebuah itemset memiliki support minimum, maka setiap subset non-empty dari itemset tersebut juga memiliki support minimum. • Item-item dalam I, sudah dalam keadaan terurutkan

secara lexicographic order.


Algoritma Apriori

10


11

Algoritma Apriori: pembentukan kandidat itemset


Contoh: Data TID 001 002 003 004 005 006 007 008 009 010

Item-item 1,2,3,5 2,3,4 2,3,6 1,2,4 1,3,4,5 2,3,5 1,3 1,2,3,5 1,2,3 1,2,3,4,5

Min Support: 40%, dan Min Confident: 60%

12


Contoh: Kandidat 2-itemsets C2 itemsets {1, 2} {1, 3} {1, 4} {1, 5} {2, 3} {2, 4} {2, 5} {3, 4} {3, 5} {4, 5}

Support Count 5 6 3 4 7 3 4 3 5 2

13


Pruning 2-itemsets C2 itemsets {1, 2} {1, 3} {1, 5} {2, 3} {2, 5} {3, 5}

Support Count 5 6 4 7 4 5

14


Kandidat 3-itemsets C3 itemsets

Support Count

{1, 2, 3}

4

{1, 3, 5}

4

{2, 3, 5}

4

15


Pruning 3-itemsets C3 itemsets

Support Count

{1, 2, 3}

4

{1, 3, 5}

4

{2, 3, 5}

4

16


Algoritma: pembentukan rule

17


Contoh Pembentukan Rule • Candidate Rule 1: • Rule1: {1,2}  {3} • Support: 4/10 • Confident: 4/5

• Rule 2: {1,3}  {2} • Support: 4/10 • Confident: 4/6 • Rule 3: {2,3}  {1} • Support: 4/10 • Confident: 4/7

• H1 = {{2}, {3}}, sehingga H2 = {2,3} • Rule 4: {1}  {2,3} • Support: 4/10 • Confident: 4/7

18


19

FP-Tree • Menghasilkan frequent items tanpa perlu membuat

kandidat-kandidatnya. • Kepadatan struktur tinggi • Tidak perlu melakukan penelurusan database keseluruhan setiap

saat


FP-Tree: Algoritma

20


Contoh

21


Contoh Item 3 2 1 5 4 6

Support Count 9 8 7 5 4 1

22


23

Asosiasi untuk Kategori • Metode asosiasi, seperti Apriori dan FP-Tree, tidak

memiliki sasaran pada klausa consequent. • Klausa consequent ditentukan juga dari itemset dalam transaksi.

• Jika asosiasi dilakukan terhadap suatu consequent

dengan target tertentu, Y, maka metode yang digunakan disebut sebagai class association rules.


24

Asosiasi untuk Kategori • T adalah himpunan transaksi sebanyak n.

• Setiap transaksi diberi label y. • I adalah himpunan semua item dalam T, dan Y adalah

himpunan label class (target) dan I Ç Y = θ. • Sebuah Class Association rule (CAR) adalah bentuk implikasi dari

X ® y, X Ì I, y Î Y


Contoh I = {Student, Teach, School, City, Game, Baseball, Basketball, Team, Coach, Player, Spectator} Y = {Education, Sport}.

25


Contoh • Misal minsup = 20% dan minconf = 60%, maka: • Student, School Education • [sup= 2/7, conf = 2/2]

• Game

Sport

• [sup= 2/7, conf = 2/3]

26


Pembangkit Rule

27


28

Contoh CAR • F1: {({School}, Education):(3, 3), ({Student},

Education):(2, 2), ({Teach}, Education):(2, 2), ({Baseball}, Sport):(2, 2), ({Basketball}, Sport):(3, 3), ({Game}, Sport):(3, 2), ({Team}, Sport):(2, 2)} • CAR1: • School • •

• • • •

Education Student Education Teach Education Baseball Sport Basketball Sport Game Sport Team Sport

[sup = 3/7, conf = 3/3] [sup = 2/7, conf = 2/2] [sup = 2/7, conf = 2/2] [sup = 2/7, conf = 2/2] [sup = 3/7, conf = 3/3] [sup = 2/7, conf = 2/3] [sup = 2/7, conf = 2/2]


Contoh CAR • C2: { • ({School, Student}, Education), • ({School, Teach}, Education), • ({Student, Teach}, Education), • ({Baseball, Basketball}, Sport), • ({Baseball, Game}, Sport), • ({Baseball, Team}, Sport), • ({Basketball, Game}, Sport), • ({Basketball, Team}, Sport), • ({Game, Team}, Sport)

}

29


Contoh CAR • F2 : { • ({School, Student}, Education):(2, 2), • ({School, Teach}, Education):(2, 2), • ({Game, Team}, Sport):(2, 2) } • CAR2: • School, Student

Education

• [sup = 2/7, conf = 2/2]

• School, Teach

Education

• [sup = 2/7, conf = 2/2]

• Game, Team

Sport

• [sup = 2/7, conf = 2/2]

30


31

Lift Ratio • Jika suatu rule memiliki confidence tinggi, berarti rule

tersebut mencirikan aturan asosiasi yang kuat. • Pemilihan rule berdasar confidence bisa menipu, sebab jika (A)ntecedent/(C)onsequent memiliki support yang tinggi, maka rule dapat memiliki confidence tinggi, walaupun sebetulnya independen.


32

Lift Ratio • Ukuran yang lebih baik untuk mengukur kekuatan aturan

asosiasi adalah • Membandingkan confidence rule dengan confidence yang

diharapkan. • Kemunculan consequent itemset dalam transaksi bersifat independen

terhadap kemunculan antecedent tiap rulenya. • Support consequent dibagi dengan jumlah transaksi.

• Expected confidence dari sebuah rule adalah perkalian

support antecedence dan consequence dibagi dengan support dari antecedence.


33

Lift Ratio • Sebuah lift ratio > 1.0 menyatakan Ant dan Cons muncul

lebih sering dari yang diharapkan • kemunculan rule Ant memiliki efek positif terhadap kemunculan

Cons

• Sebuah lift ratio < 1.0 menyatakan Ant dan Cons muncul

lebih jarang dari yang diharapkan • kemunculan rule Ant memiliki efek negatif terhadap kemunculan

Cons

• Sebuah list ratio ≈ 1.0 menyatakan Ant dan Cons muncul

hampir selalu bersamaan seperti yang diharapkan • kemunculan rule Ant hampir tidak memiliki pengaruh terhadap

kemunculan Cons


Lift Ratio s ( A ÈC ) c ( A Þ C ) = P (C | A) = s ( A)

s(A)´ s(C) c' ( A Þ C ) = s ( A)

34


Contoh Lift Ratio

35

36


Contoh Lift Ratio A

C

c(A)

s(C)

c(A U C)

conf

lift

{1,2}

{5}

4

2/9

2

2/4

18/8

{1,5}

{2}

2

7/9

2

2/2

9/7

{2,5}

{1}

2

6/9

2

2/2

9/6

{1}

{2,5}

6

2/9

2

2/6

9/6

{2}

{1,5}

7

2/9

2

2/7

9/7

{5}

{2,1}

2

4/9

2

2/2

9/4

{1,2}

{3}

4

6/9

2

2/4

9/12

{1,3}

{2}

4

7/9

2

2/4

18/28

{2,3}

{1}

4

6/9

2

2/4

9/12

{1}

{2,3}

6

4/9

2

2/6

9/12

{2}

{1,3}

7

4/9

2

2/7

9/14

{3}

{1,2}

6

4/9

2

2/6

9/12


37

SEQUENCE PATTERN


38

Sequential Pattern Mining • Diberikan sebuah himpunan sequential, temukan

himpunan lengkap dari frequent subsequences. Sebuah sequence : < (ef) (ab) (df) c b >

Database SID 10 20 30 40

sequence <(ad)c(bc)(ae)> <(ef)(ab)(df)cb> <eg(af)cbc>

An element may contain a set of items. Items within an element are unordered and we list them alphabetically.

sebuah subsequence dari

Diberikan min_sup =2, <(ab)c> adalah sebuah sequential pattern


39

Tantangan Sequental Pattern Mining • Sejumlah besar pola sekuensial tersembunyi dalam

database. • Sebuah algoritma mining harus • Menemukan himpulan pola-pola lengkap, yang memenuhi ambang

batas minimum support (frekuensi). • Harus efisien, scalable, melibatkan hanya sejumlah kecil penelurusan database. • Mampu dikaitkan dengan berbagai macam user-specific constraint.


40

Konsep Sequence Pattern • Association Rule tidak memperhatikan urutan dari

transaksi. • I = {i1, i2, ..., im} adalah himpunan item • Sebuah sequence adalah daftar urutan dari itemset. • X ⊆ I, dimana X adalah itemset. • s =, ai adalah sebuah itemset (elemen dari s). • ai = {x1, x2, ..., xk}, dimana xj ∈ I adalah item. • Sebuah item hanya dapat muncul sekali dalam suatu sequence. • Ukuran suatu sequence adalah jumlah itemset dalam sequence • Panjang suatu sequence adalah jumlah item dalam suquence. • k-sequence adalah sequence dengan panjang k.


41

Konsep Sequence Pattern • s1 = adalah sebuah subsequence s2 =

, atau s2 adalah supersequence dari s1, jika terdapat integer 1≤j1 <j2 <...<jr-1<jr ≤ v sehinga a1 ⊆ bj, a2 ⊆ bj, ..., ar ⊆ bjr. • Kita juga mengatakan s2 berisi s1.


42

Konsep Sequence Pattern • c adalah subsequence dari s jika memenuhi salah satu

kondisi berikut: • c diturunkan dari s dengan membuang sebuah item dari salah satu

sequence baik s1 atau sn. • c diturunkan dari s dengan membuang sebuah item dari sebuah elemen sj yang memiliki minimum 2 item. • c adalah contiguous subsequence dari ċ dan ċ adalah contiguous subsequence dari s.


Contoh • I = {1, 2, 3, 4, 5, 6, 7, 8, 9}

• s1 = <{3}{4, 5}{8}> • Ukuran = 3 • Panjang = 4 • s2 = <{6} {3, 7}{9}{4, 5, 8}{3, 8}> • s1 subsequence s2 karena • {3} ⊆ {3, 7}, {4, 5} ⊆ {4, 5, 8}, dan {8} ⊆ {3, 8} • Sedangkan <{3}{8}> bukan subsequence <{3, 8}>,

demikian juga sebaliknya.

43


44

Contoh SID

sequence

10

20

<(ad)c(bc)(ae)>

30

<(ef)(ab)(df)cb>

40

<eg(af)cbc>

• Bagaimana dengan: • • <(ab)c>

Data sequence

Subsequence

Contain?

< {2,4} {3,5,6} {8} >

< {2} {3,5} >

Yes

< {1,2} {3,4} >

< {1} {2} >

No

< {2,4} {2,4} {2,5} >

< {2} {4} >

Yes


45

Contoh Object A A A B B C C C D D D E E

Timestamp 1 2 3 1 2 1 2 3 1 2 3 1 2

Events 1,2,4 2,3 5 1,2 2,3,4 1, 2 2,3,4 2,4,5 2 3, 4 4, 5 1, 3 2, 4, 5

Minsup = 50% Examples of Frequent Subsequences: < {1,2} > < {2,3} > < {2,4}> < {3} {5}> < {1} {2} > < {2} {2} > < {1} {2,3} > < {2} {2,3} > < {1,2} {2,3} >

s=60% s=60% s=80% s=80% s=80% s=60% s=60% s=60% s=60%


46

GSP • Generalized Sequential Patterns: Srikant & Agrawal @

EDBT’96 • Berdasar algoritma Apriori (Agrawal & Sirkant’94) • Jika sebuah sequence S bukan frekuen, • Maka tidak ada super-sequences dari S adalah frekuen. • Contoh: • adalah infrequent, maka • dan <(ah)b>


47

GSP • Outline dari metode GSP: • Inisialisasi, setiap item dalam DB sebagai sebuah kandidat length1. • Untuk setiap level (sequence length-k) • Scan database untuk mengumpulkan support count untuk setiap

kandidat sequence. • Hasilkan kandidat length-(k+1) sequence dari length-k frequent sequence menggunakan Apriori. • Ulangi sampai tidak ada frekuen sequence atau tidak ada lagi

kandidat yang ditemukan.


Algoritma GSP

48


candidate-gen-SPM(Fk-1)

49


Contoh candidate-gen-SPM()

50


Contoh GSP min_sup =2 Seq. ID

Sequence

10

<(bd)cb(ac)>

20

<(bf)(ce)b(fg)>

30

<(ah)(bf)abf>

40

<(be)(ce)d>

50

Cand <e>

Sup 3 5 4 3 3 2 1 1

51


GSP - Kandidat Length-2 <e>

<ea>

<e>

<eb>

<(ab)>

<ec>

<(ac)> <(bc)>

<ed>

<(ad)> <(bd)> <(cd)>

<e> <de> <ee>

<ef>

<e> <(ae)> <(be)> <(ce)> <(de)>

<(af)> <(bf)> <(cf)> <(df)> <(ef)>

52


53

Proses GSP 5th scan: 1 cand. 1 length-5 seq. pat.

Cand. cannot pass sup. threshold Cand. not in DB at all

<(bd)cba>

4th scan: 8 cand. 6 length-4 seq. <(bd)bc> … pat. 3rd scan: 46 cand. 19 length-3 seq. … pat. 20 cand. not in DB at all 2nd scan: 51 cand. 19 length-2 seq. … … <(ab)> … <(ef)> pat. 10 cand. not in DB at all 1st scan: 8 cand. 6 length-1 seq. <e> pat.

min_sup =2

Seq. ID

Sequence

10

<(bd)cb(ac)>

20

<(bf)(ce)b(fg)>

30

<(ah)(bf)abf>

40

<(be)(ce)d>

50


Contoh Transaksi

54


Contoh Sequence

55


Contoh Pola Sequence

56


57

SPADE • SPADE (Sequential PAttern Discovery using Equivalent

Class) dikembangkan oleh Zaki 2001 • Sebuah metode format vertikal sequential pattern mining • Sebuah sequence database dipetakan ke suatu

himpunan dari • Item: <SID, EID>

• Sequential pattern mining dikerjakan dengan • Menumbuhkan subsequences (patterns) satu item pada satu waktu

dengan menggunakan Apriori candidate generation


58


TERIMA KASIH. Akhir pertemuan #4

59

ASSOCIATION RULES PADA TEXT MINING

Recommend Documents