Link Analysis (Superset) 3 Kategori Link Analysis (#1) 3 Kategori Link Analysis (#2) Association Rule Mining. 3 Kategori Link Analysis (#3)

Knowledge Discovery in Databases (IS704) dan Data Mining (CS704)

Link Analysis (Superset) Š Tujuan: Mencari hubungan antara atribut-atribut suatu database. Š Dibandingkan dengan operasi-operasi data mining lainnya, link analysis lebih sering dipakai karena informasi yang dihasilkan lebih sederhana dan dapat diterapkan langsung untuk pengambilan keputusan bisnis dibanding dengan operasi data mining lain yang cenderung membutuhkan analisis lanjut.

Kuliah #7: Association Rules Mining (Bagian 1)

Gunawan Jurusan Teknik Informatika Sekolah Tinggi Teknik Surabaya

14 December 2005

3 Kategori Link Analysis (#1)

Gunawan, Teknik Informatika STTS

2

3 Kategori Link Analysis (#2)

Š Association Discovery (Market Basket Analysis): Menganalisis barang-barang yang dibeli secara bersamaan pada suatu transaksi, sehingga ditemukan hubungan yang mungkin tersembunyi di antara barang-barang tersebut.

14 December 2005

Gunawan, Teknik Informatika STTS

Š Sequential Pattern Discovery: Mengidentifikasi hubungan antara transaksi pembelian barang dari waktu ke waktu untuk mendapatkan informasi mengenai urutan barang yang dibeli customer. Tujuannya adalah mengenali kebiasaan customer dalam jangka waktu tertentu.

3

–

Sequential pattern mining adalah pencarian pattern yang terjadi cukup sering sehubungan dengan waktu atau sequence lainnya.

–

Contoh: "Customer yang membeli pentium PC sembilan bulan yang lalu cenderung untuk memesan CPU baru dalam satu bulan ini".

–

Sequential pattern mining berguna dalam analisa data untuk marketing atau ramalan cuaca.

14 December 2005

Gunawan, Teknik Informatika STTS

4

Association Rule Mining 3 Kategori Link Analysis (#3)

Š Motivasi awal pencarian association rule berasal dari keinginan untuk menganalisa data transaksi supermarket, ditinjau dari perilaku customer dalam membeli produk. Š Association rule ini menjelaskan seberapa sering suatu produk dibeli secara bersamaan. Sebagai contoh, association rule “beer ⇒ diaper (80%)” menunjukkan bahwa empat dari lima customer yang membeli beer juga membeli diaper. Š Dalam suatu association rule X ⇒ Y, X disebut dengan antecedent dan Y disebut dengan consequent. Š Rule seperti ini sangat berguna untuk mengambil keputusan yang berhubungan dengan promosi, penetapan harga suatu produk atau penataan produk dalam rak.

Š Similar Time Sequence Discovery: Menemukan hubungan antara dua kelompok data yang bergantung pada waktu, berdasarkan tingkat kemiripan pola yang ditunjukkan data tersebut. Š Jadi tujuannya mencari kemunculan semua sequence yang mirip dengan sequence yang diberikan, dalam suatu time-series database. – Tidak seperti query database pada umumnya yang mencari data

sama persis seperti yang diberikan dalam query, similarity search mencari data sequence yang mempunyai perbedaan kecil dari query yang diberikan. 14 December 2005

Gunawan, Teknik Informatika STTS

5

14 December 2005

Gunawan, Teknik Informatika STTS

6

1

Contoh Manfaat AR

Ukuran Ketertarikan suatu Rule

Š Rule yang mengandung y sebagai consequent dapat membantu merencanakan apa yang harus dilakukan oleh suatu toko untuk meningkatkan penjualan y. Š Rule yang mengandung x sebagai antecedent dapat digunakan untuk membantu menentukan barang-barang apa saja yang terpengaruh apabila toko tersebut memutuskan untuk berhenti menjual x. Š Rule yang mengandung x sebagai antecedent dan y sebagai consequent dapat digunakan untuk menentukan produk lainnya yang harus dijual bersama dengan x untuk meningkatkan penjualan y. Š Rule yang berhubungan dengan barang yang terdapat pada rak A dan rak B pada suatu toko dapat membantu merencanakan pengaturan barang pada rak dengan menentukan bahwa penjualan barang di rak A berhubungan dengan penjualan barang di rak B.

Š Pengukuran ketertarikan pada suatu rule dapat dilakukan secara subyektif atau obyektif. Š Pengukuran secara obyektif dapat membantu identifikasi interesting rules, tetapi hal ini masih belum cukup jika tidak dikombinasikan dengan pengukuran secara subyektif yang mencerminkan keinginan dan kebutuhan user tertentu. Š Pengukuran secara objektif dapat dilakukan dengan menggunakan nilai minimum support threshold dan minimum confidence threshold, sedangkan pengukuran secara subyektif pada dasarnya kasuistis untuk setiap user, sehingga hal ini dapat berbeda untuk setiap user.

14 December 2005

Gunawan, Teknik Informatika STTS

7

14 December 2005

Gunawan, Teknik Informatika STTS

8

Contoh Input dan Output AR Mining

Rule Support & Rule Confidence

Š Input: Database Transaksi Pembelian oleh Customer

Š Rule Support dan Rule Confidence adalah 2 ukuran ketertarikan pemakai AR Mining: Š Contoh: computer => financial_management_software [support = 2%, confidence = 60%]

Š Untuk 2% dari semua transaksi komputer dan financial_management_software dibeli secara bersama- sama. Š 60% dari pelanggan yang membeli komputer juga membeli financial_management_software. 14 December 2005

Gunawan, Teknik Informatika STTS

Constraints: Minimum Support = 40% Minimum Confidence = 75%

9

14 December 2005

Output: Strong Association Rules • {beer} => {diaper}, [confidence = 100%, support = 60%] • {diaper} => {beer}, [confidence = 75%, support = 60%] • {coke} => {diaper}, [confidence = 100%, support = 40%] • {coke} => {milk}, [confidence = 100%, support = 40%] • {beer, bread} => {diaper}, [confidence = 100%, support = 40%] • {beer, milk} => {diaper}, [confidence = 100%, support = 40%] • {coke, diaper} => {milk}, [confidence = 100%, support = 40%] • {coke, milk} => {diaper}, [confidence = 100%, support = 40%] • {coke} => {diaper, milk}, [confidence = 100%, support = 40%]

Gunawan, Teknik Informatika STTS

10

2 (Dua) Proses Utama AR Mining (#1)

Blok Sistem AR Mining

Š Permasalahan untuk menemukan seluruh association rule yang ada pada suatu database dapat dibagi menjadi dua fase utama berikut: – Fase Pencarian Large Itemset: Menemukan seluruh item dari

transaksi yang memenuhi minimum support threshold. Support untuk suatu itemset adalah jumlah transaksi dalam database yang mengandung itemset tersebut. Itemset yang memenuhi persyaratan ini disebut frequent itemset (large itemset) dan sebaliknya infrequent itemset (small itemset). – Fase Generate Strong Association Rules: Dengan menggunakan frequent itemset yang terbentuk dihasilkan (strong) association rules yang memenuhi minimum confidence threshold yang telah dispesifikasikan.

14 December 2005

Gunawan, Teknik Informatika STTS

11

14 December 2005

Gunawan, Teknik Informatika STTS

12

2

Contoh Input, Frequent Itemset & Output

2 (Dua) Proses Utama AR Mining (#2) Š Kebanyakan dari algoritma yang ada saat ini menggunakan pendekatan dengan dua fase di atas untuk menyelesaikan permasalahan association rule mining. Walaupun tidak menutup kemungkinan adanya algoritma lain yang berhasil menemukan seluruh association rule yang ada, tanpa harus membagi proses ke dalam dua tahap tersebut. – Contoh: Algoritma Opus dengan versi komersialnya disebut Magnum

Opus. – Algoritma ini menggunakan strategi lain untuk menghasilkan secara

langsung frequent subset dari seluruh association rule.

Š Hampir semua varian Algoritma AR Mining berupaya meningkatkan efisiensi (baca: speed dan memory usage) fase Pencarian Large Itemset. Š Fase Additional Interesting Measure yang optional dapat dilakukan misalnya dengan memfilter semua Strong Association Rules yang diperoleh pada tahap II dengan memanfaatkan pengukuran correlation, sehingga yang dihasilkan benar-benar sekumpulan Interesting Association Rules. 14 December 2005

Gunawan, Teknik Informatika STTS

13

Klasifikasi Association Rule Mining Š

• • •

Gunawan, Teknik Informatika STTS

14

Berdasar Tipe Nilai yang dapat Ditangani Rule

Association rule dapat diklasifikasikan dalam beberapa cara berdasarkan sejumlah kriteria: •

14 December 2005

Š Boolean Association Rule: Jika suatu rule hanya menangani ada tidaknya hubungan antar item.

Berdasar tipe nilai yang dapat ditangani rule (Boolean vs. Quantitative). Berdasar dimensi dari data yang ada pada rule (Single Dimensional vs. Multidimensional). Berdasar level abstraksi yang ada pada rule (Single Level vs. Multilevel). Berdasar pengembangan selanjutnya (baik dari perspektif modifikasi algoritma untuk meningkatkan efisiensi algoritma, ataupun dari perspektif pemanfaatannya, termasuk penggabungan dengan data mining tasks lainnya).

– Contoh: computer ⇒ financial_management_software – atau dapat ditulis: buys(X, “computer”) ⇒ buys(X, “financial_

management_software”)

Š Quantitative Association Rule: bila rule tersebut dapat menunjukkan hubungan antar item atau atribut secara kuantitatif. – Contoh: age(X, “30..39”) ∧ income(X, “42K..48K”) ⇒ buys(X,

high resolution TV) – Pada contoh ini atribut age dan income telah mengalami

diskretisasi. 14 December 2005

Gunawan, Teknik Informatika STTS

15

14 December 2005

Gunawan, Teknik Informatika STTS

16

Contoh Quantitative AR

“Hubungan” sebagai Tabel Boolean pada Boolean Association Rules Š Karena Boolean Association Rule adalah association rule yang hanya memperhatikan hubungan antara ada atau tidaknya suatu item dalam transaksi, maka secara konsepsi, hal ini dapat dipandang sebagai pencarian hubungan antara nilai “1” dalam sebuah tabel yang semua atributnya adalah boolean. Š Tabel tersebut mempunyai atribut yang sesuai dengan setiap item dan record yang sesuai dengan transaksi. Š Atribut dari sebuah record bernilai “1” jika item yang sesuaian dengan atribut tersebut terdapat dalam transaksi yang sesuai dengan record tersebut, dan bernilai “0” jika sebaliknya. Š Contoh: Tunjukkan tabel Boolean ini pada sebuah dataset transaksi.

14 December 2005

Gunawan, Teknik Informatika STTS

17

14 December 2005

Gunawan, Teknik Informatika STTS

18

3

Berdasar Dimensi Data yang Terdapat pada Rule: Multidimensional AR

Berdasar Dimensi Data yang Terdapat pada Rule: Single Dimensional AR Š Single Dimensional Association Rule: bila item atau atribut dalam rule hanya melibatkan satu dimensi saja. Š Contoh: buys(X, “IBM desktop computer”) ⇒ buys(X, “Sony B/W Printer”) Š Disebut juga Intradimension Association Rule, karena hanya terdiri dari satu buah predikat (buys) dengan beberapa pengulangan (predikat digunakan lebih dari satu kali dalam sebuah rule). 14 December 2005

Gunawan, Teknik Informatika STTS

19

Š Multidimensional Association Rule: bila association rule melibatkan dua atau lebih predikat. Š Predikat dapat berupa: – Attribute (dari database atau dataset) – Dimensi (dari sebuah datawarehouse)

Š Contoh: age(X, “20…29”) ∧ occupation(X, “student”) ⇒ buys(X, “laptop”). Š 2 kategori Multidimensional Association Rule: – Interdimension Association Rule: jika tanpa predikat yang

diulang, seperti contoh di atas (3 dimensi masing-masing: age, occupation, dan buys). – Hybrid-dimension Association Rule: jika terdapat satu atau

lebih predikat yang diulang, contoh: age(X, “20…29”) ∧ buys(X, “laptop”) ⇒ buys(X, “b/w printer”).

14 December 2005

Gunawan, Teknik Informatika STTS

Konsep Hirarki

Berdasar Level Abstraksi yang Terdapat pada Rule Š Konsep Hirarki mendefinisikan sebuah urutan pemetaan dari konsep dengan level yang rendah menuju ke level yang lebih tinggi, yaitu konsep yang lebih umum. Š Data dapat digeneralisasi dengan menggantikan konsep yang lebih rendah dengan konsep yang lebih tinggi, atau ancestor, pada sebuah konsep hirarki. Š Konsep hirarki pada gambar berikut terdiri dari empat level, yaitu level 0, 1, 2 dan 3. Level dalam konsep hirarki dihitung mulai dari atas ke bawah, dimulai dari level 0 pada root, yang merupakan level abstraksi yang paling umum. Š Association Rule Mining harus dapat menyediakan kemampuan untuk melakukan ekstraksi association rule pada level abstraksi yang berbeda. 14 December 2005

Gunawan, Teknik Informatika STTS

21

Berdasar Level Abstraksi yang Terdapat pada Rule

…

14 December 2005

… …

… …

…

… …

Gunawan, Teknik Informatika STTS

22

Berdasar Pengembangan Selanjutnya (1) – – –

buys(X, “Toshiba Desktop Tipe X”) ⇒ buys(X, “Sony B/W Printer Tipe Y”).

FP-Tree Eclat Top-Down

Š Peningkatan performansi algoritma Apriori dengan memanfaatkan struktur data lainnya, seperti: – – – –

Š Multilevel Association Rule: jika rule melibatkan item-item pada level abstraksi yang berbeda. – Lebih “mudah” untuk menemukan interesting association antara item-item pada beberapa level yang berbeda daripada antara item-item dengan level yang rendah. Contoh: buys(X, “computer”) ⇒ buys(X, “software”). – Cross Level Association Rule: jika rule diperoleh dari level yang berbeda. Contoh: “buys(X, computer) ⇒ buys(X, “B/W Printer”). Computer pada level 1 dan B/W Printer pada level 2. Gunawan, Teknik Informatika STTS

… …

Š Meningkatkan efisiensi mining dengan konstruksi struktur data khusus seperti Frequent Pattern Growth (FP-Growth):

Š Single Level Association Rule: jika rule tidak mengacu pada itemitem atau atribut-atribut pada level abstraksi yang berbeda. Contoh:

14 December 2005

20

Hash-Table Prefix-Tree Patricia Tree FP-Tree

Š Peningkatan performansi algoritma Apriori: – – – –

23

DHP (memperkecil ukuran candidate set) DIC dan Partitioning (menggabungkan proses pencarian frequent k-itemset). TFP dan LPMiner (menggunakan Nilai Rule Support yang Dinamik) ExaMiner dan FICM (mengatasi ditambahkannya sejumlah constraint). Lihat latihan 6.15)

14 December 2005

Gunawan, Teknik Informatika STTS

24

4

Berdasar Pengembangan Selanjutnya (2) Š Pemanfaatan algoritma association rule untuk klasifikasi e-mail: COMAR. Š Integrasi association rules mining dan classification rules mining, misalnya untuk membentuk classifier yang akurat: – – – – –

CARs (Class Association Rules) CBA (Classification Based on Association) FOIL (First Order Inductive Learner) PRM (Predictive Rule Mining) CPAR (Classification based on Predictive Association Rules).

Š Pemanfaatan algoritma association rule mining untuk clustering dokumen: – – –

FTC (Frequent Term-Based Clustering) HFTC (Hierarchical Frequent Term-Based Clustering) FIHC (Frequent Itemset Based Clustering)

Š Pemanfaatan algoritma association rule mining untuk Pemberian Rekomandasi: AR-CRS (Association Rules for Collaborative Recomender System): AR-CRS1 dan AR-CRS2. Š Hari ini diyakini terdapat ratusan pengembangan AR Mining lainnya dari berbagai perspektif yang berbeda. 14 December 2005

Gunawan, Teknik Informatika STTS

25

5