Constructing Cluster Trees from Density Estimates

From a Density Estimate to a Hierarchy

A density estimate describes where observations are concentrated, but a clustering summary must also describe how high-density regions split and join as the required density level changes. The central construction is to take connected components of the estimated density's superlevel sets at many thresholds. At high thresholds, only the most concentrated regions remain; lowering the threshold can enlarge existing components or join previously separate ones.

The resulting hierarchy depends not only on the observed sample but also on the density estimator, the domain on which it is analyzed, and the thresholds and connectivity convention used in computation. These choices should be made explicit: a tree built from estimated densities is a defined object, not an automatic by-product of fitting a density.

For a finite threshold range, take \(a\leq\inf_{x\in D}\hat f(x)\) and \(b\geq\sup_{x\in D}\hat f(x)\), and consider \(\lambda\in[a,b]\). Then \(L_a(\hat f)=D\), so the baseline set is connected. In applications, \(D\) is often a prespecified compact region; restricting the domain makes the range and boundary convention part of the analysis rather than leaving them implicit. If \(D\) is not connected, the construction gives a forest at the baseline instead of a single root.

Why the Components Form a Tree

The hierarchy follows from a basic nesting property. If \(\lambda_2>\lambda_1\), then every point with estimated density at least \(\lambda_2\) also has estimated density at least \(\lambda_1\). Thus \(L_{\lambda_2}(\hat f)\subseteq L_{\lambda_1}(\hat f)\). A component at the higher threshold must lie inside exactly one component at the lower threshold.

Proof. Since \(\lambda_2>\lambda_1\), \(L_{\lambda_2}(\hat f)\subseteq L_{\lambda_1}(\hat f)\), so \(C_2\subseteq L_{\lambda_1}(\hat f)\). A connected subset of a space lies in one of that space's connected components: the union of the subset with any component it intersects is connected, so maximality of components places the subset inside that component. The component containing \(C_2\) is unique because distinct connected components are disjoint. \(\square\)

This result tells us how to link levels: each component at a higher threshold has one parent at every lower threshold where it exists. Conversely, a component at a lower threshold may contain several higher-threshold components, representing a split as the density requirement rises. The tree does not require the number of components to be finite at every threshold; finite data alone do not guarantee that for every possible estimator.

For two points \(x,y\in D\), their merge height summarizes when their paths through this hierarchy first become connected as the threshold is lowered.

The set inside the supremum is nonempty because it contains \(a\). It is downward persistent: if \(x,y\) belong to the same component at \(\lambda\), then they belong to the same component at every threshold between \(a\) and \(\lambda\), since the connected component is contained in a component of the lower superlevel set. The supremum need not itself be in the set. This distinction matters when a tree is represented on a finite threshold grid.

Building a Finite-Threshold Tree

A practical finite representation selects thresholds \(G=\{t_0,\ldots,t_J\}\), where \(a=t_0<t_1<\cdots<t_J=b\). At each selected level, compute the components of \(L_{t_j}(\hat f)\). Link every component at \(t_{j+1}\) to the unique component at \(t_j\) containing it. Repeating this gives a tree at the chosen levels. A split between recorded levels is not observed by this representation; its displayed height is therefore limited by the threshold spacing.

For example, a kernel density estimate with observations \(X_1,\ldots,X_n\), kernel \(K\), and bandwidth \(h>0\) is \(\hat f_h(x)=\frac{1}{nh^d}\sum_{i=1}^n K((x-X_i)/h)\) in \(d\) dimensions. The cluster tree is built from this estimate, not directly from the observations. Changing \(h\) can change the number and location of peaks and the thresholds at which regions join. Likewise, a boundary correction or a different analysis domain can change the tree.

In numerical work, a density estimate may be evaluated on a grid. A rule such as “join neighboring grid cells when both meet the threshold” defines a graph-based approximation to connectedness. The neighbor rule (for example, edge-sharing cells only, or edge- and corner-sharing cells) can change the computed components. This spatial approximation is distinct from choosing only finitely many density thresholds: refining one does not automatically correct the other.

Threshold Grids and Merge-Height Error

For a grid \(G=\{t_0,\ldots,t_J\}\) with \(t_0=a\), define \(m_G(x,y)\) as the largest grid threshold at which \(x\) and \(y\) are in the same component. The baseline assumption ensures that at least one such grid threshold exists. The following bound concerns only the vertical resolution of the merge height; it does not bound spatial error in the estimated components.

Proof. Every qualifying grid level qualifies in the full interval, so \(m_G(x,y)\leq m_{\hat f}(x,y)\). Write \(m=m_{\hat f}(x,y)\). If \(m=a\), the baseline qualifies and \(m_G=a=m\). If \(m\) is a grid point and qualifies, then \(m_G=m\), giving zero error. In all other cases, let \(t\) be the largest grid point strictly below \(m\). Such a point exists because \(a\) qualifies when \(m>a\). By the definition of a supremum, for every \(t<m\) there is a qualifying level \(s>t\); otherwise \(t\) would be an upper bound smaller than \(m\). Downward persistence then implies that \(t\) qualifies. Hence \(m_G\geq t\). The distance from \(m\) to this largest grid point strictly below it is no greater than the largest adjacent grid gap \(\Delta\), including when \(m\) itself is a grid point that does not qualify. Therefore \(0\leq m-m_G\leq\Delta\). \(\square\)

Common Pitfall and Practical Interpretation

A common mistake is to say that a merge height \(m\) must itself qualify, and then infer that a grid containing \(m\) must record that merge exactly. A supremum need not be attained: a pair can be connected at every level below \(m\) and disconnected at \(m\). The correction is to use \(m\) only if it qualifies; otherwise use the largest grid point strictly below it. Downward persistence guarantees that this lower grid point qualifies, and its distance from \(m\) is at most the maximum grid gap.

A second practical distinction is that a finite-threshold tree is not a claim that the density estimate has only finitely many meaningful levels. It is a summary at selected levels. A separate spatial grid or graph introduces another approximation, governed by the evaluation resolution and adjacency rule. Reporting these choices makes the resulting clustering structure interpretable and reproducible.