Phân cụm DBSCAN

Phân cụm DBSCAN là gì?

DBSCAN nhóm các điểm gần nhau và đánh dấu điểm vùng thưa là ngoại lai. Không cần chỉ định trước số cụm và có thể tìm cụm hình dạng bất kỳ.

Hai tham số: epsilon (eps) — khoảng cách tối đa để coi là lân cận; minSamples — số điểm tối thiểu trong vùng eps. Điểm được phân loại: lõi, biên, nhiễu.

DBSCAN hiệu quả cho dữ liệu có mật độ đa dạng, hình dạng không lồi và nhiều nhiễu. Tuy nhiên gặp khó khăn khi các cụm có mật độ rất khác nhau.

Formula: Điểm lõi: |N_eps(p)| ≥ minSamples Điểm biên: |N_eps(p)| < minSamples nhưng nằm trong bán kính eps của một điểm lõi Nhiễu: không phải lõi cũng không phải biên N_eps(p) = {q : dist(p,q) ≤ eps}

Ví dụ tính toán

Điểm: (1,1), (1.1,1.2), (0.9,0.8), (5,5), (5.1,5.2), (4.9,4.8), (10,10). eps=1.0, minSamples=2. Cụm 1: 3 điểm, Cụm 2: 3 điểm, Nhiễu: (10,10).

Khi nào sử dụng công cụ này

• Nhà khoa học dữ liệu thực hiện phát hiện bất thường khi các giá trị ngoại lai cần được xác định rõ ràng là điểm nhiễu tách biệt khỏi các cụm
• Chuyên viên phân tích không gian phân cụm dữ liệu địa lý (ví dụ: điểm nóng tội phạm, vị trí giao hàng) khi hình dạng cụm bất thường và số nhóm chưa biết
• Nhà nghiên cứu phân tích dữ liệu có nhiễu tự nhiên khi việc ép mọi điểm vào một cụm (như K-Means làm) sẽ bóp méo phân tích
• Kỹ sư nhóm các số đọc cảm biến tạo thành mẫu hình không phải hình cầu (vòng, lưỡi liềm, hình kéo dài) mà K-Means không thể phát hiện

Những sai lầm thường gặp

• Đặt epsilon quá lớn — điều này gộp các cụm riêng biệt thành một; hãy dùng biểu đồ k-distance để tìm giá trị eps phù hợp tại điểm gấp khúc của đường cong
• Đặt epsilon quá nhỏ — điều này phân loại hầu hết các điểm là nhiễu và tìm được ít hoặc không có cụm nào; nếu phần lớn dữ liệu bị gắn nhãn nhiễu, eps có lẽ quá nhỏ
• Không chuẩn hóa thang đo đặc trưng trước khi phân cụm — DBSCAN dùng khoảng cách Euclid, nên các đặc trưng có thang lớn hơn chi phối phép tính khoảng cách; hãy chuẩn hóa mọi đặc trưng trước
• Dùng DBSCAN khi các cụm có mật độ rất khác nhau — một giá trị eps duy nhất không thể phù hợp đồng thời với cả cụm dày và cụm thưa; hãy cân nhắc HDBSCAN hoặc OPTICS thay thế

Cách diễn giải kết quả

• Các điểm nhiễu (được gắn nhãn ngoại lai) là điểm dữ liệu trong vùng mật độ thấp — chúng có thể là bất thường thực sự, sai số đo hoặc dữ liệu chuyển tiếp giữa các cụm
• Số cụm được xác định tự động bởi dữ liệu và tham số, không cần chỉ định trước — đây là lợi thế then chốt so với K-Means
• Nếu thuật toán chỉ tìm được một cụm hoặc phân loại mọi thứ là nhiễu, hãy thử điều chỉnh eps và minSamples — các tham số cần được tinh chỉnh để khớp với cấu trúc mật độ của dữ liệu

Tiêu chuẩn và tài liệu tham khảo

• Ester, Kriegel, Sander & Xu (1996), 'A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise', Proc. KDD-96 — bài báo DBSCAN gốc
• Schubert, Sander, Ester, Kriegel & Xu (2017), 'DBSCAN Revisited, Revisited', ACM Transactions on Database Systems — hướng dẫn hiện đại về chọn tham số và heuristic k-distance

Câu hỏi thường gặp

Làm sao chọn eps và minSamples?

minSamples: thường 2 × số chiều. eps: vẽ đồ thị khoảng cách k-láng giềng gần nhất, chọn tại điểm 'gối'.

Khi nào dùng DBSCAN thay K-Means?

Khi không biết số cụm, hình dạng bất thường, hoặc nhiều nhiễu. K-Means nhanh hơn cho cụm hình cầu.