Pertemuan 14 HIERARCHICAL CLUSTERING METHODS
berdasar gambar
berdasar warna
A
A
A
A
Q
Q
Q
Q
K
K
K
K
J
J
J
J
2
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
6
6
6
6
7
7
7
7
8
8
8
8
9
9
9
9
10
10
10
10
A K Q J
A
(a). Individual Cards
(d). Major and minor suits (bridge)
K Q J
A K Q J
A K Q J
(b). Individual suits
A K Q J (c). Black and red suits
(e). Hearts plus queen of spades and other suits (hearts)
A K Q J (f). Like face cards
HIERARCHICAL CLUSTERING METHODS (Metode Pengklusteran berhierarki) Pengklasteran adalah pengelompokan objek/kasus (responden) menjadi kelompokkelompok yang lebih kecil, dimana setiap kelompok berisi objek yang mirip satu sama lain. Objek akan sangat berbeda ketika berasal dari kelompok yang berbeda Teknik pengklasteran hierarkis dilakukan dengan penggabungan secara berurutan (successive merger) atau pembagian secara berurutan (successive divisions) Metode aglomeratif hierarkis (agglomerative hierarchical methods), mulai dengan objek/kasus secara individual. Jadi mula-mula terdapat jumlah kluster sebanyak objek/kasus. Objek yang paling mirip (most similar) atau jaraknya paling dekat, yang pertama di kelompokan, dan kelompok yang awal ini digabung sesuai dengan kemiripan objek. Pada akhirnya, jika tingkat kemiripan menurun, semua kelompok-kelompok yang kecil (sub group) digabung/disatukan menjadi satu kluster. Metode hierarkis divisif (divisive hierarchical methods), bekerja dalam arah yang bertentangan. Suatu kelompok objek tunggal dibagi ke dalam dua kelompok yang lebih kecil (sub-groups), sehingga objek yang berada di kelompok yang satu sangat berbeda dengan objek yang berada di kelompok lainnya. Kelompok-kelompok yang kecil ini kemudian dibagi menjadi kelompok yang berbeda, proses akan berlanjut sampai diperoleh kelompok sebanyak objek yang ada, artinya sampai satu objek membentuk satu kelompok.
Hasil dari kedua metode aglomeratif dan devisif mungkin bisa disajikan dalam bentuk dendogram, sebagai suatu diagram dua dimensi. Pada uraian berikut pembahasan di fokuskan pada prosedure aglomeratif hierarkis dan khususnya metode pertalian (linkage methods), untuk mengelompokkan objek atau variabel. Pembahasan dimulai dengan pertalian tunggal (single linkage) yang diwakili jarak minimum atau tetangga terdekat (minimum distance or nearest neighbour), pertalian lengkap (complete linkage), yang diwakili jarak maksimum atau tetangga terjauh (maximum distance or farthest neighbour) dan pertalian rata-rata (average linkage or average distance). a). Single linkage , diperoleh ketika kelompok disatukan sesuai dengan jarak antara objek yang berdekatan. b). Complete linkage, terjadi kalau kelompok disatukan sesuai dengan jarak antara objek yang terjauh. c). Average linkage, diperoleh jika kelompok disatukan sesuai dengan rata-rata jarak antara pasangan objek didalam set masing-masing.
3
Single linkage
4
1 2
5
a). Jarak kluster 3
Complete linkage
4
1
5
2
b). Jarak kluster
3
Average linkage
4
1 2
c). Jarak kluster = rata-rata jarak =
5
Langkah-langkah pengklasteran aglomeratif hierarkis untuk mengelompokkan N objek/variabel 1. Mulai dengan N kluster, masing-masing kelompok memuat objek tunggal dan matriks simetri N x N berjarak
2. Selidiki jarak matriks untuk pasangan kelompok (paire of clusters) yang paling mirip atau paling dekat. Misalkan jarak antara kelompok yang paling mirip (most similar clusters) yaitu U dan V 3. Gabungkan kelompok atau cluster U dan V. Kluster ini disebut kluster (UV).
Perbarui entry di dalam matriks jarak dengan :
a. Menghapus/menghilangkan baris dan kolom, sesuai dengan kluster (kelompok) U dan V. b. Tambah satu baris dan kolom memberikan jarak antara klaster (UV) dan sisa klaster 4. Ulangi langkah (2 dan 3) sebanyak (N-1) kali. (Seluruh objek akan berada dalam 1 klaster/kelompok setelah algoritma selesai). Catat identitas klaster yang digabung dan tingkatan (levels=distances or similarities) pada mana penggabungan terjadi.
Pertalian Tunggal (Single Linkage) Masukan (input) bagi algoritma pertalian tunggal bisa merupakan jarak atau kemiripan (distances or similarities), antara pasangan objek. Kelompok/kluster di bentuk dari individu objek dengan jelas menggabungkan tetangga terdekat di mana tetangga terdekat diartikan jarak terdekat. dan Pada awalnya, harus ditemukan jarak terdekat dalam menggabungkan objek yang bersangkutan, misalnya U dan V, untuk mendapatkan kelompok atau kluster (UV). Untuk langkah (3) dari algoritma umum (lihat urutan 1 sampai dengan 4), jarak antara kluster (UV) dengan kluster W di hitung sebagai berikut, merupakan jarak dan Dalam hal ini, angka yang ditunjukkan oleh antara tetangga terdekat dari kluster (U dan W) dan kluster (V dan W) masing-masing
Hasil berupa single linkage clustering dapat disajikan dalam bentuk suatu dendogram atau diagram pohon (tree diagram). Cabang-cabang pohon menunjukkan kluster/kelompok.
Contoh 1: Pengklusteran dengan Pertalian Tunggal (dari 5 objek). Sebagai suatu ilustrasi algoritma pertalian tunggal (the single linkage algorithm) diberikan data hipotesis tentang jarak (distance) antara 5 pasang objek sbb:
Tampak bahwa jarak terpendek Maka objek 5 dan 3 digabung menjadi kluster (3 5) Untuk membentuk kluster berikutnya, perlu dicari jarak kluster (3 5) dengan objek sisanya yaitu 1 , 2 dan 4 sbb
maka diperoleh suatu matriks jarak yang baru sebagai berikut
Sekarang jarak terdekat adalah Sehingga kluster (3 5) digabung dengan kluster (1), diperoleh kluster baru (1 3 5). Untuk membentuk kluster berikutnya, perlu dicari jarak kluster (1 3 5) dengan objek sisanya yaitu 2 dan 4 sbb
Diperoleh matriks jarak untuk pengklusteran berikutnya sebagai berikut
Sekarang jarak yang terdekat adalah kluster 4 dan 2 . Sekarang bentuk kluster (24)
, yaitu jarak pasangan
Pada saat ini sudah dipunyai dua kluster yang berbeda yaitu kluster (1 3 5) dan kluster (2 4). Jarak yang paling dekat (minimum) adalah Matriks jarak yang terakhir menjadi
Konsekwensinya, kluster (135) dan (24) digabung untuk membentuk kluster tunggal dari semua objek, sebanyak 5 buah yaitu (1 2 3 4 5), ketika jarak terdekat dari dua kluster sebesar (6)
Gambar dendogram hasil pengklusteran hierarkis yang dilakukan secara bertahap. Kluster pertama (3 5) berjarak (2)
(3) dan (5) berisi 2 objek
Kluster kedua (1 3 5) berjarak (3)
(35) dan (1) berisi 3 objek
Kluster ketiga (24 ) berjarak (5)
(2) dan (4) berisi 2 objek
Kluster keempat (1 2 3 4 5) berjarak (6)
(1 3 5) dan (2 4) berisi 5 objek
Distances
6
4 Single linkage dendrogram for distances between five objects
2
0
1
3 5 o b j e c t s
2
4
Complete Linkage (Pertalian Lengkap) Pertalian lengkap dilaksanakan sama seperti prosedure single linkage, dengan suatu kekecualian (exception). Pada setiap tahap, jarak (kemiripan) antara kluster ditentukan oleh jarak antara dua objek, satu dari setiap kluster yang paling jauh (most distant). Jadi pertalian lengkap menjamin bahwa semua objek dalam suatu kluster akan berada di dalam some maximum distance (or minimum similarity) satu sama lain Pengklasteran menggunakan Pertalian lengkap (Complete Linkage)
Kembali pada matriks jarak pada contoh 1.
Langkah pertama, objek 3 dan 5 di gabung (mergred) karena keduanya paling mirip (most similar). Hal ini memberikan cluster (35). Langkah kedua, hitung jarak terjauh antara kluster (35) dengan objek sisa 1, 2 dan 4
Sehingga matriks jarak menjadi
penggabungan selanjutnya (the most similar group) berjarak 5, yaitu objek 2 dan 4, menghasilkan kluster (24).
Langkah ketiga, hitung jarak terjauh antara kluster (24) dengan (35) dan 1
dan matriks jarak menjadi
Penggabungan selanjutnya adalah kluster (124). Langkah terakhir, penggabungan kluster (35) dan (124) menjadi single cluster (12345) pada level
Gambar dendrogram complete linkage diberikan sebagai berikut
12
Distances
10 8 6 4 2 0
1
3 4 o b j e c t s 2
5
Complete linkage dendrogram for distances between five objects
10
Distances
8 6 4 2 0
E
N
Da Fr I Sp P Du G H Fi Languages Single linkage dendrogram for distances between numbers in 11 languages
10
Distances
8 6 4 2 0
E
N
Da G Fr I Sp P Du H Fi Languages Complete linkage dendrogram for distances between numbers in 11 languages
10
Distances
8 6 4 2 0
E
N
Da
G
Du Fr I Languages
Sp
P
H
Fi
Average linkage dendrogram for distances between numbers in 11 languages
