Hierarchical Clustering

k-means memaksa kita menembakkan angka k sebelum melihat strukturnya. Hierarchical clustering membalik alurnya: algoritme membangun seluruh tangga pengelompokan dari data — dari “tiap titik adalah klaster sendiri” sampai “semua titik menjadi satu klaster” — dan kita baru memutuskan di mana memotong tangga itu setelah melihat bentuknya. Untuk membedah mekanismenya sampai ke butir terakhir, chapter ini memakai 12 pelanggan ritel yang kita tulis tangan: cukup kecil agar setiap penggabungan bisa dibaca satu per satu, cukup nyata untuk tetap bercerita tentang segmentasi.

Agglomerative: Menggabung dari Bawah #

Hierarchical clustering punya dua arah. Divisive mulai dari satu klaster raksasa lalu membelah berulang; agglomerative bekerja sebaliknya dan jauh lebih umum. Alurnya: mulailah dengan tiap titik sebagai klaster tunggal, hitung jarak antar semua pasangan klaster, gabungkan pasangan terdekat, perbarui jarak, lalu ulangi sampai tersisa satu klaster besar. Untuk n titik, prosesnya tepat n - 1 penggabungan — 12 pelanggan berarti 11 langkah yang semuanya tercatat.

Kriteria Linkage Menentukan Karakter #

“Jarak antar klaster” tidak punya satu definisi — dan pilihan definisinya, disebut linkage, mengubah hasil akhir. Empat kriteria standar:

Efek rantai pada single linkage layang diwaspadai: karena hanya butir terdekat yang dihitung, dua gumpalan yang benar-benar terpisah bisa tersambung pelan-pelan lewat titik-titik jembatan di antaranya — klaster memanjang tak berbentuk. Ward, pilihan default AgglomerativeClustering di scikit-learn, secara konsep bersaudara dengan k-means: keduanya menghukum jarak kuadrat terhadap pusat, sehingga keduanya menyukai gumpalan bulat dan sama-sama membutuhkan scaling fitur.

Membaca Dendrogram #

Hasil agglomerative biasanya digambar sebagai dendrogram: daun-di-bawah adalah titik data, dan tinggi tempat dua cabang bertemu menyatakan jarak saat keduanya digabung. Semakin tinggi pertemuan, semakin “reluktang” dua kelompok itu digabungkan. Jarak penggabungan yang mendadak melonjak adalah sinyal batas klaster alami — memotong tangga tepat di bawah lonjakan menghasilkan segmentasi yang bermakna, dan memotong pada ketinggian berbeda memberi jumlah klaster berbeda tanpa perlu melatih ulang.

Fungsi dendrogram milik scipy menggambar pohon itu; pada contoh kita, isi pohon yang sama dibaca dari matriks linkage — satu baris per penggabungan dengan format [indeks_A, indeks_B, jarak, jumlah_titik]. Indeks bernilai n ke atas menunjuk klaster hasil penggabungan sebelumnya, bukan titik asli. Membaca angka mentah ini membuat mekanismenya tak terselubung — dan sepenuhnya deterministik.

Perbandingan dengan k-Means #

Praktik: Kronik Penggabungan 12 Pelanggan #

# Hierarchical clustering: tangga penggabungan dari 12 pelanggan.
# Kisah: 12 pelanggan digabung bertahap dari bawah ke atas (agglomerative).

from itertools import permutations

import numpy as np
from scipy.cluster.hierarchy import fcluster, linkage
from sklearn.cluster import AgglomerativeClustering, KMeans

# 12 pelanggan ritel: [kunjungan per bulan, rata-rata belanja (juta Rp)].
# Tiga kelompok alami, masing-masing berisi 4 pelanggan.
X = np.array([
    [1.0, 1.2], [1.4, 0.8], [0.8, 1.5], [1.6, 1.4],   # hemat
    [4.5, 3.8], [5.0, 4.2], [4.2, 4.5], [5.4, 3.6],   # rutin
    [8.2, 7.8], [8.8, 8.4], [7.8, 8.8], [9.0, 7.6],   # premium
])

# 1) Matriks linkage: kronik 11 penggabungan (n - 1 langkah).
# Format tiap baris: [indeks A, indeks B, jarak, jumlah titik tergabung].
# Indeks >= 12 menunjuk klaster hasil penggabungan sebelumnya.
Z = linkage(X, method="ward")
print("Matriks linkage (metode ward):")
print("  langkah  gabung    jarak   titik tergabung")
for i, baris in enumerate(Z):
    a, b, jarak, n = int(baris[0]), int(baris[1]), baris[2], int(baris[3])
    print(f"  {i + 1:>2}       {a:>2}+{b:<2}   {jarak:6.3f}   {n:>2}")

# 2) Memotong tangga pada ketinggian berbeda -> jumlah klaster berbeda.
print("\nMemotong tangga pada ketinggian berbeda:")
for tinggi in [2.0, 10.0]:
    label_potong = fcluster(Z, t=tinggi, criterion="distance")
    banyak = len(set(label_potong.tolist()))
    print(f"  tinggi {tinggi:>4.1f} -> {banyak} klaster: {label_potong.tolist()}")

# 3) Bandingkan hasilnya dengan k-means pada data yang sama.
label_agglo = AgglomerativeClustering(n_clusters=3, linkage="ward").fit_predict(X)
label_km = KMeans(n_clusters=3, n_init="auto", random_state=42).fit_predict(X)
print("\nLabel 12 pelanggan:")
print(f"  agglomerative: {label_agglo.tolist()}")
print(f"  k-means      : {label_km.tolist()}")

# 4) Kesepakatan setelah nomor klaster diselaraskan (permutasi terbaik).
terbaik = max(
    sum(1 for a, k in zip(label_agglo, label_km) if p[a] == k)
    for p in permutations(range(3))
)
print(f"Kesepakatan setelah penomoran diselaraskan: {terbaik}/12 titik")

Output yang Dihasilkan:

Matriks linkage (metode ward):
  langkah  gabung    jarak   titik tergabung
   1        0+2     0.361    2
   2        1+3     0.632    2
   3        4+5     0.640    2
   4        9+11    0.825    2
   5        8+15    0.841    3
   6        6+14    0.858    3
   7       12+13    0.919    4
   8        7+17    1.234    4
   9       10+16    1.501    4
  10       18+19    9.082    8
  11       20+21   17.943   12

Memotong tangga pada ketinggian berbeda:
  tinggi  2.0 -> 3 klaster: [2, 2, 2, 2, 3, 3, 3, 3, 1, 1, 1, 1]
  tinggi 10.0 -> 2 klaster: [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1]

Label 12 pelanggan:
  agglomerative: [2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0]
  k-means      : [2, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1]
Kesepakatan setelah penomoran diselaraskan: 12/12 titik

Mari kita bedah hasil eksekusinya:

1. Baris 24–26 (kronik penggabungan): sembilan langkah pertama hanya menggabungkan tetangga dekat — jaraknya 0,361 sampai 1,501, dan kelompok hemat, rutin, premium terkumpul utuh menjadi tiga klaster berisi 4 titik. Langkah 10 melonjak ke 9,082 (dua kelompok dipaksa bergabung jadi 8 titik), langkah 11 ke 17,943 (segalanya menyatu). Dua lonjakan itulah batas klaster alami pada dendrogram.
2. Baris 29–33 (potong tangga): memotong pada ketinggian 2,0 membiarkan sembilan penggabungan kecil terjadi tapi menghentikan dua lonjakan besar — hasilnya tepat 3 klaster [2,2,2,2, 3,3,3,3, 1,1,1,1]. Ketinggian 10,0 mengizinkan satu lonjakan tambahan — kelompok hemat dan rutin melebur sehingga tinggal 2 klaster. Jumlah klaster berubah tanpa satu kali pun melatih ulang; inilah fleksibilitas utama pendekatan hierarkis.
3. Baris 36–40 (dua algoritme, satu data): AgglomerativeClustering(n_clusters=3, linkage="ward") dan k-means menghasilkan daftar label yang tampak berbeda — [2,2,2,2, 1,1,1,1, 0,0,0,0] versus [2,2,2,2, 0,0,0,0, 1,1,1,1]. Jangan tertipu: penomoran klaster tetap sembarang pada kedua algoritme.
4. Baris 43–47 (permutasi terbaik): karena nomor tidak bisa dibandingkan langsung, kode mencoba keenam pemetaan angka yang mungkin dan mengambil yang paling banyak menyamai. Hasilnya 12/12 — kedua algoritme sepenuhnya setuju tentang pembagian dua belas pelanggan ini, hanya berbeda cara menomorinya.

Baik k-means maupun Ward sama-sama menghendaki gumpalan bulat berukuran serupa — asumsi yang mudah dilanggar data nyata. Bagaimana jika klaster Anda berbentuk sabit melengkung, atau justru ingin mengenali titik yang tidak masuk kelompok mana pun? Chapter DBSCAN menjawab keduanya sekaligus dengan cara berpikir yang sepenuhnya berbeda: kepadatan.

Referensi Resmi #

• Hierarchical clustering — scikit-learn User Guide — penjelasan resmi agglomerative clustering dan kriteria linkage.
• sklearn.cluster.AgglomerativeClustering — API Reference — parameter lengkap estimatornya.
• scipy.cluster.hierarchy.linkage — SciPy Documentation — format matriks linkage yang kita cetak pada contoh.