Algoritma Hierarchical Clustering

Algoritma hierarchical Clustering

Hierarchical methods adalah teknik clustering membentuk hirarki atau berdasarkan tingkatan tertentu sehingga menyerupai struktur pohon. Dengan demikian proses pengelompokannya dilakukan secara bertingkat atau bertahap. Biasanya, metode ini digunakan pada data yang jumlahnya tidak terlalu banyak dan jumlah cluster yang akan dibentuk belum diketahui.

Di dalam metode hirarki, terdapat dua jenis strategi pengelompokan yaitu agglomerative dan divisive.

Agglomerative (metode penggabungan) adalah strategi pengelompokan hirarki yang dimulai dengan setiap objek dalam satu cluster yang terpisah kemudian membentuk cluster yang semakin membesar. Jadi, banyaknya cluster awal adalah sama dengan banyaknya objek.
Sedangkan Divisive (metode pembagian) adalah strategi pengelompokan hirarki yang dimulai dari semua objek dikelompokkan menjadi cluster tunggal kemudian dipisah sampai setiap objek berada dalam cluster yang terpisah. (Supranto, 2004)

Okay… sekarang kita hanya fokus pada cluster hirarki agglomerative method.

Teknik Agglomerative

Dalam agglomerative method, teknik pengelompokan yang paling dikenal adalah:

a. Single linkage (jarak terdekat atau tautan tunggal)
Teknik yang menggabungkan cluster-cluster menurut jarak antara anggota-anggota terdekat di antara dua cluster.

b. Average linkage (jarak rata-rata atau tautan rata-rata)
Teknik yang menggabungkan cluster-cluster menurut jarak rata-rata pasangan anggota masing-masing pada himpunan antara dua cluster.

c. Complete linkage (jarak terjauh atau tautan lengkap)
Teknik yang menggabungkan cluster-cluster menurut jarak antara anggota-anggota terjauh di antara dua cluster.

Algoritma Agglomerative

Sesuai dengan judul artikel, berikut adalah algoritma cluster hirarki agglomerative:

1. Hitung matriks jarak
Ada berbagai macam jenis jarak, namun jarak yang sering digunakan adalah Euclidean.

2. Gabungkan dua cluster terdekat
Jika jarak objek a dengan b memiliki nilai jarak paling kecil dibandingkan jarak antar objek lainnya dalam matriks jarak Euclidean, maka gabungan dua cluster pada tahap pertama adalah d_ab.

3. Perbarui matriks jarak sesuai dengan teknik pengelompokan agglomerative method
Jika d_ab adalah jarak terdekat dari matriks jarak Euclidean, maka rumus untuk metode agglomerative adalah:

4. Ulangi langkah 2 dan 3 sampai hanya tersisa satu cluster
5. Buat dendrogram

Contoh

Setelah kita tau algoritmanya, yuk sekarang kita coba praktek menggunakan data pengeluaran harian 5 orang untuk makanan dan pakaian.

Langkah pertama, hitung matriks jarak dengan rumus Euclidean.

Contoh perhitungan jarak di atas hanya dari objek A ke B sampai jarak objek A ke E, untuk perhitungan jarak yang lainnya silahkan teman-teman coba ya… Jika perhitungannya benar, nanti hasilnya akan sama dengan matriks jarak yang ada di bawah ini.

Sesuai yang telah dijelaskan sebelumnya, metode agglomerative berawal dari setiap objek berada dalam cluster yang berbeda. Jadi, matriks jarak di atas menunjukan jumlah cluster sebanyak 5.

Langkah kedua, menggabungkan dua cluster terdekat yaitu cluster B dengan E karena nilai jaraknya adalah 1.118 yang paling kecil dibandingkan yang lainnya.

Langkah ketiga, kita akan memperbarui matriks jarak menggunakan teknik pengelompokan complete linkage (algoritma yang menggunakan teknik pengelompokan single linkage bisa lihat disini).

Perhitungan tahap 1

Setelah diperoleh jarak maksimumnya, berikut adalah matriks tahap 1

Kemudian, gabungan dua cluster terdekat dari matriks tahap 1 adalah A dengan D.

Perhitungan tahap 2

Setelah diperoleh jarak maksimumnya, berikut adalah matriks tahap 2

Kemudian, gabungan dua cluster terdekat dari matriks tahap 2 adalah C dengan BE.

Perhitungan tahap 3

Setelah diperoleh jarak maksimumnya, berikut adalah matriks tahap 3

Proses pembaruan matriks jarak dengan teknik complete linkage telah selesai karena cluster yang tersisa pada matriks tahap 3 hanyalah satu. Sehingga tahap 4 memiliki satu cluster yang beranggotakan semua cluster-cluster awal.

Langkah terakhir adalah membuat dendrogram sesuai anggota cluster yang terbentuk dan nilai jarak terdekatnya.