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

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

Cá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 một vùng lân cận xung quanh mỗi điểm dữ liệu và đếm số điểm khác nằm trong vùng đó. Hai siêu tham số chính kiểm soát quy trình này, đòi hỏi phải tinh chỉnh siêu tham số cẩn thận để phù hợp với các đặc điểm cụ thể của dữ liệu:

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

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

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

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

3. Điểm nhiễu: Các điểm không phải là điểm lõi cũng không phải là điểm biên. Về cơ bản, chúng được xử lý như các điểm ngoại lệ, hữu ích cho những tác vụ như phát hiện điểm ngoại lệ.

DBSCAN 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 riêng so với phân cụm K-Means trong một số tình huống cụ thể. K-Means dựa vào các tâm cụm và khoảng cách Euclid, thường giả định các cụm có dạng lồi hoặc hình cầu. Điều này có thể dẫn đến hiệu suất kém trên dữ liệu có dạng kéo dài 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 thuật toán bám theo các đường bao tự nhiên của phân bố dữ liệu.

Một khác biệt đáng kể khác nằm ở quá trình 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ó thực hiện nếu không có kiến thức từ trước. DBSCAN tự nhiên suy ra số lượng cụm từ mật độ dữ liệu. Ngoài ra, K-Means nhạy cảm với các điểm ngoại lệ vì buộc mọi điểm 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 ngăn các bất thường trong dữ liệu làm nhiễm các cụm hợp lệ, đảm bảo kết quả sạch hơn cho những tác vụ tiếp theo như mô hình hóa dự đoán.

Các ứng dụng trong thực tế#

DBSCAN được ứng dụng rộng rãi trong các ngành yêu cầu 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 chuyên gia phân tích sử dụng DBSCAN để nhóm các tọa độ GPS từ đội xe giao hàng hoặc dịch vụ đi chung xe. Bằng cách xác định các khu vực trả khách hoặc giao hàng có mật độ cao, doanh nghiệp có thể tối ưu hóa lập kế hoạch tuyến đường và vị trí kho hàng. 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 để nâng cao 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 bằng hình ảnh được hỗ trợ bởi những model như YOLO26 có thể phát hiện các khuyết tật bề mặt. DBSCAN có thể phân cụm tọa độ của các khuyết tật này trên bản đồ sản phẩm. Các phát hiện riêng lẻ có thể được loại bỏ vì bị xem 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 mang tính hệ thống, kích hoạt cảnh báo để kiểm tra chất lượng.

Ví dụ mã: Phân cụm tâm của các đối tượng được phát hiện#

Trong các workflow thị giác máy tính, các developer thường sử dụng Ultralytics Platform để train model phát hiện đối tượng, sau đó hậu xử lý kết quả. Ví dụ sau minh họa cách sử dụng thư viện sklearn để phân cụm các tâm của những đối tượng được phát hiện. Điều này giúp nhóm các kết quả phát hiện có mối liên hệ về mặt không gian, có khả năng hợp nhất nhiều bounding box của 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]

Tích hợp với Deep Learning#

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