Introduction
DBSCAN groups observations by looking for areas with many nearby points. Unlike a method that requires the analyst to specify the number of clusters first, DBSCAN can identify groups from local density and leave isolated observations unclustered as noise. Its result depends on two settings: a distance threshold and a minimum neighborhood size.
The central idea is that a dense point can extend a group to other nearby points, and those points may in turn extend it further. This creates a cluster through a chain of local connections; the cluster need not be a compact ball around a central representative. The definitions below make clear which points can extend such a chain and which can only be included at its edge.
This tutorial uses the standard convention that the point itself counts toward MinPts. Some software or descriptions may present the counting convention differently, so state the convention when interpreting results. DBSCAN also requires a distance definition suitable for the data. For numeric features, the distance and the scales of those features matter: a distance threshold is meaningful only relative to the chosen representation. The earlier material on distance matrices and scaling gives the groundwork for that choice.
From Core Points to Density-Reachable Groups
A core point can extend a group because it has enough nearby observations. If one of those observations is itself core, its neighborhood can extend the group again. This is the mechanism behind density reachability.
The condition on the preceding points matters. A border point may be reached from a core point, but it cannot continue the chain: it does not have enough neighbors to be core. In particular, a border point sitting between two dense groups cannot by itself join those groups. Two points are density-connected if some point can reach both by density-reachability chains. DBSCAN clusters are maximal density-connected groups, with border points included where they are adjacent to core points.
For each point, include the point itself and count all observations at distance no greater than \(\varepsilon\).
A point with at least MinPts observations in its neighborhood is core. Other points are not core.
Join core points that are within \(\varepsilon\) of one another. Continue through connected core points, so a sequence of local links can extend the group.
A non-core point within \(\varepsilon\) of a core point is border. A non-core point with no core point in its neighborhood is noise.
This process does not require a prespecified cluster count. The number of groups is determined by the core-point connections under the chosen \(\varepsilon\), MinPts, and distance. The choice of those settings is a separate modeling decision; here the focus is on how to interpret a specified choice.
Worked Examples
Worked Example: A Chain of Core Points With Border Endpoints
Five observations lie on a line at \(A=0\), \(B=1\), \(C=2\), \(D=3\), and \(E=4\). Use ordinary distance on the line, \(\varepsilon=1.1\), and MinPts \(=3\), counting each point itself. Classify the observations and identify the cluster.
Method. List every observation no more than 1.1 units away from each point, then compare the count with 3. The adjacent-point distance is 1, which is within the threshold; the distance between points two positions apart is 2, which is not.
For \(A\), the neighborhood is \(\{A,B\}\), with count 2, so \(A\) is not core. For \(B\), the neighborhood is \(\{A,B,C\}\), with count 3, so \(B\) is core. For \(C\), the neighborhood is \(\{B,C,D\}\), with count 3, so \(C\) is core. For \(D\), the neighborhood is \(\{C,D,E\}\), with count 3, so \(D\) is core. For \(E\), the neighborhood is \(\{D,E\}\), with count 2, so \(E\) is not core.
The core points \(B,C,D\) form a connected chain: \(B\) is within 1.1 of \(C\), and \(C\) is within 1.1 of \(D\). Point \(A\) is within 1.1 of core point \(B\), and \(E\) is within 1.1 of core point \(D\). Therefore \(A\) and \(E\) are border points, and all five observations belong to one cluster. There are no noise points.
Check. The two endpoints each have only two points in their neighborhoods, so neither is core; each nevertheless touches a core point. A common mistake is to treat every cluster member as a core point. The endpoint counts show why that is incorrect.
Worked Example: Two Groups and an Isolated Observation
Consider \(P=(0,0)\), \(Q=(1,0)\), and \(R=(0,1)\), together with \(U=(5,0)\), \(V=(6,0)\), \(W=(5,1)\), and \(Z=(10,10)\). Use Euclidean distance, \(\varepsilon=1.1\), and MinPts \(=3\), including the point itself. Find the clusters and noise points.
Method. First compute the distances within each nearby triple. In the first triple, \(d(P,Q)=1\) and \(d(P,R)=1\), while \(d(Q,R)=\sqrt{2}\approx1.414\), which exceeds 1.1. Thus \(P\)'s neighborhood is \(\{P,Q,R\}\), count 3, so \(P\) is core. \(Q\)'s neighborhood is \(\{P,Q\}\), count 2, and \(R\)'s is \(\{P,R\}\), count 2. They are non-core, but each is within \(\varepsilon\) of core point \(P\), so both are border points.
The second triple has the same distances: \(d(U,V)=1\), \(d(U,W)=1\), and \(d(V,W)=\sqrt{2}\approx1.414\). Therefore \(U\) is core, while \(V\) and \(W\) are border points. Distances between the two triples are much greater than 1.1; for example, \(d(Q,U)=4\). They cannot be connected by density reachability.
For \(Z\), the distances to the other points all exceed 1.1. Its neighborhood contains only itself, so its count is 1. It is non-core and has no core point within \(\varepsilon\), making it noise. The result is two clusters, \(\{P,Q,R\}\) and \(\{U,V,W\}\), and one noise point, \(Z\).
Check. The core point in each triple accounts for the two border points that are not close to each other. The wrong calculation would call \(Q\) and \(R\) core because they are both near \(P\); their own neighborhood counts, not the size of the cluster, determine whether they are core.
Worked Example: A Border Point Near Two Core Groups
Use Euclidean distance, \(\varepsilon=1\), and MinPts \(=4\). The left group consists of \(L_1=(0.1,0)\), \(L_2=(-0.2,0)\), \(L_3=(-0.2,0.1)\), and \(L_4=(-0.2,-0.1)\). The right group consists of \(R_1=(1.9,0)\), \(R_2=(2.2,0)\), \(R_3=(2.2,0.1)\), and \(R_4=(2.2,-0.1)\). There is also \(T=(1,0)\). Classify \(T\), and decide whether it connects the two groups.
Method. Within the left group, the greatest distance is between \(L_1\) and either \(L_3\) or \(L_4\): \(\sqrt{0.3^2+0.1^2}=\sqrt{0.10}\approx0.316\), less than 1. Thus each left-group point has all four left-group points in its neighborhood. By symmetry, the same holds for the right group. All eight of those points are core, even before considering \(T\).
The distance from \(T\) to \(L_1\) is \(0.9\), and the distance from \(T\) to \(R_1\) is also \(0.9\). Its distances to \(L_2,L_3,L_4\) are respectively \(1.2\), \(\sqrt{1.2^2+0.1^2}=\sqrt{1.45}\approx1.204\), and \(\sqrt{1.45}\approx1.204\). The corresponding distances to \(R_2,R_3,R_4\) have the same values. Hence \(T\)'s neighborhood is exactly \(\{T,L_1,R_1\}\), with count 3. Since 3 is less than MinPts \(=4\), \(T\) is not core.
Because \(T\) is within \(\varepsilon\) of core points \(L_1\) and \(R_1\), it is a border point. It does not connect the two groups: a chain cannot continue through \(T\), because \(T\) is not core, and the core groups are farther than 1 apart. Depending on the implementation's assignment rule, a border point adjacent to two clusters may be assigned to either one; it does not merge them.
Check. \(T\) has three neighbors when it counts itself, not four. The common mistake is to infer that \(T\) is core because it is close to points in both groups. Core status depends on \(T\)'s own neighborhood count.
Why the Expansion Rule Works
A useful way to justify the expansion process is to represent each core point as a vertex in a graph, connecting two core points whenever their distance is at most \(\varepsilon\). A connected component of this graph is a set of core points linked by a chain of core-to-core steps. Each such step is directly density-reachable, so following a path in the graph gives a density-reachability chain between its core points.
Conversely, a density-reachability chain between core points can only pass through core points before its endpoint. Each successive pair in that chain is within \(\varepsilon\), so it is a path in the core-point graph. Therefore two core points belong to the same density-reachable group exactly when they lie in the same connected component of that graph. Non-core points adjacent to a component may then be included as border points; they cannot create a path between components.
This explains why DBSCAN expands from core points rather than simply collecting every point that is near any member of a cluster. The expansion rule preserves the distinction between a dense connection and a sparse edge point.
Interpretation and Common Traps
| Point type | Neighborhood count | Role in DBSCAN |
|---|---|---|
| Core | At least MinPts | Can start or continue density expansion |
| Border | Below MinPts, but within \(\varepsilon\) of a core point | Can be included at a cluster's edge but cannot expand it |
| Noise | Below MinPts and not within \(\varepsilon\) of a core point | Unassigned to a cluster under the specified settings |
DBSCAN can be useful when a cluster count is not known in advance and when the analyst wants the method to identify isolated observations rather than forcing every observation into a group. However, its labels are conditional on the distance definition and the specified settings. “Noise” means not assigned to a cluster under those choices; it does not establish that an observation is erroneous or unimportant. Also, a point labelled border does not provide evidence of a dense connection through itself.
- Forgetting to count the point itself. Under the convention used here, the point is one member of its own neighborhood.
- Using distance less than \(\varepsilon\) rather than at most \(\varepsilon\). A point exactly at the threshold belongs to the neighborhood.
- Letting a border point expand a cluster. Only core points can continue density reachability.
- Assuming a cluster count is an input. DBSCAN discovers the number of groups implied by the chosen neighborhood rule and data; it does not ask for a target count.
- Interpreting noise as a judgment about the observation. Noise is a model classification under a chosen distance and settings, not a conclusion about data quality.
Check Your Understanding
For each problem, use the stated convention that a point counts toward its own neighborhood. Classify the points and give the cluster membership where requested.
- Four points on a line are at \(0\), \(0.5\), \(1\), and \(3\). With \(\varepsilon=0.6\) and MinPts \(=3\), classify each point and identify any cluster. (Answer: \(0.5\) is core; \(0\) and \(1\) are border; they form one cluster; \(3\) is noise.)
- Points \(A=(0,0)\), \(B=(0.5,0)\), and \(C=(0,0.5)\) use Euclidean distance, \(\varepsilon=0.6\), and MinPts \(=3\). Is \(A\) core? Are \(B\) and \(C\) core, border, or noise? (Answer: \(A\) is core; \(B\) and \(C\) are border, since \(d(B,C)=\sqrt{0.5}\approx0.707>0.6\); all three form one cluster.)
- Points on a line are at \(0\), \(0.4\), \(0.8\), and \(2\). With \(\varepsilon=0.9\) and MinPts \(=3\), find the core points and noise points. (Answer: \(0\), \(0.4\), and \(0.8\) are core; they form one cluster; \(2\) is noise.)
- Suppose a non-core point is within \(\varepsilon\) of one core point in each of two separate core components. Can it merge those components? Explain using density reachability. (Answer: No. It is a border point reachable from both components, but because it is not core, the chain cannot continue through it; it does not connect the core components.)