hierarchical clustering
DESCRIPTION
Hierarchical Clustering ini membahas topik clustering analisis menggunakan metode single & average linkage clustering.TRANSCRIPT
-
HIERARCHICAL CLUSTERING
-
Prinsip Dasar Hierarchical Cluster
Keanggotaan pada suatu cluster ditentukan menggunakan matriks jarak dalam bentuk dendogram atau tree
Setiap objek bergabung dalam susunan hierarki dimana jarak terdekat merepresentasikan kemiripan sedangkan jarak terjauh menunjukkan perbedaan
Penjelasan terbaik dapat dideskripsikan menggunakan algoritma atau sekelompok instruksi yang menghasilkan dendogram
-
Hierarchical Clustering berdasarkan Jumlah Perbedaan Objek Cluster
Single Linkage Clustering (K-Nearest Network) Jika penggabungan cluster hanya boleh dilakukan pada
objek terdekat sebanyak satu kali Nilai k diperoleh ketika hanya tersisa 1 pasang objek
yang berbeda pada nilai < level yang ditetapkan
Complete Linkage Clustering (Furthest Network) Jika penentuan jumlah cluster ditentukan dari jumlah
maksimum pasangan cluster yang berbeda Nilai k diperoleh dari jumlah cluster yang tersisa pada
nilai < level yang ditetapkan
Average Linkage Clustering Penggabungan kluster dilakukan dengan menghitung rata-
rata jarak antar 2 pasang objek data yang berbeda
-
Single Linkage Clustering
Algoritma: Buat matriks jarak antar objek di dalam dataset Cari pasangan objek yang memiliki jarak euclidean
paling kecil Gabung pasangan objek dengan nilai jarak paling kecil
dan gambarkan dendogramnya Update pasangan objek yang memiliki jarak paling
dekat (d= MIN) dan gabungkan pasangan objek baru dengan nilai jarak MAX
Tentukan nilai similarity dari jarak euclidean Sisa cluster yang tersisa pada dendogram/tree yang
terpotong adalah jumlah k optimum
-
Contoh Implementasi Algoritma Single Linkage Clustering (1):
Dari dataset sebagai berikut
Dataset Outlook Temperature Humidity Windy Play golf
1 Rainy Hot High FALSE No
2 Rainy Hot High TRUE No
3 Overcast Hot High FALSE Yes
4 Sunny Mild High FALSE Yes
5 Sunny Cool Normal FALSE Yes
6 Sunny Cool Normal TRUE No
7 Overcast Cool Normal TRUE Yes
Dataset Outlook Temperature Humidity Windy Play golf
1 1 1 1 2 2
2 1 1 1 1 2
3 2 1 1 2 1
4 3 2 1 2 1
5 3 3 2 2 1
6 3 3 2 1 2
7 2 3 2 1 1
-
Contoh Implementasi Algoritma Single Linkage Clustering (2):
Buat matriks jarak berpasangan antar objek dalam dataset:
Pilih pasangan objek dengan jarak terkecil dan buat dendogramnya
1 2 3 4 5 6 7
1 0 1 1 2.236 3 3.162 2.646
2 1 0 1.414 2.449 3.162 3 2.449
3 1 1.414 0 1.414 2.449 2.646 2.449
4 2.236 2.449 1.414 0 1.414 1.732 2
5 3 3.162 2.449 1.414 0 1 1.414
6 3.162 3 2.646 1.732 1 0 1
7 2.646 2.449 2.449 2 1.414 1 0 2 1 3 5 6 74
-
Contoh Implementasi Algoritma Single Linkage Clustering (3):
Update jarak terkecil antar objek berpasangan menggunakan matriks berpasangan hingga dataset habis
(1,2) (1,3) 4 (5,6) (6,7)
(1,2) 0 2.44949 3.162 3.162
(1,3) 1.414 0 2.23607 3.162 3.162
4 2.44949 2.23607 0 1.732 2
(5,6) 3.16228 3.16228 1.73205 0 1.414
(6,7) 3.16228 3.16228 2 1.414 0
(1,2,3) 4 (5,6,7)
(1,2,3) 0 2.44949 3.16228
4 2.44949 0 1.73205
(5,6,7) 3.16228 1.73205 0
-
Contoh Implementasi Algoritma Single Linkage Clustering (4):
Update dendogram sehingga menghasilkan model cluster akhir
Tetapkan nilai similarity untuk memotong dendogram/tree yang telah dibuat ( d= 1,5)
Dari model dendogram dapat dilihat bahwa apabila (d = 1,5) akan menghasilkan k = 3
2 1 3 5 6 74
-
Implementasi Menggunakan SPSS (1):
-
Implementasi Menggunakan SPSS (2):
-
Implementasi Menggunakan SPSS (3):
-
Implementasi Menggunakan SPSS (4):
-
Implementasi Menggunakan SPSS (5):
Euclidean Distance Iterasi ke-1:
-
Implementasi Menggunakan SPSS (6):
Dendogram Single Linkage:
-
Complete Linkage Clustering
Algoritma: Buat matriks jarak antar objek di dalam dataset Cari pasangan objek yang memiliki jarak euclidean
paling kecil Gabung pasangan objek dengan nilai jarak paling kecil
dan gambarkan dendogramnya Update pasangan objek yang memiliki jarak terjauh
(d= MAX) dan gabungkan pasangan objek baru dengan nilai jarak MIN
Tentukan nilai similarity dari jarak euclidean Sisa cluster yang tersisa pada dendogram/tree yang
terpotong adalah jumlah k optimum
-
Contoh Implementasi Algoritma Complete Linkage Clustering (1):
Diberikan dataset sebagai berikut:
Dataset Outlook Temperature Humidity Windy Play golf
1 Rainy Hot High FALSE No
2 Rainy Hot High TRUE No
3 Overcast Hot High FALSE Yes
4 Sunny Mild High FALSE Yes
5 Sunny Cool Normal FALSE Yes
6 Sunny Cool Normal TRUE No
7 Overcast Cool Normal TRUE Yes
Dataset Outlook Temperature Humidity Windy Play golf
1 1 1 1 2 2
2 1 1 1 1 2
3 2 1 1 2 1
4 3 2 1 2 1
5 3 3 2 2 1
6 3 3 2 1 2
7 2 3 2 1 1
-
Contoh Implementasi Algoritma Complete Linkage Clustering (2):
Buat matriks jarak berpasangan antar objek dalam dataset:
Pilih pasangan objek dengan jarak terkecil dan buat dendogramnya
1 2 3 4 5 6 7
1 0.00 1.00 1.00 2.24 3.00 3.16 2.65
2 1.00 0.00 1.41 2.45 3.16 3.00 2.45
3 1.00 1.41 0.00 1.41 2.45 2.65 2.45
4 2.24 2.45 1.41 0.00 1.41 1.73 2.00
5 3.00 3.16 2.45 1.41 0.00 1.00 1.41
6 3.16 3.00 2.65 1.73 1.00 0.00 1.00
7 2.65 2.45 2.45 2.00 1.41 1.00 0.00
-
Contoh Implementasi Algoritma Complete Linkage Clustering (3):
Update jarak terjauh antar objek berpasangan menggunakan matriks berpasangan hingga dataset habis
(2,5) 3 4 (1,6) 7(2,5) 0 1.41 1.41 1 1.41
3 1.41 0 1.41 1.00 2.45
4 1.41 1.41 0 1.73 2.00
(1,6) 1 1.00 1.73 0 1.00
7 1.41 2.45 2.00 1.00 0
(1,6) (2,5) (3,7) 4
(1,6) 0 1 1.00 1.73
(2,5) 1 0 1.41 1.41
(3,7) 1.00 1.41 0 1.41
4 1.73 1.41 1.41 0
(1,6,4) (2,5) (3,7)
(1,6,4) 0 1.00 1.00
(2,5) 1 0 1.41
(3,7) 1 1.41 0
(1,6,4) (2,5,3,7)
(1,6,4) 0 1.00
(2,5,3,7) 1.00 0
-
Contoh Implementasi Algoritma Complete Linkage Clustering (4):
Update dendogram sehingga menghasilkan model cluster akhir
Tetapkan nilai similarity untuk memotong dendogram/tree yang telah dibuat ( d= 1,5)
Dari model dendogram dapat dilihat bahwa apabila (d = 1,5) akan menghasilkan k = 4
1 6 3 72 54
-
Average Linkage Clustering
Algoritma:
Buat matriks jarak antar objek di dalam dataset
Cari pasangan objek yang memiliki jarak euclidean paling kecil
Gabung pasangan objek dengan nilai jarak paling kecil dan gambarkan dendogramnya