ANALISA ASOSIASI & ANALISA CLUSTER

PERTEMUAN 6

ANALISA ASOSIASICoba analisa tabel pembelian berikut:

Id_Trans Id_Cust Tanggal Item Jumlah

111 201 5/1/2016 Pena 2

111 201 5/1/2016 Tinta 1

111 201 5/1/2016 Susu 3

111 201 5/1/2016 Jus 6

112 105 6/3/2016 Pena 1

112 105 6/3/2016 Tinta 1

112 105 6/3/2016 Susu 1

113 106 5/10/2016 Pena 1

113 106 5/10/2016 Susu 2

114 201 6/1/2016 Pena 2

114 201 6/1/2016 Tinta 2

114 201 6/1/2016 Jus 4

114 201 6/1/2016 Air 1

Frequent ItemsetDari tabel relasi pada slide sebelumnya yang disusun terurut dalamkelompok-kelompok berdasarkan transaksi. Semua record dalam satukelompok mempunyai id_trans yang sama. Jika diamati adaredundancy pada tabel pembelian tersebut, yaitu dapat dipecahdengan menyimpan triple (id_trans, id_cust, tanggal) dalam sebuahtabel yang terpisah dan menghapus id_cust, dan tanggal dari tabelpembelian. Meskipun demikian, akan lebih mudah menggunakan tabelpembelian sebelumnya untuk menghitung frequent itemset.Pembuatan tabel ‘denormalized’ untuk mempermudah data miningbiasanya dilakukan pada tahap data cleaning dari proses KDD.

Untuk mempermudah analisa asosiasi antar item dalam sebuahtransaksi, data pada tabel pembelian tersebut dapat dinyatakan dalamsebuah tabel representasi biner sebagai berikut:

Representasi biner dari tabel transaksi

Misalkan I={i1,i2,i3,...,id} adalah himpunan dari semua item dalam keranjangbelanja dan T={t1,t2,...,tN} merupakan himpunan dari semua transaksi. Tiaptransaksi ti, berisi sebuah subhimpunan item-item yang dipilih dari I. Dalamanalisa asosiasi, suatu himpunan satu atau lebih item disebut satu itemset. Jika sebuah itemset berisi k-items maka disebut dengan ‘k-itemset’. Sebagaicontoh, {pena,tinta} merupakan sebuah 2-itemset.

Id_Trans Pena Tinta Susu Jus Air

111 1 1 1 1 0

112 1 1 1 0 0

113 1 0 1 0 0

114 1 1 0 1 1

Frequent Itemset (Lanjutan)

Lebar transaksi didefinisikan sebagai jumlah item yang terdapat dalamsebuah transaksi. Suatu transaksi tj dikatakan berisi sebuah itemset X jika X merupakan subset dari tj. Contohnya, transaksi pertama pada tabelsebelumnya berisi itemset {Pena,Tinta} dan bukan {Pena,Air}

Support count � merupakan jumlah transaksi yang berisi suatu itemsettertentu atau dengan kata lain merupakan frekuensi kejadian dari suatuitemset. Support dari suatu itemset adalah perbandingan dari transaksidalam basis data yang berisi semua item dalam itemset. Dalam contohsebelumnya, itemset {pena,tinta} memiliki support 75% dalam tabelpembelian. Kita dapat menyimpulkan bahwa pena dan tinta sering munculbersamaan. Jika kita perhatikan itemset {susu,jus}, support-nya hanya 25%, susu dan jus tidak sering dibeli bersamaan.

Frequent Itemset (Lanjutan)

Association Rule

Association rule merupakan sebuah ekspresi implikasi yang berbentuk X Y, dimana X dan Y merupakan disjoint itemset � ∩ � = ∅. Contoh: {Pena, Tinta} {Jus}. Dalam association rule, dapat dihitung support dan confidence.

Confidence menyatakan seberapa sering item-item dalam Y muncul dalam transaksi yang berisi X. Secara formal dapat dinyatakan dengan persamaan:

� � → � = (�∪�)

�� � → � =

(�∪�)

(�)

Dimana s adalah support dan c adalah confidence

Association Rule (Lanjutan)

Contoh: untuk association rule {Pena, Tinta}{Jus}, maka:

� � → � =�( ����, �����, ��� )

4=

2

4= 0.5

� � → � =�( ����, �����, ��� )

�( ����, ����� )=

2

3= 0.67

Association Rule Mining

Jika terdapat sebuah himpunan transaksi T, maka tujuan dari association rule mining adalah untuk menemukan semua aturan yang mempunyai support >=minsup dan confidence >=minconf.

Pendekatan brute-force untuk association rule mining menggunakan pendekatan dengan menghitung support dan confidence dari semua kemungkinan rule. Pendekatan Brute-force terdiri dari langkah-langkah berikut:

Daftar semua kemungkinan association rules

Hitung support dan confidence untuk setiap rule

Pangkas rule yang tidak memenuhi minsup dan minconf thresholds

Association Rule Mining (Lanjutan)

Secara umum, pendekatan ini sangat mahal dalam waktu komputasinya. Jumlah kemungkinan rule dari sebuah tabel transaksi yang terdiri dari d item adalah sebesar:

$ = 3% − 2%'( + 1

Misalkan digunakan data pada tabel pembelan sebelumnya dengan jumlah item d=5, maka jumlah kemungkinan rule adalah sebesar:

$ = 3+ − 2, + 1 = 243 − 64 + 1 = 180

Association Rule Mining (Lanjutan)Contoh: jika diketahui sebuah transaksi sbb:

Maka support dan confidence dari association rule sebagai berikut:

{Milk,Diaper}{Beer} (s=0.4,c=0.67)

{Milk,Beer} {Diaper} (s=0.4,c=1.0)

{Diaper,Beer} {Milk} (s=0.4,c=0.67)

{Beer} {Milk,Diaper} (s=0.4,c=0.67)

{Diaper} {Milk,Beer} (s=0.4,c=0.5)

{Milk} {Diaper,Beer} (s=0.4,c=0.5)

Id_trans Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke

4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

Association Rule Mining (Lanjutan)

Semua rule tersebut merupakan partisi biner dari itemset yang sama: {Milk, Diaper, Beer}. Rules yang berasal dari itemset yang samamempunyai support yang identik tetapi mempunyai confidence yang berbeda, sehingga dapat dipasangkan ulang untuk keperluan support

dan confidence.

Analisa Cluster

Analisa cluster yaitu menemukan kumpulan objek hingga objek-objekdalam satu kelompok sama (atau punya hubungan) dengan yang lain danberbeda (atau tidak berhubungan) dengan objek-objek dalam kelompoklain. Tujuan dari analisa cluster adalah meminimalkan jarak didalamcluster dan memaksimalkan jarak antar cluster.

Aplikasi dari analisa cluster dibedakan menjadi dua, yaitu:

Understanding, antara lain kelompok dokumen-dokumen yang salingberhubungan untuk proses browsing, pengelompokan gen dan protein yang mempunyai fungsi sama atau pengelompokan stok dengan hargayang fluktuatif

Summerization, untuk menurunkan ukuran dari dataset yang besar

Analisa Cluster (Lanjutan)

Yang bukan termasuk cluster analisis adalah:

Supervised classification, yang mempunyai informasi label kelas

Simple segmentation, misalkan membagi siswa kedalam kelompokberdasarkan urutan nama

Hasil dari sebuah query yang pengelompokannya merupakan hasil darispesifikasi eksternal

Graph partitioning, dimana dalam graph beberapa mempunyaihubungan relevansi dan sinergi tetapi areanya tidak identik

Tipe Clustering

Clustering merupakan suatu kumpulan dari keseluruhan cluster. Beberapa tipe penting dari clustering adalah:

Partitional vs Hierarchical

Partitional clustering adalah pembagian objek data kedalamsubhimpunan (cluster) yang tidak overlap sedemikian hingga tiap objekdata berada dalam tepat satu sub himpunan.

Tipe Clustering (Lanjutan)

Hierarchical clustering merupakan sebuah himpunan cluster bersarangyang diatur sebagai suatu pohon hirarki. Tiap simpul (cluster) dalampohon (kecuali simpul daun) merupakan gabungan dari anaknya(subcluster) dan simpul akar berisi semua objek

Tipe Clustering (Lanjutan)

Exclusive vs non-exclusive

Exclusive cluster jika setiap objek berada tepat disatu cluster, sebaliknyadalam overlapping atau non-exclusive clustering sebuah objek dapat beradadilebih dari satu cluster secara bersamaan

Fuzzy vs non-fuzzy

Dalam fuzzyclustering, sebuah titik termasuk dalam setiap cluster dengansuatu nilai bobot antara 0 dan 1. Jumlah dari bobot-bobot tersebut samadengan 1. Clustering probabilitas mempunyai karakteristik yang sama

Partial vs complete

Dalam completeclustering, setiap objek ditempatkan dalam sebuah cluster. Tetapi dalam partial clustering, tidak semua objek ditempatkan dalamsebuah cluster. Kemungkinan ada objek yang tidak tepat untuk ditempatkandisalah satu cluster, misalkan berupa outlier atau noise.

Tipe-tipe clusterClustering bertujuan menemukan kelompok (cluster) objek yang berguna, dimana penggunaannya tergantung dari tujuan analisa data. Secara visual ada beberapa tipe dari cluster, diantaranya:

• Well-separated clusters: sebuah cluster merupakan himpunan titiksedemikian rupa hingga tidak ada titik dalam sebuah cluster yang mendekati (atau lebih mirip) ke setiap titik lain dalam cluster yang tidak ditempati titik tersebut.

Tipe-tipe cluster (Lanjutan)

• Center-based: sebuah cluster adalah himpunan dari objek-objeksedemikian rupa hingga sebuah objek dalam sebuah cluster mendekati (lebih mirip) dengan ‘pusat’ dari sebuah cluster dibandingkan dengan pusat cluster lain. Pusat dari sebuah cluster dapat berupa centroid, yaitu rata-rata dari semua titik dalam cluster tersebut, atau medoid, merupakan representasi titik dari sebuahcluster.

Tipe-tipe cluster (Lanjutan)

• Contiguous cluster (Nearest neighbor atau transitive), dimana sebuah cluster merupakan himpunan titik sedemikian hingga sebuah titik dalam cluster mendekati (atau lebih serupa) dengan satu atau lebih titik lain dalam cluster tersebut dibandingkan dengan titik yang tidak berada pada cluster tersebut.

• Density-based, dimana sebuah cluster merupakan suatu daerah titik yang padat, yang dipisahkan oleh daerah kepadatan rendah (low-density), dari daerahkepadatan tinggi (high-density) yang lain. Digunakan ketika cluster-cluster tidakberaturan atau terjalin dan ketika terdapat noise dan outlier

Tipe-tipe cluster (Lanjutan)• Shared Property atau conceptualclusters, menemukan cluster-cluster yang membagi beberapa

sifat umumnya atau menyatakan konsep tertentu.

Menghitung semua kemungkinan cara untuk membagi titik-titik kedalam cluster dan men-evaluasimempunyai tujuan global dan local

Algoritma clustering hierarchical mempunyai local objectives

Algoritma partitional mempunyai global obectives

Variasi dari pendekatan fungsi objektif global adalah menyusun data menjadi sebuah model yang terukur (parameterized)

Parameter-parameter untuk model tersebut ditentukan dari data

Model campuran (mixture model) mengasumsikan bahwa data merupakan suatu campuranbilangan yang terdistribusi secara statistik

Algoritma clustering

K-Means clustering

Menggunakan pendekatan partitional clustering. Tiap cluster

dihubungkan sebuah centroid (titik pusat). Tiap titik ditempatkan kedalam cluster dengan centroid terdekat. Jumlah cluster, K, harus ditentukan. Algoritma dasarnya sangat sangat sederhana, yaitu:

1. Pilih K titik sebagai centroid awal

2. Ulangi

3. Bentuk K cluster dengan menempatkan semua titik yang terdekat

4. Ulangi perhitungan centroid dari tiap cluster

5. Sampai centroid tidak berubah

Contoh soal K-Means clustering

Misalkan data X={2,3,4,10,11,12,20,25,35} akan dibagi dalam dua cluster (k=2), dipilih dua initial centroid yaitu 1=2 dan 2=4 dan menggunakan ukuran city-block distance. Hitung distance setiap xX dengan city-block

1. Iterasi 1:

Diperoleh: cluster1 (C1)={2,3}

cluster2 (C2)={4,10,11,12,20,25,35}

X 2 3 4 10 11 12 20 25 35

(x,1) 0 1 2 8 9 10 18 23 33

(x,2) 2 1 0 6 7 8 16 21 31

Min((x,1), (x,2) C1 C1 C2 C2 C2 C2 C2 C2 C2

Contoh soal K-Means clustering (Lanjutan)

Perhitungan centroid baru:

.(/ =

0'1

0=

+

0=2.5

.0/ =

4 + 10 + 11 + 12 + 20 + 25 + 35

7=

112

7= 16

2. Iterasi 2

Diperoleh: cluster1 (C1)={2,3,4}

cluster2 (C2)={10,11,12,20,25,35}

X 2 3 4 10 11 12 20 25 35

(x,1)=(x,2.5) 0.5 0.5 1.5 7.5 8.5 9.5 17.5 22.5 32.5

(x,2)=(x,16) 14 13 12 6 5 4 4 9 19

Min((x,1), (x,2) C1 C1 C1 C2 C2 C2 C2 C2 C2

Contoh soal K-Means clustering (Lanjutan)

Perhitungan centroid baru:

.(/ =

0'1'2

1=

3

1=3

.0/ =

10 + 11 + 12 + 20 + 25 + 35

6=

108

6= 18

3. Iterasi 3

Diperoleh: cluster1 (C1)={2,3,4,10}

cluster2 (C2)={11,12,20,25,35}

X 2 3 4 10 11 12 20 25 35

(x,1)=(x,3) 1 0 1 7 8 9 17 22 32

(x,2)=(x,18) 16 15 14 8 7 6 2 7 17

Min((x,1), (x,2) C1 C1 C1 C1 C2 C2 C2 C2 C2

Contoh soal K-Means clustering (Lanjutan)Perhitungan centroid baru:

.(/ =

0'1'2'(4

2=

(3

2=4.75

.0/ =

11 + 12 + 20 + 25 + 35

5=

98

5= 19.6

Proses iterasi berhenti jika baru = lama atau dengan kata lain elemen dalam sebuah cluster tidak berubah

Perhatikan tabel berikut:

1. Dari tabel diatas, support count untuk itemset [roti, keju, susu] adalah

A. 0%

B. 25%

C. 50%

D. 75%

E. 100%

Id_Trans Roti Keju Susu Jus Air

111 1 1 0 0 0

112 1 0 1 0 0

113 1 1 1 0 0

114 1 1 1 1 1

Soal Latihan Pertemuan 6

Perhatikan tabel berikut:

1. Dari tabel diatas, support count untuk itemset [roti, keju, susu] adalah

A. 0%

B. 25%

C. 50%

D. 75%

E. 100%

Id_Trans Roti Keju Susu Jus Air

111 1 1 0 0 0

112 1 0 1 0 0

113 1 1 1 0 0

114 1 1 1 1 1

Soal Latihan Pertemuan 6

Perhatikan tabel berikut:

2. Dari tabel diatas, support count untuk itemset [roti, keju] adalah

A. 0%

B. 25%

C. 50%

D. 75%

E. 100%

Id_Trans Roti Keju Susu Jus Air

111 1 1 0 0 0

112 1 0 1 0 0

113 1 1 1 0 0

114 1 1 1 1 1

Soal Latihan Pertemuan 6 (Lanjutan)

Perhatikan tabel berikut:

2. Dari tabel diatas, support count untuk itemset [roti, keju] adalah

A. 0%

B. 25%

C. 50%

D. 75%

E. 100%

Id_Trans Roti Keju Susu Jus Air

111 1 1 0 0 0

112 1 0 1 0 0

113 1 1 1 0 0

114 1 1 1 1 1

Soal Latihan Pertemuan 6 (Lanjutan)

3. Gambar disamping merupakan clustering dengan tipe

A. partition

B. hierarchical

C. exclusive

D. fuzzy

E. partial

4. Tidak ada titik dalam sebuah cluster yang lebih mirip, hal ini dapatdikategorikan dalam tipe cluster

A. shared property

B. density based

C. contiguous cluster

D. center based

E. well-separated cluster

Soal Latihan Pertemuan 6 (Lanjutan)

3. Gambar disamping merupakan clustering dengan tipe

A. partition

B. hierarchical

C. exclusive

D. fuzzy

E. partial

4. Tidak ada titik dalam sebuah cluster yang lebih mirip, hal ini dapatdikategorikan dalam tipe cluster

A. shared property

B. density based

C. contiguous cluster

D. center based

E. well-separated cluster

Soal Latihan Pertemuan 6 (Lanjutan)

4. Tidak ada titik dalam sebuah cluster yang lebih mirip kesetiap titik lain dalam cluster yang tidak ditempati titik tersebut, hal ini dapat dikategorikan dalam tipe cluster

A. shared property

B. density based

C. contiguous cluster

D. center based

E. well-separated cluster

5. Ketika terdapat noise dan outlier, tipe dari cluster berupa

A. shared property

B. density based

C. contiguous cluster

D. center based

E. well-separated cluster

Soal Latihan Pertemuan 6 (Lanjutan)

5. Ketika terdapat noise dan outlier, tipe dari cluster berupa

A. shared property

B. density based

C. contiguous cluster

D. center based

E. well-separated cluster

Soal Latihan Pertemuan 6 (Lanjutan)

Perhatikan tabel berikut:

1. Dari tabel diatas, support count untuk itemset [roti, keju, susu] adalah

A. 0%

B. 25%

C. 50%

D. 75%

E. 100%

Id_Trans Roti Keju Susu Jus Air

111 1 1 0 0 0

112 1 0 1 0 0

113 1 1 1 0 0

114 1 1 1 1 1

Soal Latihan Pertemuan 6