data mining iii asosiasi - · pdf filedata mining - asosiasi • bila diberi data transaksi...

Data Mining III

Asosiasi

Mata Kuliah Data Warehouse

Data Mining-Aturan Asosiasi-AAB 1

Universitas Darma Persada

Oleh

Adam Arif B

2011

Data Mining - Asosiasi

• Market basket analysis

• Tool untuk menemukan pengetahuan

berdasarkan hubungan asosiasi dua set data

Data Mining-Aturan Asosiasi-AAB 2

berdasarkan hubungan asosiasi dua set data

Data Mining - Asosiasi• Bila diberi data transaksi item belanja dari 14 pengunjung

pada swalayan UNSADA

Data Mining-Aturan Asosiasi-AAB 3

Data Mining - asosiasi

• Informasi apa yang bisa diperoleh dari data

tersebut?

• Pengetahuan apa yang tersimpan dalam data

Data Mining-Aturan Asosiasi-AAB 4

• Pengetahuan apa yang tersimpan dalam data

di atas?

Istilah-istilah

• Data di atas merupakan data historis, data masa

lalu

• � data latihan/training data

• � data data pengalaman

• Algoritma aturan asosiasi akan menggunakan data

Data Mining-Aturan Asosiasi-AAB 5

• Algoritma aturan asosiasi akan menggunakan data

latihan ini untuk menemukan pengetahuan sesuai

dengan definisi data mining

• Pengetahuan yang dihasilkan adalah mengetahui

item-item belanja yang sering dibeli secara

bersamaan

Istilah-istilah (lanj)

• Aturan asosiasi yang berbentuk “if….then….” atau “jika….maka”, merupakan pengetahuan yang dihasilkan dari fungsi aturan asosiasi.

• Item � barang yang dibeli atau barang yang

Data Mining-Aturan Asosiasi-AAB 6

• Item � barang yang dibeli atau barang yang menjadi objek kegiatan belanja.

• Pada swalayan unsada terdapat 7 jenis item yaitu (urut abjad) asparagus, beans, brocolli, corn, green

peppers, squash dan tomatoes.

Istilah-istilah (lanj)

• Himpunan item dilambangkan dengan Imerupakan himpunan dari semua jenis item yang akan dibahas.

• Persamaan himpunan item �

Persamaan 1:

Data Mining-Aturan Asosiasi-AAB 7

Persamaan 1:I = {asparagus, beans, brocolli, corn,

green peppers, squash, tomatoes}

• Himpunan item yang dibeli pengunjung ke–i disebut transaksi ke – i

• Dilambangkan Ti

Istilah-istilah (lanj)

Persamaan 2:

• T1 = {brocolli, green, peppers, corn}

• T2 = {Asparagus, squash, corn}

• ………

Data Mining-Aturan Asosiasi-AAB 8

• T14 = {corn, green, peppers, tomatoes,

beans, brocolli}

Persamaan 3:

• Himpunan seluruh transaksi dilambangkan

dengan D sehingga persamaan 3 ini

Data Mining-Aturan Asosiasi-AAB 9

dengan D sehingga persamaan 3 ini

menjadi:

D = {T1, T2, ….., T14}

Istilah-istilah

Persamaan 4� implikasi

“jika A, maka B” atau “ A ⇒ B ”

• A disebut anteseden atau pendahulu

• B disebut konsekuen atau pengikut

Aturan asosiasi yang dihasilkan nanti harus

Data Mining-Aturan Asosiasi-AAB 10

Aturan asosiasi yang dihasilkan nanti harus

memenuhi dua sifat

1. A maupun B adalah himpunan bagian

murni dari I

� Persamaan 5 yaitu A,B ⊂ I

Istilah-istilah

2. A dan B adalah dua himpunan yang saling

lepas. Sehingga disimbolkan pada

persamaan 6:

A ⇒ B = ø

Salah satu ukuran kinerja bagi aturan asosiasi

Data Mining-Aturan Asosiasi-AAB 11

Salah satu ukuran kinerja bagi aturan asosiasi

“A ⇒ B ” adalah besaran support

(dukungan) yang dilambangkan dengan

s(A ⇒ B). Dan didefinisikan sebagaimana

di persamaan 7.

Istilah-istilah (lanj)

• Persamaan 7

• Ukuran kinerja lain bagi aturan asosiasi

Data Mining-Aturan Asosiasi-AAB 12

“A ⇒ B “ adalah besaran support yang

dilambangkan dengan conf (A ⇒ B ) dan

didefinisikan sebagai Persamaan 8

Istilah-istilah (lanj)

• Persamaan 8

Jumlah transaksi yang mengandung A

Data Mining-Aturan Asosiasi-AAB 13

• Itemset � suatu himpunan yang

beranggotakan sebagian atau seluruh item

yang menjadi anggota I.

Jumlah transaksi yang mengandung BB A

Istilah-istilah (lanj)

• Contoh dari itemset adalah {Asparagus}

atau {Asparagus, Bean}, atau {Asparagus,

Beans, Squash}

Data Mining-Aturan Asosiasi-AAB 14

Beans, Squash}

• Itemset yang beranggotakan k buah item

disebut k-itemset.

Istilah-istilah (lanj)

1. Himpunan {Asparagus} adalah suatu itemset.

Lebih spesifik lagi 1-itemset karena hanya

beranggotakan satu buah item saja

2. Himpunan {Asparagus, Beans} adalah suatu

itemset. Lebih spesifik lagi 2-itemset karena

hanya beranggotakan dua buah item saja

Data Mining-Aturan Asosiasi-AAB 15

hanya beranggotakan dua buah item saja

3. Himpunan {Asparagus, beans, squash} adalah

suatu itemset. Lebih spesifik lagi 3-itemset

karena beranggotakan tiga buah item saja

Istilah-istilah (lanj)

• Besaran frekuensi itemset � mengukur

berapa kali sebuah itemset muncul sebagai

bagian atau keseluruhan transaksi yang

menjadi anggota daftar transaksi D.

Contoh:

Data Mining-Aturan Asosiasi-AAB 16

Contoh:

1. Frekuensi itemset {asparagus} adalah

6 karena himpunan ini menjadi bagian dari

enam transaksi (lihat data transaksi slide 3),

yaitu T2, T5, T6, T9, T12 dan T13

Istilah-istilah (lanj)

2. Frekuensi itemset {asparagus,

beans} adalah 5 karena himpunan ini

menjadi bagian dari lima transaksi , yaitu

T5, T6, T9, T12 dan T13

3. Frekuensi itemset {asparagus,

Data Mining-Aturan Asosiasi-AAB 17

3. Frekuensi itemset {asparagus,

beans, squash} adalah 4 karena

himpunan ini menjadi bagian dari empat

transaksi (slide 3), yaitu T6, T9, T12 dan

T13

Istilah-istilah (lanj)

• Itemset sering/frequent itemset � suatu

itemset yang memiliki frekuensi itemset

minimal sebesar bilangan Φ yang

ditetapkan.

Contoh� bila kita tetapkan Φ = 4, maka:

Data Mining-Aturan Asosiasi-AAB 18

Contoh� bila kita tetapkan Φ = 4, maka:

1. Itemset {asparagus, beans,

squash} termasuk itemset yang sering

karena memiliki frekuensi itemset yang

telah melebihi atau minimal sebesar Φ = 4.

Istilah-istilah (lanj)

2. Itemset {squash, tomatoes} tidak

termasuk itemset sering karena memiliki frekuensi

itemset sebesar 3, artinya masih di bawah nilai Φ

yang ditetapkan

Itemset sering yang memiliki k buah anggota disebut

k-itemset sering. Misalnya itemset

Data Mining-Aturan Asosiasi-AAB 19

k-itemset sering. Misalnya itemset

{asparagus, beans, squash} termasuk

3 itemset sering karena himpunan ini termasuk

itemset sering dan memiliki 3 anggota.

Himpunan dari seluruh k-itemset dilambangkan

dengan Fk.

Istilah-istilah (lanj)

• Aturan asosiasi secara ringkas digambarkan sbb:

1. Berawal dari data latihan yang tersedia (lihat slide 3)

2. Data latihan diolah dengan menggunakan

Data Mining-Aturan Asosiasi-AAB 20

2. Data latihan diolah dengan menggunakan algoritma atuan asosiasi.

3. Masalah aturan asosiasi berakhir dengan dihasilkannya pengetahuan yang direpresentasikan dalam bentuk diagram yang disebut aturan asosiasi.

Prototip masalah aturan asosiasi dan

pengetahuan yang dihasilkan

“jika membeli asparagus, maka membeli beans”

Dapat diartikan:

• Item asparagus mempunyai kecenderungan untuk

dibeli bersama-sama dengan item beans, atau

Data Mining-Aturan Asosiasi-AAB 21

• Pengunjung toko unsada yang membeli asparagus

mempunyai kecenderungan untuk juga membeli

beans

• Dan lain-lain. (misalnya…?)

Prototip masalah aturan asosiasi dan

pengetahuan yang dihasilkan

• Dengan adanya prototip ,masalah aturan

asosiasi kita dapat mengetahui definisi

masalah aturan asosiasi

• Dengan pembahasan interpretasi

Data Mining-Aturan Asosiasi-AAB 22

• Dengan pembahasan interpretasi

pengetahuan yang dihasilkan oleh fungsi

mayor aturan asosiasi, kita bisa mengetahui

cara memaknai pengetahuan yang

dihasilkan dari masalah ini.

Algoritma aturan asosiasi

Market Basket Analysis (MBA)

Hasil pembahasan sebelumnya dapat disimpulkan menjadi:

• Data historis merupakan data penting sebagai data latihan/training data

• Data tersebut akan dijadikan input bagi suatu

Data Mining-Aturan Asosiasi-AAB 23

• Data tersebut akan dijadikan input bagi suatu algoritma yang saat ini belum kita ketahui algoritmnya

• Sebagai keluaran algoritma yang saat ini belum kita ketahui jenisnya , kita akan memperoleh pengetahuan yang secara sederhana dapat direpresentasikan dalam bentuk “jika…., maka….”

langkah umum Market Basket Analysis

(MBA)

1. Menetapkan besaran Φ (itemset sering), nilai minimum besaran support dan besaran confidence yang diinginkan untuk dipenuhi oleh aturan asosiasi yang ingin dihasilkan

2. Menetapkan semua itemset sering, yaitu itemset

Data Mining-Aturan Asosiasi-AAB 24

2. Menetapkan semua itemset sering, yaitu itemset yang memiliki frekuensi itemset minimal sebesar bilangan Φ yang telah ditetapkan sebelumnya

3. Dari semua itemset sering, hasilkan aturan asosiasi yang memenuhi nilai minimum support dan confidence (yang telah ditetapkan)

Langkah dalam MBA-1

1. Langkah pertama

menetapkan besaran Φ dan nilai minimum support dan confidence , misalnya Φ = 4, maka min (support) = 30% dan min (confidence) = 70%

Data Mining-Aturan Asosiasi-AAB 25

2. Langkah kedua

Menyusun semua itemset sering, yaitu itemset yang memiliki frekuensi itemset minimal sebesar bilangan Φ = 4 yang telah ditetapkan di langkah pertama.

Langkah dalam MBA-2• Kita mulai dari pembahasan setiap 1-itemset sbb:

{asparagus}, {beans}, {brocolli},

{corn}, {green peppers}, {squash}

dan {tomatoes} adalah 1-itemset sering,

karena itemset ini berhasil muncul melebihi Φ kali,

atau 4 kali dalam daftar D, sehingga bisa dituliskan

Data Mining-Aturan Asosiasi-AAB 26

atau 4 kali dalam daftar D, sehingga bisa dituliskan

sebagai berikut:

F1 ={{asparagus}, {beans},

{brocolli}, {corn}, {green

peppers}, {squash} {tomatoes}}

Langkah dalam MBA-2 (lanj)

• Dilanjutkan dengan 2-itemset

1. {asparagus,beans}, {asparagus,brocoli},{asparagus,corn},{a

sparagus, green peppers}, {asparagus,

squash}, {asparagus, tomatoes}, {beans,

corn},{beans, green peppers}, {beans,

squash}, {beans, tomatoes},{brocoli,

Data Mining-Aturan Asosiasi-AAB 27

squash}, {beans, tomatoes},{brocoli,

corn}, {brocoli, green peppers},

{brocoli, squash}, {brocoli, tomatoes},

{corn, green peppers}, {corn, squash},

{corn, squash},{corn, tomatoes}, {green

peppers, squash}, {green peppers,

tomatoes}, {squash, tomatoes}

Langkah dalam MBA-2 (lanj)

2. Kesimpulan � hanya {asparagus, beans},

{asparagus, squash}, {bean, corn},

{bean, squash}, {bean, tomatoes},

{brocolli, greenpepper}, dan {corn,

tomatoes} yang merupakan 2-itemset sering

sehingga :

Data Mining-Aturan Asosiasi-AAB 28

sehingga :

F2 = {{asparagus, beans},

{asparagus, squash}, {bean, corn},

{bean, squash}, {bean, tomatoes},

{brocolli, greenpepper}, {corn,

tomatoes} }

Langkah dalam MBA-2 (lanj)

Untuk meringankan kita dalam mengkaji F3,

F4, F5 dan seterusnya , gunakan aturan

berikut:

“jika Z bukan itemset sering, maka Z ∪ A

pasti bukan itemset sering , untuk setiap A”

Data Mining-Aturan Asosiasi-AAB 29

pasti bukan itemset sering , untuk setiap A”

Aturan ini disebut aturan apriori

Langkah dalam MBA-2 (lanj)

Penggunaan aturan apriori

Bila {asparagus, brocolli} bukan 2-itemset sering, maka menurut aturan apriori:

{asparagus, brocoli, corn}

Data Mining-Aturan Asosiasi-AAB 30

{asparagus, brocoli, corn}

merupakan gabungan dari 2-itemset {asparagus, brocolli} yang tidak termasuk kedalam 2-itemset sering, dengan 1-itemset sering {corn},maka {asparagus, brocolli, corn} tidak akan pernah 3-itemset sering.

Langkah dalam MBA-2 (lanj)

• Penerapan aturan apriori terhadap seluruh anggota F2 hanya akan memberikan {asparagus, beans, squash}

sebagai satu-satunya 3-itemset sering sehingga didapatkan:

F3 = {{asparagus, beans,

Data Mining-Aturan Asosiasi-AAB 31

F3 = {{asparagus, beans,

squash}}

Selanjutnya akan diperoleh F4=F5=F6=F7= ø

Singkatnya akan menghasilkan himpunan itemset sering F1, F2, F3

Langkah dalam MBA-3

• Aturan asosiasi yang memenuhi nilai

minimum support dan confidence (yang

telah ditetapkan) dari semua itemset sering

yang ada akan dibangun

A. Dari semua itemset sering s yang ada di

Data Mining-Aturan Asosiasi-AAB 32

A. Dari semua itemset sering s yang ada di

F2, F3 dan seterusnya, daftarkan semua

himpunan bagian murni yang tak kosong

dari s sebutlah ss. Sehingga…..

Langkah dalam MBA-3 (lanj)

• Sehingga:

1. Untuk s = {asparagus,beans} didapatkan

ss = {asparagus} atau ss = {beans}

2. Untuk s = {asparagus,squash} didapatkan

ss = {asparagus} atau ss = {squash}

Data Mining-Aturan Asosiasi-AAB 33

ss = {asparagus} atau ss = {squash}

3. Untuk s = {beans,corn} didapatkan ss =

{beans} atau ss = {corn}

4. Untuk s = {beans,squash} didapatkan ss =

{beans} atau ss = {squash}

Langkah dalam MBA-3 (lanj)

5. Untuk s = {beans,tomatoes} didapatkan ss =

{beans} atau ss = {tomatoes}

6. Untuk s = {brocolli, green pepper} didapatkan ss

= {brocolli} atau ss = {greenpepper}

7. Untuk s = {corn, tomatoes} didapatkan ss =

Data Mining-Aturan Asosiasi-AAB 34

7. Untuk s = {corn, tomatoes} didapatkan ss =

{corn} atau ss = {tomatoes}

8. Untuk s = {asparagus, beans, squash} didapatkan

ss = {asparagus} atau ss = {beans} atau ss =

{squash} atau ss = {asparagus, bean}, atau ss =

{bean, squash}

Langkah dalam MBA-3 (lanj)

B. Bentuk aturan asosiasi yang berpola

“ jika ss, maka (s-ss) “ atau “s ⇒ (s-ss)”

Untuk mempermudah, pilihlah aturan yang

hanya berkonsekuen sebuah item saja

sehingga (s-ss) hanya beranggotakan sebuah

Data Mining-Aturan Asosiasi-AAB 35

sehingga (s-ss) hanya beranggotakan sebuah

item saja. Sehingga masalah toko unsada

didapatkan calon aturan asosiasi pada tabel

berikut.

Langkah dalam MBA-3 (lanj)

Data Mining-Aturan Asosiasi-AAB 36

keterangan:

kolom support = 5/14 � asosiasi terbanyak asparagus dan beans per banyaknya transaksi (14)

Kolom confidence = 5/6 � 6 => jumlah banyaknya asparagus

5/10 � 10 => jumlah banyaknya beans

Langkah dalam MBA-3 (lanj)

C. Pilih aturan asosiasi yang memenuhi nilai

minimum (support) dan minimum

(confidence) saja. Sebelumnya ditentukan

batasan min (support) = 30% dan min

(confidence) = 70% tampak pada tabel di

Data Mining-Aturan Asosiasi-AAB 37

(confidence) = 70% tampak pada tabel di

bawah

Langkah dalam MBA-3 (lanj)

Data Mining-Aturan Asosiasi-AAB 38

Capeeknya habis

ngitung

gituan…bobok

dulu ah

Data Mining-Aturan Asosiasi-AAB 39

Pengetahuan apa yang bisa diperoleh

dari perhitungan tersebut?

• Jika pelanggan membeli asparagus maka barang

berikutnya yang dibeli adalah beans dan atau squash �

83.3%

• Jika pelanggan membeli squash, maka barang berikutnya

Data Mining-Aturan Asosiasi-AAB 40

• Jika pelanggan membeli squash, maka barang berikutnya

yang dibeli adalah asparagus� 71.4%

• Jika pelanggan membeli beans, maka barang berikutnya

yang dibeli adalah squash � 60%

• Jika pelanggan membeli corn, maka barang berikutnya

yang dibeli adalah beans � 62.5%

Langkah selanjutnya?

• Berdasarkan data tersebut bisa dilakukan penataan barang berdasarkan yang banyak dibeli

• Pemberian discount pada hari tertentu

• Dll

Data Mining-Aturan Asosiasi-AAB 41

• Dll

• Dll

• Stok asparagus dan beans diperbanyak sesuai permintaan pembelian salah satu barang

Algoritma lain?

• Market basket Analysis bukan satu-satunya

algoritma untuk mengetahui asosiasi

• Terdapat algoritma lain untuk keperluan

Data Mining-Aturan Asosiasi-AAB 42

• Terdapat algoritma lain untuk keperluan

yang sama misalnya:

- algoritma Generalized Association Rules

- Algoritma Quantitative Association rule

- Algoritma Asynchronous Parallel Mining

Pekerjaan Rumah(kumpulkan minggu depan)

• Saya tinggal di pedesaan. Di desa ku sering

ada pertunjukkan sirkus. Tidak setiap hari

sirkus ini show di desaku. Saya pernah

Data Mining-Aturan Asosiasi-AAB 43

sirkus ini show di desaku. Saya pernah

mengamati kapan saja mereka main ke sini.

Dan data pengamatan saya , saya buatkan

tabel sebagai berikut

Data Mining-Aturan Asosiasi-AAB 44

• Dengan data di atas perkirakan kapan rombongan

sirkus tersebut show atau tidak di desa saya.

• selamat mengerjakan

Data Mining-Aturan Asosiasi-AAB 45

referensi

Data Mining-Aturan Asosiasi-AAB 46