ASSOCIATION RULES PADA TEXT MINING

Budi Susanto

ASSOCIATION RULES PADA TEXT MINING

Text dan Web Mining - FTI UKDW - BUDI SUSANTO

1

Tujuan   Memahami

algoritma Apriori dan FP-

Growth   Memahami penerapannya pada penambangan dokumen   Memamahmi algoritma GSP   Memahami penerapannya pada penambangan dokumen


2

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

3

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

4

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


5

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


6

Contoh   Terdapat

himpunan transaksi I:

  Chicken, Clothes → Milk [sup = 3/7, conf = 3/3]   Clothes → Milk, Chicken [sup = 3/7, conf = 3/3]


7

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.


8

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.


9

Algoritma Apriori


10

Algoritma Apriori: pembentukan kandidat itemset


11

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

Algoritma: pembentukan rule


13

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 Text dan Web Mining - FTI UKDW - BUDI SUSANTO

14

FP-Tree   Menghasilkan

frequent items tanpa perlu membuat kandidat-kandidatnya. ◦  Kepadatan struktur tinggi ◦  Tidak perlu melakukan penelurusan database keseluruhan setiap saat


15

FP-Tree: Algoritma


16

Contoh


17

Contoh Item 3 2 1 5 4 6

Support Count 9 8 7 5 4 1


18

Asosiasi untuk Kategori   Metode

asosiasi, seperti Apriori dan FPTree, 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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

19

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 Text dan Web Mining - FTI UKDW - BUDI SUSANTO

20

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


21

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]


22

Pembangkit Rule


23

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]


24

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)


25

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]


26

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 = 〈a1a2...ar〉, ai adalah sebuah itemset. 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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

27

Konsep Sequence Pattern   s1

= 〈a1a2...ar〉 adalah sebuah subsequence s2 = 〈b1b2...bv〉, 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.


28

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. Text dan Web Mining - FTI UKDW - BUDI SUSANTO

29

Contoh Transaksi


30

Contoh Sequence


31

Contoh Pola Sequence


32

Algoritma GSP


33

Pembangkit Kandidat SPM  

Join step:

◦  Kandidat sequence dihasilkan dari penggabungkan Fk-1 dengan Fk-1.

  s1 digabungkan dengan s2 jika subsequence yang didapat dari pembuangan item pertama dari s1 adalah sama dengan pembuangan item terakhir dari s2.   Kandidat sequence yang dihasilkan dari penggabungan s1 dan s2 adalah sequence s1 diperluas dengan item terakhir dalam s2.   Item yang ditambahkan membentuk elemen terpisah jika item tersebut merupakan elemen dalam s2 dan ditambahkan sebagai elemen terakhir pada s1.   Item yang ditambahkan merupakan bagian dari elemen terakhir s1.

◦  Ketika menggabungkan F1 dan F1, kita perlu menambahkan item pada s2 baik sebagai bagian dari itemset atau elemen terpisah.

  <{x}> dengan <{y}> akan membentuk <{x, y}> dan <{x}{y}> Text dan Web Mining - FTI UKDW - BUDI SUSANTO

34

Pembangkit Kandidat SPM   Prune

step:

◦  Sebuah kandidat sequence dibuang jika ada sembarang (k-1) subsequence adalah infrequent.


35

Contoh kandidat SPM


36

Akhir pertemuan #4

TERIMA KASIH.


37

ASSOCIATION RULES PADA TEXT MINING

Recommend Documents