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

DBSCAN (Phân cụm không gian dựa trên mật độ cho các ứng dụng có nhiễu) là một thuật toán học không giám sát mạnh mẽ được sử dụng để xác định các nhóm riêng biệt trong dữ liệu dựa trên mật độ. Không giống như các phương pháp phân cụm truyền thống giả định các cụm hình cầu hoặc yêu cầu xác định trước số lượng nhóm, DBSCAN định vị các vùng có mật độ cao được ngăn cách bởi các vùng có mật độ thấp. Khả năng này cho phép nó khám phá các cụm với hình dạng và kích thước bất kỳ, làm cho nó trở nên đặc biệt hiệu quả trong việc phân tích các tập dữ liệu thực tế phức tạp mà cấu trúc cơ bản chưa được biết đến. Một ưu điểm chính của thuật toán này là khả năng phát hiện bất thường tích hợp, vì nó tự động phân loại các điểm trong vùng mật độ thấp là nhiễu thay vì ép buộc chúng vào một cụm.

Link to this sectionCác khái niệm và tham số cốt lõi#

Thuật toán hoạt động bằng cách xác định vùng lân cận xung quanh mỗi điểm dữ liệu và đếm số lượng các điểm khác nằm trong vùng đó. Hai siêu tham số chính kiểm soát quá trình này, đòi hỏi phải tinh chỉnh siêu tham số cẩn thận để khớp với các đặc điểm cụ thể của dữ liệu:

• Epsilon (eps): Tham số này chỉ định bán kính tối đa xung quanh một điểm để tìm kiếm các lân cận. Nó xác định khoảng cách "có thể tiếp cận".
• Số điểm tối thiểu (minPts): Tham số này thiết lập số lượng điểm dữ liệu tối thiểu cần thiết trong bán kính Epsilon để hình thành một vùng mật độ cao hoặc "cốt lõi" (core).

Dựa trên các tham số này, DBSCAN phân loại mọi điểm trong tập dữ liệu thành một trong ba loại:

1. Điểm cốt lõi (Core Points): Các điểm có ít nhất minPts lân cận trong bán kính eps. Các điểm này tạo thành phần bên trong của một cụm.

2. Điểm biên (Border Points): Các điểm nằm trong bán kính eps của một điểm cốt lõi nhưng bản thân chúng có ít hơn minPts lân cận. Chúng tạo thành các cạnh của một cụm.

3. Điểm nhiễu (Noise Points): Các điểm không phải là điểm cốt lõi cũng không phải điểm biên. Chúng được xử lý hiệu quả như các điểm ngoại lai, điều này hữu ích cho các tác vụ như phát hiện ngoại lai.

Link to this sectionDBSCAN so với phân cụm K-Means#

Mặc dù cả hai đều là nền tảng của học máy (ML), DBSCAN mang lại những ưu điểm rõ rệt so với phân cụm K-Means trong các tình huống cụ thể. K-Means dựa vào trọng tâm và khoảng cách Euclid, thường giả định các cụm là lồi hoặc hình cầu. Điều này có thể dẫn đến hiệu suất kém đối với dữ liệu hình thoi hoặc hình lưỡi liềm. Ngược lại, phương pháp dựa trên mật độ của DBSCAN cho phép nó tuân theo các đường nét tự nhiên của phân phối dữ liệu.

Một sự khác biệt đáng kể khác nằm ở việc khởi tạo. K-Means yêu cầu người dùng chỉ định trước số lượng cụm (k), điều này có thể khó khăn nếu không có kiến thức trước. DBSCAN suy luận số lượng cụm một cách tự nhiên từ mật độ dữ liệu. Ngoài ra, K-Means nhạy cảm với các điểm ngoại lai vì nó buộc mọi điểm phải vào một nhóm, có khả năng làm lệch các tâm cụm. Khả năng gán nhãn các điểm là nhiễu của DBSCAN giúp ngăn chặn dữ liệu bất thường làm hỏng các cụm hợp lệ, đảm bảo kết quả sạch hơn cho các tác vụ tiếp theo như mô hình hóa dự đoán.

Link to this sectionCác ứng dụng trong thực tế#

DBSCAN được ứng dụng rộng rãi trong các ngành đòi hỏi phân tích không gian và xử lý nhiễu mạnh mẽ.

• Phân tích không gian địa lý: Trong quy hoạch đô thị và logistics, các nhà phân tích sử dụng DBSCAN để nhóm các tọa độ GPS từ đội xe giao hàng hoặc các dịch vụ chia sẻ chuyến đi. Bằng cách xác định các khu vực có mật độ trả khách cao, các công ty có thể tối ưu hóa lập kế hoạch lộ trình và vị trí kho bãi. Ví dụ, AI trong logistics thường bao gồm việc phân cụm các điểm dừng giao hàng để cải thiện hiệu quả.
• Phát hiện bất thường dựa trên thị giác: Trong sản xuất, các hệ thống kiểm tra trực quan được hỗ trợ bởi các mô hình như YOLO26 có thể phát hiện các lỗi bề mặt. DBSCAN có thể phân cụm các tọa độ của các lỗi này trên bản đồ sản phẩm. Các phát hiện riêng lẻ có thể bị loại bỏ là nhiễu cảm biến, trong khi các cụm dày đặc cho thấy một lỗi sản xuất hệ thống, kích hoạt cảnh báo cho kiểm tra chất lượng.

Link to this sectionVí dụ mã nguồn: Phân cụm các trọng tâm phát hiện#

Trong các quy trình làm việc về thị giác máy tính, các nhà phát triển thường sử dụng Nền tảng Ultralytics để huấn luyện các bộ phát hiện đối tượng và sau đó xử lý hậu kỳ kết quả. Ví dụ sau đây minh họa cách sử dụng thư viện sklearn để phân cụm các trọng tâm của các đối tượng đã phát hiện. Điều này giúp nhóm các phát hiện có liên quan về mặt không gian, có khả năng hợp nhất nhiều hộp bao (bounding box) cho cùng một đối tượng hoặc xác định các nhóm đối tượng.

import numpy as np
from sklearn.cluster import DBSCAN

# Simulated centroids of objects detected by YOLO26
# [x, y] coordinates representing object locations
centroids = np.array(
    [
        [100, 100],
        [102, 104],
        [101, 102],  # Cluster 1 (Dense group)
        [200, 200],
        [205, 202],  # Cluster 2 (Another group)
        [500, 500],  # Noise (Outlier)
    ]
)

# Initialize DBSCAN with a radius (eps) of 10 and min_samples of 2
# This groups points close to each other
clustering = DBSCAN(eps=10, min_samples=2).fit(centroids)

# Labels: 0, 1 are cluster IDs; -1 represents noise
print(f"Cluster Labels: {clustering.labels_}")
# Output: [ 0  0  0  1  1 -1]

Link to this sectionTích hợp với học sâu#

Mặc dù DBSCAN là một thuật toán cổ điển, nó kết hợp hiệu quả với học sâu hiện đại. Ví dụ, các đặc trưng chiều cao được trích xuất từ một mạng thần kinh tích chập (CNN) có thể được giảm chiều bằng các kỹ thuật giảm chiều dữ liệu như PCA hoặc t-SNE trước khi áp dụng DBSCAN. Cách tiếp cận kết hợp này cho phép phân cụm dữ liệu hình ảnh phức tạp dựa trên sự tương đồng về ngữ nghĩa thay vì chỉ dựa vào vị trí pixel. Điều này đặc biệt hữu ích trong các kịch bản học không giám sát nơi dữ liệu huấn luyện được dán nhãn khan hiếm, giúp các nhà nghiên cứu tổ chức hiệu quả các kho lưu trữ khổng lồ gồm hình ảnh chưa được dán nhãn.