DBSCAN là viết tắt của Density-Based Spatial Clustering of Applications with Noise (Cụm hóa không gian dựa trên mật độ của ứng dụng với nhiễu). Đây là thuật toán cụm hóa 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à tìm các cụm hình dạng tùy ý trong cơ sở dữ liệu không gian với nhiễu. Nó biểu diễn một cụm như một nhóm tối đa các điểm kết nối mật độ.
Khái niệm cụm hóa dựa trên mật độ bao gồm một số định nghĩa mới:
- Lân cận trong bán kính ε của một đối tượng cho trước được gọi là ε-lân cận của đối tượng.
- Nếu ε-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 đối tượng, thì đối tượng được gọi là đối tượng lõi (core object).
- Cho tập đối tượng D, có thể nói đối tượng p là trực tiếp density-reachable từ đối tượng q nếu p nằm trong ε-lân cận của q, và q là đối tượng lõi.
- Đối tượng p là density-reachable từ đối tượng q về ε và MinPts trong nhóm đối tượng D, nếu tồn tại chuỗi đối tượng p₁,..., pₙ, với p₁ = q và pₙ = p, trong đó pᵢ₊₁ trực tiếp density-reachable từ pᵢ về ε và MinPts, với 1 ≤ i ≤ n, pᵢ ∈ D.
- Đối tượng p là density-connected đến đối tượng q về ε và MinPts trong nhóm D, nếu tồn tại đối tượng o ∈ D sao cho cả p và q đều density-reachable từ o về ε và MinPts.
Density reachability là bao bao đóng truyền tĩnh của direct density reachability, và mối quan hệ này bất đối xứng. Chỉ có đối tượng lõi mới density-reachable lẫn nhau. Density connectivity là quan hệ đối xứng.
Một cụm dựa trên mật độ là nhóm các đối tượng density-connected tối đa về density-reachability. Mỗi đối tượng không nằm trong bất kỳ cụm nào được coi là nhiễu.
DBSCAN tìm kiếm 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 điểm p bao gồm nhiều hơn MinPts, một cụm mới với p là đối tượng lõi được tạo. DBSCAN lặp lại thu thập các đối tượng trực tiếp density-reachable từ các đối tượng lõi này, có thể bao gồm hợp nhất một vài cụm density-reachable. Quy trình dừng khi không có điểm mới có thể thêm vào bất kỳ cụm nào.
Nếu chỉ mục không gian được dùng, độ phức tạp tính toán của DBSCAN là O(n log n), với n là số đối tượng cơ sở dữ liệu. Do đó là O(n²). Với cài đặt tham số phù hợp ε và MinPts do người dùng đại diện, thuật toán hiệu quả khám phá cụm hình dạng tùy ý.