Hierarchical Clustering

K-Means menuntut satu keputusan yang kadang sulit: jumlah kelompok k harus ditetapkan sebelum kita melihat apa pun. Hierarchical clustering membalik urutannya — algoritma membangun dulu seluruh pohon pengelompokan dari titik paling individual sampai semua menyatu, lalu kita memotong pohon itu kapan pun sesuai kebutuhan. Keluarga ini juga menghasilkan satu karya yang tidak dimiliki K-Means: dendrogram, diagram pohon yang memperlihatkan proses penggabungan dan jaraknya. Pada chapter ini kita memakai data sembilan cabang Toko Kopi Kita, membangun hierarki dengan aturan ward lewat SciPy, membaca dendrogramnya, dan membandingkan beberapa aturan linkage yang berbeda hasilnya.

Agglomerative: Menggabungkan dari Bawah #

Ada dua arah membangun hierarki: divisive yang memecah dari satu kelompok besar ke bawah, dan agglomerative yang menggabungkan dari bawah ke atas. Yang umum dipakai — dan yang kita bahas — adalah agglomerative:

1. Mulai dari per titik: setiap cabang adalah klaster beranggotakan satu.
2. Cari dua klaster terdekat menurut aturan jarak antar klaster (linkage).
3. Gabungkan keduanya menjadi satu klaster; catat jarak penggabungannya.
4. Ulangi langkah 2-3 sampai semua titik menyatu dalam satu klaster besar.

Hasil akhirnya bukan satu pembagian, melainkan rangkaian penggabungan dari halus ke kasar — seperti foto perjalanan yang bisa kita jeda di titik mana pun. “Jarak antar klaster” sendiri punya beberapa definisi, dan pilihan ini mengubah hasil:

Data: Sembilan Cabang Toko Kopi Kita #

Kita bekerja dengan sembilan cabang yang masing-masing dicatat penjualan harian dan jumlah pelanggan per harinya. Sebelum menghitung jarak, kedua fitur kita standarisasi — penjualan (180-610 ribu) dan pelanggan (55-150 orang) tidak boleh saling meniadakan:

Matriks Linkage dan Memotong Pohon #

Fungsi linkage dari scipy.cluster.hierarchy menjalankan agglomerative dan mengembalikan matriks penggabungan — satu baris per penggabungan, berisi indeks dua klaster yang digabung, jaraknya, dan jumlah anggota hasilnya:

import numpy as np
from scipy.cluster.hierarchy import fcluster, linkage
from sklearn.preprocessing import StandardScaler

# Sembilan cabang Toko Kopi Kita: (penjualan harian ribu Rp, pelanggan per hari)
cabang = np.array([
    [520, 140],  # bandung
    [180, 55],   # cimahi
    [610, 150],  # jakarta
    [300, 80],   # bogor
    [330, 85],   # bekasi
    [280, 75],   # depok
    [580, 145],  # surabaya
    [200, 60],   # malang
    [420, 105],  # cirebon
])
nama = ["bandung", "cimahi", "jakarta", "bogor", "bekasi", "depok",
        "surabaya", "malang", "cirebon"]

fitur_z = StandardScaler().fit_transform(cabang)

Z = linkage(fitur_z, method="ward")
print("Matriks linkage (tiap baris = satu penggabungan):")
print("titik_a  titik_b  jarak  jumlah_anggota")
for a, b, j, n in Z:
    print("%6.0f %8.0f %7.2f %8.0f" % (a, b, j, n))

label = fcluster(Z, t=3, criterion="maxclust")
print()
print("Hasil memotong pohon menjadi 3 klaster:")
for n, l in sorted(zip(nama, label), key=lambda x: (x[1], x[0])):
    print("  %-9s -> klaster %d" % (n, l))

Output yang Dihasilkan:

Matriks linkage (tiap baris = satu penggabungan):
titik_a  titik_b  jarak  jumlah_anggota
     1        7    0.19        2
     3        5    0.19        2
     2        6    0.24        2
     4       10    0.39        3
     0       11    0.62        3
     8       12    1.29        4
     9       14    2.04        6
    13       15    5.43        9

Hasil memotong pohon menjadi 3 klaster:
  bandung   -> klaster 1
  jakarta   -> klaster 1
  surabaya  -> klaster 1
  cimahi    -> klaster 2
  malang    -> klaster 2
  bekasi    -> klaster 3
  bogor     -> klaster 3
  cirebon   -> klaster 3
  depok     -> klaster 3

Mari kita telaah baris-baris kode dan hasilnya:

1. StandardScaler().fit_transform(cabang) menyeragamkan kedua fitur menjadi z-skor; seluruh jarak pada matriks linkage berada dalam satuan ini.
2. linkage(fitur_z, method="ward") mengembalikan matriks 8 baris — selalu n-1 baris untuk n titik, karena setiap penggabungan mengurangi jumlah klaster satu.
3. Baris pertama matriks (1 7) berarti titik indeks 1 (cimahi) digabung dengan indeks 7 (malang) pada jarak 0,19 — dua cabang kecil yang paling mirip. Indeks n ke atas (misal 10) merujuk klaster hasil penggabungan sebelumnya: baris keempat menggabungkan bekasi (indeks 4) dengan klaster hasil bogor+depok (indeks 9+1=10).
4. fcluster(Z, t=3, criterion="maxclust") memotong pohon sehingga diperoleh paling banyak tiga klaster — inilah jawaban atas kelemahan K-Means: k dipilih SETELAH pohon jadi, bukan sebelumnya.
5. Hasil potongannya masuk akal secara geografis dan skala usaha: kota besar (jakarta, surabaya, bandung), kota kecil (cimahi, malang), dan kota penengah Jabodetabek termasuk cirebon yang ukurannya memang di antara.

Perhatikan kolom jarak: 0,19 - 0,19 - 0,24 - 0,39 - 0,62 adalah penggabungan halus antar tetangga dekat, lalu melonjak ke 1,29 - 2,04 - 5,43 saat kelompok-kelompok yang berbeda karakter dipaksa menyatu. Lonjakan jarak inilah sinyal alami di mana pohon sebaiknya dipotong — dipaksa menggabungkan jakarta dengan cimahi (jarak 5,43) jelas lain cerita dengan menggabungkan bogor dan depok (0,19).

Membaca Dendrogram #

Matriks linkage sulit dibayangkan; dendrogram menggambarkannya langsung. Diagram ini kita buat dengan dendrogram dari SciPy dan matplotlib:

import matplotlib.pyplot as plt
import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.preprocessing import StandardScaler

# Sembilan cabang Toko Kopi Kita: (penjualan harian ribu Rp, pelanggan per hari)
cabang = np.array([
    [520, 140],  # bandung
    [180, 55],   # cimahi
    [610, 150],  # jakarta
    [300, 80],   # bogor
    [330, 85],   # bekasi
    [280, 75],   # depok
    [580, 145],  # surabaya
    [200, 60],   # malang
    [420, 105],  # cirebon
])
nama = ["bandung", "cimahi", "jakarta", "bogor", "bekasi", "depok",
        "surabaya", "malang", "cirebon"]

fitur_z = StandardScaler().fit_transform(cabang)
Z = linkage(fitur_z, method="ward")

plt.figure(figsize=(8, 4))
dendrogram(Z, labels=nama, leaf_rotation=45)
plt.ylabel("Jarak penggabungan (data z-skor)")
plt.title("Dendrogram sembilan cabang Toko Kopi Kita")
plt.tight_layout()
plt.show()

Bentuk gambarnya dapat dibayangkan seperti pohon tumbuh terbalik: di dasar (daun) tertulis sembilan nama cabang; cimahi dan malang bergabung di ketinggian rendah (0,19), begitu pula bogor-depok; batang jakarta-surabaya menyatu di 0,24 lalu menerima bandung di 0,62; bekasi bergabung dengan klaster bogor-depok membentuk kabilah Jabodetabek; dan cirebon menyusul bergabung dengan kabilah itu pada ketinggian 1,29. Di puncak, dua sub-pohon besar — kota besar versus gabungan Jabodetabek — baru menyatu di ketinggian 5,43. Semakin tinggi dua cabang bertemu, semakin berbeda karakternya; memotong garis horizontal di ketinggian 3 akan memisahkan tiga kelompok yang sama dengan hasil fcluster di atas.

Perbandingan Aturan Linkage #

Aturan linkage bukan sekadar selera — pada data dengan titik jembatan, hasilnya benar-benar berbeda. Kita ulangi potongan tiga klaster dengan empat aturan sekaligus:

import numpy as np
from scipy.cluster.hierarchy import fcluster, linkage
from sklearn.preprocessing import StandardScaler

# Sembilan cabang Toko Kopi Kita: (penjualan harian ribu Rp, pelanggan per hari)
cabang = np.array([
    [520, 140],  # bandung
    [180, 55],   # cimahi
    [610, 150],  # jakarta
    [300, 80],   # bogor
    [330, 85],   # bekasi
    [280, 75],   # depok
    [580, 145],  # surabaya
    [200, 60],   # malang
    [420, 105],  # cirebon
])
nama = ["bandung", "cimahi", "jakarta", "bogor", "bekasi", "depok",
        "surabaya", "malang", "cirebon"]

fitur_z = StandardScaler().fit_transform(cabang)

print("Perbandingan aturan linkage, dipotong menjadi 3 klaster:")
for metode in ["single", "complete", "average", "ward"]:
    Z = linkage(fitur_z, method=metode)
    label = fcluster(Z, t=3, criterion="maxclust")
    kelompok = {}
    for n, l in zip(nama, label):
        kelompok.setdefault(l, []).append(n)
    bagan = " | ".join("+".join(sorted(v)) for k, v in sorted(kelompok.items()))
    print("  %-9s: %s" % (metode, bagan))

Output yang Dihasilkan:

Perbandingan aturan linkage, dipotong menjadi 3 klaster:
  single   : bandung+jakarta+surabaya | bekasi+bogor+cimahi+depok+malang | cirebon
  complete : bandung+jakarta+surabaya | cimahi+malang | bekasi+bogor+cirebon+depok
  average  : bandung+jakarta+surabaya | bekasi+bogor+cimahi+depok+malang | cirebon
  ward     : bandung+jakarta+surabaya | cimahi+malang | bekasi+bogor+cirebon+depok

Bedah hasilnya per aturan:

1. ward dan complete sepakat membagi menjadi kota besar, kota kecil, dan Jabodetabek+direbon — potongan yang sejalan dengan intuisi skala usaha.
2. single merantai: karena hanya melihat pasangan titik terdekat, kota kecil (cimahi, malang) terseret masuk kelompok Jabodetabek — jarak malang-depok memang cukup dekat, dan rantai terus menjalar. Akibat sampingnya, cirebon yang posisinya di antara dua dunia justru terkucur sendiri.
3. average mengikuti single pada data ini: rata-rata jarak masih dipengaruhi pasangan-pasangan dekat antar klaster.
4. Moralnya: klaster memanjang yang saling terhubung lewat titik-titik jembatan adalah wilayah rawan single; ward lebih tahan karena menilai kenaikan variansi keseluruhan, bukan satu pasangan terdekat.

Hierarchical vs K-Means #

Hierarchical unggul saat data berukuran sedang (ratusan sampai ribuan titik), saat kita ingin memahami tingkatan pengelompokan — misalnya cabang, area, region — atau saat jumlah kelompok belum bisa diputuskan sejak awal. Untuk jutaan titik, K-Means tetap pilihan realistis.

Rangkuman #

• Agglomerative clustering memulai dari per titik dan menggabungkan dua klaster terdekat berulang kali sampai semua menyatu; seluruh sejarahnya terekam di matriks linkage.
• fcluster(..., criterion="maxclust") memotong pohon menjadi paling banyak t klaster — jumlah kelompok dipilih setelah hasilnya terlihat, menjawab kelemahan utama K-Means.
• Dendrogram menggambarkan proses itu: ketinggian pertemuan = jarak penggabungan; lonjakan jarak adalah kandidat tempat pemotongan.
• Aturan linkage mengubah hasil: single mudah merantai kelompok memanjang, ward dan complete memberikan potongan lebih kompak.
• Biaya hierarki adalah matriks jarak O(n²) — untuk data besar, K-Means tetap yang paling praktis.

Hierarchical dan K-Means sama-sama bekerja dengan jarak antar titik, sehingga keduanya berorientasi gumpalan. Bagaimana dengan data yang klasternya berbentuk lengkung, atau bercampur titik-titik pencilan yang tidak masuk kelompok mana pun? Keluarga berikutnya menjawab dengan logika yang sama sekali berbeda: kepadatan. Lanjut ke chapter Density-Based Clustering .

Referensi #

1. scikit-learn — Clustering
2. Matplotlib — User Guide