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

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 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 một số lượng nhóm được xác định trước, 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 thuật toán phát hiện các cụm có hình dạng và kích thước tùy ý, làm cho nó cực kỳ hiệu quả trong việc phân tích các tập dữ liệu thế giới thực phức tạp nơi cấu trúc cơ bản chưa được biết rõ. Một ưu điểm quan trọng của thuật toán này là tính 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 mật độ thấp là nhiễu thay vì ép 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ố lượng điểm khác rơi vào vùng lân cận đó. 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 để phù hợ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 lõi: Các điểm có ít nhất minPts điểm 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: Các điểm nằm trong bán kính eps của một điểm lõi nhưng có ít hơn minPts điểm lân cận. Các đ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. Những điểm này được xử lý hiệu quả như các giá trị ngoại lai, rất hữu ích cho các tác vụ như phát hiện giá trị ngoại lai.

DBSCAN so với phân cụm K-Means#

Mặc dù cả hai đều đóng vai trò cơ bản đối với 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 kịch bản cụ thể. K-Means dựa vào các tâm cụm và khoảng cách Euclid, thường giả định rằng 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 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 nó tuân theo các đường輪 contour tự nhiên của phân phối dữ liệu.

Một sự khác biệt quan trọng 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ể gặp 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 giá trị ngoại lai vì nó ép buộc mọi điểm vào một nhóm, có thể làm lệch tâm cụm. Khả năng gán nhãn các điểm là nhiễu của DBSCAN ngăn chặn các bất thường 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 các 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 đò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à hậu cần, 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ụ đi chung xe. Bằng cách xác định các khu vực thả khách có mật độ cao, các công ty 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 liên quan đến 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 khiếm khuyết bề mặt. DBSCAN có thể phân cụm tọa độ của các khiếm khuyết này trên bản đồ sản phẩm. Các phát hiện cô lập có thể được coi 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 có hệ thống, kích hoạt cảnh báo để kiểm tra chất lượng.

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

Trong các quy trình thị giác máy tính, các nhà phát triển thường sử dụng Ultralytics Platform để 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 tâm của các đối tượng được 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 bounding boxes 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]

Tí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 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 chiều bằng cách sử dụ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 độ tương đồng về mặt ngữ nghĩa thay vì chỉ dựa vào vị trí điểm ảnh. Đ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ó gắn nhãn khan hiếm, giúp các nhà nghiên cứu tổ chức các kho lưu trữ hình ảnh chưa gán nhãn khổng lồ một cách hiệu quả.