Data Mining III Asosiasi

Data Mining III Asosiasi Mata Kuliah Data Warehouse Universitas Darma Persada Oleh Adam Arif B 2011

Data Mining-Aturan Asosiasi-AAB

1

Data Mining - Asosiasi • Market basket analysis • Tool untuk menemukan pengetahuan berdasarkan hubungan asosiasi dua set data


2

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


3

Data Mining - asosiasi • Informasi apa yang bisa diperoleh dari data tersebut? • Pengetahuan apa yang tersimpan dalam data di atas?


4

Istilah-istilah • Data di atas merupakan data historis, data masa lalu • data latihan/training data • data data pengalaman • 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 Data Mining-Aturan Asosiasi-AAB

5

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 menjadi objek kegiatan belanja. • Pada swalayan unsada terdapat 7 jenis item yaitu (urut abjad) asparagus, beans, brocolli, corn, green peppers, squash dan tomatoes. Data Mining-Aturan Asosiasi-AAB

6

Istilah-istilah (lanj) • Himpunan item dilambangkan dengan I merupakan himpunan dari semua jenis item yang akan dibahas. • Persamaan himpunan item Persamaan 1: I = {asparagus, beans, brocolli, corn, green peppers, squash, tomatoes}

• Himpunan item yang dibeli pengunjung ke–i disebut transaksi ke – i • Dilambangkan Ti Data Mining-Aturan Asosiasi-AAB

7

Istilah-istilah (lanj) Persamaan 2: • • • •

T1 = {brocolli, green, peppers, corn} T2 = {Asparagus, squash, corn} ……… T14 = {corn, green, peppers, tomatoes, beans, brocolli}


8

Persamaan 3: • Himpunan seluruh transaksi dilambangkan dengan D sehingga persamaan 3 ini menjadi: D = {T1, T2, ….., T14}


9

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 memenuhi dua sifat 1. A maupun B adalah himpunan bagian murni dari I Persamaan 5 yaitu A,B ⊂ I Data Mining-Aturan Asosiasi-AAB

10

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 “A ⇒ B ” adalah besaran support (dukungan) yang dilambangkan dengan s(A ⇒ B). Dan didefinisikan sebagaimana di persamaan 7. Data Mining-Aturan Asosiasi-AAB

11

Istilah-istilah (lanj) • Persamaan 7

• Ukuran kinerja lain bagi aturan asosiasi “A ⇒ B “ adalah besaran support yang dilambangkan dengan conf (A ⇒ B ) dan didefinisikan sebagai Persamaan 8


12

Istilah-istilah (lanj) • Persamaan 8 Jumlah transaksi yang mengandung A B

A

Jumlah transaksi yang mengandung B

• Itemset suatu himpunan yang beranggotakan sebagian atau seluruh item yang menjadi anggota I. Data Mining-Aturan Asosiasi-AAB

13

Istilah-istilah (lanj) • Contoh dari itemset adalah {Asparagus} atau {Asparagus, Bean}, atau {Asparagus, Beans, Squash} • Itemset yang beranggotakan k buah item disebut k-itemset.


14

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 3. Himpunan {Asparagus, beans, squash} adalah suatu itemset. Lebih spesifik lagi 3-itemset karena beranggotakan tiga buah item saja


15

Istilah-istilah (lanj) • Besaran frekuensi itemset mengukur berapa kali sebuah itemset muncul sebagai bagian atau keseluruhan transaksi yang menjadi anggota daftar transaksi D. 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 Data Mining-Aturan Asosiasi-AAB

16

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, beans, squash} adalah 4 karena himpunan ini menjadi bagian dari empat transaksi (slide 3), yaitu T6, T9, T12 dan T13 Data Mining-Aturan Asosiasi-AAB

17

Istilah-istilah (lanj) • Itemset sering/frequent itemset suatu itemset yang memiliki frekuensi itemset minimal sebesar bilangan Φ yang ditetapkan. 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. Data Mining-Aturan Asosiasi-AAB

18

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 {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. Data Mining-Aturan Asosiasi-AAB

19

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 algoritma atuan asosiasi. 3. Masalah aturan asosiasi berakhir dengan dihasilkannya pengetahuan yang direpresentasikan dalam bentuk diagram yang disebut aturan asosiasi. Data Mining-Aturan Asosiasi-AAB

20

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 • Pengunjung toko unsada yang membeli asparagus mempunyai kecenderungan untuk juga membeli beans • Dan lain-lain. (misalnya…?)


21

Prototip masalah aturan asosiasi dan pengetahuan yang dihasilkan • Dengan adanya prototip ,masalah aturan asosiasi kita dapat mengetahui definisi masalah aturan asosiasi • Dengan pembahasan interpretasi pengetahuan yang dihasilkan oleh fungsi mayor aturan asosiasi, kita bisa mengetahui cara memaknai pengetahuan yang dihasilkan dari masalah ini. Data Mining-Aturan Asosiasi-AAB

22

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 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….” Data Mining-Aturan Asosiasi-AAB

23

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 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) Data Mining-Aturan Asosiasi-AAB

24

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% 2. Langkah kedua Menyusun semua itemset sering, yaitu itemset yang memiliki frekuensi itemset minimal sebesar bilangan Φ = 4 yang telah ditetapkan di langkah pertama. Data Mining-Aturan Asosiasi-AAB

25

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 sebagai berikut: F1 ={{asparagus}, {beans}, {brocolli}, {corn}, {green peppers}, {squash} {tomatoes}}


26

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, 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}


27

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 : F2 = {{asparagus, beans}, {asparagus, squash}, {bean, corn}, {bean, squash}, {bean, tomatoes}, {brocolli, greenpepper}, {corn, tomatoes} } Data Mining-Aturan Asosiasi-AAB

28

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” Aturan ini disebut aturan apriori


29

Langkah dalam MBA-2 (lanj) Penggunaan aturan apriori Bila {asparagus, brocolli} bukan 2-itemset sering, maka menurut aturan apriori: {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. Data Mining-Aturan Asosiasi-AAB

30

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, squash}} Selanjutnya akan diperoleh F4=F5=F6=F7= ø

Singkatnya akan menghasilkan himpunan itemset sering F1, F2, F3 Data Mining-Aturan Asosiasi-AAB

31

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 F2, F3 dan seterusnya, daftarkan semua himpunan bagian murni yang tak kosong dari s sebutlah ss. Sehingga…..


32

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} 3. Untuk s = {beans,corn} didapatkan ss = {beans} atau ss = {corn} 4. Untuk s = {beans,squash} didapatkan ss = {beans} atau ss = {squash} Data Mining-Aturan Asosiasi-AAB

33

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 = {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} Data Mining-Aturan Asosiasi-AAB

34

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 item saja. Sehingga masalah toko unsada didapatkan calon aturan asosiasi pada tabel berikut.


35

Langkah dalam MBA-3 (lanj)

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 Data Mining-Aturan Asosiasi-AAB

36

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 bawah


37

Langkah dalam MBA-3 (lanj)


38

Capeeknya habis ngitung gituan…bobok dulu ah


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 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%


40

Langkah selanjutnya? • Berdasarkan data tersebut bisa dilakukan penataan barang berdasarkan yang banyak dibeli • Pemberian discount pada hari tertentu • Dll • Dll • Stok asparagus dan beans diperbanyak sesuai permintaan pembelian salah satu barang Data Mining-Aturan Asosiasi-AAB

41

Algoritma lain? • Market basket Analysis bukan satu-satunya algoritma untuk mengetahui asosiasi • Terdapat algoritma lain untuk keperluan yang sama misalnya: - algoritma Generalized Association Rules - Algoritma Quantitative Association rule - Algoritma Asynchronous Parallel Mining Data Mining-Aturan Asosiasi-AAB

42

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 mengamati kapan saja mereka main ke sini. Dan data pengamatan saya , saya buatkan tabel sebagai berikut


43

• Dengan data di atas perkirakan kapan rombongan sirkus tersebut show atau tidak di desa saya. Data Mining-Aturan Asosiasi-AAB

44

• selamat mengerjakan


45

referensi


46

Data Mining III Asosiasi

Recommend Documents