DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (phân cụm không gian dựa trên mật độ có nhiễu) là một thuật toán học không giám sát, nhóm các điểm nằm sát nhau thành cụm và gán nhãn nhiễu cho các điểm ở vùng thưa. Martin Ester, Hans-Peter Kriegel, Jörg Sander và Xiaowei Xu giới thiệu thuật toán này tại hội nghị KDD năm 1996. Thuật toán không cần xác định trước số cụm, tìm được cụm có hình dạng bất kỳ như vòng, lưỡi liềm hoặc đường quanh co, và nhãn nhiễu cũng đóng vai trò như một dạng phát hiện bất thường đơn giản. Toàn bộ thuật toán được điều khiển bởi hai tham số: bán kính lân cận và số điểm cần có để lân cận được xem là dày đặc.

Điểm lõi, điểm biên và nhiễu#

DBSCAN xét lân cận của từng điểm, tức tập hợp các điểm nằm trong khoảng cách eps, rồi đếm số điểm trong đó:

• Điểm lõi: Có ít nhất min_samples điểm trong lân cận, tính cả chính nó theo cách triển khai của scikit-learn. Các điểm lõi tạo nên phần bên trong dày đặc của cụm.
• Điểm biên: Có quá ít láng giềng để trở thành điểm lõi nhưng nằm trong phạm vi eps của một điểm lõi. Các điểm biên tạo nên rìa cụm.
• Điểm nhiễu: Không thuộc hai loại trên, vì vậy không thuộc cụm nào và nhận nhãn -1.

Một cụm phát triển từ bất kỳ điểm lõi nào chưa được duyệt. DBSCAN thêm mọi điểm trong lân cận của điểm đó, rồi tiếp tục từ từng điểm lõi mới được thêm vào cho đến khi không còn điểm nào có thể tiếp cận; vì vậy, một chuỗi các lân cận dày đặc chồng lấn sẽ tạo thành một cụm duy nhất dù đường đi uốn cong ra sao. Điểm biên gia nhập cụm nhưng không mở rộng cụm. Kết quả có tính xác định với một thứ tự đầu vào nhất định, nhưng nếu một điểm biên nằm trong phạm vi tiếp cận của hai cụm, điểm đó sẽ gia nhập cụm tiếp cận nó trước; do đó, xáo trộn dữ liệu có thể làm các điểm biên chuyển giữa các cụm.

Chọn eps và min_samples#

Bán kính eps là yếu tố quan trọng nhất và phụ thuộc vào thang đo của dữ liệu, vì vậy các đặc trưng thường được chuẩn hóa trước. Bán kính quá nhỏ khiến phần lớn điểm bị xem là nhiễu, còn bán kính quá lớn sẽ gộp các cụm lân cận thành một. Heuristic phổ biến là sắp xếp khoảng cách từ mỗi điểm đến láng giềng gần thứ k, với k bằng min_samples, rồi chọn eps tại điểm gối của đường cong, nơi khoảng cách bắt đầu tăng mạnh. Giá trị min_samples lớn hơn giúp phân cụm dễ chấp nhận nhiễu hơn và thường được dùng trên dataset lớn hoặc nhiều nhiễu. Trong không gian nhiều chiều như embedding ảnh, khoảng cách giữa các điểm trở nên tương tự nhau, nên các chuyên gia thường áp dụng giảm chiều như phân tích thành phần chính (PCA) trước khi chạy DBSCAN.

DBSCAN, K-Means và HDBSCAN#

Phân cụm K-means cần biết trước số cụm, gán mỗi điểm cho centroid gần nhất, vì vậy ưu tiên các cụm tròn, gọn và kéo các điểm ngoại lệ vào một nhóm nào đó. DBSCAN tìm số cụm dựa trên mật độ và loại các điểm ngoại lệ ra ngoài. Điểm yếu của DBSCAN là chỉ có một giá trị eps dùng chung: khi các cụm có mật độ rất khác nhau, không có bán kính nào vừa tách cụm thưa khỏi nhiễu, vừa tách các cụm dày đặc khỏi nhau. HDBSCAN giải quyết vấn đề này bằng cách chạy DBSCAN trên toàn bộ các giá trị eps và giữ lại những cụm ổn định nhất; cả hai thuật toán đều có trong module clustering của scikit-learn, cùng với OPTICS có liên quan.

Ví dụ này phân cụm hai đường cong hình lưỡi liềm đan xen với 20 điểm ngoại lệ ngẫu nhiên được thêm vào, rồi chấm điểm từng kết quả so với các nhóm thực bằng chỉ số Rand hiệu chỉnh, trong đó 1.0 là mức khớp hoàn hảo:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

Script in ra 2 cụm và 15 điểm nhiễu cho DBSCAN, cùng chỉ số Rand hiệu chỉnh lần lượt là 0.97 cho DBSCAN và 0.20 cho k-means. DBSCAN bám theo cả hai đường cong hình lưỡi liềm và tách riêng các điểm ngoại lệ nằm cách xa chúng; trong khi đó, k-means cắt ngang hai đường cong bằng một ranh giới thẳng, dù đã được cung cấp đúng số cụm.

Ứng dụng thực tế#

• Tri giác LiDAR: Các pipeline xe tự hành và robot loại bỏ các điểm mặt đất khỏi bản quét LiDAR, rồi phân cụm các điểm 3D còn lại thành từng chướng ngại vật riêng; phân cụm dựa trên mật độ là lựa chọn phổ biến vì không biết trước số lượng đối tượng.
• Hậu xử lý detection: Tâm bounding box của các detection YOLO26, có sẵn dưới dạng result.boxes.xywh, có thể được phân cụm bằng DBSCAN để tìm nhóm người trong đám đông hoặc các vị trí lỗi lặp lại trên dây chuyền sản xuất; các detection riêng lẻ sẽ bị loại thành nhiễu.
• Giám sát gian lận và cảm biến: Các giao dịch hoặc chỉ số được gán nhãn -1 nằm cách xa mọi cụm hành vi bình thường có mật độ cao và trở thành đối tượng cần xem xét.
• Phân tích không gian địa lý: Các công ty giao hàng và gọi xe phân cụm điểm GPS để tìm các điểm dừng thường xuyên và điểm đón khách đông. DBSCAN của Scikit-learn chấp nhận metric="haversine" cho vĩ độ và kinh độ tính bằng radian; trong trường hợp đó, eps là một góc trên mặt cầu đơn vị, vì vậy bán kính 100 mét tương đương eps = 0.1 / 6371, khi sử dụng bán kính trung bình của Trái Đất là 6,371 km.