Hierarchical clustering adalah salah satu metode yang umum digunakan dalam analisis klasterisasi data. Metode ini memungkinkan kita untuk mengelompokkan data ke dalam kelompok-kelompok yang saling terkait berdasarkan tingkat kesamaan atau perbedaan antara entitas-entitas yang ada.
Dalam artikel ini, kita akan menjelajahi konsep dan penggunaan hierarchical clustering serta algoritma-algoritma yang terkait.
Apa itu Hierarchical Clustering?
Hierarchical clustering merupakan metode klasterisasi yang membangun sebuah hirarki dari data dengan cara mengelompokkan entitas-entitas yang memiliki tingkat kesamaan tertentu. Tujuan utama dari hierarchical clustering adalah untuk menghasilkan representasi visual yang menunjukkan hubungan antara entitas-entitas tersebut.
Sejarah Hierarchical Clustering
Metode ini pertama kali diperkenalkan pada tahun 1950-an dan terus mengalami perkembangan sejak saat itu. Pada awalnya, konsep Hierarchical Clustering diajukan oleh Mirkin S. Rottenberg pada tahun 1951. Namun, pada waktu itu belum ada teknologi komputasi yang memadai untuk mengimplementasikannya.
Pada tahun 1960-an, beberapa ahli statistik dan ilmu komputer mengembangkan algoritma dan metode Hierarchical Clustering yang lebih canggih. Robert L. Sibson pada tahun 1963 memperkenalkan algoritma “single linkage” yang menggabungkan klaster berdasarkan jarak terdekat antara entitas dalam klaster-klasternya.
Selanjutnya, pada tahun 1967, L.L. Cavalli-Sforza dan A. W. Edwards mengembangkan algoritma “complete linkage” yang mempertimbangkan jarak terjauh antara dua entitas dalam klaster untuk menggabungkan klaster.
Pada tahun yang sama, Maurice S. Johnson memperkenalkan algoritma “average linkage” yang menggunakan rata-rata jarak antara entitas dalam klaster untuk penggabungan klaster.
Pada tahun 1973, Joe H. Ward Jr. mengusulkan algoritma “Ward’s Method” yang menggunakan fungsi objektif untuk mengoptimalkan varian dalam klaster, sehingga menghasilkan penggabungan klaster yang memiliki kesamaan yang tinggi.
Seiring dengan perkembangan teknologi komputer, Hierarchical Clustering menjadi lebih populer dan dapat diterapkan pada dataset yang lebih besar. Algoritma dan teknik Hierarchical Clustering terus diperbaiki dan dikembangkan untuk meningkatkan kecepatan dan akurasi klasterisasi.
Hingga saat ini, Hierarchical Clustering tetap menjadi metode klasterisasi yang penting dan banyak digunakan dalam berbagai bidang seperti ilmu data, bioinformatika, pengenalan pola, dan analisis pasar.
Jenis-jenis Hierarchical Clustering
Ada dua jenis utama, yaitu agglomerative clustering dan divisive clustering.
1. Agglomerative Clustering
Agglomerative clustering, juga dikenal sebagai “bottom-up clustering,” dimulai dengan setiap objek sebagai kelompok individu. Kemudian, objek-objek yang paling mirip secara berpasangan digabungkan menjadi kelompok yang lebih besar. Proses penggabungan berlanjut hingga semua objek tergabung dalam satu kelompok.
2. Divisive Clustering
Divisive clustering, juga dikenal sebagai “top-down clustering,” dimulai dengan semua objek sebagai satu kelompok. Kemudian, kelompok tersebut dibagi menjadi kelompok yang lebih kecil berdasarkan perbedaan yang signifikan antara objek-objeknya. Proses ini berlanjut hingga setiap objek berada dalam kelompok terpisah.
Cara Kerja Hierarchical Clustering
a. Agglomerative Hierarchical Clustering
Pendekatan agglomerative dimulai dengan menganggap setiap entitas sebagai klaster tunggal. Langkah-langkah berikut ini menjelaskan cara kerjanya:
- Langkah 1: Hitung matriks jarak antara semua pasangan entitas dalam dataset. Matriks ini menggambarkan jarak antara setiap entitas.
- Langkah 2: Gabungkan dua entitas yang memiliki jarak terdekat menjadi satu klaster baru. Jarak antara klaster baru dengan klaster lain dihitung berdasarkan metode penggabungan yang dipilih (misalnya, single linkage, complete linkage, average linkage, atau metode Ward).
- Langkah 3: Perbarui matriks jarak dengan menghitung jarak antara klaster-klaster yang tersisa dan klaster baru yang terbentuk.
- Langkah 4: Ulangi langkah-langkah 2 dan 3 hingga semua entitas tergabung menjadi satu klaster besar.
Proses ini menghasilkan sebuah dendrogram, yaitu representasi visual hierarki klaster yang menunjukkan hubungan antara entitas-entitas dalam klaster.
b. Divisive Hierarchical Clustering
Pendekatan divisive dimulai dengan menganggap semua entitas sebagai satu klaster utama. Langkah-langkah berikut ini menjelaskan cara kerjanya:
- Langkah 1: Hitung matriks jarak antara semua pasangan entitas dalam dataset.
- Langkah 2: Bagi klaster awal menjadi dua klaster yang lebih kecil berdasarkan kriteria pemisahan tertentu.
- Langkah 3: Perbarui matriks jarak dengan menghitung jarak antara klaster-klaster baru yang terbentuk dan klaster yang tersisa.
- Langkah 4: Ulangi langkah-langkah 2 dan 3 hingga setiap entitas berada dalam klaster terpisah.
Proses ini juga menghasilkan sebuah dendrogram yang merepresentasikan hubungan hierarki antara entitas dalam klaster.
Metode ini memanfaatkan metrik jarak untuk mengukur tingkat kesamaan atau perbedaan antara entitas-entitas. Beberapa metrik jarak umum yang digunakan termasuk Euclidean distance, Manhattan distance, atau metrik jarak korelasi.
Dalam agglomerative hierarchical clustering, langkah penggabungan klaster didasarkan pada metode penggabungan yang dipilih.
- Single linkage menggabungkan klaster berdasarkan jarak terdekat antara dua entitas dalam klaster-klasternya.
- Complete linkage menggabungkan klaster berdasarkan jarak terjauh antara dua entitas dalam klaster-klasternya.
- Average linkage menggabungkan klaster berdasarkan rata-rata jarak antara entitas-entitas dalam klaster-klasternya.
- Metode Ward mengoptimalkan varian dalam klaster untuk menggabungkan klaster yang memiliki kesamaan yang tinggi.
Cara kerja metode ini memungkinkan identifikasi pola dan struktur dalam data, serta memberikan representasi visual yang intuitif melalui dendrogram. Dengan memahami tingkat kesamaan atau perbedaan antara entitas dalam klaster, kita dapat mengambil wawasan yang berguna dalam berbagai aplikasi seperti analisis genetika, segmentasi pasar, dan segmentasi gambar.
Kelebihan Hierarchical Clustering
Berikut ini beberapa kelebihan, antara lain:
- Tidak perlu menentukan jumlah cluster sebelumnya.
- Menghasilkan struktur hierarki yang memberikan pemahaman yang lebih mendalam tentang data.
- Tidak tergantung pada bentuk atau ukuran cluster yang sebelumnya telah ditentukan.
- Dapat mengatasi data yang memiliki pola yang kompleks.
Kelemahan Hierarchical Clustering
Meskipun memiliki kelebihan, metode ini juga memiliki beberapa kelemahan, seperti:
- Rentan terhadap noise dan data outlier.
- Memiliki kompleksitas komputasi yang tinggi, terutama pada dataset besar.
- Hasil clustering dapat dipengaruhi oleh metode penggabungan dan metode pengukuran jarak yang digunakan.
- Tidak efisien dalam mengatasi data dengan dimensi yang tinggi.
Contoh Penggunaan Hierarchical Clustering
Hierarchical clustering dapat diterapkan dalam berbagai bidang dan kasus penggunaan, seperti:
- Analisis pembagian wilayah berdasarkan karakteristik demografi, ekonomi, atau geografis.
- Pengelompokan konsumen berdasarkan perilaku pembelian atau preferensi produk.
- Segmentasi pelanggan untuk mengidentifikasi kelompok target yang berbeda.
- Analisis genetika untuk mengklasifikasikan jenis-jenis penyakit berdasarkan profil genetik.
Kesimpulan
Pada pembelajaran kita di atas dapat disimpulkan bahwa Hierarchical clustering adalah metode yang berguna dalam mengelompokkan objek atau data berdasarkan kemiripan atau kedekatan mereka. Dalam metode ini, objek-objek digabungkan secara bertahap hingga terbentuk hierarki kelompok yang lengkap. Metode ini tidak memerlukan informasi sebelumnya tentang jumlah cluster yang ada dan dapat menghasilkan struktur hierarki yang memberikan pemahaman yang lebih mendalam tentang data. Meskipun memiliki beberapa kelemahan, metode ini tetap menjadi pilihan yang populer dalam analisis data.
Artikel ini merupakan bagian dari seri artikel belajar Kecerdasan Buatan dan jika ada ide topik yang mau kita bahas silahkan komen di bawah ya.
