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 phổ biến, được sử dụng để nhóm các điểm dữ liệu được đóng gói chặt chẽ với nhau, đánh dấu các điểm nằm riêng lẻ trong các vùng mật độ thấp là ngoại lệ. Không giống như các phương pháp phân cụm khác, DBSCAN không yêu cầu chỉ định trước số lượng cụm. Khả năng tìm các cụm có hình dạng tùy ý và khả năng chống nhiễu của nó làm cho nó trở thành một công cụ mạnh mẽ cho khai thác dữ liệu và phân tích dữ liệu. Thuật toán này lần đầu tiên được giới thiệu trong một bài báo năm 1996 của Martin Ester, Hans-Peter Kriegel, Jörg Sander và Xiaowei Xu, bài báo này đã trở thành một công trình nền tảng trong lĩnh vực này.

Cách DBSCAN hoạt động

DBSCAN xác định các cụm dựa trên mật độ của các điểm dữ liệu trong một không gian nhất định. Nó hoạt động dựa trên hai tham số chính:

• Epsilon (ε hoặc eps): Tham số này xác định bán kính của một vùng lân cận xung quanh một điểm dữ liệu. Tất cả các điểm trong khoảng cách này được coi là lân cận.
• Điểm tối thiểu (MinPts): Đây là số lượng điểm dữ liệu tối thiểu (bao gồm cả chính điểm đó) cần thiết để tạo thành một vùng hoặc cluster dày đặc.

Dựa trên các tham số này, DBSCAN phân loại mọi điểm dữ liệu thành một trong ba loại:

1. Điểm lõi: Một điểm là điểm lõi nếu nó có ít nhất MinPts bên trong nó eps lân cận. Những điểm này là phần bên trong của một cụm.
2. Điểm biên: Một điểm là điểm biên nếu nó nằm trong eps lân cận của một điểm lõi nhưng không có đủ láng giềng để tự nó là một điểm lõi. Những điểm này tạo thành rìa của một cụm.
3. Noise Points (Outliers) (Điểm Nhiễu (Giá trị Ngoại lai)):/strong> Một điểm được coi là nhiễu nếu nó không phải là điểm lõi cũng không phải là điểm biên. Đây là những giá trị ngoại lai không thuộc bất kỳ cluster (cụm) nào.

Thuật toán bắt đầu với một điểm tùy ý và truy xuất vùng lân cận của nó. Nếu đó là một điểm lõi, một cụm mới sẽ được tạo. Sau đó, thuật toán lặp đi lặp lại mở rộng cụm bằng cách thêm tất cả các hàng xóm có thể truy cập trực tiếp vào nó, một quá trình tiếp tục cho đến khi không còn điểm nào có thể được thêm vào bất kỳ cụm nào. Bạn có thể xem triển khai trực quan trong tài liệu scikit-learn.

Các ứng dụng AI/ML thực tế

Khả năng xác định nhiễu và khám phá các cụm phi tuyến tính của DBSCAN làm cho nó có giá trị cao trong nhiều lĩnh vực khác nhau:

• Phân tích không gian địa lý: Các nhà quy hoạch đô thị và nhà địa lý học sử dụng DBSCAN để phân tích dữ liệu không gian. Ví dụ: bằng cách phân cụm tọa độ GPS của các vụ tai nạn giao thông, họ có thể xác định các điểm nóng tai nạn. Tương tự, nó có thể được sử dụng để tìm các cụm ca bệnh được báo cáo, giúp các nhà dịch tễ học theo dõi sự bùng phát dịch bệnh. Các tổ chức như Cơ quan Thông tin Địa không gian của Nhật Bản sử dụng các phương pháp dựa trên mật độ tương tự để lập bản đồ.
• Phát hiện bất thường trong Tài chính: Trong lĩnh vực tài chính, DBSCAN có thể được sử dụng để phát hiện các giao dịch gian lận. Bằng cách phân cụm các kiểu chi tiêu điển hình của khách hàng, bất kỳ giao dịch nào nằm ngoài các cụm này (tức là được gắn nhãn là nhiễu) đều có thể được gắn cờ để điều tra thêm. Cách tiếp cận này là một thành phần quan trọng của các hệ thống phát hiện gian lận hiện đại.

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 thể hiện. Mặc dù DBSCAN là một phương pháp không giám sát, nhưng các nguyên tắc của nó có liên quan trong bối cảnh rộng lớn hơn của thị giác máy tính (CV).

Ví dụ: sau khi thực hiện object detection với một mô hình như YOLO11 trên một video về một con phố đông đúc, DBSCAN có thể được áp dụng cho tọa độ trung tâm của các bounding box được phát hiện. Bước hậu xử lý này có thể nhóm các phát hiện người đi bộ riêng lẻ thành các đám đông riêng biệt, cung cấp mức độ hiểu biết về cảnh cao hơn. Hiểu phân phối dữ liệu cũng rất quan trọng khi chuẩn bị datasets để training. Phân tích dữ liệu thăm dò bằng DBSCAN có thể tiết lộ các mẫu hoặc dị thường trong dataset, có thể được quản lý và trực quan hóa bằng các nền tảng như Ultralytics HUB.

Phân biệt với các thuật ngữ liên quan

• Phân cụm K-Means: Sự khác biệt đáng kể nhất là 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 số lượng cụm. K-Means cũng gặp khó khăn với các cụm không hình cầu và nhạy cảm với các giá trị ngoại lệ, vì nó buộc mọi điểm vào một cụm. DBSCAN vượt trội trong việc tìm kiếm các cụm có hình dạng tùy ý và cô lập hiệu quả các giá trị ngoại lệ dưới dạng nhiễu.
• Phân cụm phân cấp: Phương pháp này tạo ra một cây các cụm, được gọi là dendrogram. Mặc dù hữu ích để trực quan hóa các cấu trúc cụm lồng nhau, nhưng nó có thể tốn kém hơn về mặt tính toán trên các tập dữ liệu lớn so với DBSCAN. Sự lựa chọn giữa chúng thường phụ thuộc vào kích thước tập dữ liệu và đầu ra mong muốn, như được nêu trong hướng dẫn về chọn thuật toán phân cụm phù hợp.