- Analisis Cluster
Analisis cluster adalah pengelompokan data (objek) yang didasarkan hanya pada informasi yang ditemukan dalam data yang menggambarkan objek tersebut dan hubungan antar data. Tujuan analisis cluster adalah agar objek-objek yang bergabung dalam sebuah kelompok merupakan objek-objek yang mirip (atau berhubungan) satu sama lain dan berbeda (atau tidak berhubungan) dengan objek dalam kelompok yang lain.
Secara umum terdapat dua metode yang dapat digunakna untuk melakukan analisis cluster, yaitu metode hierarki dan metode non hierarki. Metode hierarki memulai pengelompokan dengan dua atau lebih objek yang mempunyai kesamaan paling dekat, kemudian proses diteruskan ke objek lain yang mempunyai kedekatan kedua. Demikian seterusnya hingga cluster akan membentuk semacam pohon dimana ada hierarki (tingkatan) yang jelas antar objek dari yang paling mirip hingga yang paling tidak mirip. Secara logika semua objek pada akhirnya akan membentuk sebuah klaster. Dendogram biasanya digunakan untuk membantuk memperjelas proses hierarki tersebut.
- Metode Hierarki
Teknik pengelompokan pada metode hierarki menggunakan teknik penggabungan (agglomerative) dan teknik pembagian (divisive). Teknik pengelompokan antar kelompok adalah sebagai berikut:
a. Single Linkage
Metode Single Linkage adalah proses clustering yang didasarkan pada jarak terdekat antar objeknya. Jika dua objek terpisah oleh jarak pendek, maka kedua objek tersebut akan bergabung menjadi satu cluster dan demikian seterusnya. Pengukuran jarak metode ini dapat ditulis dalam rumus berikut:
dimana
Adapun algoritma dari metode single linkage adalah sebagai berikut:
1. Menghitung matriks jarak dengan menggunakaan jarak manhattan pada persamaan dibawah sebagai berikut:
2. Menggabungkan dua cluster yang memiliki ukuran jarak terkecil
3. Memperbarui matriks jarak
4. Mengulangi langkah 2 untuk mendapatkan pasangan cluster terdekat berikutnya untuk digabungkan
b. Complete Linkage
Pengukuran jarak pada metode complete linkage dilakukan berdasarkan jarak maksimum atau terjauh. Rumus yang digunakan dalam menentukan jarak pada metode ini adalah sebagai berikut:
dimana
merupakan ukuran kemiripan antara kelompok ke-w dengan kelompok (i,j) yang merupakan penggabungan antara kelompok ke-i dan ke-j.
Adapun algoritma dari metode complete linkage adalah sebagai berikut:
1. Menghitung matriks jarak dengan menggunakaan jarak manhattan pada persamaan sebagai berikut:
2. Menggabungkan dua cluster yang memiliki ukuran jarak terkecil
3. Memperbarui matriks jarak
4. Mengulangi langka 2 untuk mendapatkan pasangan cluster terdekat berikutnya untuk digabungkan
c. Average Linkage
Kriteria yang digunakan dalam mengukur jarak pada metode ini adalah rata-rata jarak seluruh individu dalam satu kelompok dengan jarak seluruh individu dalam kelompok lain. Dapat dituliskan dalam rumus sebagai berikut:
dimana
merupakan ukuran kemiripan antara kelompok ke-w dengan kelompok (i,j) yang merupakan penggabungan antara kelompok ke-i dan ke-j, (disimbolkan sebagai kelompok ij).
merupakan jumlah pengamatan dalam kelompok ij dan w, sedangkan
Adapun algoritma dari metode average linkage adalah sebagai berikut:
1. Menghitung matriks jarak dengan menggunakaan jarak manhattan pada persamaan sebagai berikut:
2. Menggabungkan dua cluster yang memiliki ukuran jarak terkecil
3. Memperbarui matriks jarak
4. Mengulangi langka 2 untuk mendapatkan pasangan cluster terdekat berikutnya untuk digabungkan
- Contoh Perhitungan
Tabel Data Pengamatan
| Data Ke- | A | B |
| 1. | 1 | 1 |
| 2. | 4 | 1 |
| 3. | 1 | 2 |
| 4. | 3 | 4 |
| 5. | 5 | 4 |
a. Single Linkage
Adapun langkah pengerjaan pada metode single linkage sebagai berikut
1. Menghitung matriks jarak dengan menggunakan persamaan sebagai berikut:
Sehingga, matriks jarak yang dihasilkan adalah sebagai berikut
Tabel Jarak Manhattan pada Metode Single linkage iterasi 1
| dmanhattan | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | ||||
| 2 | 3 | 0 | |||
| 3 | 1 | 4 | 0 | ||
| 4 | 5 | 4 | 4 | 0 | |
| 5 | 7 | 4 | 6 | 2 | 0 |
2. Menggabungkan dua cluster yang memiliki ukuran jarak terkecil
Setelah memperoleh hasil jarak dengan menggunakan jarak manhattan. Langkah selanjutnya adalah menggabungkan dua cluster yang memiliki ukuran jarak terkecil. Dapat dilihat pada Tabel diatas bahwa pasangan cluster 1 dan 3 memiliki ukuran jarak yang paling kecil sebesar 1 sehingga cluster 1 dan 3 digabung menjadi satu cluster dan sekarang terbentuk 4 cluster.
3. Memperbarui matriks jarak
Setelah menggabungkan dua cluster, selanjutnya adalah memperbarui matriks jarak untuk mencari cluster terdekat dari 4 cluster. Jarak antar cluster dihitung berdasarkan metode single linkage pada persamaan sebagai berikut:
Sehingga, matriks jarak yag diperbarui dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Single lingkage iterasi 2
| dmanhattan | (1,3) | 2 | 4 | 5 |
| (1,3) | 0 | |||
| 2 | 3 | 0 | ||
| 4 | 4 | 4 | 0 | |
| 5 | 6 | 4 | 2 | 0 |
4. Setelah memperbarui matriks jarak selanjutnya adalah menggabungkan dua cluster dengan jarak terkecil, pada Tabel diatas dapat dilihat bahwa cluster 4 dan 5 memiliki ukuran jarak terkecil yaitu sebesar 2 sehingga cluster 4 dan 5 digabung menjadi satu cluster dan sekarang terbentuk 3 cluster.
5. Memperbarui matriks jarak
Adapun perhitungan jarak antar cluster sebagai berikut:
Sehingga, matriks jarak yang diperbarui pada iterasi 3 dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Single linkage iterasi 3
| dmanhattan | (1,3) | 2 | (4,5) |
| (1,3) | 0 | ||
| 2 | 3 | 0 | |
| (4,5) | 4 | 4 | 0 |
6. Pada Tabel diatas dapat dilihat bahwa cluster 2 dan (1,3) memiliki ukuran jarak terkecil yaitu sebesar 3 sehingga cluster 2 dan (1,3) digabung menjadi satu cluster dan sekarang terbentuk 2 cluster.
7. Memperbarui matriks jarak
Adapun perhitungan jarak antar cluster sebagai berikut:
Sehingga, matriks jarak yang diperbarui pada iterasi 3 dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Single linkage iterasi 3
| dmanhattan | (1,3)2 | (4,5) |
| (1,3)2 | 0 | |
| (4,5) | 4 | 0 |
b. Complete Linkage
Adapun langkah pengerjaan pada metode Complete linkage sebagai berikut
1. Menghitung matriks jarak dengan menggunakan persamaan sebagai berikut:
Sehingga, matriks jarak yang dihasilkan adalah sebagai berikut
Tabel Jarak Manhattan pada Metode Complete linkage iterasi 1
| dmanhattan | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | ||||
| 2 | 3 | 0 | |||
| 3 | 1 | 4 | 0 | ||
| 4 | 5 | 4 | 4 | 0 | |
| 5 | 7 | 4 | 6 | 2 | 0 |
2. Menggabungkan dua cluster yang memiliki ukuran jarak terkecil
Setelah memperoleh hasil jarak dengan menggunakan jarak manhattan. Langkah selanjutnya adalah menggabungkan dua cluster yang memiliki ukuran jarak terkecil. Dapat dilihat pada Tabel bahwa pasangan cluster 1 dan 3 memiliki ukuran jarak yang paling kecil sebesar 1 sehingga cluster 1 dan 3 digabung menjadi satu cluster dan sekarang terbentuk 4 cluster.
3. Memperbarui matriks jarak
Setelah menggabungkan dua cluster, selanjutnya adalah memperbarui matriks jarak untuk mencari cluster terdekat dari 4 cluster. Jarak antar cluster dihitung berdasarkan metode complete linkage pada persamaan sebagai berikut:
Sehingga, matriks jarak yag diperbarui dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Complete linkage iterasi 2
| dmanhattan | (1,3) | 2 | 4 | 5 |
| (1,3) | 0 | |||
| 2 | 4 | 0 | ||
| 4 | 5 | 4 | 0 | |
| 5 | 7 | 4 | 2 | 0 |
4. Setelah memperbarui matriks jarak selanjutnya adalah menggabungkan dua cluster dengan jarak terkecil, pada Tabel dapat dilihat bahwa cluster 4 dan 5 memiliki ukuran jarak terkecil yaitu sebesar 2 sehingga cluster 4 dan 5 digabung menjadi satu cluster dan sekarang terbentuk 3 cluster.
5. Memperbarui matriks jarak
Adapun perhitungan jarak antar cluster sebagai berikut:
Sehingga, matriks jarak yang diperbarui pada iterasi 3 dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Complete linkage iterasi 3
| dmanhattan | (1,3) | 2 | (4,5) |
| (1,3) | 0 | ||
| 2 | 4 | 0 | |
| (4,5) | 7 | 4 | 0 |
6. Pada Tabel diatas dapat dilihat bahwa cluster 2 dan (1,3) memiliki ukuran jarak terkecil yaitu sebesar 3 sehingga cluster 2 dan (1,3) digabung menjadi satu cluster dan sekarang terbentuk 2 cluster.
7. Memperbarui matriks jarak
Adapun perhitungan jarak antar cluster sebagai berikut:
Sehingga, matriks jarak yang diperbarui pada iterasi 3 dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Complete linkage iterasi 3
| dmanhattan | (1,3)2 | (4,5) |
| (1,3)2 | 0 | |
| (4,5) | 7 | 0 |
c. Average Linkage
Adapun langkah pengerjaan pada metode average linkage sebagai berikut
1. Menghitung matriks jarak dengan menggunakan persamaan sebagai berikut:
Sehingga, matriks jarak yang dihasilkan adalah sebagai berikut
Tabel Jarak Manhattan pada Metode Average linkage iterasi 1
| dmanhattan | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | ||||
| 2 | 3 | 0 | |||
| 3 | 1 | 4 | 0 | ||
| 4 | 5 | 4 | 4 | 0 | |
| 5 | 7 | 4 | 6 | 2 | 0 |
2. Menggabungkan dua cluster yang memiliki ukuran jarak terkecil
Setelah memperoleh hasil jarak dengan menggunakan jarak manhattan. Langkah selanjutnya adalah menggabungkan dua cluster yang memiliki ukuran jarak terkecil. Dapat dilihat pada Tabel diatas bahwa pasangan cluster 1 dan 3 memiliki ukuran jarak yang paling kecil sebesar 1 sehingga cluster 1 dan 3 digabung menjadi satu cluster dan sekarang terbentuk 4 cluster.
3. Memperbarui matriks jarak
Setelah menggabungkan dua cluster, selanjutnya adalah memperbarui matriks jarak untuk mencari cluster terdekat dari 4 cluster. Jarak antar cluster dihitung berdasarkan metode average linkage pada persamaan sebagai berikut:
Sehingga, matriks jarak yag diperbarui dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Average linkage iterasi 2
| dmanhattan | (1,3) | 2 | 4 | 5 |
| (1,3) | 0 | |||
| 2 | 3,5 | 0 | ||
| 4 | 4,5 | 4 | 0 | |
| 5 | 6,5 | 4 | 2 | 0 |
4. Setelah memperbarui matriks jarak selanjutnya adalah menggabungkan dua cluster dengan jarak terkecil, pada Tabel 4.11 dapat dilihat bahwa cluster 4 dan 5 memiliki ukuran jarak terkecil yaitu sebesar 2 sehingga cluster 4 dan 5 digabung menjadi satu cluster dan sekarang terbentuk 3 cluster.
5. Memperbarui matriks jarak
Adapun perhitungan jarak antar cluster sebagai berikut:
Sehingga, matriks jarak yang diperbarui pada iterasi 3 dapat dilihat pada Tabel sebagai berikut:
Tabel Jarak Manhattan yang diperbarui pada Metode Average linkage iterasi 3
| dmanhattan | (1,3) | 2 | (4,5) |
| (1,3) | 0 | ||
| 2 | 3,5 | 0 | |
| (4,5) | 5,5 | 4 | 0 |
4. Pada Tabel diatas dapat dilihat bahwa cluster 2 dan (1,3) memiliki ukuran jarak terkecil yaitu sebesar 3 sehingga cluster 2 dan (1,3) digabung menjadi satu cluster dan sekarang terbentuk 2 cluster.
5. Memperbarui matriks jarak
Adapun perhitungan jarak antar cluster sebagai berikut:
Sehingga, matriks jarak yang diperbarui pada iterasi 3 dapat dilihat pada Tabel 4.13 sebagai berikut:
Tabel 4.13 Jarak Manhattan yang diperbarui pada Metode Complete Average iterasi 3
| dmanhattan | (1,3)2 | (4,5) |
| (1,3)2 | 0 | |
| (4,5) | 5 | 0 |
Syntax:
| data=read.table(file.choose(),header=T) library(cluster) distance=dist(data,method=”manhattan”) distance #single linkage fit.sin=hclust(distance,method = “single”) plot(fit.sin) rect.hclust(fit.sin,3) kelompok=cutree(fit.sin,3) tabel=data.frame(kelompok) tabel #complete linkage fit.comp=hclust(distance,method = “complete”) plot(fit.comp) rect.hclust(fit.comp,3) kelompok=cutree(fit.comp,3) tabel=data.frame(kelompok tabel #average linkage fit.ave=hclust(distance,method = “average”) plot(fit.ave) rect.hclust(fit.ave,3) kelompok=cutree(fit.ave,3) tabel=data.frame(kelompok) tabel |