Bài 35: DBSCAN — clustering dựa trên mật độ, phát hiện anomaly

K-Means (Bài 32) gom điểm quanh \( K \) centroid, giả định cluster có dạng cầu và kích thước tương đương. Cần biết \( K \) trước, mọi điểm đều bị gán vào một cluster — không có khái niệm "điểm thừa".

Hierarchical Clustering (Bài 34) không cần \( K \) tại thời điểm fit (cắt dendrogram lúc nào cũng được), nhưng độ phức tạp \( O(n^2) \) đến \( O(n^3) \) khiến nó không scale với dataset lớn, và vẫn không có khái niệm noise — mọi điểm thuộc về một nhánh nào đó của cây.

Cả hai bí trên hai dạng dữ liệu phổ biến: cluster phi cầu (hình moon, ring, spiral, dải dài) và dữ liệu có outlier rải rác. DBSCAN xử lý chính hai trường hợp này, đổi lại đặt ra hai tham số mới cần tune: eps và min_samples.

DBSCAN — Density-Based Spatial Clustering of Applications with Noise (Ester, Kriegel, Sander, Xu — KDD 1996). Ý tưởng cốt lõi: một cluster là vùng dày đặc các điểm trong không gian feature, ngăn cách với cluster khác bởi vùng thưa. Điểm nằm trong vùng thưa và không thuộc vùng dày đặc nào → noise.

Khác biệt then chốt với K-Means / Hierarchical:

• Không cần \( K \). Số cluster do dữ liệu tự quyết định, phụ thuộc cấu trúc mật độ.
• Cluster có hình dạng bất kỳ. Concave, ring, moon, spiral — miễn là kết nối qua mật độ thì DBSCAN nhận ra.
• Có khái niệm noise. Điểm không đủ mật độ xung quanh được gán nhãn \( -1 \), không bị ép vào cluster nào.

Đánh đổi: thay vì chọn \( K \), phải chọn \( \varepsilon \) (bán kính láng giềng) và min_samples (số điểm tối thiểu định nghĩa "dày"). Hai tham số này quyết định toàn bộ kết quả.

• \( \varepsilon \) (eps) — bán kính của vùng láng giềng quanh một điểm. \( \varepsilon \)-neighborhood của điểm \( p \) là tập \( N_\varepsilon(p) = \{ q \in D : d(p, q) \leq \varepsilon \} \).
• min_samples — số điểm tối thiểu (kể cả chính nó) phải có trong \( N_\varepsilon(p) \) để \( p \) được coi là core point — tâm của một vùng đủ "dày".

Hai tham số định nghĩa "mật độ tối thiểu" cùng nhau: một vùng được coi là dày nếu trong bán kính \( \varepsilon \) có ít nhất min_samples điểm. eps nhỏ + min_samples lớn → tiêu chuẩn dày khắt khe → nhiều noise. eps lớn + min_samples nhỏ → tiêu chuẩn lỏng → các cluster có thể merge với nhau.

Khoảng cách \( d \) mặc định là Euclidean, có thể đổi sang Manhattan, cosine, hoặc custom metric.

DBSCAN phân điểm trong dataset thành ba loại:

• Core point — có \( |N_\varepsilon(p)| \geq \) min_samples. Đây là "tâm dày" của cluster. Mỗi cluster phải có ít nhất một core point.
• Border point — không đủ tiêu chuẩn core, nhưng nằm trong \( N_\varepsilon(q) \) của một core point \( q \) nào đó. Border point nằm ở rìa cluster, được gán nhãn cluster của core point gần nhất.
• Noise point — không phải core, cũng không phải border. Nhãn cluster là \( -1 \). Không thuộc về cluster nào.

Một điểm có thể đổi loại khi tham số đổi. Tăng eps: điểm noise có thể trở thành border, border có thể trở thành core. Giảm min_samples: nhiều điểm core hơn, ít noise hơn.

Lưu ý kỹ thuật: một border point có thể nằm trong \( \varepsilon \) của hai core point thuộc hai cluster khác nhau. sklearn gán nó vào cluster nào tới trước trong thứ tự duyệt — kết quả phụ thuộc thứ tự dữ liệu một chút, nhưng cluster core (vùng lõi) thì hoàn toàn xác định.

Hai khái niệm hình thức hoá "cùng cluster":

• Directly density-reachable: \( p \) trực tiếp density-reachable từ \( q \) nếu \( q \) là core và \( p \in N_\varepsilon(q) \). Quan hệ không đối xứng — \( q \) có thể không reachable từ \( p \) nếu \( p \) là border.
• Density-reachable: \( p \) density-reachable từ \( q \) nếu tồn tại chuỗi core point \( q = p_1, p_2, \ldots, p_n = p \) sao cho mỗi \( p_{i+1} \) trực tiếp density-reachable từ \( p_i \). Chain mở rộng cluster theo "đường dày" — mỗi bước nhảy không xa hơn \( \varepsilon \), đi qua các core point.
• Density-connected: \( p \) và \( q \) density-connected nếu tồn tại core point \( o \) sao cho cả \( p \) và \( q \) đều density-reachable từ \( o \). Quan hệ đối xứng — dùng để định nghĩa cluster.

Định nghĩa hình thức: một cluster là tập tối đại các điểm density-connected với nhau. Hệ quả: hai điểm cùng cluster có thể cách nhau rất xa, miễn là có một "đường mật độ" nối chúng qua các core point.

Đây là lý do DBSCAN bắt được cluster dạng moon, ring, spiral: không quan trọng hai đầu xa nhau, quan trọng là dải core point liên tục dày.

Pseudocode rút gọn:

def dbscan(X, eps, min_samples):
    labels = [UNVISITED] * len(X)
    cluster_id = 0
    for p in range(len(X)):
        if labels[p] != UNVISITED:
            continue
        neighbors = region_query(X, p, eps)         # N_eps(p)
        if len(neighbors) < min_samples:
            labels[p] = NOISE                       # tam thoi, co the bi sua
            continue
        # p la core point, mo cluster moi
        cluster_id += 1
        expand_cluster(X, labels, p, neighbors, cluster_id, eps, min_samples)
    return labels

def expand_cluster(X, labels, p, neighbors, cid, eps, min_samples):
    labels[p] = cid
    queue = list(neighbors)
    while queue:
        q = queue.pop(0)
        if labels[q] == NOISE:
            labels[q] = cid                          # border point cua cluster nay
        if labels[q] != UNVISITED:
            continue
        labels[q] = cid
        q_neighbors = region_query(X, q, eps)
        if len(q_neighbors) >= min_samples:          # q cung la core -> lan rong
            queue.extend(q_neighbors)

Hai chi tiết quan trọng:

• Một điểm bị gán NOISE ở vòng ngoài vẫn có thể được "cứu" thành border khi vòng expand_cluster sau này gặp nó qua một core point khác.
• region_query là hot path. Naive \( O(n) \) cho mỗi query → tổng \( O(n^2) \). sklearn dùng ball tree hoặc kd-tree đưa về \( O(n \log n) \) trung bình; trong high-dim, tree không hiệu quả nữa và phức tạp quay lại \( O(n^2) \).

from sklearn.cluster import DBSCAN

db = DBSCAN(eps=0.5, min_samples=5, metric="euclidean", n_jobs=-1)
labels = db.fit_predict(X)

# labels == -1 la noise
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = (labels == -1).sum()

Tham số chính:

• eps (mặc định 0.5) — bán kính \( \varepsilon \). Là khoảng cách trong không gian feature nên phụ thuộc scale — luôn standardize trước (mục 10).
• min_samples (mặc định 5) — số điểm tối thiểu kể cả tâm. Tăng để tạo cluster "đậm" hơn, giảm nếu data thưa.
• metric — "euclidean" mặc định. Hỗ trợ "manhattan", "chebyshev", "cosine", hoặc callable.
• algorithm — "auto", "ball_tree", "kd_tree", "brute". "auto" chọn ball/kd tree với low-dim, brute với high-dim.
• n_jobs — song song hoá query láng giềng.

Lưu ý: DBSCAN trong sklearn không có method predict() để gán cluster cho điểm mới sau khi fit. Lý do nguyên lý: thêm điểm mới có thể đổi mật độ cục bộ và đổi cấu trúc cluster. Nếu cần gán điểm mới, dùng HDBSCAN với approximate_predict hoặc tự cài (gán theo core point gần nhất trong \( \varepsilon \), ngược lại noise).

Heuristic chuẩn (Ester et al. 1996) để chọn eps:

• Đặt \( k = \) min_samples.
• Với mỗi điểm, tính khoảng cách đến láng giềng thứ \( k \) (k-th nearest neighbor distance).
• Sort các khoảng cách này tăng dần, plot.
• Tìm "elbow" (khuỷu) trên đường cong — đoạn đường bắt đầu dốc đứng. Giá trị eps tại elbow là ứng viên tốt: phần lớn điểm có láng giềng thứ \( k \) gần hơn \( \varepsilon \) (→ core); một số ít có láng giềng xa hơn (→ noise).

from sklearn.neighbors import NearestNeighbors
import numpy as np
import matplotlib.pyplot as plt

k = 5  # = min_samples
nn = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = nn.kneighbors(X)
k_dist = np.sort(distances[:, k - 1])

plt.plot(k_dist)
plt.xlabel("Diem (da sort)")
plt.ylabel(f"Khoang cach den lang gieng thu {k}")
plt.title("k-distance plot")
plt.grid(True)
plt.show()

Elbow không phải lúc nào cũng rõ — nếu dataset có nhiều cluster với mật độ khác nhau, đường cong có nhiều "khuỷu", mỗi khuỷu ứng với một ngưỡng mật độ. Đây là dấu hiệu cần HDBSCAN (mục 12) thay vì DBSCAN.

• Quy tắc thường dùng: min_samples \( \geq d + 1 \) trong đó \( d \) là số chiều. 2D → 3 trở lên (thực tế 4–5), 3D → 4 trở lên.
• Với data nhiễu nhiều: tăng min_samples để loại noise mạnh hơn. Trade-off: cluster nhỏ thật cũng có thể bị coi là noise.
• Với data sạch, ít điểm: min_samples nhỏ (3–4) tránh mất cluster nhỏ.
• Không có công thức tối ưu — chạy thử vài giá trị, đánh giá bằng visualization 2D (sau PCA nếu cần) hoặc domain knowledge.

Quan trọng: min_samples và eps phải được tune cùng nhau. Đổi một cái thì đổi luôn k-distance plot, phải vẽ lại để chọn eps mới.

eps là khoảng cách Euclidean trong không gian feature. Nếu feature có scale khác nhau — ví dụ tuoi (0–80) và luong (10⁶–10⁸) — khoảng cách bị feature có scale lớn áp đảo. Một eps hợp lý cho dataset này không tồn tại: hoặc tuỳ thuộc lương (ignore tuổi), hoặc tuỳ thuộc tuổi (ignore lương).

Quy trình chuẩn:

from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

db = DBSCAN(eps=0.5, min_samples=5)
labels = db.fit_predict(X_scaled)

Sau khi standardize, mỗi feature có std = 1, khoảng cách Euclidean cân bằng các chiều. eps trong khoảng 0.3–1.0 là vùng thường thử trước khi tinh chỉnh bằng k-distance plot.

Lưu ý: nếu dùng metric không phải Euclidean, cần cân nhắc kỹ — ví dụ cosine distance không yêu cầu scale nhưng yêu cầu chuẩn hoá norm. Manhattan, Mahalanobis có cách scale riêng.

Ưu điểm:

• Không cần biết \( K \) — số cluster do mật độ data quyết định.
• Tìm được cluster hình dạng bất kỳ (concave, ring, moon) — K-Means không làm được.
• Có khái niệm noise — tự đánh dấu outlier, dùng được luôn cho anomaly detection.
• Deterministic cho phần core: cùng tham số, cùng data → cùng cluster lõi (border có thể đổi tuỳ thứ tự duyệt).
• Không nhạy với khởi tạo (không có khởi tạo) — khác K-Means cần random init.

Nhược điểm:

• Tune eps khó — kết quả rất nhạy với giá trị này.
• Giả định mật độ đồng đều giữa các cluster. Nếu dữ liệu có cluster dày + cluster thưa cùng tồn tại, một eps không đủ cho cả hai: eps nhỏ thì cluster thưa bị vỡ thành noise; eps lớn thì các cluster dày bị merge với nhau. HDBSCAN giải quyết điểm này.
• Hiệu năng kém với high dimensions. Trong không gian nhiều chiều, mọi điểm gần như cách đều nhau (curse of dimensionality) → mật độ mất ý nghĩa. Giảm chiều bằng PCA (Bài 36) trước nếu \( d > 10 \).
• Không có predict() cho điểm mới sau fit (mục 7).
• Border point có thể nhập nhằng giữa hai cluster.

HDBSCAN — Hierarchical DBSCAN (Campello, Moulavi, Sander 2013). Tổng quát hoá DBSCAN bằng cách chạy DBSCAN ở mọi mức eps đồng thời, tạo cây phân cấp các cluster, rồi chọn cluster ổn định nhất qua các mức.

Hai khác biệt thực tế:

• Không có eps — bỏ luôn tham số khó tune nhất. Thay bằng min_cluster_size (kích thước cluster nhỏ nhất muốn giữ).
• Adaptive density — mỗi cluster có ngưỡng mật độ riêng. Cluster dày và cluster thưa cùng tồn tại được, không bị một eps chung ép theo một chuẩn duy nhất.

# sklearn 1.3+
from sklearn.cluster import HDBSCAN

hdb = HDBSCAN(min_cluster_size=10, min_samples=5)
labels = hdb.fit_predict(X_scaled)
# labels == -1 cho noise, giong DBSCAN

Trước sklearn 1.3, dùng package riêng hdbscan (Leland McInnes, cùng tác giả UMAP). API gần như giống nhau. Khi nghi ngờ data có nhiều ngưỡng mật độ, thử HDBSCAN trước, DBSCAN sau.

Silhouette Score (Bài 33) giả định cluster cầu và phân tách. Áp dụng cho cluster dạng moon / ring sẽ ra Silhouette thấp ngay cả khi DBSCAN đúng — vì điểm ở rìa moon "gần" điểm thuộc moon kia hơn là gần tâm moon của mình theo đường thẳng.

Tham khảo khi đánh giá DBSCAN:

• Visualization 2D — plot scatter với màu theo cluster, noise màu xám/đen. Cách kiểm tra trực quan tốt nhất, đặc biệt khi giảm chiều bằng PCA/t-SNE/UMAP trước.
• Số cluster phát hiện được và tỉ lệ noise: tỉ lệ noise quá cao (> 30%) → tham số quá khắt khe; quá thấp (= 0) → có thể quá lỏng.
• Domain knowledge — kích thước cluster có hợp lý với bài toán không? Số cluster có khớp với số nhóm thực tế đã biết không?
• Adjusted Rand Index (ARI) hoặc NMI nếu có ground truth (semi-supervised hoặc benchmark) — đánh giá so với label thật, không bị bias hình dạng cluster.
• Density-Based CV Index (DBCV) — metric thiết kế riêng cho clustering không cầu, đo bằng độ tách biệt mật độ. Có trong package hdbscan.

• Anomaly detection — noise (\( -1 \)) là ứng viên outlier. Áp dụng cho fraud detection (giao dịch lệch khỏi cluster hành vi thường), sensor fault (đo lệch), network intrusion. Khác Isolation Forest, DBSCAN cho cả nhãn cluster + outlier trong một bước.
• Spatial clustering — dữ liệu địa lý (GPS, satellite). Điểm tập trung dày tự nhiên thành cluster đô thị; điểm lẻ là vùng dân cư thưa hoặc lỗi đo. eps tính theo mét/km là một đại lượng vật lý có ý nghĩa rõ.
• Cluster bất quy tắc — phân vùng ảnh (image segmentation) khi vùng quan tâm có hình dạng cong (mạch máu, đường biên), phân tích biểu đồ phân tán có cấu trúc xoắn / vòng.
• Phát hiện cộng đồng trong embedding — sau khi nhúng documents/users/items bằng embedding model, DBSCAN/HDBSCAN nhóm các vector dày đặc thành chủ đề. Topic modeling truyền thống bị chèn ép bởi mô hình kết hợp embedding + HDBSCAN (vd BERTopic).
• Tiền xử lý cho supervised — gán cluster label làm feature mới, hoặc loại noise trước khi train classifier.

Dataset make_moons tạo hai "trăng lưỡi liềm" lồng vào nhau — bài toán kinh điển để DBSCAN trội hơn K-Means.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, DBSCAN
from sklearn.neighbors import NearestNeighbors

X, y_true = make_moons(n_samples=500, noise=0.05, random_state=42)
X = StandardScaler().fit_transform(X)

# K-Means voi K=2
km = KMeans(n_clusters=2, n_init=10, random_state=42)
km_labels = km.fit_predict(X)

# DBSCAN
db = DBSCAN(eps=0.3, min_samples=5)
db_labels = db.fit_predict(X)

print(f"DBSCAN: {len(set(db_labels)) - (1 if -1 in db_labels else 0)} cluster, "
      f"{(db_labels == -1).sum()} noise")

fig, ax = plt.subplots(1, 2, figsize=(11, 4))
ax[0].scatter(X[:, 0], X[:, 1], c=km_labels, cmap="viridis", s=10)
ax[0].set_title("K-Means (K=2)")
ax[1].scatter(X[:, 0], X[:, 1], c=db_labels, cmap="viridis", s=10)
ax[1].set_title(f"DBSCAN (eps=0.3, min_samples=5)")
plt.tight_layout()
plt.show()

K-Means cắt mặt phẳng bằng đường trung trực giữa hai centroid → cắt ngang hai moon thành "nửa trên / nửa dưới", sai cấu trúc. DBSCAN bám theo dải dày của từng moon → tách đúng hai cluster.

K-distance plot để biện minh giá trị eps:

k = 5
nn = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = nn.kneighbors(X)
k_dist = np.sort(distances[:, k - 1])
plt.plot(k_dist)
plt.axhline(0.3, color="red", linestyle="--", label="eps = 0.3")
plt.xlabel("Diem (da sort)")
plt.ylabel(f"K/c den lang gieng thu {k}")
plt.legend()
plt.grid(True)
plt.show()

Outlier detection ngắn — chèn outlier nhân tạo và kiểm tra:

rng = np.random.default_rng(0)
n_out = 25
X_out = rng.uniform(low=X.min(axis=0) - 0.5, high=X.max(axis=0) + 0.5, size=(n_out, 2))
X_aug = np.vstack([X, X_out])

db = DBSCAN(eps=0.3, min_samples=5).fit(X_aug)
mask_noise = db.labels_ == -1
print(f"Diem noise phat hien: {mask_noise.sum()} / {len(X_aug)}")
# Voi du lieu nay, phan lon noise se trung voi X_out

Module 5 đến giờ đã đi qua:

• Bài 32 — K-Means: clustering nền tảng, partition theo centroid, cần \( K \), giả định cluster cầu.
• Bài 33 — Elbow & Silhouette: chọn \( K \) cho K-Means, đánh giá chất lượng clustering cầu.
• Bài 34 — Hierarchical Clustering: agglomerative + dendrogram, không cần \( K \) tại fit, nhưng \( O(n^2) \) trở lên.
• Bài 35 — DBSCAN: density-based, không cần \( K \), bắt được cluster bất kỳ hình dạng + đánh dấu noise.
• Bài 36 — PCA (sắp tới): không phải clustering, mà giảm chiều — phục vụ cả visualization 2D cho mọi thuật toán clustering ở trên, và làm bước tiền xử lý cho DBSCAN khi data high-dim.

Quy tắc chọn trong thực tế:

• Cluster cầu, biết \( K \), dataset lớn → K-Means.
• Muốn xem cấu trúc phân cấp → Hierarchical.
• Cluster phi cầu, không biết \( K \), có outlier → DBSCAN.
• Cluster phi cầu + density khác nhau → HDBSCAN.
• High-dim → PCA/UMAP giảm chiều trước, rồi mới clustering.

Bài 1 — Ảnh hưởng của eps. Trên make_moons(n_samples=500, noise=0.05, random_state=42) đã standardize, chạy DBSCAN với min_samples=5 và eps lần lượt 0.1, 0.2, 0.3, 0.5, 1.0. Với mỗi giá trị, ghi (a) số cluster, (b) số noise, (c) plot scatter. Mô tả điều gì xảy ra khi eps quá nhỏ và quá lớn.

Bài 2 — Ảnh hưởng của min_samples. Cùng dataset trên, cố định eps=0.3, đổi min_samples trong {3, 5, 10, 20}. So sánh số cluster, số noise, độ "đậm" của cluster lõi. Trade-off chính của tham số này là gì?

Bài 3 — K-distance plot. Vẽ k-distance plot cho k=5 trên make_moons đã standardize. Xác định elbow bằng mắt, rút ra giá trị eps đề xuất. Chạy DBSCAN với eps đó và so với eps=0.3 đã dùng — kết quả giống/khác chỗ nào?

Bài 4 — Outlier detection. Tạo dataset gồm 950 điểm make_blobs(centers=3, cluster_std=0.5) + 50 điểm uniform random làm outlier (5%). Chạy DBSCAN, tính precision/recall của việc phát hiện outlier (điểm label == -1) so với ground truth (50 điểm cuối). Thử thêm Isolation Forest cùng dữ liệu — so sánh precision/recall.

Bài 5 — DBSCAN vs HDBSCAN với mật độ khác nhau. Tạo dataset hỗn hợp: 200 điểm make_blobs(centers=[(0,0)], cluster_std=0.3) (cluster dày) + 200 điểm make_blobs(centers=[(5,5)], cluster_std=1.5) (cluster thưa) + 30 điểm noise uniform. Chạy DBSCAN (thử vài eps) và HDBSCAN (min_cluster_size=20). DBSCAN có giữ được cả hai cluster với một eps không? HDBSCAN xử lý ra sao?

Bài 36: PCA — giảm chiều dữ liệu — kết thúc Module 5 với thuật toán unsupervised không phải clustering: Principal Component Analysis. Tìm các trục mới (principal component) tối đa hoá phương sai, giảm chiều giữ thông tin chính, dùng cho visualization 2D, tăng tốc model, và xử lý high-dim trước khi clustering bằng DBSCAN/HDBSCAN.