DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - Phân cụm không gian dựa trên mật độ của các ứng dụng có nhiễu

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 xác định các vùng có mật độ cao được phân tách bởi các vùng có mật độ thấp. Khả năng này cho phép nó phát hiện các cụm có hình dạng và kích thước bất kỳ, làm cho 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 lợi thế quan trọng của thuật toán này là khả năng phát hiện bất thường được tích hợp sẵn, vì nó tự động phân loại các điểm trong các vùng mật độ thấp là nhiễu thay vì ép chúng vào một cụm.

Khái niệm và thông 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 xem có bao nhiêu điểm khác nằm trong 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 điều 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 điểm lân cận. Nó xác định khoảng cách "khả năng 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 để tạo thành một vùng dày đặc hoặc "lõi".

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: Điểm có ít nhất minPts hàng xóm trong khu vực eps bán kính. 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 phạm vi eps bán kính của một điểm lõi nhưng có ít hơn minPts Chính những người hàng xóm này tạo thành các cạnh của một cụm.
3. Điểm nhiễu: Là những điểm không thuộc vùng lõi cũng không thuộc vùng biên. Chúng được coi như các điểm ngoại lai, rất hữu ích cho các tác vụ như phát hiện điểm ngoại lai .

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

Mặc dù cả hai đều là những thuật toán cơ bản trong học máy (ML) , DBSCAN mang lại những lợi thế riêng biệt so với K-Means Clustering trong các trường hợp cụ thể. K-Means dựa trên tâm cụm và khoảng cách Euclidean , 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 đối với dữ liệu có hình 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 nó bám sát theo các đường nét tự nhiên của phân bố dữ liệu.

Một điểm khác biệt quan trọng nữa nằm ở khâu khởi tạo. Thuật toán K-Means yêu cầu người dùng phải 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 từ trước. Thuật toán DBSCAN suy ra 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 sai lệch tâm của các 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 dự đoán .

Các Ứng dụng Thực tế

DBSCAN được ứng dụng rộng rãi trong các ngành công nghiệp đò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ừ các đội xe giao hàng hoặc dịch vụ chia sẻ xe. Bằng cách xác định các khu vực giao hàng có mật độ cao, các công ty có thể tối ưu hóa việc lập kế hoạch tuyến đường và vị trí kho hàng. Ví dụ, trí tuệ nhân tạo trong hậu cần thường liên quan đến việc nhó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ể detect Các khuyết tật bề mặt. DBSCAN có thể nhóm các tọa độ của những 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ể bị bỏ qua như 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ã: Tâm cụm phát hiện cụm

Trong 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 Ultralytics Nền tảng để 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 sklearn Thư viện này dùng để 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 đối tượng được phát hiện có liên quan đến nhau trong không gian, có khả năng hợp nhất nhiều đối tượng. hộp giới hạn Dùng 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 kinh điển, nó kết hợp hiệu quả với các thuật toán học sâu hiện đại. Ví dụ, các đặc trưng đa chiều được trích xuất từ ​​mạng nơ-ron tích chập (CNN) có thể được giảm chiều bằng các kỹ thuật giảm chiề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 chứ không chỉ dựa trên 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 gắn nhãn khan hiếm, giúp các nhà nghiên cứu tổ chức kho lưu trữ khổng lồ các hình ảnh chưa được gắn nhãn một cách hiệu quả.