Apa itu pengelompokan hierarkis?

Clustering atau pengelompokan adalah teknik dalam machine learning yang tanpa pengawasan yang digunakan untuk mengelompokkan objek yang memiliki kesamaan. Pengelompokan hierarkis (hierarchical clustering analysis/HCA) mengelompokkan objek ke dalam struktur hierarki kluster tanpa mengikuti urutan linier. Berbagai disiplin ilmu, seperti biologi, analisis gambar dan ilmu sosial, menggunakan metode pengelompokan hierarkis untuk menjelajahi dan mengenali pola dalam kumpulan data. Beberapa contoh penggunaan antara lain mengategorikan populasi dalam penelitian klinis, segmentasi pelanggan, dan identifikasi node komunitas dalam model jaringan.

Ada dua jenis pengelompokan hierarkis:

- Pendekatan aglomeratif atau pendekatan bawah ke atas ¹ yang berulang kali menggabungkan cluster menjadi yang lebih besar sampai muncul satu cluster.

- Pendekatan divisif atau pendekatan dari atas ke bawah yang² dimulai dengan semua data dalam satu kluster dan melanjutkan untuk membagi kluster-kluster berikutnya hingga semua kluster menjadi tunggal.

Analisis pengelompokan hierarkis menimbulkan biaya komputasi yang tinggi. Meskipun penggunaan heap dapat mengurangi waktu komputasi, kebutuhan memori meningkat. Jenis pengelompokan divisif maupun aglomeratif bersifat “serakah,” yang berarti bahwa algoritma memutuskan klaster mana yang akan digabungkan atau dipecah dengan membuat pilihan optimal secara setempat pada setiap tahap proses. Selain itu, kriteria penghentian dapat diterapkan, di mana algoritma akan menghentikan aglomerasi atau memisahkan klaster setelah mencapai jumlah kluster yang telah ditentukan sebelumnya.

Diagram berbentuk pohon yang disebut dendrogram³ sering digunakan untuk memvisualisasikan hierarki kluster. Dendrogram ini menunjukkan urutan kluster yang telah digabungkan atau dibagi, serta mengilustrasikan kemiripan atau jarak antara titik data. Secara sederhana, dendrogram juga bisa dianggap sebagai daftar bersarang ⁴ yang memiliki atribut.

Algoritme pengklusteran hierarkis menggunakan matriks ketidaksamaan untuk menentukan kluster mana yang akan digabungkan atau dibagi. Ketidaksamaan ini merujuk pada jarak antara dua titik data yang dihitung berdasarkan metode keterkaitan yang dipilih. Nilai-nilai dalam matriks perbedaan menyatakan:

-Jarak⁵, jarak Euclidean sebagai contoh, antara titik tunggal dalam satu set

- Kriteria pengelompokan keterkaitan menentukan ketidaksamaan dengan mengukur jarak antar pasangan titik data dalam seluruh set

Mari kita bahas metode keterkaitan jarak Euclide yang paling umum. Contoh metrik jarak lain yang bisa digunakan mencakup jarak Minkowski, Hamming, Mahalanobis, Hausdorf, dan Manhattan. Perlu dicatat bahwa setiap metode keterkaitan akan menghasilkan klaster yang berbeda meskipun menggunakan kumpulan data yang sama. Pemilihan metode pengelompokan keterkaitan yang tepat bergantung pada berbagai faktor, seperti jenis data yang dikelompokkan, kepadatan data, bentuk klaster, serta apakah terdapat outlier atau ketidakakuratan dalam kumpulan data.

Metode keterkaitan tunggal menghitung jarak antar pasangan item dalam dua kluster dan kemudian menggunakan jarak terkecil di antara keduanya untuk menggabungkan kluster. Metode ini efektif untuk menangani bentuk kluster nonelips, namun bisa sangat dipengaruhi oleh kebisingan dan outlier. Salah satu kelemahannya adalah efek rantai⁶. Beberapa titik yang menghubungkan dua kluster dapat menyebabkan kedua kluster tersebut bergabung meskipun secara keseluruhan tidak seharusnya. Kriteria keterkaitan min dapat direpresentasikan sebagai:

 mina∈A,b∈Bd(a,b)

di mana A dan B adalah dua set pengamatan dan d adalah fungsi jarak.

Jarak antar kluster juga dapat dihitung berdasarkan titik yang paling jauh satu sama lain. Metode max cenderung kurang sensitif terhadap noise dan outlier dibandingkan dengan metode min, namun penggunaannya bisa mempengaruhi hasil, terutama jika ada kluster berbentuk globular atau besar. Metode keterkaitan max sering menghasilkan lebih banyak kluster berbentuk bola dibandingkan metode keterkaitan min. Keterkaitan maksimal dapat direpresentasikan dalam rumus:

 maxa∈A,b∈Bd(a,b)

di mana A dan B adalah dua set pengamatan dan d adalah jarak.

Metode ini, yang diperkenalkan oleh Sokal dan Michener⁷ , mendefinisikan jarak antar kluster sebagai rata-rata jarak antar pasangan titik di dalam kluster. Algoritma yang digunakan bisa berupa metode kelompok pasangan tak berbobot dengan rata-rata aritmatika (UPGMA) atau metode kelompok pasangan berbobot dengan rata-rata aritmatika (WPGMA). Arti dari "tidak terbobot" di sini adalah bahwa semua jarak memberikan kontribusi yang sama terhadap setiap rata-rata.

UPGMA diwakili dengan rumus

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

di mana *A* dan *B* adalah dua set pengamatan dan *d* adalah jarak.

WPGMA diwakili dengan rumus

 d(i∪j,k)=d(i,k)+d(j,k)2

di mana i dan j adalah cluster terdekat yang digabungkan di setiap langkah untuk membentuk cluster baru dari gabungan i dan j. Kita kemudian dapat menghitung jarak ke kluster k lainnya, yang merupakan rata-rata aritmatika dari jarak rata-rata antara titik data di k dan i dan k dan j.

Pada metode ini, jarak dihitung berdasarkan pusat kluster atau centroid. Jarak antar centroid dihitung dengan menggunakan fungsi jarak:

A-μB∥2

di mana _μA adalah titik pusat A dan _μB adalah titik pusat B.

Joe H. Ward memperkenalkan^metode minimal increase of sum of squares (MISSQ)8 pada tahun 1960-an. Setiap titik data dimulai di klusternya sendiri. Pendekatan ini berarti jumlah kuadrat antara titik data pada awalnya adalah nol, kemudian meningkat saat kita menggabungkan cluster. Metode Ward meminimalkan jumlah jarak kuadrat titik-titik dari pusat cluster saat mereka digabungkan. Metode Ward adalah pilihan yang baik untuk variabel kuantitatif⁹, dan metode ini tidak terlalu terpengaruh oleh noise atau outlier. Hal ini dapat direpresentasikan sebagai:

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

di mana rata-rata A dan rata-rata B masing-masing adalah centroid A dan B, dan x adalah titik data yang termasuk dalam gabungan A dan B

Metode varians minimum Ward dapat ditingkatkan dengan menggunakan algoritma Lance-Williams. Algoritma ini memanfaatkan rumus rekursif untuk memperbarui jarak antar kluster dan menentukan pasangan kluster terdekat yang paling optimal untuk digabungkan.

Dalam pengelompokan hierarkis aglomeratif, atau yang dikenal juga sebagai AGNES (Agglomerative Nesting), setiap titik data dimulai sebagai kluster terpisah. Algoritma ini menggunakan kriteria pengelompokan keterkaitan yang dipilih berdasarkan matriks ketidaksamaan untuk menentukan pasangan kluster mana yang akan digabungkan. Algoritma yang bergerak naik ke hierarki dan terus menggabungkan kluster hingga semuanya tergabung dalam satu, membentuk serangkaian kluster bertingkat secara hierarkis. Secara garis besar langkah pengelompokan aglomeratif¹⁰ adalah:

1. Hitung matriks perbedaan dengan menggunakan metrik jarak tertentu.

2. Tetapkan setiap titik data ke cluster.

3. Gabungkan cluster berdasarkan kriteria keterkaitan untuk kesamaan antar cluster.

4. Perbarui matriks jarak.

5. Ulangi langkah 3 dan 4 hingga hanya tersisa satu klaster atau kriteria penghentian terpenuhi.

Prinsip pengelompokan hierarkis divisif pertama kali dikembangkan oleh Macnaughton-Smith dan rekan-rekannya¹¹ pada tahun 1964, kemudian dijelajahi lebih lanjut oleh Kaufman dan Rousseeuw melalui algoritma DIANA (Divisive ANAlysis Clustering)¹² pada tahun 1990. Pengelompokan divisif menggunakan pendekatan yang berlawanan dengan pengelompokan aglomeratif. Semua titik data dimulai dalam satu kluster besar yang kemudian dibagi berulang kali menjadi beberapa kluster. Proses pemisahan ini berlangsung hingga semua kluster yang tersisa hanya berisi satu titik data atau hingga kriteria penghentian, seperti jumlah kluster yang telah ditentukan, tercapai. Metode pembagian lebih efektif dalam mengidentifikasi kumpulan data besar¹³ dan sering kali lebih akurat dibandingkan metode aglomeratif karena algoritmanya mempertimbangkan distribusi seluruh data sejak awal proses.

Untuk meningkatkan efisiensi, metode divisif menggunakan algoritma pengelompokan datar seperti k-means untuk membagi kumpulan data menjadi beberapa kluster. Jumlah kluster harus ditentukan terlebih dahulu. Algoritma k-means membagi kluster dengan cara meminimalkan jumlah kuadrat jarak antara titik data dan centroid. Proses ini dikenal sebagai kriteria inersia¹⁴. Langkah-langkah pengelompokan divisif¹⁵ adalah:

1. Mulailah dengan semua titik data untuk ukuran kumpulan data N (d1, d2, d3 ... dN) dalam satu kluster.

2. Membagi kluster menjadi dua kluster yang berbeda atau lebih heterogen dengan menggunakan metode pengelompokan datar, seperti algoritma k-means.

3. Ulangi langkah 2 dengan memilih kluster terbaik untuk dibagi, dan hapus outlier dari kluster yang paling tidak kohesif setelah setiap iterasi.

4. Berhenti ketika setiap contoh berada di cluster tunggalnya sendiri, jika tidak ulangi langkah 3.

Hasil kluster biasanya disajikan dalam bentuk dendrogram (struktur pohon biner). Sumbu x pada dendrogram mewakili titik-titik data, sementara sumbu y, atau tinggi garis, menunjukkan jarak antar kluster saat mereka digabungkan.

Anda dapat menggunakan dendrogram untuk menentukan jumlah kluster¹⁶ dalam model pengelompokan akhir. Salah satu strategi adalah dengan mengidentifikasi titik batas alami di pohon, yaitu di tempat cabang-cabang mulai menyusut dan jaraknya semakin jauh. Sebagai alternatif, jumlah kluster dapat ditentukan dengan menghitung jumlah garis vertikal yang dipotong oleh garis horizontal saat memotong dendrogram.

Dalam contoh gambar ini, garis horizontal H1memotong dua garis vertikal. Hal ini menunjukkan bahwa ada dua kluster pada titik tersebut—satu kluster berisi titik 5, 8, dan 2, sementara kluster lainnya berisi titik-titik yang tersisa. Semakin jauh garis horizontal dapat bergerak ke atas atau ke bawah tanpa memotong garis horizontal lainnya dalam dendrogram, semakin baik pilihan jumlah kluster tersebut untuk model pengelompokan Anda. Pada contoh berikutnya, garis horizontal H2 memilih empat kluster. H2 tidak bisa bergerak sejauh H1 tanpa memotong garis horizontal lain. Hal ini menunjukkan bahwa memilih dua kluster (H1) mungkin lebih tepat untuk model pengelompokan Anda.

Model pengelompokan yang baik¹⁷ akan menghasilkan kluster dengan kesamaan yang tinggi di dalam kluster dan kesamaan yang rendah antar kluster. Namun, menentukan kualitas kluster bisa sulit, dan pemilihan kriteria keterkaitan serta jumlah kluster dapat memengaruhi hasil secara signifikan. Oleh karena itu, saat membangun model pengklusteran, cobalah berbagai opsi dan pilih yang paling membantu Anda mengeksplorasi serta mengungkap pola dalam kumpulan data untuk analisis selanjutnya. Faktor-faktor yang perlu dipertimbangkan¹⁸ meliputi:

- Jumlah cluster yang praktis atau logis untuk kumpulan data (ukuran kumpulan data, bentuk kluster, noise, dan sebagainya)

- Statistik, seperti nilai rata-rata, maksimum dan minimum untuk setiap cluster

- Metrik perbedaan atau kriteria keterkaitan terbaik untuk diterapkan

- Dampak dari setiap outlier atau variabel hasil

- Pengetahuan domain atau kumpulan data tertentu

Metode lain untuk membantu menentukan jumlah cluster yang^optimal19 meliputi:

- Metode siku, di mana Anda memplot jumlah kuadrat dalam kluster terhadap jumlah kluster dan menentukan "elbow" (titik di mana plot mendatar)

- Statistik kesenjangan membandingkan jumlah kuadrat dalam klaster yang terbentuk dengan jumlah kuadrat yang diharapkan dalam distribusi referensi nol, lalu mengidentifikasi perbedaan terbesar sebagai indikator jumlah klaster yang optimal.

Pengelompokan hierarkis membantu ilmuwan data mendapatkan insight mengenai struktur dan hubungan dalam kumpulan data serta dapat diterapkan dalam berbagai contoh penggunaan.

Pengelompokan hierarkis dapat digunakan untuk menganalisis tren dan mengelompokkan data pelanggan—misalnya berdasarkan preferensi produk, demografi, perilaku pembelian, profil risiko, atau interaksi di media sosial.

Dalam penelitian klinis, jumlah pasien dapat mencapai ribuan. Pengelompokan hierarkis membantu mengelompokkan populasi yang beragam menjadi kelompok yang lebih homogen²⁰, misalnya berdasarkan kriteria diagnostik, respons fisiologis, atau mutasi DNA. Metode ini juga dapat digunakan untuk mengelompokkan spesies berdasarkan karakteristik biologis guna memahami pola evolusi.

Pengelompokan hierarkis digunakan dalam aplikasi pengenalan teks berbasis gambar untuk mengelompokkan karakter tulisan tangan berdasarkan bentuknya. Metode ini juga digunakan untuk menyimpan dan mengambil informasi dengan menggunakan kriteria tertentu atau untuk mengategorikan hasil.

Baik Python dan bahasa pemrograman R banyak digunakan dalam ilmu data. Python fleksibel dan dapat menangani spektrum tugas yang luas. Sebagai alternatif, R dirancang khusus untuk komputasi statistik dan menyediakan banyak pilihan untuk memvisualisasikan analisis pengelompokan hierarkis Anda.

Python menyediakan fungsi AgglomerativeCluster²¹ (lihat juga contoh pengelompokan aglomeratif²² pada sklearn), dan SciPy menyediakan fungsi untuk membuat plot dendrogram²³. Paket seperti dendextend²⁴ meningkatkan fungsionalitas dendrogram R, meningkatkan analisis sensitivitas dan memungkinkan Anda untuk membandingkan dan memanipulasi dendrogram yang berbeda. Untuk pengalaman langsung, lihat tutorial langkah demi langkah kami: cara menerapkan pengelompokan hierarkis di Python dan cara mengimplementasikan pengelompokan hierarkis di R.