METODE CLUSTERING HIRARKI Entin Hartini*
ABSTRAK METODE CLUSTERING HIRARKI. Dalam makalah ini dibahas beberapa teknik clustering hirarki agglomerative yaitu metode single linkage (jarak terkecil atau tetangga terdekat), complete linkage (jarak terjauh) dan average linkage (jarak rata-rata). Teknik clustering hirarki agglomerative bekerja dengan sederetan dari penggabungan yang berurutan atau sederetan dari pembagian yang berurutan dan berawal dari objek-objek individual. Jadi pada awalnya banyaknya cluster sama dengan banyaknya objek. Objek-objek yang paling mirip dikelompokkan, dan kelompok-kelompok awal ini digabungkan sesuai dengan kemiripannya. Sewaktu kemiripan berkurang, semua subkelompok digabungkan menjadi satu cluster tunggal. Hasil-hasil dari clustering dapat disajikan secara grafik dalam bentuk dendrogram atau diagram pohon. Cabang-cabang dalam pohon menyajikan cluster dan bergabung pada node yang posisinya sepanjang sumbu jarak (similaritas) menyatakan tingkat di mana penggabungan terjadi. Dalam makalah ini diberikan juga langkah-langkah dalam algoritma clustering hirarki agglomerative untuk mengelompokkan N objek (item/variabel). Input untuk algoritma metode linkage bisa berujud jarak atau similarities antara pasangan-pasangan dari objek-objek. Kelompok-kelompok dibentuk dari entities individu dengan menggabungkan jarak paling pendek atau similaritas (kemiripan) yang paling besar.
ABSTRACT HIERARCHICAL CLUSTERING METHODS . This paper discusses several agglomerative hierarchical clustering techniques, i.e. single linkage (minimum distance or nearest neighbor), complete linkage (maximum distance or farthest neighbor) and average linkage (average distance) methods as well as their applications. Agglomerative hierarchical clustering techniques proceed by either a series of successive mergers or a series of successive divisions and start with the individual objects. Thus at the beginning the number of clusters equals the number of objects. The most similar objects are first grouped, and these initial groups are fused into a single cluster. The result of clustering method can be displayed in the form of a two-dimensional diagram known as a dendrogram or tree diagram. Branches of the tree present clusters and merge at a node where its position along the distance axis (similarity) constitutes a level where the merger occures. This paper also gives steps in agglomerative hierarchical clustering algorithms to group N objects (items or variables). Inputs for linkage method algorithms can be distances or similarities between pairs of objects. Groups are formed from individual entities by merging minimum distance or maximum similarity.
*
Pusat Pengembangan Teknologi Informasi dan Komputasi BATAN
PENDAHULUAN Pengalaman menunjukkan bahwa kita jarang dapat memeriksa semua kemungkinan untuk membentuk kelompok, bahkan dengan komputer yang paling besar dan paling cepat. Mengingat hal ini variasi yang luas dari algoritma clustering telah berkembang yang tujuannya mendapatkan cluster yang layak tanpa melihat pada semua konfigurasinya. Beberapa teknik clustering hirarki bekerja dengan sederetan dari penggabungan yang berurutan atau sederetan dari pembagian yang berurutan. Metode hirarki agglomerative berawal dari objek-objek individual. Jadi pada awalnya banyaknya cluster sama dengan banyaknya objek. Pertama-tama objek-objek yang paling mirip dikelompokkan, dan kelompok-kelompok awal ini digabungkan sesuai dengan kemiripannya. Akhirnya, sewaktu kemiripan berkurang, semua subkelompok digabungkan menjadi satu cluster tunggal. Hasil-hasil dari metode agglomerative dan metoda divisive bisa ditampilkan dalam bentuk diagram yang disebut dendrogram. Akan kita lihat bahwa dendrogram menggambarkan penggabungan atau pembagian yang akan dibuat pada tingkat-tingkat yang berurutan. Pembahasan makalah ini akan menitik beratkan pada prosedur hirarki agglomerative khususnya beberapa metode linkage. Beberapa metode linkage ternyata sesuai untuk mengcluster item-item dan variabel-variabel. Tetapi hal ini tidak berlaku untuk semua prosedur agglomerative hirarki. Beberapa metoda linkage adalah single linkage (jarak terkecil), complete linkage (jarak terjauh) dan average linkage (jarak rata-rata). Single linkage memberikan hasil bila kelompok-kelompok digabungkankan menurut jarak antara anggota-anggota yang paling dekat, complete linkage terjadi bila kelompok-kelompok digabungkan menurut jarak antara anggotaanggota yang paling jauh. Untuk average linkage, digabungkan menurut jarak rata-rata antara pasangan-pasangan anggota masing-masing pada himpunannya. Hasil-hasil dari clustering linkage dapat disajikan secara grafik dalam bentuk dendrogram atau diagram pohon. Cabang-cabang dalam pohon menyajikan cluster. Kemudian cabangcabang bergabung pada node yang posisinya sepanjang sumbu jarak (similaritas) menyatakan tingkat di mana penggabungan terjadi. Langkah-langkah dalam algoritma clustering hirarki agglomerative untuk mengelompokkan N objek (item/variabel): 1. Mulai dengan N cluster, setiap cluster mengandung entiti tunggal dan sebuah matriks simetrik dari jarak (similarities) D = {d ik} dengan tipe NxN. 2. Cari matriks jarak untuk pasangan cluster yang terdekat (paling mirip). Misalkan jarak antara cluster U dan V yang paling mirip adalah d uv. 3. Gabungkan cluster U dan V. Label cluster yang baru dibentuk dengan (UV). Update entries pada matrik jarak dengan cara :
a. Hapus baris dan kolom yang bersesuaian dengan cluster U dan V b. Tambahkan baris dan kolom yang memberikan jarak-jarak antara cluster (UV) dan cluster-cluster yang tersisa. 4. Ulangi langkah 2 dan 3 sebanyak (N-1) kali. (Semua objek akan berada dalam cluster tunggal setelah algoritma berahir). Catat identitas dari cluster yang digabungkan dan tingkat-tingkat (jarak atau similaritas) di mana penggabungan terjadi.
METODE-METODE CLUSTER HIRARKI Metode Single Linkage Input untuk algoritma single linkage bisa berujud jarak atau similarities antara pasangan-pasangan dari objek-objek. Kelompok-kelompok dibentuk dari entities individu dengan menggabungkan jarak paling pendek atau similarities (kemiripan) yang paling besar. Pada awalnya, kita harus menemukan jarak terpendek dalam D = {d ik} dan menggabungkan objek-objek yang bersesuaian misalnya, U dan V , untuk mendapatkan cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara (UV) dan cluster W yang lain dihitung dengan cara d ( UV )W = min{ d UW , dVW } (1) Di sini besaran-besaran d UW dan dVW berturut-turut adalah jarak terpendek antara cluster-cluster U dan W dan juga cluster-cluster V dan W .
Metode Complete Linkage Complete linkage memberikan kepastian bahwa semua item-item dalam satu cluster berada dalam jarak paling jauh ( simila ritas terkecil) satu sama lain. Algoritma aglomerative pada umumnya dimulai dengan menentukan entri (elemen matriks) dalam D = {d ik} dan menggabungkan objek-objek yang bersesuaian misalnya U dan V untuk mendapatkan cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara cluster (UV) dan cluster W yang lain dihitung dengan
d ( UV )W = maks{ dUW ,dVW }
(2)
Di sini besaran-besaran dUW dan d VW berturut-turut adalah jarak antara tetangga terdekat cluster-cluster U dan W dan juga cluster-cluster V dan W.
Metode Average Linkage Average linkage memperlakukan jarak antara dua cluster sebagai jarak rata-rata antara semua pasangan item-item di mana satu anggota dari pasangan tersebut kepunyaan tiap cluster. Mulai dengan mencari matriks jarak D = {d ik} untuk memperoleh objek-objek paling dekat ( paling mirip) misalnya U dan V . Objek objek ini digabungkan untuk membentuk cluster (UV). Untuk langkah (3) dari algoritma di atas jarak-jarak antara(UV) dan cluster W yang lain ditentukan oleh
d ( UV )W =
∑∑ d
ik
i
k
(3)
N( UV ) NW
di mana d ik adalah jarak antara objek i dalam cluster (UV) dan objek k dalam cluster W , dan Nuv dan Nw berturut-turut adalah banyaknya item-item dalam cluster (UV) dan W.
PEMBAHASAN Contoh Metode Single Linkage Untuk menggambarkan algoritma linkage kita pandang jarak-jarak hipotetis antara 5 objek berikut ini
D = {d ik} =
1 2 1 0 2 9 0 3 3 7 4 6 5 5 11 10
3 4 5 0 9 0 2 8 0
Dengan memperlakukan setiap objek sebagai cluster, kita memulai pengklasteran dengan menggabungkan dua item yang paling dekat. Karena
min (d ik ) = d53 = 2 i,k
objek 5 dan 3 digabung untuk membentuk cluster (35). Untuk memperoleh tingkat pengklasteran berikutnya, kita memerlukan jarak-jarak antara cluster (35) dan objekobjek yang lain yang tersisa yaitu 1, 2 dan 4. Jarak – jarak yang berdekatan adalah: d (35 )1 = min {d 31, d 51 } = min {3, 11} = 3 d (35 )2 = min {d 32, d 52 } = min {7, 10} = 7 d (35 )4 = min {d 34, d 54 } = min { 9, 8} = 8 Dengan menghapus baris-baris dan kolom-kolom dari D yang bersesuaian dengan objek 3 dan 5 dan ading baris dan kolom untuk cluster (35), kita dapatkan matrik jarak yang baru
35 35 0 1 3 2 7 4 8
1 2 4 0 9 0 6 5 0
Jarak terkecil antara pasangan-pasangan cluster sekarang adalah d (35 )1 = 3 dan kita gabung cluster (1) dengan cluster (35) untuk mendapatkan cluster berikutnya. Dengan menghitung d (135 )2 = min {d (35)2, d 12 } = min {7, 9} = 7 d (135 )4 = min {d (35)4, d 14 } = min {8, 6} = 6 kita mendapatkan bahwa matrik jarak untuk tingkat pengklasteran berikutnya adalah
135 2 4 135 0 2 7 0 4 6 5 0 Jarak terdekat yang paling kecil antara pasangan cluster adalah d gabung objek 4 dan 2 untuk mendapatkan cluster (24)
42
= 5, dan kita
Pada saat ini kita punya 2 cluster yang berlainan, (135) dan (24). Jarak terdekat mereka adalah d (135 )24 = min {d (135 )2 , d (135 )4 } = min {7, 6} = 6 Matriks jarak yang terakhir menjadi
135 24 135 0 6 0 2 Jadi cluster (135) dan (24) digabung membentuk cluster tunggal dari semua 5 objek, (12345), sewaktu jarak terdekat mencapai 6. Dendrogram yang menggambarkan pengklasteran hitarki (pengelompokan dan tingkat-tingkat jarak yang diperoleh). digambarkan pada gambar berikut. 6 J a r a k
4
2 0 1
3
5
2
4
Objek
Gambar 1. Single linkage dendogram untuk jarak antara lima objek.
Contoh Metode Complete Linkage Kembali ke matriks jarak dalam contoh pertama di atas. Pada tahap pertama objek- objek 3 dan 5 digabung karena mereka paling mirip. Ini memberikan cluster (35). Pada tahap 2 kita hitung d (35 )1 = maks {d31, d 51 } = maks {3, 11} = 11
d (35 )2 = maks {d32, d 52 } = maks {7, 10} = 10 d (35 )4 = maks {d34, d 54 } = maks { 9, 8} = 9 dan matriks jarak yang dimodifikasi menjadi
35 35 0 1 11 2 10 4 9
1 2 4 0 9 0 6 5 0
Penggabungan berikutnya terjadi antara kelompok-kelompok yang paling mirip, 2 dan 4, untuk membentuk cluster (24). Pada tahap 3 kita hitung d (24)(35) = maks {d2(35), d 4(35)} = maks {10, 9} = 10 d (24)1 = maks {d 21, d 41 } = 9
dan matriks jarak
35 24 1 35 0 10 0 24 1 11 9 0
Penggabungan berikutnya menghasilkan cluster (124). Pada tahap akhir kelompok (35) dan (124) digabungkan menjadi cluster tunggal (12345) pada tingkat d(124)(35) = maks {d1(35) , d (24)(35) } = maks {11, 10} = 11 Dendrogramnya diberikan pada Gambar 2.
12 10 J a r a k
8 6 4 2 0 1
2
4
3
5
Objek
Gambar 2. Dendrogram complete linkage untuk jarak antara lima objek.
Contoh Metode Average Linkage Kembali ke matriks jarak dalam contoh pertama di atas. Pada tahap pertama objek- objek 3 dan 5 digabung karena mereka paling mirip. Ini memberikan cluster (35). Pada tahap 2 kita hitung d (35 )1 = {d 31+ d 51 }/ 2 = {3 +11}/ 2 = 7 d (35 )2 = {d 32 + d 52 }/2 = {7 + 10}/2 = 8,5 d (35 )4 = {d 34 +d 54 }/2 = { 9 + 8}/2 = 8,5 dan matriks jarak yang dimodifikasi menjadi
35 35 1 1 7 2 8,5 4 8,5
1 2 4 0 9 0 6 5 0
Penggabungan berikutnya terjadi antara kelompok-kelompok yang paling mirip, 2 dan 4, untuk membentuk cluster (24). Pada tahap 3 kita hitung
d (35)35 d (24)24 d (24)35 d (24)1
= {d (3,5) +d (5,3) + d (3,3) +d (5,5) }/4 = (0+0+2+2)/4 = 1 = {d (2,2) +d (4,4) + d (2,4) +d(4,2) }/4 = (0+0+5+5)/4 = 2,5 = {d (2,3) +d (2,5) + d (4,3) +d (4,5) }/4 = (7+10+9+8)/4 = 8,5 = {d (2,1) +d (4,1) }/2 = (9+6)/2 = 7,5
dan matriks jarak menjadi
35 24 1
35 24 1 1 8,5 2,5 7 7,5 0
Penggabungan berikutnya menghasilkan cluster (135). Pada tahap akhir kelompok (135) dan (24) digabungkan menjadi cluster tunggal (13524) pada tingkat d (135)(24) = {d (2,1)+d (2,3) +d (2,5) +d (4,1)+d (4,3) +d (4,5) }/6 = 49/6 =8,17
135 24 135 0 8,17 0 24 j 8,17 a 7 r a 5 k 2 0 1
3
5
2
4
Objek
Gambar 3 Dendrogram average linkage untuk jarak antara lima objek
KESIMPULAN Membandingkan Gambar 1, Gambar 2 dan Gambar 3 terlihat bahwa dendrogram untuk single linkage dan complate linkage berbeda dalam alokasi objek 1 ke kelompok-kelompok sebelumnya. Perbandingan dari dendrogram pada pada ke tiga metode menunjukkan bahwa average linkage menghasilkan konfigurasi yang sangat mirip dengan konfigurasi complate linkage. Tetapi karena jarak didefinisikan secara berbeda untuk setiap kasus maka penggabungan-penggabungan mengambil tempat pada tingkat-tingkat yang berlainan. Sebagaimana dengan metode clustering pada umumnya sumber kekeliruan dan variasi tidak diperhitungkan dalam prosedur hirarki. Ini berarti bahwa metode clustering akan sensitif terhadap outliers atau titik nois. Dalam clustering hirarki tidak ada ketentuan untuk realokasi (penempatan kembali) dari objek-objek yang mungkin telah dikelompokkan secara tidak benar pada tahap awal. Pada problem yang khusus untuk mencoba beberapa metode pengklasteran dengan metode yang diberikan, ada dua cara yang berbeda untuk menentukan jarak atau similiarities. Bila hasil dari beberapa metode konsisten satu sama lain ada kemungkinan pengelompokan alami dapat dilanjutkan. Stabilitas dari solusi hirarki dapat diperiksa dengan menerapkan algoritma clustering sebelum dan sesudah kekeliruan kecil ditambahkan pada satuan data. Bila pengelompokan dapat dibedakan dengan jelas, pengelompokan sebelum kekeliruan dan sesudah kekeliruan seharusnya tidak bertentangan. Nilai yang umum dalam matriks jarak atau similarities dapat menghasilkan beberapa penyelesaian pada masalah clustering hirarki. Dalam hal ini dendrogram yang sesuai dengan perlakuan yang berbeda dari jarak atau similarities dapat berbeda, khususnya pada tingkat-tingkat yang lebih rendah.
DAFTAR PUSTAKA 1. JOHNSON, RICHARD A. and DEAN W. WICHERN, Applied Multivariate Statistical Analysis, Prentice Hall, Upper Saddle River, New Jersey , 2002. 2. EVERITT, B.S. Cluster Analysis (3ed). London: Edward Arnold, 1993. 3. MORRISON, D.F., Multivariate Statistical Methods, McGraw-Hill Book Company, 1988.
DISKUSI
RIDWAN Mohon diberikan contoh metode clustering yang sudah diaplikasi. ENTIN HARTINI Metode clustering dapat digunakan untuk meneliti pasar dari sekumpulan produk industri peralatan mesin. Untuk setiap produk (observasi) dicatat setiap kumpulan karakteristik object (variable). Harga dapat dianggap sebuah karakteristik dan macam produk dianggap sebagai lainnya. Pengukuran jarak didasarkan pada seluruh karakteristik.
DAFTAR RIWAYAT HIDUP
1. Nama
: Dra. Entin Hartini
2. Tempat/Tanggal Lahir
: Majalengka, 19 Februari 1962
3. Instansi
: BATAN
4. Pekerjaan / Jabatan
: Staf P2TIK
5. Riwayat Pendidikan
: S1 Statistik Universitas Padjadjaran
6. Pengalaman Kerja
: BATAN
Back
