Hierarchical Clustering

Pengenalan Hierarchical Clustering

Hierarchical clustering adalah salah satu teknik dalam analisis klaster yang bertujuan untuk mengelompokkan data ke dalam struktur bertingkat atau hirarki. Pendekatan ini berbeda dengan metode klaster lain seperti k-means yang membutuhkan jumlah klaster ditentukan di awal. Hierarchical clustering secara bertahap menggabungkan atau memisahkan data untuk membentuk pohon klaster yang menggambarkan hubungan antar data.

Teknik ini sangat berguna ketika kita ingin memahami bagaimana data berkelompok pada berbagai level kedalaman, sehingga memberikan gambaran yang lebih fleksibel dan komprehensif tentang struktur data.

Prinsip Dasar Hierarchical Clustering

Hierarchical clustering dapat dibagi menjadi dua jenis utama berdasarkan arah proses pengelompokannya:

• Agglomerative (Bottom-Up): Dimulai dengan setiap data sebagai satu klaster terpisah, kemudian secara bertahap menggabungkan klaster-klaster yang paling mirip hingga semua data tergabung dalam satu klaster besar.
• Divisive (Top-Down): Dimulai dengan keseluruhan data sebagai satu klaster besar, lalu secara bertahap memisahkannya menjadi klaster-klaster yang lebih kecil sampai mencapai kondisi yang diinginkan.

Biasanya, metode yang paling umum digunakan adalah agglomerative karena implementasinya yang relatif lebih mudah dan hasilnya dapat divisualisasikan dalam bentuk dendrogram.

Langkah-Langkah Hierarchical Clustering

Untuk hierarchical clustering jenis agglomerative, proses umum yang terjadi sebagai berikut:

1. Inisialisasi: Anggap setiap titik data sebagai klaster tersendiri, sehingga jika ada n data, akan ada n klaster awal.
2. Hitung Jarak Antar Klaster: Menghitung jarak atau kemiripan antar pasangan klaster berdasarkan metrik tertentu, misalnya jarak Euclidean atau Manhattan.
3. Gabungkan Klaster Terdekat: Pilih dua klaster yang memiliki jarak paling kecil (atau kemiripan paling tinggi) kemudian gabungkan menjadi satu klaster baru.
4. Perbarui Matriks Jarak: Hitung ulang jarak antara klaster baru dengan klaster-klaster lainnya.
5. Ulangi: Lakukan penggabungan berulang kali sampai seluruh data tergabung dalam satu klaster besar (atau hingga memenuhi kriteria penghentian lain).

Metrik Pengukuran Jarak

Pemilihan metrik jarak sangat penting dalam hierarchical clustering karena akan menentukan bentuk dan hasil pengelompokan. Beberapa metrik jarak yang sering digunakan antara lain:

• Jarak Euclidean: d(a,b) = (a_i - b_i), paling umum digunakan, cocok untuk data kontinu.
• Jarak Manhattan: d(a,b) = |a_i - b_i|, juga dikenal sebagai jarak taksi.
• Jarak Cosine: mengukur sudut antara dua vektor, sering digunakan pada data teks atau vektor berdimensi tinggi.
• Jarak Minkowski: generalisasi jarak Euclidean dan Manhattan dengan parameter p.

Metode Penggabungan Klaster (Linkage Criteria)

Setelah jarak antar klaster dihitung, metode bagaimana jarak antar klaster dihitung saat menggabungkan klaster sangat menentukan bentuk hasil klaster. Beberapa metode linkage yang populer:

• Single Linkage: Jarak antar klaster diukur berdasarkan jarak terpendek antar elemen di dua klaster tersebut. Rentan terhadap efek ranting (chaining effect) sehingga bisa menghasilkan klaster memanjang.
• Complete Linkage: Menghitung jarak terbesar antar elemen di dua klaster yang menjadi kandidat penggabungan. Lebih ketat dan biasanya menghasilkan klaster yang lebih kompak.
• Average Linkage: Rata-rata jarak antar seluruh pasangan elemen dari dua klaster. Metode yang memberikan keseimbangan di antara single dan complete linkage.
• Centroid Linkage: Menghitung jarak antara centroid (rata-rata vektor) tiap klaster. Bisa menyebabkan masalah jika centroid berpindah posisi secara drastis.
• Wards Method: Menggabungkan dua klaster yang meminimalkan pertambahan variansi total dalam klaster hasil penggabungan. Sering menghasilkan klaster yang seimbang dan homogen.

Dendrogram: Visualisasi Hasil Hierarchical Clustering

Salah satu kekuatan utama hierarchical clustering adalah kemampuannya untuk divisualisasikan dalam bentuk dendrogram. Dendrogram adalah diagram pohon yang menunjukkan urutan penggabungan klaster dan jarak penggabungan tersebut.

Pada dendrogram, setiap daun atau ujung pohon mewakili data individual, sedangkan cabang menggambarkan penggabungan klaster. Tinggi cabang menunjukkan jarak atau kesamaan saat klaster bergabung cabang yang lebih rendah berarti data lebih mirip.

Dengan dendrogram, kita dapat memilih tingkat pemotongan (cut-off) untuk menentukan jumlah klaster yang sesuai secara visual dan kontekstual.

Kelebihan dan Kekurangan Hierarchical Clustering

Kelebihan:

• Tidak perlu menentukan jumlah klaster di awal.
• Menyediakan struktur klaster bertingkat yang kaya informasi.
• Mudah divisualisasikan dan diinterpretasi melalui dendrogram.
• Cocok untuk eksplorasi data dan memahami hubungan antar data.

Kekurangan:

• Komputasi bisa sangat mahal untuk data yang sangat besar (berskala O(n) atau lebih).
• Sensitif terhadap noise dan outlier, yang dapat mempengaruhi hasil pengelompokan.
• Hasil pengelompokan tidak dapat diubah setelah klaster bergabung (tidak fleksibel).
• Pemilihan metrik jarak dan metode linkage sangat mempengaruhi hasil akhir.

Aplikasi Hierarchical Clustering

Hierarchical clustering banyak diaplikasikan di berbagai bidang, beberapa contohnya:

• Biologi dan Genetika: mengelompokkan gen atau spesies berdasarkan kemiripan genetik.
• Analisis Pasar dan Segmentasi Pelanggan: mengelompokkan pelanggan berdasarkan perilaku pembelian untuk strategi pemasaran.
• Pengolahan Citra: segmentasi gambar sebagai dasar pengenalan pola.
• Pengolahan Teks dan Bahasa: mengelompokkan dokumen atau artikel berdasarkan konten/topik umum.
• Analisis Sosial dan Jejaring: mengidentifikasi komunitas dalam jaringan sosial.

Contoh Implementasi Sederhana dengan Python

Berikut contoh kode sederhana hierarchical clustering menggunakan pustaka scipy dan menampilkan dendrogram:

import numpy as npfrom scipy.cluster.hierarchy import dendrogram, linkageimport matplotlib.pyplot as plt# Data sampel (2D)data = np.array([    [1, 2],    [1, 4],    [1, 0],    [4, 2],    [4, 4],    [4, 0]])# Menggunakan linkage dengan metode wardZ = linkage(data, method='ward')# Membuat dan menampilkan dendrogramplt.figure(figsize=(8, 4))dendrogram(Z)plt.title('Dendrogram Hierarchical Clustering')plt.xlabel('Index Data')plt.ylabel('Jarak')plt.show()

Code di atas mengelompokkan enam titik data dalam ruang dua dimensi dan menampilkan pohon pengelompokan secara visual.

Kesimpulan

Hierarchical clustering adalah metode klaster yang sangat berguna untuk memahami struktur data secara bertingkat tanpa harus menentukan jumlah klaster sebelumnya. Kemampuan visualisasi melalui dendrogram memungkinkan analisis yang lebih intuitif dan mendalam.

Meski memiliki keterbatasan dalam hal efisiensi komputasi dan sensitivitas terhadap data, teknik ini tetap menjadi pilihan utama dalam banyak kasus eksplorasi data dan pengelompokan yang memerlukan pemetaan hubungan yang kompleks antar data.