Centroid methods such as k-means assume that each cluster is compact around a center and force every observation into some cluster. Hierarchical clustering produces a whole tree and leaves the choice of a cut to the user. DBSCAN takes a different view: a cluster is a region of the space where observations are densely packed, separated from other such regions by sparse space, and observations in sparse space are declared noise rather than forced into a cluster. The method needs a distance, so the preceding unit on distances and scaling applies directly, and its output depends on two parameters that we study carefully.
Definitions
Definition 15.1.1
(Neighborhood, core, border and noise points)
Let be a finite set of points with a metric , and fix a radius and an integer (called minPts). The -neighborhood of is , which always contains itself. A point is a core point if . A point is directly density-reachable from if is a core point and . A point is density-reachable from if there is a chain in which each is directly density-reachable from , ; thus are core points. A non-core point density-reachable from some core point is a border point; every other point is noise.
The count in the core condition includes the point itself. Conventions differ between textbooks and software, and a stated value of minPts means something different if the point is excluded, so the convention must always be recorded with the parameters.
The algorithm
- Mark every point unlabeled and set the cluster counter .
- For each point in a fixed order: if is already labeled or is not a core point, skip it. Otherwise increase , label with , and put in a queue.
- While the queue is nonempty, remove a point . For each that is unlabeled, give it label ; if is a core point, add it to the queue.
- At the end, points still unlabeled are noise.
Theorem 15.1.2
(Core clusters are well defined and DBSCAN finds them)
Density-reachability restricted to core points is an equivalence relation. Let be its equivalence classes, which are the connected components of the graph on the core points with an edge between and whenever . DBSCAN terminates after at most queue insertions, the core points in each class receive one common label and different classes receive different labels, and every border point receives the label of some class containing a core point within distance of it. Every noise point stays unlabeled. The partition of core points does not depend on the processing order; only the label given to a border point near several classes may.
Proof
(Proof)
Reflexivity holds by a chain of length zero. For symmetry, let be core points and let be a chain. Every with is core by definition and is core by assumption, so every consecutive pair consists of two core points at distance at most ; the reversed chain is valid because is symmetric and every term is core. Transitivity follows by concatenating chains. Hence the classes are exactly the connected components of the -graph on core points.
Termination: a point is placed in the queue only when it receives a label, and a point is labeled at most once, so at most insertions occur and each inner loop is finite. Invariant: during the run seeded by core point , every labeled point is density-reachable from , and every core point labeled in this run has been, or is waiting in the queue to be, scanned. When the queue empties, all core points of the class of have been labeled, since any chain of core points from can be followed one step at a time. Core points of other classes cannot be reached, because reaching one would put it in the class of . A core point is never skipped as already labeled unless an earlier seed's run labeled it, so each class receives exactly one label. A border point is labeled only when it lies in the neighborhood of a scanned core point, and a noise point is in the neighborhood of no core point, so it is never labeled.
Proof X-ray
Where the hypotheses enter the proof
The proof has one structural move and one place where the hypotheses are easy to misplace. The structural move is to replace density-reachability by connectivity in the -graph on the core points; order-independence is then automatic, because connected components do not depend on the order in which a search visits them. The queue plays the role of a breadth-first search that visits exactly one component, together with the non-core points adjacent to it.
Symmetry is where the hypotheses are used. The symmetry of lets a step be undone as , and the requirement that every point of the chain except the last be core is what makes the undone step legal, since a step may only leave a core point. If the endpoint is also core, the reversed chain is a chain. If is a border point, the last step cannot be reversed, so density-reachability is not symmetric outside the core points and the statement has to be restricted to them.
The argument closes because each point is labeled at most once and enters the queue only when labeled, so the queue empties after at most insertions. A border point adjacent to two classes is genuinely reachable from both, which is why its label, unlike the partition of the core points, may depend on the order.
Cost: if each point's neighborhood is computed once and kept, the core tests and step 3 need one neighborhood query per point, in total queries, each of which scans all points. The naive implementation therefore uses distance evaluations. A spatial index can make each query cheaper in low dimensions, but the worst case is not improved in general and the benefit fades as the dimension grows.
Concept lensGeometric
A cluster as a union of balls
Geometrically, a cluster (its core class and border points together) lies in the union of the closed balls of radius centered at the core points of that class. Conversely, every point of in that union is a core point of the class or a border point, which another cluster may have labeled first. A cluster is thus a chain of overlapping balls, and noise points are exactly those lying in no ball around a core point. In the first worked example, the balls around cover , which contains the border points and .
Worked examples
Worked example 15.1.3
(Two clusters and noise on a line)
Take the points with and . The neighborhoods are , , , , , , , and . The core points are and . The core points form one class, since . The points and are border points of this class, and and are border points of the class . The point is noise. The clusters are and ; they are not joined because and is not a core point.
Now vary with . For every neighborhood is a single point, so every point is noise. For , the point has and becomes a core point, and so does with ; the two clusters merge into , while remains noise because its nearest point is away.
Worked example 15.1.4
(A border point that belongs to two clusters)
Take the points with and . The neighborhood sizes are in the order listed; for example , and . The core points are and . The two groups are different classes, because the only link between them is the non-core point , which cannot extend a chain. The points and are border points of one class each. The point is a border point of both classes: it lies within of the core point and the core point . If the scan visits the points in increasing order, the run seeded at comes first and labels as a member of the left cluster; if the run seeded at came first, would instead join the right cluster. The partition of core points is the same in both cases, but the label of depends on the order. With instead, would itself be a core point and would connect everything into one cluster.
Worked example 15.1.5
(Boundary cases: distance exactly and too few points)
Take the points with and . Because the neighborhood is closed, , , and . The core points are and ; they are at distance , so they form one class, and and are border points of it. The single cluster is . Had the neighborhood used the strict inequality , every neighborhood would be a single point and all four points would be noise, so the convention at the boundary changes the answer.
Now take only the two points and with . Every neighborhood has at most two points, so no point is core, no cluster is formed and both points are noise. In general, if then no cluster can be formed.
Common mistakes and subtle points
Common mistake
(DBSCAN is not parameter-free and does not handle varying density)
Different give different clusterings, as the parameter study shows, and a single cannot describe a data set that contains a dense cluster and a much sparser one: a radius small enough to separate the dense groups declares the sparse group noise, and a radius large enough to keep the sparse group together merges the dense ones. Border assignment is not symmetric or canonical. DBSCAN output is also not a statement about probability: noise means only that a point is not density-reachable under the chosen parameters. Finally, remember that distances must be meaningful, so unscaled features can distort the neighborhoods in the same way as for nearest-neighbor methods.
The next item is a specific failure of the definition rather than general advice.
Counterexample mode
Border points break symmetry of density-reachability
Claim: if is density-reachable from , then is density-reachable from , so density-connected sets could be formed over all points. Take the three points with and . Then has two points, has three and has two, so only is a core point. The point is directly density-reachable from , because is core and . But is not density-reachable from : a chain with starting at would need to be core, and it is not, so the only chain from is the trivial one, which reaches only . The claim is false, and the failure is exactly that is a border point. The repaired statement is the one in the theorem: density-reachability is symmetric on core points, and a border point is attached to a class through a core point rather than by symmetry.
Two further errors occur when the definition is applied by hand.
Common mistake
(Counting neighbors without the point itself)
In the first worked example, has three points, so is a core point for . If one counted only the other points, would have two neighbors and fail the test; in fact no point of that example has three other points within distance , so everything would be noise. The count includes the point itself, as in the definition. When comparing with software, check which convention it uses: a package that excludes the point and uses minPts corresponds to here.
Common mistake
(Letting a border point extend a cluster)
A chain may pass only through core points. In the border-point example, and are both within of the point , but has only three points in its neighborhood, so it is not core for and does not link the two groups. Treating as a bridge would merge two clusters that DBSCAN keeps apart.
Exercises
Quick check
(Run DBSCAN by hand on the points with and . List the core points, the clusters and the noise.)
Compute the neighborhoods first.
Solution · Answer
The neighborhoods are , , , , , , , . The core points are , and . The clusters are and , since and are within of each other. The point is noise.
Quick check
(Prove that a core point for remains a core point for every with the same .)
Compare the two neighborhoods.
Solution · Answer
If then implies , so . Hence .
Quick check
(For the eleven points of the border-point example with , how many clusters and noise points result when ?)
Count the points in each neighborhood.
Solution · Answer
The neighborhood sizes are , all at least , so every point is a core point. The point links and (both within ), so the single class contains all eleven points: one cluster and no noise.
Exercise 15.1.6
(Show that for no point is noise and the clusters are the connected components of the graph joining points at distance at most . Apply this to the points with and compare with .)
CoreProof
Hint(1)
Every neighborhood contains the point itself.
Solution(4)
- 1
Show that every point is a core point
Border points are non-core points and noise points are non-core points that are not density-reachable, so with there are neither.
Because: The neighborhood of contains , so .
- 2
Identify the clusters
Key step
All points are core, so the clusters are the connected components of the graph that joins points at distance at most .
Because: The core clusters are the connected components of the -graph on the core points.
- 3
Compute the components for the eight points
With the consecutive gaps are . The components are , and : three clusters.
- 4
Compare with m=2
∎For the point has only itself in its neighborhood, so it is noise. Every other point has a neighbor within distance and remains core, so the first two clusters are unchanged: two clusters and one noise point.