K-Means
Phân cụm K-means là thuật toán phân hoạch. K-means gán lại mỗi dữ liệu trong tập dữ liệu cho chỉ một trong các cụm mới được hình thành. Một dữ liệu hoặc điểm dữ liệu được gán cho cụm gần nhất bằng phép đo khoảng cách hoặc độ tương đồng.
Trong K-means, một đối tượng được gán cho tâm gần nhất. Có thể định nghĩa các ràng buộc cannot-link, và nó sửa đổi quá trình gán tâm trong K-means thành gán tâm gần nhất có thể. Khi các đối tượng được gán cho các tâm theo trình tự, ở mỗi bước có thể đảm bảo các gán cho đến nay không vi phạm bất kỳ ràng buộc cannot-link nào. Một đối tượng được gán cho tâm gần nhất do đó gán đó tuân theo các ràng buộc cannot-link.
DBSCAN
DBSCAN là viết tắt của 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 với nhiễu). Đây là thuật toán phân cụm dựa trên mật độ. Thuật toán mở rộng các vùng có mật độ đủ cao thành các cụm và khám phá các cụm cấu trúc tùy ý trong cơ sở dữ liệu không gian với nhiễu. Nó định nghĩa một cụm như một tập hợp tối đa các điểm kết nối mật độ.
Một cụm dựa trên mật độ là một tập hợp các đối tượng kết nối mật độ mà là tối đa về mặt khả năng đạt được mật độ. Mỗi đối tượng không nằm trong bất kỳ cụm nào được coi là nhiễu.
DBSCAN kiểm tra các cụm bằng cách kiểm tra lân cận ε của mọi điểm trong cơ sở dữ liệu. Nếu lân cận ε của một điểm p chứa nhiều hơn MinPts, một cụm mới với p là phần tử lõi được tạo. DBSCAN lặp lại thu thập chính xác các đối tượng đạt được mật độ từ các phần tử lõi này, có thể bao gồm việc hợp nhất một vài cụm đạt được mật độ. Quá trình kết thúc khi không có điểm mới nào có thể được thêm vào bất kỳ cụm nào.
Hãy xem so sánh giữa K-Means và DBSCAN.
| K-Means | DBSCAN |
|---|---|
| K-means thường phân cụm tất cả các đối tượng. | DBSCAN loại bỏ các đối tượng mà nó định nghĩa là nhiễu. |
| K-means cần khái niệm cụm dựa trên mẫu. | DBSCAN cần khái niệm dựa trên mật độ. |
| K-means gặp khó khăn với cụm không cầu hình và cụm nhiều kích thước. | DBSCAN dùng để xử lý cụm nhiều kích thước và cấu trúc và không bị ảnh hưởng mạnh bởi nhiễu hoặc ngoại lai. |
| K-means có thể dùng cho dữ liệu có tâm rõ ràng, bao gồm trung bình hoặc trung vị. | DBSCAN yêu cầu định nghĩa mật độ của nó, dựa trên khái niệm mật độ Euclid truyền thống, có ý nghĩa cho dữ liệu. |
| K-means có thể dùng cho dữ liệu thưa, số chiều cao, bao gồm dữ liệu văn bản. | DBSCAN thường hoạt động kém cho dữ liệu như vậy vì định nghĩa mật độ Euclid truyền thống không hoạt động tốt cho dữ liệu số chiều cao. |
| Thuật toán K-means cơ bản tương tự phương pháp phân cụm thống kê (mô hình hỗn hợp) giả định tất cả cụm đến từ phân phối Gaussian cầu hình với các trung bình khác nhau nhưng ma trận hiệp phương sai giống nhau. | DBSCAN không đưa ra giả định về phân phối bản ghi. |