DBSCAN

Diperbarui 2025-11-05 Baca 3 menit

Ringkasan

DBSCAN mengelompokkan titik berdasarkan kepadatan lokal sehingga bentuk klaster bisa bebas dan area jarang otomatis jadi noise.
Dua hiperparameter utama: eps (radius tetangga) dan min_samples (jumlah minimum tetangga untuk menjadi titik inti).
Setiap titik diklasifikasikan sebagai inti, tepi, atau noise; klaster terbentuk dari komponen terhubung titik inti beserta tetangga tepinya.
Biasanya min_samples dipatok terlebih dahulu (≥ dimensi + 1) lalu eps disapu sambil memonitor porsi titik yang berubah menjadi noise.

Intuisi #

Metode ini dipahami lewat asumsi dasarnya, karakteristik data, dan dampak pengaturan parameter terhadap generalisasi.

Penjelasan Rinci #

1. Gambaran umum #

DBSCAN tidak memerlukan jumlah klaster di muka. Ia menginspeksi tiap sampel:

Inti: punya ≥ min_samples tetangga dalam jarak eps.
Tepi: berada dalam radius eps dari titik inti tetapi tidak memenuhi syarat inti sendiri.
Noise: tidak berada pada tetangga inti mana pun.

Pendekatan ini membuat DBSCAN tangguh untuk pola berbentuk bulan sabit atau cincin. Pastikan fitur sudah diskalakan agar jarak bermakna.

2. Definisi formal #

Untuk (x_i \in \mathcal{X}), tetangga (\varepsilon)-nya adalah

$$ \mathcal{N}_\varepsilon(x_i) = \{ x_j \in \mathcal{X} \mid \lVert x_i - x_j \rVert \le \varepsilon \}. $$

Jika (|\mathcal{N}_\varepsilon(x_i)| \ge \texttt{min_samples}|) maka titik inti. DBSCAN memperluas klaster dengan menjelajah titik yang dapat dijangkau secara densitas dan menandai sisanya sebagai noise. Kompleksitasnya (O(n \log n)) bila memakai indeks spasial.

3. Contoh Python #

Contoh berikut menjalankan DBSCAN pada dataset dua bulan sabit, membedakan warna inti/tepi, dan menghitung jumlah noise.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from __future__ import annotations

import japanize_matplotlib
import matplotlib.pyplot as plt
import numpy as np
from numpy.typing import NDArray
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler

def run_dbscan_demo(
    n_samples: int = 600,
    noise: float = 0.08,
    eps: float = 0.3,
    min_samples: int = 10,
    random_state: int = 0,
) -> dict[str, int]:
    japanize_matplotlib.japanize()
    features, _ = make_moons(
        n_samples=n_samples,
        noise=noise,
        random_state=random_state,
    )
    features = StandardScaler().fit_transform(features)

    model = DBSCAN(eps=eps, min_samples=min_samples)
    labels = model.fit_predict(features)

    unique_labels = sorted(np.unique(labels))
    cluster_ids = [label for label in unique_labels if label != -1]
    noise_count = int(np.sum(labels == -1))

    core_mask = np.zeros(labels.shape[0], dtype=bool)
    if hasattr(model, "core_sample_indices_"):
        core_mask[model.core_sample_indices_] = True

    fig, ax = plt.subplots(figsize=(6.2, 5.2))
    palette = plt.cm.get_cmap("tab10", max(len(cluster_ids), 1))

    for order, cluster_id in enumerate(cluster_ids):
        mask = labels == cluster_id
        color = palette(order)
        ax.scatter(
            features[mask & core_mask, 0],
            features[mask & core_mask, 1],
            c=[color],
            s=36,
            edgecolor="white",
            linewidth=0.2,
            label=f"Cluster {cluster_id} inti",
        )
        ax.scatter(
            features[mask & ~core_mask, 0],
            features[mask & ~core_mask, 1],
            c=[color],
            s=24,
            edgecolor="white",
            linewidth=0.2,
            marker="o",
            label=f"Cluster {cluster_id} tepi",
        )

    if noise_count:
        noise_mask = labels == -1
        ax.scatter(
            features[noise_mask, 0],
            features[noise_mask, 1],
            c="#9ca3af",
            marker="x",
            s=28,
            linewidth=0.8,
            label="Noise",
        )

    ax.set_title("Demo DBSCAN")
    ax.set_xlabel("Fitur 1")
    ax.set_ylabel("Fitur 2")
    ax.grid(alpha=0.2)
    ax.legend(loc="upper right", fontsize=9)
    fig.tight_layout()
    plt.show()

    return {"n_clusters": len(cluster_ids), "n_noise": noise_count}

hasil = run_dbscan_demo()
print(f"Jumlah cluster: {hasil['n_clusters']}")
print(f"Jumlah noise: {hasil['n_noise']}")

Hasil DBSCAN

4. Tips praktis #

Gunakan grafik jarak tetangga ke-k (k = min_samples) untuk menemukan eps di titik siku.
Jalankan penyeragaman fitur dan clustering di pipeline yang sama.
Untuk data besar, pertimbangkan pendekatan HDBSCAN atau struktur tetangga mendekati agar pencarian tetangga lebih hemat.

5. Referensi #

Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD.
Schubert, E., Sander, J., Ester, M., Kriegel, H.-P., & Xu, X. (2017). DBSCAN Revisited, Revisited. ACM Transactions on Database Systems.
scikit-learn developers. (2024). Clustering. https://scikit-learn.org/stable/modules/clustering.html