DBSCAN (Phân cụm không gian dựa trên mật độ của các ứng dụng có nhiễu)

DBSCAN hoạt động như thế nào

DBSCAN xác định các cụm dựa trên khái niệm về khả năng tiếp cận mật độ. Nó xem các cụm là các vùng có mật độ cao được phân tách bởi các vùng có mật độ thấp. Hành vi của thuật toán chủ yếu được kiểm soát bởi hai tham số:

1. Epsilon (eps): Tham số này xác định khoảng cách tối đa giữa hai điểm dữ liệu để một điểm được coi là nằm trong vùng lân cận của điểm kia. Về cơ bản, nó tạo ra bán kính xung quanh mỗi điểm.
2. Điểm tối thiểu (minPts): Tham số này chỉ định số điểm dữ liệu tối thiểu cần có trong vùng lân cận eps của một điểm (bao gồm chính điểm đó) để điểm đó được phân loại là 'điểm lõi'.

Dựa trên các thông số này, các điểm dữ liệu được phân loại thành ba loại:

• Điểm cốt lõi: Một điểm là điểm cốt lõi nếu nó có ít nhất minPts những người hàng xóm trong đó eps bán kính. Những điểm này thường nằm ở bên trong một cụm.
• Điểm biên giới: Một điểm là điểm biên giới nếu có thể tiếp cận được từ một điểm cốt lõi (tức là trong eps bán kính của một điểm lõi) nhưng không có minPts hàng xóm của chính nó. Các điểm biên giới nằm trên rìa của cụm.
• Điểm nhiễu (Điểm ngoại lệ): Một điểm không phải là điểm lõi cũng không phải là điểm biên được coi là nhiễu. Những điểm này thường bị cô lập trong các vùng có mật độ thấp.

Thuật toán bắt đầu bằng cách chọn một điểm dữ liệu tùy ý, chưa được truy cập. Nó kiểm tra xem điểm đó có phải là điểm cốt lõi hay không bằng cách kiểm tra eps-neighborhood. Nếu đó là điểm cốt lõi, một cụm mới được hình thành và thuật toán đệ quy thêm tất cả các điểm có thể đạt được mật độ (điểm cốt lõi và điểm biên trong khu vực lân cận) vào cụm này. Nếu điểm được chọn là điểm nhiễu, nó được đánh dấu tạm thời như vậy và thuật toán di chuyển đến điểm chưa được ghé thăm tiếp theo. Quá trình này tiếp tục cho đến khi tất cả các điểm đã được ghé thăm và được gán cho một cụm hoặc được đánh dấu là nhiễu. Để tìm hiểu sâu hơn về phương pháp luận ban đầu, hãy tham khảo bài báo nghiên cứu: "Một thuật toán dựa trên mật độ để khám phá các cụm trong cơ sở dữ liệu không gian lớn có nhiễu".

Ưu điểm và nhược điểm chính

DBSCAN mang lại một số lợi ích:

• Xử lý các hình dạng tùy ý: Không giống như các thuật toán như K-means, DBSCAN có thể tìm thấy các cụm không phải hình cầu.
• Không cần xác định trước số lượng cụm: Số lượng cụm được xác định bởi thuật toán dựa trên mật độ.
• Chống lại các điểm bất thường: Có cơ chế tích hợp để xác định và xử lý các điểm nhiễu.

Tuy nhiên, nó cũng có những hạn chế:

• Độ nhạy tham số: Chất lượng của kết quả phân cụm phụ thuộc rất nhiều vào sự lựa chọn eps và minPts. Việc tìm kiếm các thông số tối ưu có thể là một thách thức. Các công cụ như scikit-learn cung cấp các triển khai có thể điều chỉnh được.
• Khó khăn với mật độ thay đổi: Nó gặp khó khăn với các tập dữ liệu trong đó các cụm có mật độ khác nhau đáng kể, như một eps-minPts sự kết hợp này có thể không hiệu quả với tất cả các cụm.
• Dữ liệu chiều cao: Hiệu suất có thể giảm sút trong không gian chiều cao do " lời nguyền của chiều ", khi đó khái niệm mật độ trở nên ít ý nghĩa hơn.

DBSCAN so với các phương pháp phân cụm khác

DBSCAN thường được so sánh với các thuật toán phân cụm khác, đặc biệt là phân cụm K-means . Những khác biệt chính bao gồm:

• Hình dạng cụm: K-means giả định các cụm có hình cầu và kích thước bằng nhau, trong khi DBSCAN có thể tìm thấy các cụm có hình dạng tùy ý.
• Số lượng cụm: K-means yêu cầu người dùng chỉ định số lượng cụm (k) trước đó, trong khi DBSCAN tự động xác định điều này.
• Xử lý ngoại lệ: K-means gán mọi điểm vào một cụm, khiến nó nhạy cảm với các ngoại lệ. DBSCAN xác định rõ ràng và cô lập các ngoại lệ như nhiễu.
• Độ phức tạp tính toán: K-means thường nhanh hơn DBSCAN, đặc biệt là trên các tập dữ liệu lớn, mặc dù độ phức tạp của DBSCAN có thể thay đổi tùy thuộc vào lựa chọn tham số và tối ưu hóa cấu trúc dữ liệu như cây KD .

Ứng dụng trong thế giới thực

Khả năng tìm nhóm dày đặc và phân lập các giá trị ngoại lai của DBSCAN khiến nó phù hợp với nhiều ứng dụng khác nhau:

• Phát hiện bất thường : Xác định các mô hình bất thường khác với hành vi bình thường. Ví dụ: phát hiện các giao dịch thẻ tín dụng gian lận thường xuất hiện dưới dạng các điểm riêng biệt so với các cụm chi tiêu hợp pháp dày đặc hoặc xác định các cuộc xâm nhập vào dữ liệu lưu lượng mạng để bảo mật mạng . Khám phá các khái niệm liên quan trong Vision AI để phát hiện bất thường .
• Phân tích dữ liệu không gian: Phân tích dữ liệu địa lý hoặc không gian. Ví dụ, nhóm các vị trí khách hàng để xác định phân khúc thị trường, phân tích các điểm nóng tội phạm trong một thành phố ( AI trong thành phố thông minh ) hoặc xác định các mẫu trong phân tích hình ảnh vệ tinh để phân loại sử dụng đất hoặc giám sát môi trường .
• Phân tích dữ liệu sinh học: Phân nhóm dữ liệu biểu hiện gen hoặc xác định cấu trúc trong cơ sở dữ liệu protein.
• Hệ thống đề xuất: Nhóm người dùng có sở thích tương tự dựa trên dữ liệu tương tác thưa thớt ( tổng quan về hệ thống đề xuất ).

DBSCAN và Ultralytics

Hệ sinh thái Ultralytics chủ yếu tập trung vào các mô hình học có giám sát , chẳng hạn như Ultralytics YOLO cho các tác vụ bao gồm phát hiện đối tượng , phân loại hình ảnh và phân đoạn hình ảnh . Mặc dù DBSCAN, là một phương pháp không giám sát, không được tích hợp trực tiếp vào các vòng đào tạo cốt lõi của các mô hình như YOLOv8 hoặc YOLO11 , nhưng các nguyên tắc của nó có liên quan trong bối cảnh rộng hơn của thị giác máy tính (CV) và phân tích dữ liệu . Việc hiểu mật độ và phân phối dữ liệu là rất quan trọng khi chuẩn bị và phân tích các tập dữ liệu để đào tạo hoặc khi xử lý hậu kỳ đầu ra của mô hình, ví dụ, phân cụm các đối tượng được phát hiện dựa trên vị trí gần không gian của chúng sau khi suy luận . Các nền tảng như Ultralytics HUB cung cấp các công cụ để quản lý và trực quan hóa tập dữ liệu, có thể bổ sung cho các kỹ thuật phân tích dữ liệu khám phá, trong đó các thuật toán phân cụm như DBSCAN có thể được áp dụng.