KAL
Menu

Clustering Hierarkis

AgglomerativeClustering dan kesadaran dendrogram.

Daftar isi

Clustering hierarkis membangun pembagian klaster secara bertingkat, dari tiap titik yang berdiri sendiri hingga satu klaster besar yang memuat semuanya. Topik ini menjelaskan cara kerja AgglomerativeClustering, peran linkage dalam mengukur jarak antarklaster, dendrogram sebagai gambaran prosesnya, pilihan antara n_clusters dan distance_threshold, serta situasi ketika pendekatan ini lebih cocok daripada KMeans.

Cara kerja penggabungan berulang#

Pendekatan agglomerative, yaitu penggabungan dari bawah ke atas, memulai pekerjaannya dengan menjadikan setiap sampel satu klaster. Tahap-tahapnya berurutan sebagai berikut.

  1. Anggap setiap sampel sebagai satu klaster.
  2. Hitung jarak antar semua pasangan klaster.
  3. Gabungkan dua klaster yang jaraknya terdekat.
  4. Ulangi langkah dua dan tiga sampai tinggal satu klaster atau sampai target jumlah klaster tercapai.

Langkah ketiga membutuhkan definisi jarak antara dua klaster, dan definisi itu disebut linkage, yakni aturan yang merangkum jarak banyak anggota menjadi satu angka. Metode ward menggabungkan pasangan klaster yang menambah total kuadrat jarak ke pusat sesedikit mungkin, sehingga mengarah pada klaster berukuran mirip. Metode average menggunakan rata-rata jarak semua pasangan anggota dua klaster berbeda, sedangkan metode complete menggunakan jarak pasangan anggota terjauhnya dan menghasilkan klaster yang padat. Nilai bawaan scikit-learn adalah ward, dan aturan ward menuntut metrik Euclidean.

Seluruh proses ini deterministik karena tidak ada inisialisasi acak, sehingga hasil yang sama selalu diperoleh pada data yang sama tanpa pengaturan random_state apa pun. Prosesnya juga tidak menawarkan metode predict, karena penugasan hanya berlaku bagi sampel yang ikut digabungkan sejak awal.

Dendrogram sebagai gambaran proses#

Urutan penggabungan tersebut dapat digambar sebagai dendrogram, yaitu diagram pohon yang menyandikan setiap penggabungan sebagai sambungan horizontal pada ketinggian yang menunjukkan jarak penggabungannya. Membaca dendrogram dari bawah ke atas berarti membaca ulang seluruh proses, dari sampel tunggal hingga klaster akhir. Diagram berikut memperlihatkan bentuknya pada delapan sampel.

jarak penggabunganambang jarak12345678
Dendrogram delapan sampel dengan garis ambang jarak

Garis putus-putus pada diagram adalah distance_threshold, yakni ambang jarak yang memotong pohon. Semua penggabungan yang terjadi di bawah garis itu dibiarkan utuh, sedangkan penggabungan di atasnya dibatalkan, sehingga jumlah klaster sama dengan banyaknya batang yang terpotong. Pada diagram, potongan tersebut menghasilkan tiga klaster, yaitu kelompok sampel 1 sampai 6, sampel 7, dan sampel 8.

scikit-learn menghitung penggabungan tetapi tidak menggambar dendrogramnya. Untuk penggambaran, paket scipy.cluster.hierarchy menyediakan fungsi linkage dan dendrogram yang menjadi kebiasaan umum di kalangan pengguna, sehingga disebut di sini sebagai penunjuk saja.

Jumlah klaster: n_clusters atau distance_threshold#

AgglomerativeClustering menerima salah satu dari dua pengaturan jumlah klaster. Parameter n_clusters menetapkan targetnya secara langsung, sedangkan n_clusters=None bersama distance_threshold membiarkan jumlahnya muncul dari data. Ambang itu bekerja seperti garis potong pada dendrogram, yaitu penggabungan yang jaraknya melebihi ambang tidak dilakukan. Sapuan berikut menguji tiga nilai ambang pada data tiga klaster buatan make_blobs.

python ambang-jarak.py 
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering

X, _ = make_blobs(n_samples=300, centers=3, cluster_std=1.0, random_state=42)

for ambang in [5.0, 15.0, 30.0]:
    agg = AgglomerativeClustering(
        n_clusters=None, distance_threshold=ambang, linkage="ward"
    ).fit(X)
    print(
        f"ambang={ambang:5.1f}  jumlah klaster={agg.n_clusters_}"
        f"  ukuran={np.bincount(agg.labels_)}"
    )
text Keluaran 
ambang=  5.0  jumlah klaster=15  ukuran=[26 18 32 23 34 16 10 27 18  8 17 22 13 15 21]
ambang= 15.0  jumlah klaster=3  ukuran=[100 100 100]
ambang= 30.0  jumlah klaster=3  ukuran=[100 100 100]

Ambang 5.0 memotong pohon terlalu rendah sehingga terbentuk 15 klaster kecil. Ambang 15.0 dan 30.0 sama-sama menghasilkan tiga klaster berukuran 100, 100, dan 100, dan kesamaan pada rentang ambang yang lebar adalah tanda bahwa jumlah tiga itu merupakan struktur alami datanya. Pemakaian n_clusters_ pada kode memanfaatkan atribut yang menyimpan jumlah klaster yang ditemukan, sehingga hasilnya dapat diperiksa tanpa menghitung ulang. Sapuan ambang semacam ini berfungsi sebagai pengganti sapuan k pada KMeans, dan dataran hasilnya yang stabil lebih mudah dibaca daripada satu nilai ambang tunggal.

Demonstrasi dan kapan hierarkis berguna#

Pada data yang kelompoknya jelas, AgglomerativeClustering dan KMeans biasanya sepakat. Kode berikut menyandingkan keduanya pada data yang sama.

python hierarkis-blobs.py 
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering, KMeans

X, y = make_blobs(n_samples=300, centers=3, cluster_std=1.0, random_state=42)

agg = AgglomerativeClustering(n_clusters=3, linkage="ward").fit(X)
kmeans = KMeans(n_clusters=3, random_state=42, n_init=10).fit(X)

print("Ukuran sebenarnya :", np.bincount(y))
print("Agglomerative     :", np.bincount(agg.labels_))
print("KMeans            :", np.bincount(kmeans.labels_))
text Keluaran 
Ukuran sebenarnya : [100 100 100]
Agglomerative     : [100 100 100]
KMeans            : [100 100 100]

Kedua algoritma menemukan tiga klaster berukuran 100 tanpa keliru satu sampel pun pada data yang terpisah jelas ini. Perbedaan keduanya baru tampak pada data yang sulit, pada kebutuhan struktur bertingkat, dan pada cara memilih jumlah klaster.

Pendekatan hierarkis paling berguna pada tiga situasi. Dataset yang kecil memungkinkan biaya penggabungan berulangnya masih terjangkau, karena jumlah pasangan yang diperiksa tumbuh kuadratik terhadap jumlah sampel. Struktur bertingkat, misalnya produk yang tergabung menjadi kategori dan kategori menjadi divisi, terwakili secara alami di dalam dendrogram. Terakhir, ketika jumlah klaster belum pasti, sapuan distance_threshold memberi kesempatan melihat struktur pada beberapa ketinggian sekaligus tanpa menjalankan ulang algoritmanya.

Kesalahan umum#

Kesalahan pertama adalah menggunakan linkage="ward" pada data yang bukan Euclidean, misalnya matriks jarak yang tidak berasal dari koordinat. Ward dihitung dari kuadrat jarak ke pusat, sehingga scikit-learn menuntut metrik Euclidean untuknya, sedangkan average dan complete menerima metrik lain.

Kesalahan kedua adalah menjalankan penggabungan hierarkis pada dataset besar tanpa pertimbangan biaya. Jumlah pasangan yang diperiksa pada setiap putaran tumbuh kuadratik, sehingga puluhan ribu sampel sudah membuat prosesnya berat, dan KMeans atau DBSCAN menjadi pilihan yang lebih wajar untuk data berukuran besar.

Kesalahan ketiga adalah menganggap hasil hierarkis sama fleksibelnya dengan KMeans pada data baru. Tanpa metode predict, penambahan sampel menuntut pelatihan ulang, dan kebutuhan ini sebaiknya dipertimbangkan sejak perancangan.

Ringkasan#

  • AgglomerativeClustering memulai dari satu klaster per sampel, lalu menggabungkan pasangan terdekat berulang kali sesuai aturan linkage seperti ward, average, atau complete.
  • Dendrogram menggambarkan seluruh urutan penggabungan, dan memotongnya pada distance_threshold tertentu menentukan jumlah klaster tanpa menetapkan k.
  • Pada data tiga klaster yang jelas, AgglomerativeClustering dan KMeans sama-sama menghasilkan ukuran 100, 100, dan 100.
  • Pendekatan ini cocok untuk dataset kecil dan struktur bertingkat, tetapi biayanya tumbuh kuadratik dan tidak ada metode predict untuk sampel baru.

Referensi#