Agglomerative Hierarchical Clustering (AHC)

 Agglomerative Hierarchical Clustering (AHC)

A.    Pengertian Agglomerative Hierarchical Clustering (AHC)

Agglomerative Hierarchical Clustering adalah suatu metode hierarchical clustering yang bersifat bottom-up yaitu menggabungkan n buah klaster menjadi satu klaster tunggal. Metode ini dimulai dengan meletakkan setiap objek data sebagai sebuah klaster tersendiri (atomic cluster) dan selanjutnya menggabungkan klaster-klaster tersebut menjadi klaster yang lebih besar dan lebih besar lagi sampai akhirnya semua objek data menyatu dalam sebuah klaster tunggal. Kunci dari metode AHC adalah perhitungan proximity antara 2 klaster. Perhitungan ini terbagi menjadi 3 yaitu Single Linkage (jarak terkecil), Complete Linkage (jarak terbesar) dan Average Linkage (jarak ratarata). karena metode hirarki tidak dapat menghasilkan klaster secara langsung, maka digunakan metode cophenet distance untuk menganalisis hasil hirarki yang terbentuk. Dari hasil yang didapat menunjukkan bahwa Agglomerative Hierarchical Clustering (AHC) dapat digunakan untuk pengelompokan data.

Agglomerative Hierarchical Clustering merupakan metode dengan menggunakan strategi disain Bottom-Up yang dimulai dengan meletakkan setiap obyek sebagai sebuah cluster tersendiri (atomic cluster) dan selanjutnya menggabungkan atomic cluster – atomic cluster tersebut menjadi cluster yang lebih besar dan lebih besar lagi sampai akhirnya semua obyek menyatu dalam sebuah cluster atau proses dapat pula berhenti jika telah mencapai batasan kondisi tertentu

B.    Analisis Cluster

Cluster atau klaster adalah sebutan lain dari “kelompok” atau “grup”.
Lalu apa itu analisis cluster?

Analisis cluster merupakan metode pengelompokan multivariat (banyak variabel) dengan tujuan utama yaitu mengelompokkan objek berdasarkan kemiripan karakteristik yang dimilikinya. Analisis cluster terbagi menjadi dua metode yaitu hirarki dan non-hirarki.
Pada artikel ini, bagian cluster yang akan dibahas hanya metode hirarki saja.

Metode Cluster Hirarki

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)

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.

C.    Langkah – Langkah Algoritma AHC

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.

Matriks jarak Euclidean

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

Matriks pembaruan 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

Matriks pembaruan 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

Matriks pembaruan 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.

Dendrogram dari algoritma metode agglomerative dengan teknik complete linkage

Wassalamu’aliakum warahmatullah wabarakatuh. Sekian dan Terima kasih 😊