Tuning Epsilon And MinPts In DBSCAN

Why DBSCAN Requires Parameter Checks

DBSCAN forms groups from regions of sufficiently high point density. Its two parameters determine what “sufficiently high” means: epsilon (\(\varepsilon\)) is the distance threshold for a neighbourhood, and MinPts is the minimum number of observations in that neighbourhood for its centre to qualify as a core point. A small change to either setting can change which observations are core, which are border points, and which are labelled as noise.

There is rarely a single parameter pair that can be selected by a formula alone. A k-distance plot helps identify plausible values of \(\varepsilon\), but the plot does not certify that the resulting clusters are useful. The practical check is to run DBSCAN at a small set of candidate settings and examine how the assignments change in the context of the problem.

Definition: For an observation \(x_i\), its \(\varepsilon\)-neighbourhood is the set of observations whose distance from \(x_i\) is at most \(\varepsilon\). This neighbourhood includes \(x_i\) itself. The observation is a core point if its \(\varepsilon\)-neighbourhood contains at least MinPts observations. A point that is not core but lies within \(\varepsilon\) of a core point can be assigned as a border point. An observation that is neither core nor reachable from a core point is labelled noise.

This self-inclusion convention matters when choosing and interpreting MinPts. For example, MinPts \(=4\) requires at least three other observations within the specified distance, as well as the observation itself. A k-distance plot can use a different convention: many nearest-neighbour functions report distances to neighbours excluding the observation itself. State which convention is in use before connecting a plotted distance to MinPts.

Using a k-Distance Plot

Fix a value of MinPts. For each observation, find the distance to its \((\text{MinPts}-1)\)th nearest other observation. Sort these distances and plot them against their order. This is the k-distance plot under the self-inclusion convention above. A sharp upward bend can indicate that the later observations need much larger neighbourhood radii than the earlier ones. A candidate \(\varepsilon\) near the bend is worth testing.

The reason for this diagnostic is direct: an observation is core exactly when it has at least MinPts observations in its \(\varepsilon\)-neighbourhood. Since one of those observations is itself, it needs at least MinPts \(-1\) other observations at distance no greater than \(\varepsilon\). Thus, its k-distance is at most \(\varepsilon\) exactly when it meets the core-point count requirement.

x_i\text{ is core} \quad\Longleftrightarrow\quad d_{i,(\text{MinPts}-1)}\leq \varepsilon

Here \(d_{i,k}\) denotes the distance from \(x_i\) to its \(k\)th nearest other observation. The equivalence concerns core status only. It does not by itself determine which core points are connected, whether border points join a cluster, or whether the resulting groups are useful.

Worked Example: Finding Candidate Epsilon Values

A hypothetical analyst has eight observations on a single prepared feature, with values \(0,\ 0.1,\ 0.2,\ 0.3,\ 0.4,\ 1.0,\ 1.1,\ 3.0\). The feature’s distance scale is meaningful for this analysis. Using MinPts \(=3\), calculate the k-distances, sort them, and identify a candidate \(\varepsilon\). Distances are absolute differences, and the observation itself is excluded when finding other neighbours.

Method. Since MinPts \(=3\) includes the observation itself, find each observation’s second-nearest other observation.

For \(0\), the other-observation distances begin \(0.1,\ 0.2,\ 0.3\), so its k-distance is \(0.2\). For \(0.1\), the two nearest distances are \(0.1\) and \(0.1\), giving \(0.1\). For \(0.2\), the two nearest are \(0.1\) and \(0.1\), giving \(0.1\). For \(0.3\), they are \(0.1\) and \(0.1\), giving \(0.1\). For \(0.4\), they are \(0.1\) and \(0.2\), giving \(0.2\).

For \(1.0\), the nearest other observation is \(1.1\), at distance \(0.1\); the next nearest is \(0.4\), at distance \(0.6\), so its k-distance is \(0.6\). For \(1.1\), the nearest is \(1.0\), at distance \(0.1\), and the next nearest is \(0.4\), at distance \(0.7\), so its k-distance is \(0.7\). For \(3.0\), the nearest is \(1.1\), at distance \(1.9\), and the next nearest is \(1.0\), at distance \(2.0\), so its k-distance is \(2.0\).

In the order of the original observations, the k-distances are \(0.2,\ 0.1,\ 0.1,\ 0.1,\ 0.2,\ 0.6,\ 0.7,\ 2.0\). In increasing order they are \(0.1,\ 0.1,\ 0.1,\ 0.2,\ 0.2,\ 0.6,\ 0.7,\ 2.0\). There is a noticeable increase between \(0.2\) and \(0.6\), so values around \(0.2\) to \(0.6\) deserve investigation. The plot alone does not dictate which value to use; the next example checks assignments at selected values.

Common mistake avoided: using the third-nearest other observation for MinPts \(=3\). Because the point itself counts toward MinPts, the relevant distance is to the second-nearest other observation. In particular, the second-nearest other point to \(1.1\) is \(0.4\), at distance \(0.7\), not \(0.9\).

Check Epsilon by Recomputing Assignments

After identifying candidate radii, calculate neighbourhood counts and inspect the cluster structure at each one. The following comparison uses the same hypothetical observations as the preceding example and MinPts \(=3\). A distance exactly equal to \(\varepsilon\) is included, because the neighbourhood condition is “at most \(\varepsilon\).”

Worked Example: How Epsilon Changes Noise Assignments

Compare \(\varepsilon=0.2,\ 0.6,\) and \(0.7\) for the eight observations \(0,\ 0.1,\ 0.2,\ 0.3,\ 0.4,\ 1.0,\ 1.1,\ 3.0\), with MinPts \(=3\). Identify the core, border, and noise observations at each setting.

Method. At each radius, count the observation itself and every other observation within that radius. Then connect core points that lie within the radius of one another; attach a non-core observation only if it lies within the radius of a core point.

At \(\varepsilon=0.2\), observations \(0,\ 0.1,\ 0.2,\ 0.3,\) and \(0.4\) form a connected group. The neighbourhood of \(0\) is \(\{0,0.1,0.2\}\), with count 3; the neighbourhood of \(0.4\) is \(\{0.2,0.3,0.4\}\), also with count 3. The intermediate observations have at least 3 neighbours as well. Thus all five are core and form one cluster. The observations \(1.0\) and \(1.1\) are within \(0.1\) of each other, so each has a neighbourhood count of 2; neither is core, and neither is within \(0.2\) of a core point. Both are noise. The observation \(3.0\) is also noise.

At \(\varepsilon=0.6\), the first five observations remain connected. The neighbourhood of \(0.4\) now includes \(0.2,\ 0.3,\ 0.4,\) and \(1.0\), so \(0.4\) is core. The neighbourhood of \(1.0\) includes \(0.4,\ 1.0,\) and \(1.1\), so \(1.0\) is core as well. They are exactly \(0.6\) apart and therefore connected. The point \(1.1\) has only \(1.0\) in its neighbourhood besides itself: \(0.4\) is \(0.7\) away. It is not core, but it is within \(0.6\) of core point \(1.0\), so it is a border point. The first seven observations belong to one cluster; \(3.0\) remains noise.

At \(\varepsilon=0.7\), the neighbourhood of \(1.1\) includes \(0.4,\ 1.0,\) and \(1.1\). It is now core, since the boundary point \(0.4\) is exactly \(0.7\) away. The first seven observations still form one cluster, and \(3.0\) is still noise.

Check. The assignments are consistent with the k-distances: \(1.0\) has k-distance \(0.6\), so it becomes core at \(\varepsilon=0.6\); \(1.1\) has k-distance \(0.7\), so it becomes core at \(\varepsilon=0.7\). A common mistake is to exclude a point at exactly the radius. That would incorrectly leave \(1.0\) non-core at \(0.6\), and \(1.1\) non-core at \(0.7\).

Check MinPts as Well as Epsilon

A k-distance plot depends on the chosen MinPts, so parameter selection is not a one-way process. Choose a plausible MinPts, inspect its k-distance plot, test a few candidate radii, and then repeat the check for a nearby MinPts value if the result is sensitive. Increasing MinPts makes the core condition stricter at a fixed radius. It can turn a core point into a border point or noise, although it does not guarantee that the number of reported clusters will change in a particular direction.

Worked Example: Separating the Effects of MinPts

For the observations \(0,\ 0.1,\ 0.2,\ 0.3,\ 0.4,\ 1.0,\ 1.1,\ 3.0\), compare MinPts \(=3\) and MinPts \(=4\) at \(\varepsilon=0.2\). State what changes in the first group of five observations and what happens to the other observations.

Method. Count all observations in each \(\varepsilon\)-neighbourhood, including its centre, and compare each count with the specified MinPts.

For the first five observations, at radius \(0.2\), the neighbourhood counts in order are \(3,\ 4,\ 5,\ 4,\ 3\). For instance, the neighbourhood of \(0\) is \(\{0,0.1,0.2\}\), while the neighbourhood of \(0.2\) contains all five values from \(0\) through \(0.4\). With MinPts \(=3\), all five are core and form one cluster. With MinPts \(=4\), only \(0.1,\ 0.2,\) and \(0.3\) are core. The endpoints \(0\) and \(0.4\) are not core, but each lies within \(0.2\) of a core point, so each remains a border point in the same cluster.

The two observations \(1.0\) and \(1.1\) each have a neighbourhood count of 2 at this radius, and \(3.0\) has a count of 1. None is core under either setting, and none is within \(0.2\) of a core point. All three are noise for both MinPts values. Thus the cluster membership is unchanged here, but the core-versus-border distinction changes for the endpoints of the first group.

Check. MinPts \(=4\) requires a count of at least 4, not four other neighbours. Counting the centre as an additional point would wrongly classify the two endpoints as core.

A Practical R Workflow and Its Limits

When using R, calculate the nearest-neighbour distances using the same convention as the clustering function. For example, with a prepared numeric matrix x, the dbscan package’s k-nearest-neighbour distance functions report distances to other observations. For a DBSCAN setting of MinPts \(=m\), use \(k=m-1\) for a plot of the distances described here. Then sort and inspect the distances, fit candidate models, and compare assignments rather than selecting a radius solely from the graph.

m \text{ in DBSCAN, with self counted} \quad\longleftrightarrow\quad k=m-1 \text{ other neighbours in the k-distance calculation}

An illustrative R sequence is:

Fix the distance representation.
Use the feature matrix and distance measure appropriate to the analysis; the resulting epsilon is expressed in those distance units.

Plot candidate distances.
For MinPts \(=4\), calculate distances to the third-nearest other observation, for example with d <- dbscan::kNNdist(x, k = 3), and inspect sort(d) or a plot of the sorted values.

Fit nearby settings.
Run, for example, dbscan::dbscan(x, eps = 0.2, minPts = 4), then repeat for candidate epsilon values and a nearby MinPts value.

Compare concrete assignments.
Record the number of core points, border points, and noise points, and check which observations change assignment. Do not assume that an apparently sharp bend guarantees an interpretable result.

Package functions can differ in how they count the query observation, so confirm the function’s convention before setting \(k\). Also keep epsilon tied to the distance scale used for the input. A numerical value that is sensible for one feature representation need not be sensible for another. This is why a parameter pair should be reported together with the distance definition and feature preparation used.

Common Tuning Traps

Using the wrong neighbour rank. If MinPts includes the point itself, use the \((\text{MinPts}-1)\)th other-neighbour distance for the corresponding k-distance plot.
Treating the bend as an exact answer. A bend suggests candidate radii; it does not prove that the resulting clusters are meaningful.
Forgetting the boundary. A point at distance exactly \(\varepsilon\) is included in the neighbourhood.
Assuming every noise point is an outlier. Noise means the point is not assigned to a density-reachable cluster under the selected parameters. Another plausible parameter pair can change that assignment.
Changing both parameters without tracking the effect. Compare settings systematically so that changes in core status or noise can be related to the parameter that changed.

Key takeaway: Use a k-distance plot to propose epsilon values for a stated MinPts, then verify those candidates by counting neighbourhoods and comparing DBSCAN assignments. Report the parameter choices as modeling decisions whose effects have been checked, not as values discovered automatically by the plot.

Check Your Understanding

For each problem, apply the stated convention that a point counts as one member of its own neighbourhood.

An observation has other-neighbour distances \(0.08,\ 0.12,\ 0.20,\ 0.31\). With MinPts \(=4\) and \(\varepsilon=0.20\), is it core? (Answer: Yes; its neighbourhood has four observations including itself.)
Observations lie at \(0,\ 0.1,\ 0.2,\ 1.0,\ 1.1\). With MinPts \(=3\) and \(\varepsilon=0.11\), identify the cluster and noise observations. (Answer: Cluster \(\{0,0.1,0.2\}\); noise \(\{1.0,1.1\}\).)
Five observations lie at \(0,\ 0.1,\ 0.2,\ 0.3,\ 0.4\). With MinPts \(=4\) and \(\varepsilon=0.2\), identify the core and border points. (Answer: Core \(\{0.1,0.2,0.3\}\); border \(\{0,0.4\}\).)
A sorted k-distance plot for a stated MinPts has values \(0.05,\ 0.06,\ 0.07,\ 0.08,\ 0.10,\ 0.12,\ 0.65,\ 0.90\). What is a reasonable candidate region to investigate, and why is it not a final answer? (Answer: Investigate epsilon values near \(0.12\) to \(0.65\), especially around the apparent bend; check actual cluster and noise assignments because the plot does not establish their usefulness.)
For MinPts \(=5\) under the self-inclusion convention, what other-neighbour rank should a k-distance plot use, and what condition makes an observation core at epsilon? (Answer: Use the fourth-nearest other observation; the observation is core when that distance is at most epsilon.)

What You'll Learn