DBSCAN là viết tắt của cụm từ Phân cụm không gian dựa trên mật độ của các ứng dụng có tiếng ồn. Nó là một thuật toán phân cụm dựa trên mật độ. Thuật toán tăng các vùng có mật độ đủ cao thành các cụm và tìm các cụm có kiến trúc tùy ý trong cơ sở dữ liệu không gian có nhiễu. Nó đại diện cho một cụm như một nhóm các điểm được kết nối với mật độ tối đa.
Khái niệm phân cụm dựa trên mật độ bao gồm một số định nghĩa mới như sau -
-
Vùng lân cận trong bán kính ε của một đối tượng nhất định được gọi là ε vùng lân cận của đối tượng.
-
Nếu ε-vùng lân cận của một đối tượng bao gồm ít nhất một số tối thiểu, MinPts, của các đối tượng, thì đối tượng đó được gọi là đối tượng cốt lõi.
-
Cho một tập hợp các đối tượng, D, có thể nói rằng một đối tượng p có thể tiếp cận trực tiếp với mật độ từ đối tượng q nếu p nằm bên trong ε-lân cận của q và q là một đối tượng cốt lõi.
-
Đối tượng p có thể tiếp cận theo mật độ từ đối tượng q liên quan đến ε và MinP trong một nhóm đối tượng, D, nếu có một chuỗi đối tượng p 1 , ..., p n , trong đó p 1 =q và p n =p bao gồm p i +1 có thể truy cập trực tiếp theo mật độ từ p i liên quan đến ε và MinPts, cho 1 ≤ i ≤ n, p i ε D.
-
Một đối tượng p được liên kết mật độ với đối tượng q liên quan đến ε và MinPts trong một nhóm đối tượng, D, nếu có một đối tượng o ε D sao cho cả p và q đều có thể truy cập được theo mật độ o liên quan đến ε và MinPts.
Khả năng tiếp cận mật độ là sự kết thúc bắc cầu của khả năng tiếp cận mật độ trực tiếp và kết nối này là không đối xứng. Chỉ có các đối tượng cốt lõi là có thể truy cập được với nhau về mật độ. Kết nối mật độ là một quan hệ đối xứng.
Cụm dựa trên mật độ là một nhóm các đối tượng được kết nối với mật độ là tối đa liên quan đến khả năng tiếp cận theo mật độ. Mỗi đối tượng không có trong bất kỳ cụm nào đều được coi là nhiễu.
DBSCAN tìm kiếm các cụm bằng cách kiểm tra vùng 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 bao gồm nhiều hơn MinPts, một cụm mới với p làm đối tượng cốt lõi sẽ được tạo ra. DBSCAN thu thập lặp lại các đối tượng có thể tiếp cận theo mật độ trực tiếp từ các đối tượng cốt lõi này, có thể chứa sự hợp nhất của một vài cụm có thể tiếp cận theo mật độ. Quá trình xóa khi không có điểm mới nào có thể được chèn vào bất kỳ cụm nào.
Nếu sử dụng chỉ mục không gian, độ phức tạp tính toán của DBSCAN là O (nlogn), trong đó n là số đối tượng cơ sở dữ liệu. Do đó, nó là O (n 2 ). Với các cài đặt thích hợp của các tham số ε và MinPts do người dùng đại diện, thuật toán có hiệu quả trong việc phát hiện các cụm có hình dạng tùy ý.