Phân cụm với DBSCAN

DBSCAN (Phân cụm không gian dựa trên mật độ của các ứng dụng có tiếng ồn) là một thuật toán phân cụm nhóm các điểm gần nhau dựa trên tiêu chí mật độ. Trái ngược với các mô hình Phân cụm khác như K-means, DBSCAN có thể xác định các cụm có hình dạng tùy ý và không yêu cầu phải chỉ định trước số lượng cụm. Nó ít nhạy cảm với tiếng ồn hơn và có thể xử lý các cụm có mật độ khác nhau.

Để có kết quả thỏa mãn khi sử dụng thuật toán DBSCAN, giả định rằng các cụm khác nhau trong dữ liệu có mật độ tương đối giống nhau, theo mật độ, chúng tôi muốn nói đến số lượng điểm tồn tại trong mọi vùng lân cận N(x, ε) được xác định bởi bán kính ε và một điểm dữ liệu x. Tuyên bố này có thể được xác minh về mặt quang học bằng cách quan sát ví dụ DBSCAN ở giữa hình ảnh trên, trong đó các điểm xung quanh cụm màu xanh lam, có mật độ hơi khác, được coi là một phần của cụm màu cam.

Các tham số duy nhất cần thiết để triển khai DBSCAN là:

• MinPts = Các điểm tối thiểu mà một vùng lân cận của điểm dữ liệu cần phải có để điểm dữ liệu được coi là điểm cốt lõi của cụm
• ε = Bán kính của các vùng lân cận (nghĩa là chúng ta muốn “vòng tròn” xung quanh điểm dữ liệu trung tâm lớn đến mức nào )

1. Core Point : Loại điểm dữ liệu này có mật độ ≥ MinPts. Có nghĩa là số điểm dữ liệu trong N(x, ε) lớn hơn hoặc bằng MinPts.

2. Điểm biên : Loại điểm dữ liệu này có mật độ < MinPts nhưng khoảng cách(y, cp) ≤ ε trong đó cp là điểm cốt lõi. Có nghĩa là những điểm đó không có mật độ cần thiết để trở thành điểm cốt lõi nhưng chúng cũng không cách xa điểm cốt lõi để được coi là nhiễu.

Ví dụ: MinPts = 4, ε = 3 thì y là điểm biên

3. Điểm nhiễu : Loại điểm dữ liệu này có mật độ < MinPts và khoảng cách(z, cp) ≥ ε. Có nghĩa là nó không có mật độ cần thiết để trở thành điểm cốt lõi và nó cách xa bất kỳ điểm cốt lõi nào.

Ví dụ: MinPts = 4, ε = 3 thì z là điểm nhiễu

Và do đó, dựa trên quá trình phân loại điểm dữ liệu đó, thuật toán DBSCAN diễn ra như sau:

1. Lặp lại mọi điểm dữ liệu và phân loại nó theo một trong ba loại đó
2. Loại bỏ tất cả các điểm nhiễu
3. Xem xét tất cả các điểm cốt lõi nằm gần nhau trong cùng một cụm ( Có nghĩa là nếu cp_1 và cp_2 là các điểm cốt lõi và khoảng cách (cp_1, cp_2) ≤ ε thì cp_1 và cp_2 được coi là trong cùng một cụm. )
4. Chỉ định mọi điểm biên giới trong một cụm điểm cốt lõi dựa trên khoảng cách của chúng (các điểm biên giới nằm chính xác ở điểm giữa của hai cụm phải được giải quyết riêng, có thể tung đồng xu ;D)