Population Cluster Trees and Merge Heights

From Density Thresholds to a Tree

A density can have several separated high-density regions at a stringent threshold, with those regions gradually joining as the threshold is lowered. The resulting hierarchy is a population-level object: it describes the connected structure of the density itself, rather than the behavior of a particular sample or density estimate. Its branches record the appearance of high-density components and the levels at which those components meet.

Let \(f\) be a density on a domain \(\mathcal{X}\subseteq\mathbb{R}^d\). For a positive threshold \(t\), its superlevel set is \(L_t=\{x\in\mathcal{X}: f(x)\ge t\}\). We use connected components in the usual topological sense: a component is a maximal connected subset of a set. The focus on positive thresholds avoids treating the potentially much larger zero-density region as part of the cluster structure.

This tree is a hierarchy, not necessarily a binary tree. A cluster can contain several distinct higher-level clusters, and several components can join at the same height. In general, there may be infinitely many components or infinitely many changes in the hierarchy. When discussing a finite list of births and merges, we will explicitly use a tame setting: the density has only finitely many relevant component-changing levels, as happens for many piecewise-linear examples.

Why the Components Are Nested

If \(0<t_2<t_1\), then \(L_{t_1}\subseteq L_{t_2}\): every point whose density is at least \(t_1\) also has density at least \(t_2\). This set inclusion induces a corresponding relationship between components.

Proof. Let \(C\) be a component of \(L_{t_1}\). Since \(L_{t_1}\subseteq L_{t_2}\), \(C\) is a connected subset of \(L_{t_2}\). Every connected subset of a topological space is contained in a connected component of that space: for any point in the subset, take the component containing that point, which contains the whole connected subset by maximality of components. Thus \(C\) is contained in some component \(D\) of \(L_{t_2}\). If it were also contained in a different component, those two components would intersect, which is impossible because distinct connected components are disjoint. Therefore \(D\) is unique. \(\square\)

As the threshold decreases, a component can stay intact or become part of a larger component; it cannot split into smaller components. This is the source of the tree structure. The theorem does not say that every pair of clusters must eventually join: the domain or the positive-density region can have separated parts.

Pointwise Merge Heights

A useful way to record when two locations become connected is to assign them a merge height. Fix \(x,y\in\mathcal{X}\), and consider the positive thresholds at which they lie in the same component.

The value is finite: if \(x\) and \(y\) are connected at level \(t\), then both have density at least \(t\), so \(t\le \min\{f(x),f(y)\}\). If there is no positive threshold at which they are connected, the merge height is zero. A supremum need not be attained for every density and domain; in a tame example it is typically attained at the merge level. If \(m_f(x,y)>t\), the definition and the nesting of superlevel sets imply that \(x\) and \(y\) are connected at level \(t\). When \(m_f(x,y)=t\), that conclusion requires the supremum to be attained.

For any three locations, merge heights satisfy a useful hierarchy inequality.

Proof. Write \(a=m_f(x,y)\) and \(b=m_f(y,z)\). If \(\min\{a,b\}=0\), the result follows from \(m_f(x,z)\ge0\). Otherwise, take any \(s\) with \(0<s<\min\{a,b\}\). Since \(s<a\), the definition of supremum gives a threshold \(u>s\) at which \(x\) and \(y\) are in the same component of \(L_u\). Because \(L_u\subseteq L_s\), they are also in the same component of \(L_s\). The same argument shows that \(y\) and \(z\) lie in the same component of \(L_s\). Those two components contain \(y\), so they are the same component; hence \(x\) and \(z\) are connected at level \(s\). Thus \(m_f(x,z)\ge s\) for every \(s\) strictly below \(\min\{a,b\}\), which implies the stated inequality. \(\square\)

The inequality says that if \(x\) meets \(y\), and \(y\) meets \(z\), at a given height, then \(x\) and \(z\) are connected by at least the lower of those two heights. This is a hierarchical property, not a statement that the merge height is an ordinary spatial distance.

Component Births and Merges

A branch describes a component as the threshold varies. In a tame setting, one can follow a component over a range of levels until it joins another component. Its birth height is the upper endpoint of the range where that branch exists as a distinct component. When it is born at an isolated local maximum, this height is the maximum density on that branch. A plateau can instead give a component with more than one point at birth.

The branch's merge height is the level at which, as the threshold is lowered, its component first becomes part of a component containing another branch. With the closed superlevel convention \(f\ge t\), a merge at height \(d\) occurs at level \(d\) when the joining points are included there. Above \(d\), the branches remain distinct; below \(d\), they lie in the same component. For two representative locations on separate branches, the pointwise merge height gives this level. This branch description assumes the component changes can be tracked across finitely many critical levels; the pointwise definition itself does not require that assumption.

What Merge Heights Do—and Do Not—Measure

Merge heights are useful because they summarize a density's population-level organization in a way that retains both the existence of separate high-density regions and the levels at which they connect. The same definition applies in any dimension: connectivity is determined by the topology of the superlevel set, not by a particular path algorithm or distance rule. In one dimension, the interval between two locations makes the calculation especially transparent. In higher dimensions, connectedness need not be reducible to checking a single straight line segment.

A common mistake is to interpret a merge height as the probability mass of a cluster. It is not. The height is a density value, with units inverse to the volume units of the domain. Probability mass instead requires integrating the density over a set. A second mistake is to identify two regions as merged merely because their locations are close. They are merged at level \(t\) only if they belong to the same connected component of \(L_t\); nearby regions can still be separated by a low-density gap. Conversely, a connected route through a superlevel set can join regions even when their representatives are far apart.