STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Data Mining
Dicky Nofriansyah, S.Kom., M.Kom
Materi : Clustering Hierarki
Algoritmatif
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Metode-Metode Terkait Pengelompokan Hierarki AglomeratifKunci operasi metode AHC (Algoritma Hierarki Cluster)
adalah penggunaan ukuran kedekatan (proximity) diantara dua kelompok” (Hartini dalam Prasetyo, 2012 : 214). Ada tiga tehnik kedekatan yang dijelaskan disini:
Single Linkage Complete Linkage
Average Linkage
STMIK TRIGUNA DHARMA
• Jarak Terdekat atauTautan tunggal memberikan hasil bila kelompok-kelompok digabungkan menurut jarak antara anggota-anggota yang terdekat diantara dua kelompok.
Single Linka
ge• Jarak Terjauh atau Tautan lengkap
terjadi bila kelompok-kelompok digabungkan menurut jarak antara anggota-anggota yang terjauh di antara dua kelompok.
Complete
Linkage• Jarak Rata-rata atau Tautan rata-rata
digabungkan menurut jarak rata-rata pasangan-pasangan anggota masing-masing pada himpunan di antara dua kelompok
AverageLinkage
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Tehnik Pengukuran JarakAda beberapa macam ukuran jarak yang biasa dipakai dalam analisis cluster, diantaranya :
Eucladian Distance
Manhattan
Pearson
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
1. Pembentukan kelompok tergantung apakah jarak dari objek kekelompok pertama lebih dekat dibandingkan dengan jarak objek tersebut dengan objek lainnya yang belum terkelompok
Keterangan Rumus : X = Rata-rata data XXi = Data X ke-iN = Banyak data XStd (X) = Standar deviasi data X Zi = Data standar (skor standar) X ke-i
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
2. Menentukan ukuran kemiripan atau ketidakmiripan antar data dengan metode jarak Euclidean
n
dAB = ∑ | x1 - y1 |2
i = 1Keterangan Rumus : dAB = Ukuran kemiripan / ketidakmiripan antara objek ke-x dengan objek ke-y.
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Sampel Kasus:Analisis cluster termasuk dalam analisis multivariat yang mewakili seluruh hubungan interdependensi, tidak ada perbedaan variabel bebas dan variabel tidak bebas (independent and dependent variables) dalam analisis ini. Analisis cluster adalah teknik yang digunakan untuk mengidentifikasi objek atau individu yang serupa dengan memperhatikan beberapa kriteria.
Langkah Pasti Menuju Sukses
No Lagu Waktu Putar
Negara Asal
Genre Musik
1Timmy Thomas - You Are All I Need
05.00 - 05.59 Barat Pop
2Lighthouse Family - Ain't No Sunshine
06.00 - 06.59 Barat AudioPhille
3Cake - I Will Survive 07.00 -
07.59 Barat Pop Mix
4Anggun - Still Reminds Me 08.00 -
08.59 Indonesia Pop
5Aloe Blacc - Hello World 09.00 -
09.59 Barat Pop
6One Direction – Story of My Life 10.00 -
10.59 Barat Pop Mix
7Rihanna - Diamonds 11.00 -
11.59 Barat R & B
8Hayley Westenra - Prayer 12.00 -
12.59 Barat AudioPhille
9Feel Fascinated - Peng You 13.00 -
13.59 Chinese Mandarin
10Lisa Ono - I Feel Good 14.00 -
14.59 Barat Jazz
11James Morrison – I Won't Let You Go
15.00 - 15.59 Barat Pop
12Nidji - Laskar Pelangi 16.00 -
16.59 Indonesia Pop
13Jason Mraz - Im Yours 17.00 -
17.59 Barat Pop
14Titi DJ - Tak Kan Ada Cinta Yang Lain
18.00 - 18.59 Indonesia Pop
15The Beatles - Dont Let Me Down 19.00 -
19.59 Barat Pop
16Diana Krall - All Night Long 20.00 -
20.59 Barat AudioPhille
17Cymande - Brother On The Side 21.00 -
21.59 Barat Jazz
18Maliq&D'essentials - Terdiam 22.00 -
22.59 Indonesia Pop
19Norah Jones - Don't Know Why 23.00 -
23.59 Barat AudioPhille
20Citra Shcolastika 24.00 -
00.59 Indonesia Jazz
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Maka berdasarkan data music playlist diatas terlebih dahulu dikelompokkan sesuai set objek dan variabelnya beserta asumsi nilai yang dipergunakan seperti pada tabel-tabel berikut
Data KategoriLagu Objek
Waktu Putar Variabel 1 (x1)Negara Asal Variabel 2 (x2)Genre Musik Variabel 3 (x3)
Tabel Set Objek Dan Variabel
No Objek Asumsi
1 Timmy Thomas - You Are All I Need A
2 Lighthouse Family - Ain't No Sunshine B3 Cake - I Will Survive C4 Anggun - Still Reminds Me D5 Aloe Blacc - Hello World E6 One Direction – Story of My Life F7 Rihanna - Diamonds G8 Hayley Westenra - Prayer H9 Feel Fascinated - Peng You I
10 Lisa Ono - I Feel Good J11 James Morrison – I Won't Let You Go K13 Jason Mraz - Im Yours M14 Titi DJ - Tak Kan Ada Cinta Yang Lain
N15 The Beatles - Dont Let Me Down O16 Diana Krall - All Night Long P17 Cymande - Brother On The Side Q18 Maliq&D'essentials - Terdiam R19 Norah Jones - Don't Know Why S20 Citra Scholastika T
Tabel Asumsi Objek
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
X1 NilaiPagi (05.00 - 10.59) 1Siang (11.00 - 14.59) 2Sore (15.00 - 18.59) 3Malam (19.00 - 00.59) 4
Tabel Asumsi Waktu Putar Tabel Asumsi Negara Asal
X2Nila
iBarat 1Indonesia 2Chinese 3
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Genre Musik (V3) Nilai
Pop 6AudioPhille 5Pop Mix 4R & B 3Jazz 2Mandarin 1
Tabel Asumsi Genre MusikDalam tabel-tabel diatas dapat dilihat bahwa objek atau lagu dimisalkan dengan huruf (A, B, C, D dan seterusnya) dan variabel dimisalkan dengan kode (x1, x2 dan x3) begitu juga dengan nilai asumsi adalah sebagai perumpamaan, agar mempermudah perhitungan
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Setelah pengelompokkan objek dan variabel nilai, maka langkah selanjutnya adalah melakukan perhitungan sesuai algoritma yang dipilih. Namun untuk menghindari terjadinya kesalahan, terlebih dahulu beberapa tabel asumsi diatas digabungkan menjadi satu tabel yang lebih terperinci seperti berikut ini
Tabel Asumsi Data dan VariabelnyaNo Objek X1 X2 X31 A 1 1 62 B 1 1 53 C 1 1 44 D 1 2 65 E 1 1 66 F 1 1 47 G 2 1 38 H 2 1 59 I 2 3 1
10 J 2 1 211 K 3 1 612 L 3 2 613 M 3 1 614 N 3 2 615 O 4 1 616 P 4 1 517 Q 4 1 218 R 4 2 619 S 4 1 520 T 4 1 2
Langkah Pasti Menuju Sukses
Algoritma Single Linkage Method Dengan Jarak Euclidean Distance1. Menstandarisasi data-data yang terkumpul dalam tabel menggunakan
rumus-rumus yang telah tersedia :a. Mencari rata-rata data dari setiap variabel
STMIK TRIGUNA DHARMA
b. Mencari standar deviasi data dari setiap variabel
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
c. Mencari skor standar (zero standar) dari masing-masing objek setiap variabel.
Objek X1 X2 X3A -1,214 -0,509 0,824B -1,214 -0,509 0,236C -1,214 -0,509 -0,353D -1,214 1,188 0,824E -1,214 -0,509 0,824F -1,214 -0,509 -0,353G -0,405 -0,509 -0,942H -0,405 -0,509 0,236I -0,405 2,884 -2,120J 0,405 1,188 -1,531K 0,405 -0,509 0,824L 0,405 1,188 0,824M 0,405 -0,509 0,824N 0,405 1,188 0,824O 1,214 -0,509 0,824P 1,214 -0,509 0,236Q 1,214 -0,509 -1,531R 1,214 1,188 0,824S 1,214 -0,509 0,236
Tabel Data Music Playlist Standar
Langkah Pasti Menuju Sukses
2. Menentukan ukuran kemiripan atau ketidakmiripan antara data dengan jarak Euclidean distance.
Tabel Matriks Jarak
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
3.Melakukan algoritma pengelompokkan euclidean single linkage clustering, dengan langkah-langkah sebagai berikut :
a.Mencari nilai terkecil dari matriks jarak. ACEFKLMNPQST mempunyai nilai terkecil yakni 0, maka objek ini menjadi satu cluster.
b. Menghitung jarak antar cluster ACEFKLMNPQST dengan objek lainnya.
Langkah Pasti Menuju Sukses
d(ACEFKLMNPQST)B = min {dAB,dCB,dEB,dFB,dKB,dLB,dMB, dNB,dPB,dQB,dSB,dTB} = dAB,dCB,dEB,dFB = 0,589
d(ACEFKLMNPQST)D = min {dAD,dCD,dED,dFD,dKD,dLD,dMD,dND,dPD,dQD,dSD,dTD} = dLD,dND = 1,619
d(ACEFKLMNPQST)G = min {dAG,dCG,dEG,dFG,dKG,dLG,dMG, dNG,dPG,dQG,dSG,dTG} = dCG,dFG = 1,001
d(ACEFKLMNPQST)H = min {dAH,dCH,dEH,dFH,dKH,dLH,dMH, dNH,dPH,dQH,dSH,dTH} = dAH,dCH,dEH,dFH,dKH,dMH = 1,001
d(ACEFKLMNPQST)I = min {dAI,dCI,dEI,dFI,dKI,dLI,dMI,dNI,dPI,dQI,dSI,dTI} = dLI,dNI = 3,493
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
d(ACEFKLMNPQST)J = min{dAJ,dCJ,dEJ,dFJ,dKJ,dLJ,dMJ,dNJ,dPJ,dQJ,dSJ,dTJ} = dQJ, dTJ = 1,880
d(ACEFKLMNPQST)O = min{dAO,dCO,dEO,dFO,dKO,dLO,dMO,dNO,dPO,dQO,dSO,dTO} = dPO,dSO = 0,589
d(ACEFKLMNPQST)R = min {dAR,dCR,dER,dFR,dKR,dLR,dMR,dNR,dPR,dQR,dSR,dTR} = dLR,dNR = 0,809
Setelah melakukan perhitungan diatas, maka terbentuk matriks jarak yang baru yang menjadi sebuah cluster antara ACEFKLMNPQST pada table di bawah, yaitu cluster 1.
ACEFKLMNPQS
T
B D G H I J O R
ACEFKLMNPQST 0 0,589 1,619 1,00
11,00
1 3,493 1,880 0,589 0,809
B 0,589 0 1,766 1,575
1,046 4,212 2,989 2,511 3,013
D 1,619 1,766 0 2,644
2,053 3,541 2,931 2,955 2,441
G 1,001 1,575 2,644 0 1,178 3,533 1,899 2,251 2,800
H 1,001 1,046 2,053 1,178 0 4,080 2,526 1,514 2,251
I 3,493 4,212 3,541 3,533
4,080 0 1,899 4,659 3,659
J 1,880 2,989 2,931 1,899
2,526 1,899 0 2,968 2,456
O 0,589 2,511 2,955 2,251
1,514 4,659 2,968 0 1,665
R 0,809 3,013 2,441 2,800
2,251 3,659 2,456 1,665 0
Tabel Cluster 1
c. Mencari nilai terkecil dari matriks jarak, objek ACEFKLMNPQST dan BO yang memiliki nilai terkecil yaitu 0,589. Maka ACEFKLMNPQST dan BO bergabung menjadi satu cluster baru.
d(ACEFKLMNPQST-BO)D = min{dACEFKLMNPQST-D, dBD, dOD} = dACEFKLMNPQST-D = 1,619d(ACEFKLMNPQST-BO)G = min{dACEFKLMNPQST-G, dBG, dOG}
= dACEFKLMNPQST-G = 1,001d(ACEFKLMNPQST-BO)H = min{dACEFKLMNPQST-H, dBH, dOH}
= dACEFKLMNPQST-H = 1,001d(ACEFKLMNPQST-BO)I = min {dACEFKLMNPQST - I, dBI, dOI}
= dACEFKLMNPQST-I = 3,493d(ACEFKLMNPQST-BO)J = min { dACEFKLMNPQST - J, dBJ, dOJ}
= dACEFKLMNPQST-J = 1,880d(ACEFKLMNPQST-BO)R = min{dACEFKLMNPQST-R, dBR, dOR}
= dACEFKLMNPQST-R = 0,809
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Setelah pengelompokkan tersebut maka terbentuk matriks jarak baru yang menjadi sebuah cluster antara ACEFKLMNPQST dan BO seperti pada table di bawah yaitu cluster 2.
ACEFKLMNPQSTBO D G H I J R
ACEFKLMNPQSTBO 0 1,61
91,00
1 1,001 3,493
1,880 0,809
D 1,619 0 2,644 2,053 3,54
12,93
1 2,441
G 1,001 2,644 0 1,178 3,53
31,89
9 2,800
H 1,001 2,053
1,178 0 4,08
02,52
6 2,251
I 3,493 3,541
3,533 4,080 0 1,89
9 3,659
J 1,880 2,931
1,899 2,526 1,89
9 0 2,456
R 0,809 2,441
2,800 2,251 3,65
92,45
6 0
Tabel Cluster 2
d. Setelah itu kembali lagi mencari nilai terkecil dari matriks jarak, untuk objek ACEFKLMNPQSTBO dan R yang memiliki nilai terkecil yaitu 0,809. Maka objek ACEFKLMNPQSTBO dan R akan bergabung menjadi satu cluster
d(ACEFKLMNPQSTBO - R)D =min {dACEFKLMNPQSTBO-D,dRD}= dACEFKLMNPQSTBO-D = 1,619
d(ACEFKLMNPQSTBO - R)G =min {dACEFKLMNPQSTBO-G,dRG}= dACEFKLMNPQSTBO-G = 1,001
d(ACEFKLMNPQSTBO - R)H =min {dACEFKLMNPQSTBO-H,dRH}= dACEFKLMNPQSTBO-H = 1,001
d(ACEFKLMNPQSTBO - R)I = min {dACEFKLMNPQSTBO-I, dRI}= dACEFKLMNPQSTBO-I = 3,493
d(ACEFKLMNPQSTBO - R)J = min {dACEFKLMNPQSTBO-J, dRJ}= dACEFKLMNPQSTBO-J = 1,880
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
ACEFKLMNPQSTBORGHDJ I
ACEFKLMNPQSTBORGHDJ 0
1,899
I 1,899 0
Cluster Akhir
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
Berdasarkan tabel matriks jarak diatas, dari pengelompokan euclidean distance yang dilakukan telah sesuai dengan langkah-langkah dalam pengelompokkan tehnik tersebut. Sebab, telah tersisa 2 objek dalam satu cluster, yakni
ACEFKLMNPQSTBORGHDJ dan I
STMIK TRIGUNA DHARMA
Langkah Pasti Menuju Sukses
SEKIAN DAN
TERIMA KASIH