🌲 Hierarchical Clustering & DBSCAN

Dua alternatif k-means: penggabungan bertingkat (dendrogram) dan clustering berbasis densitas (deteksi outlier).

🎬 Animasi: DBSCAN: Klaster Padat + Deteksi Noise

Titik = inti jika punya ≥ minPts tetangga dalam radius ε. Klaster tumbuh dari daerah padat; titik terisolasi = noise (dicoret).

📌 1. Hierarchical (Agglomerative) Clustering

Ide: mulai tiap titik = cluster sendiri, lalu GABUNGKAN yang terdekat,
    berulang sampai tersisa k cluster.

    ● ●   ●      ●● ●   ●     →  gabung 2 terdekat
     \ /     \ /
      ●       ●
      |       |
      ●───────●        → gabung antar-cluster
      |
      ●

LINKAGE = cara mengukur jarak antar-cluster:
• Single    : jarak titik TERDEKAT antar cluster (rawan "chain effect")
• Complete  : jarak titik TERJAUH (cluster cenderung kompak)
• Average   : jarak rata-rata semua pasangan (paling umum)

Kelebihan: tidak perlu menentukan k di awal — dendrogram (pohon penggabungan)
          menunjukkan struktur pada SEMUA level; bisa dipotong di mana saja.
Kekurangan: O(n³) — lambat untuk data besar; keputusan gabung tidak bisa dibatalkan.

📌 2. DBSCAN: Clustering Berbasis Densitas

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)
Parameter: eps (radius) dan min_samples (kerapatan minimum)

• CORE POINT    : ada ≥ min_samples titik dalam radius eps
• BORDER POINT  : bukan core, tapi berada dalam radius eps titik core
• NOISE         : sisanya → OUTLIER!

Cluster = titik core + semua border yang "terjangkau" dari core.

Kelebihan:
• Jumlah cluster TIDAK perlu ditentukan (muncul sendiri)
• Bisa menemukan cluster BENTUK APA PUN (bulan, cincin, spiral)
• BONUS: secara alami menandai OUTLIER (k-means tidak bisa!)
Kekurangan: sensitif terhadap eps; kinerja turun di densitas tidak seragam.

📌 3. Contoh: Agglomerative Clustering

print("=== AGGLOMERATIVE CLUSTERING (average linkage) ===\n")
random_seed(42)
X, y = make_blobs(60, centers=[(2, 2), (8, 3), (5, 8)], spread=0.7)

def agglomerative(X, k):
    clusters = [[i] for i in range(len(X))]
    history = []
    while len(clusters) > k:
        best = None
        for a in range(len(clusters)):
            for b in range(a + 1, len(clusters)):
                d, n = 0.0, 0
                for i in clusters[a]:
                    for j in clusters[b]:
                        d += euclidean(X[i], X[j])
                        n += 1
                d /= n
                if best is None or d < best[0]:
                    best = (d, a, b)
        d, a, b = best
        clusters[a] = clusters[a] + clusters[b]
        del clusters[b]
        history.append(d)
    return clusters, history

clusters, history = agglomerative(X, 3)

print("Sejarah penggabungan (jarak saat digabung):")
print("  merge  1: d=%.2f  (2 titik terdekat)" % history[0])
print("  merge  2: d=%.2f" % history[1])
print("  ...")
print("  merge %2d: d=%.2f" % (len(history) - 2, history[-2]))
print("  merge %2d: d=%.2f  ← gap besar = struktur alami!" % (len(history) - 1, history[-1]))

labels = [0] * len(X)
for ci, cl in enumerate(clusters):
    for i in cl:
        labels[i] = ci
print("\nUkuran cluster: %s" % [labels.count(i) for i in range(3)])
plot_points(X, labels, title="Hasil agglomerative (k=3)")

Output:

Perhatikan gap di akhir history: penggabungan antar-cluster terjadi pada jarak jauh lebih besar daripada penggabungan dalam-cluster. Gap itulah yang menunjukkan "jumlah cluster alami".

📌 4. Contoh: DBSCAN + Deteksi Outlier

print("=== DBSCAN: CLUSTER + OUTLIER ===\n")
random_seed(42)
X, y = make_moons(90, noise=0.2)
# Tambahkan 8 outlier tersebar
for _ in range(8):
    X.append([rand() * 4.0 - 2.0, rand() * 2.0 - 1.0])
    y.append(-1)

def dbscan(X, eps, min_samples):
    n = len(X)
    neigh = [[j for j in range(n) if euclidean(X[i], X[j]) <= eps]
             for i in range(n)]
    state = [0] * n          # 0=belum, 1=dikunjungi
    labels = [-1] * n        # -1 = noise
    cid = 0
    for i in range(n):
        if state[i] != 0:
            continue
        state[i] = 1
        if len(neigh[i]) < min_samples:
            continue         # (sementara) noise
        labels[i] = cid
        seeds = list(neigh[i])
        while seeds:
            j = seeds.pop()
            if state[j] == 0:
                state[j] = 1
                if len(neigh[j]) >= min_samples:
                    seeds.extend(neigh[j])
            if labels[j] == -1:
                labels[j] = cid
        cid += 1
    return labels, cid

labels, n_clusters = dbscan(X, eps=0.35, min_samples=5)
n_noise = labels.count(-1)
print("Cluster ditemukan : %d  (sebenarnya: 2)" % n_clusters)
print("Titik noise       : %d  (outlier yang ditabur: 8)" % n_noise)

# Berapa outlier asli yang tertangkap?
true_out = [i for i, l in enumerate(y) if l == -1]
caught = sum(1 for i in true_out if labels[i] == -1)
print("Outlier asli tertangkap: %d/8" % caught)

pts = []
for p, l in zip(X, labels):
    ch = "E" if l == -1 else ("o" if l == 0 else "x")
    pts.append((p[0], p[1], ch))
scatter2d(pts, title="DBSCAN: o/x = cluster, E = noise/outlier")
print("\nCoba ubah eps (0.2 / 0.6) dan min_samples (3 / 10) —")
print("lihat jumlah cluster & noise berubah drastis.")

Output:

💡 Memilih eps: plot jarak ke tetangga ke-k untuk semua titik (k-distance plot); eps berada di "lembah" sebelum kurva melonjak.

🧠 Latihan

Ganti average linkage dengan complete linkage (max jarak pasangan). Apa bedanya hasil di data blobs?
Di DBSCAN, apa yang terjadi jika eps terlalu kecil (0.1)? Terlalu besar (1.0)?
Buat data make_circles() + noise, lalu bandingkan: k-means k=2 vs DBSCAN. Siapa yang menemukan 2 cincin dengan benar?
Jelaskan kenapa hierarchical clustering tidak cocok untuk 1 juta titik, tapi DBSCAN bisa (kompleksitas & sifat algoritma).