4.5 Density connectivity and mean shift

Two ways to use local concentration

Representing every cluster by one center can obscure a curved or elongated group. Density methods begin with local concentration instead. DBSCAN asks which observations have enough nearby observations, then connects the dense regions. Mean shift builds a smooth density from the data and moves a seed toward higher density. The two methods use neighborhoods differently: a graph connection is not a gradient step, and a kernel mode is not a neighborhood count.

Both approaches require a geometric scale. Changing a radius or bandwidth changes what counts as nearby. The number of resulting groups is an output, but the geometry still comes from a chosen distance and its feature units. We first work with a finite indexed dataset in a metric space; the mean-shift derivation will then specialize to Euclidean feature vectors.

Core, border and noise in DBSCAN

Definition

Closed neighborhoods and core observations

Choose $\varepsilon>0$ and an integer $m\ge1$. For each observation $i$,

$$N_\varepsilon(i)=\{j:d(x_i,x_j)\le\varepsilon\},\qquad \mathcal C=\{i:|N_\varepsilon(i)|\ge m\}.$$

The neighborhood includes $i$ itself. Indices in $\mathcal C$ are core observations. A non-core observation is a border observation if its neighborhood contains a core observation, and noise if it has no core neighbor. Repeated observations count separately because their indices are distinct.

Build a graph using only the core observations as vertices. Connect two different core observations when their distance is at most $\varepsilon$. Its connected components are the core parts of the clusters. Attach a border observation to a component containing one of its core neighbors. If there is more than one such component, a fixed component order determines its single assigned label. Leave noise unassigned, conventionally with label $-1$.

Proposition

Core connectivity does not pass through a border

The core components are independent of traversal order. A border observation can be adjacent to more than one core component, but attaching it to one component does not merge those components.

Proof

Track which observations may extend a path

A core path uses only core vertices and edges of length at most $\varepsilon$. Whether such a path exists is a property of the fixed graph, so its connected components do not depend on a search order. A density expansion can extend through a core observation; a non-core endpoint can be included but cannot extend the expansion. A border point shared by two components is therefore an endpoint for either expansion, rather than an intermediate core vertex connecting them. Its final label depends on the chosen attachment rule, while the core components stay separate.

This distinction is central to the algorithm. Taking connected components of a graph that allows every edge with at least one core endpoint would let a shared border act as a bridge. Also, isolated non-core observations are noise, rather than additional singleton clusters. For $m=1$ all observations are core, so DBSCAN reduces to connected components of the ordinary $\varepsilon$-neighborhood graph.

Worked example

A shared border and an isolated observation

Take $\varepsilon=1$, $m=4$ and the one-dimensional observations

$$X=(-1.8,-1.6,-1.4,-0.9,0,0.9,1.4,1.6,1.8,4).$$

The four negative observations are core and connected; the four positive observations below two form another core component. The observations at $-0.9$ and $0.9$ each have five neighbors including themselves. The other six core observations have four. The neighborhood of zero is exactly $\{-0.9,0,0.9\}$, so zero is a border observation with only three neighbors. It can attach to either component according to the fixed order, but cannot join the two core components. Four has only itself in its neighborhood and is noise. Processing the negative component first gives two clusters with sizes five and four, plus one noise observation.

Here is a direct calculation of precisely that construction. The first loop labels only core components. The second loop attaches each remaining observation to the lowest numbered adjacent component, if one exists.

import numpy as np

x = np.array([-1.8, -1.6, -1.4, -0.9, 0., 0.9, 1.4, 1.6, 1.8, 4.])
near = np.abs(x[:, None] - x[None, :]) <= 1.
core = near.sum(axis=1) >= 4
labels = np.full(len(x), -1, dtype=int)
next_label = 0
for start in np.flatnonzero(core):
    if labels[start] != -1:
        continue
    labels[start] = next_label
    stack = [int(start)]
    while stack:
        i = stack.pop()
        for j in np.flatnonzero(near[i] & core):
            if labels[j] == -1:
                labels[j] = next_label
                stack.append(int(j))
    next_label += 1
for i in np.flatnonzero(~core):
    adjacent = labels[near[i] & core]
    if len(adjacent):
        labels[i] = adjacent.min()
print(near.sum(axis=1).tolist())
print(labels.tolist())

The neighborhood counts are $4,4,4,5,3,5,4,4,4,1$, and the labels are $0,0,0,0,0,1,1,1,1,-1$. This implementation deliberately separates the connectivity question from the border-label convention. Neither step asks for a prescribed number of clusters.

Parameters and changing density levels

For fixed $m$, increasing $\varepsilon$ can turn non-core observations into core observations and can connect formerly separated core regions. A new core region can also appear before it joins an old one. Consequently the total number of clusters need not decrease at every increase in radius. For fixed radius, raising $m$ makes the core requirement harder to satisfy. The same physical radius can reveal a dense region while classifying a sparser but meaningful group as noise.

DBSCAN uses one radius and one count threshold over the whole dataset. This is a choice of a common density scale, rather than an assumption that all observed densities are identical. Coordinate rescaling changes the neighborhoods unless the distance is changed correspondingly. Choosing the metric and its units is therefore part of defining the clustering problem.

From core distances to a density hierarchy

Instead of selecting one radius immediately, a hierarchical density method tracks connectivity across radii. Fix $1\le m\le n$ and use the same self-counting convention as above. Define

$$c_m(i)=\min\{r\ge0:|N_r(i)|\ge m\},\qquad w(i,j)=\max\{c_m(i),c_m(j),d(x_i,x_j)\}\quad(i\ne j).$$

The core distance $c_m(i)$ is the radius needed to collect $m$ observations. The mutual-reachability edge weight $w(i,j)$ cannot be small unless both endpoints are locally concentrated and near each other. This formula defines weights between different vertices; a diagonal value, if needed in a distance matrix, is set to zero.

Worked example

A sparse endpoint raises an edge weight

Use $X=(0,0.1,0.2,1.2,2.2)$ and $m=3$, including each observation itself. The core distances in that order are

$$(c_m(i))_{i=1}^5=(0.2,0.1,0.2,1,2).$$

The edge from zero to $0.1$ has weight $0.2$, while the edge from $1.2$ to $2.2$ has weight two despite its Euclidean length being one. The second endpoint needs a radius of two to find its third observation; the edge weight carries this information about local sparsity.

Construct the complete weighted graph, then a minimum spanning tree, or MST. Thresholding the MST preserves the graph's connected components at every edge-weight threshold. To see why, take an omitted edge of weight at most $t$. Every edge on its MST path has weight no larger than that edge: otherwise replacing a larger path edge would decrease the tree's total weight. Its endpoints therefore remain connected after removing tree edges larger than $t$. The tree retains the whole hierarchy with only $n-1$ edges.

HDBSCAN condenses this hierarchy using a minimum cluster size, then selects branches that persist over density levels. This size is conceptually different from the local count $m$. A small branch may be treated as points leaving a persistent group rather than a new substantial group. A stability score can measure accumulated membership at positive thresholds $t>0$ using $\lambda=1/t$; selecting a parent excludes its descendants from the same flat partition. This uses different lifetimes within a hierarchy instead of imposing a single global cut. The outcome still depends on the distance and both size choices.

Gaussian mean shift with fixed observations

We now return to feature vectors $x_i\in\mathbb R^d$. Keep these observations fixed throughout the calculation. For bandwidth $h>0$, define

$$K_i(p)=\exp\!\left(-\frac{\|x_i-p\|_2^2}{2h^2}\right),\qquad F(p)=\sum_{i=1}^nK_i(p),\qquad q_i(p)=\frac{K_i(p)}{F(p)}.$$

Multiplying $F$ by the positive normalizing constant of a Gaussian density estimate does not change its modes or its logarithmic gradient. The weights $q_i(p)$ are positive and sum to one. The weighted mean and update are

$$\mu(p)=\sum_iq_i(p)x_i,\qquad p^{(t+1)}=\mu(p^{(t)}).$$

Only the seed $p$ moves. Moving all observations and then using their new locations as the next reference dataset would change the density being optimized. To cluster observations, start seeds at their locations, run the fixed-density update, and group seeds by the limiting location reached or an explicitly chosen tolerance for nearby terminal seeds.

Proposition

Direction and ascent of Gaussian mean shift

For the fixed finite dataset and $h>0$,

$$\nabla\log F(p)=\frac{\mu(p)-p}{h^2},\qquad \log F(\mu(p))-\log F(p) \ge\frac{\|\mu(p)-p\|_2^2}{2h^2}.$$

Thus every nonzero mean-shift step strictly increases this density value.

Proof

Differentiate and then use a weighted logarithm inequality

Differentiating each Gaussian gives $\nabla K_i(p)=K_i(p)(x_i-p)/h^2$. Sum and divide by $F(p)$ to obtain the gradient formula. For any candidate location $z$, write $F(z)/F(p)$ as a weighted sum with fixed weights $q_i(p)$. Concavity of the logarithm gives

$$\log\frac{F(z)}{F(p)} \ge-\frac1{2h^2}\sum_iq_i(p) \left(\|z-x_i\|_2^2-\|p-x_i\|_2^2\right) =\frac{\|p-\mu(p)\|_2^2-\|z-\mu(p)\|_2^2}{2h^2}.$$

The equality uses the weighted-mean squared-distance identity. Set $z=\mu(p)$ to obtain the claimed bound.

Because $F(p)\le n$, density values along the iteration increase to a finite limit. Summing the ascent bound shows that the squared step lengths have a finite sum, so the step lengths tend to zero. These statements concern the objective and steps; a fixed point satisfies the stationary equation $\nabla F(p)=0$. It need not be the global maximum, and symmetry can even keep a seed at a local minimum.

Worked example

Two exact updates, using the original data each time

Let $X=\{0,2\}$, $h^2=2/\log2$ and $p^{(0)}=0$. The initial kernel weights before normalization are one and one half. Therefore

$$p^{(1)}=\frac23,\qquad p^{(2)}=\frac{2}{1+2^{1/3}}\approx0.884986668.$$

For the second value, the ratio of the weights at zero and two is $2^{1/3}$. Both weights are recomputed from the original zero and two, rather than from any other updated seeds. The bandwidth controls how much each observation contributes to the weighted center.

import numpy as np

x = np.array([0., 2.])
h2 = 2. / np.log(2.)
p = 0.
for _ in range(2):
    weights = np.exp(-(x - p) ** 2 / (2. * h2))
    p = float(weights @ x / weights.sum())
    print(f"{p:.9f}")

The output is 0.666666667 followed by 0.884986668. For a general kernel, the connection between its weighted update and a density gradient must be derived for that kernel. The Gaussian formula above follows from its particular derivative and bandwidth convention.

Bandwidth, stationary points and stopping

The bandwidth controls the density landscape as well as the size of an individual update. With the symmetric observations $X=\{-1,1\}$, direct simplification gives

$$\mu(p)=\tanh(p/h^2),\qquad \mu'(0)=h^{-2},\qquad F''(0)=2e^{-1/(2h^2)}(h^{-4}-h^{-2}).$$

Zero is always a fixed point. If $h>1$, the second derivative is negative and the derivative of the update has magnitude less than one: zero is a local density maximum and nearby seeds are drawn toward it. If $0<h<1$, the second derivative is positive and the update locally pushes nonzero seeds away from zero, although a seed exactly at zero remains there. At $h=1$ these derivative tests are inconclusive. Changing bandwidth can therefore change both the stationary geometry and the attraction behavior; it is not simply a computational speed adjustment.

Every weighted-mean update is a convex combination of the fixed observations. After its first update a seed lies in their compact convex hull, so the sequence is bounded. Combine this with the step lengths tending to zero: if a subsequence tends to $p_*$, continuity of $\mu$ gives $\mu(p_*)-p_*=0$. Thus every accumulation point is stationary. This argument explains which conclusion follows from density ascent without identifying a particular stationary point as the answer for every initialization.

In a numerical calculation, a displacement tolerance has a bandwidth-dependent meaning. The exact gradient identity gives $\|\nabla\log F(p)\|_2=\|\mu(p)-p\|_2/h^2$. The same displacement tolerance can therefore correspond to different logarithmic-gradient sizes at different bandwidths. The stopping rule concerns a seed's density update; the tolerance for merging nearby terminal seeds is a separate grouping choice.

Counting scale and repeated observations

Neighborhood counts also have a sampling scale. Suppose each indexed observation is repeated exactly twice at the same location. At a fixed radius, every neighborhood count doubles. Holding $m$ fixed can turn a previous border or noise observation into a core observation, changing the clustering even though no new geometric locations were introduced. This is why changing sample size and changing feature units are different questions.

For exact repetitions, doubling the required count along with the observations preserves the original core condition at each location. It does not supply a general rule for new samples drawn at different locations. In an image application, changing pixel resolution changes neighborhood counts; in a tracking application, changing the number of sampled frames changes how much local evidence the same physical radius collects. A count threshold should be interpreted together with that observation process.

Exercises

Checkpoint

1. Counting the observation itself

For $X=\{0,0.4,0.8,3\}$, $\varepsilon=0.5$ and $m=3$, identify the core, border and noise observations.

Solution · Exercise 1 solution

Only $0.4$ is core: its neighborhood is $\{0,0.4,0.8\}$. Zero and $0.8$ each have two neighbors and are border observations adjacent to that core point. Three is noise. The result is one three-observation cluster and one unassigned observation.

Checkpoint

2. A border shared by two components

In the ten-observation example, does assigning zero to the negative group make the positive core component part of that same cluster?

Solution · Exercise 2 solution

No. Zero is non-core and cannot extend a density expansion. Its adjacency to $0.9$ does not create an edge between the two core components. Choosing the positive group first changes zero's label, not the two core components.

Checkpoint

3. A fixed point that is not a mode

Use $X=\{-1,1\}$ and $h=1/2$. What happens to a Gaussian mean-shift seed initialized at zero? Is that point a local maximum of $F$?

Solution · Exercise 3 solution

Symmetry gives equal weights, so $\mu(0)=0$ and the seed stays there. But $F''(0)=24e^{-2}>0$, making zero a strict local minimum. A stationary seed need not reach a mode when its initialization lies exactly at such a symmetry point.

Checkpoint

4. Why the spanning tree retains a threshold connection

An edge of weight $0.7$ is omitted from an MST. Could its endpoints be disconnected after deleting only tree edges of weight greater than one?

Solution · Exercise 4 solution

No. Every edge along the MST path between those endpoints has weight at most $0.7$; a larger one could be replaced by the omitted edge to reduce the total tree weight. The entire path survives the threshold at one.

Related notes

• Hierarchical linkages and dendrograms develops single-link connectivity and tree cuts.
• Learned metrics and random projections explains how changing a metric changes neighborhood geometry.
• Gaussian mixtures and expectation maximization uses a different probabilistic meaning for soft memberships.
• Course reading list collects the recommended books.