Algorithm Agglomerative Hierarchical Clustering — and Practice with R
السَّلاَمُ عَلَيْكُمْ وَرَحْمَةُ اللهِ وَبَرَكَاتُهُ
Hai semuanyaa…
Pada kesempatan kali ini (alias the first article), aku mau sedikit cerita nih tentang algoritma cluster hirarki agglomerative.
Sebelumnya udah pada tau belum apa sih cluster itu??
Nah… buat yang masih belum tau dan pengen tau, yuk ikuti sampai selesai.
>> 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)
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.
Practice with R
Nah, setelah kita menyelesaikan contoh studi kasus sesuai dengan algoritmanya, sekarang saatnya kita selesaikan menggunakan software R.
Install package yang akan digunakan, kemudian aktifkan.
## Install package
install.packages("cluster")
install.packages("dendextend")
install.packages("factoextra")## Aktifkan package
library(cluster)
library(dendextend)
library(factoextra)
Lakukan pengecekan package yang telah diaktifkan (bila perlu).
## Cek package yang telah berhasil diaktifkan
search()
Selanjutnya, input data yang terdapat pada tabel studi kasus.
## Input data
X1 = c(2,8,9,1,8.5) #makanan
X2 = c(4,2,3,5,1) #pakaian
data1 = data.frame(X1,X2)
data1
# Memberikan nama baris pada data
rownames(data1) = c("A","B","C","D","E")
data1
Tampilkan plot data antar variabel (bila perlu).
## Melihat plot data antar variabel
plot(data1)
text(data1,rownames(data1))
Hitung matriks jarak Euclidean dengan script berikut.
## Matriks jarak Euclidean
dist(data1)
Setelah diperoleh matriks jarak, lakukan analisis cluster hirarki agglomerative dengan teknik complete linkage (penyelesaian studi kasus dengan teknik single linkage menggunakan software R bisa lihat disini).
## Cluster hirarki agglomerative dengan teknik complete linkage
hasil = hclust(dist(data1),"complete")
hasil
Berdasarkan output di atas, dapat diperoleh informasi bahwa data1 terdiri dari 5 objek yang kemudian dianalasis menggunakan jarak Euclidean dan teknik cluster complete linkage.
Setelah data berhasil dianalisis, maka langkah selanjutnya adalah menampilkan hasil cluster dalam bentuk dendrogram.
# Dendrogram
plot(hasil)
Mmm… gimana teman-teman, hasil dendrogramnya sama kan…?
Itu artinya perhitungan algoritma kita udah bener.
Nah, karena teknik complete linkage dan single linkage sudah dicoba, sekarang saatnya kalian mencoba perhitungan algoritma teknik average linkage lalu praktekkan juga dengan software R.
Script hanya berbeda pada kata “complete” yang diganti dengan kata “ave”. Script ini terletak setelah membuat matriks jarak Eulidean (silahkan scroll up kembali).
Oh iya, kalian pasti bilang “Koq praktek pada software R-nya sederhana banget sih, studi kasusnya juga dikit. Terus kalo udah jadi dendrogram, kita bisa tentukan jumlah k-nya darimana”
Eitss.. jangan salah, aku udah punya jawabannya.
Analisis cluster itu sebenarnya punya asumsi yang harus dipenuhi terlebih dulu.
Nanti, kita ulas di artikel selanjutnya menggunakan data yang lebih real alias ngga dikit-dikit banget dengan teknik average linkage.
Terus untuk penentuan jumlah k (cluster) itu bisa disesuaikan dari kita sebagai analis atau peneliti setelah melihat dendrogram. Namun, ada beberapa metode penentuan jumlah k optimum yang dapat menjadi saran untuk kita.
Silahkan kunjungi artikel aku yang kedua yaitu Hierarchical Clustering — Average Linkage with R untuk menemukan jawabannya.
Yeayy… finish !!
Selamat mencoba, semoga bermanfaat yaaa
Terimakasih sudah mampir ke sini…
وَ السَّلاَمُ عَلَيْكُمْ وَرَحْمَةُ اللهِ وَبَرَكَاتُهُ
Referensi
Supranto. (2004). Analisis Multivariat: Arti dan Interpretasi. Jakarta: PT. Rineka Cipta.
https://informatikalogi.com/algoritma-hierarchical-clustering/
http://www.yorku.ca/ptryfos/f1500.pdf
https://www.youtube.com/watch?v=bn3_KZx6pV4
