Level Sets and Cluster Trees · Tutorial 679 of 989

Metrics for Comparing Cluster Trees

Compare cluster trees using worst-case merge-height error and average pairwise disagreement, and see what each distance can reveal.

Advanced 10 min read

What You'll Learn

Define merge-distortion from the pairwise merge-height functions of two cluster trees.
Define level-wise and probability-weighted measures of component-membership disagreement.
Derive the identity linking integrated membership disagreement to average absolute merge-height error.
Prove basic metric and pseudometric properties of the comparison distances.
Interpret how supremum and probability-weighted distances respond to localized tree errors.
Check the endpoint convention for pairs whose merge heights differ.

Why Compare Cluster Trees?

Two cluster trees can differ in the heights at which branches join, in which points share a component at a given level, or in both ways. A useful comparison should say which discrepancy it measures. A worst-case distance can reveal a large error on even a rare branch; an average distance can emphasize discrepancies affecting many pairs under a chosen probability distribution.

The comparison will use merge heights, which summarize when pairs of points first belong to the same cluster as the level decreases. The earlier material on population cluster trees introduced these heights. Here the focus is how to compare them and how to interpret the resulting distances.

Merge Heights and Merge-Distortion

Let $X$ be a set of points and let $H<\infty$ be a common upper bound on the levels being considered. For a cluster tree $T$, write $m_T(x,y)\in[0,H]$ for the merge height of $x,y\in X$. Use the convention that $x$ and $y$ belong to the same component at level $\lambda$ exactly when $m_T(x,y)\geq\lambda$. In particular, the equality case is included. Set $m_T(x,x)=H$.

For a valid cluster tree, the relation defined by $m_T(x,y)\geq\lambda$ is an equivalence relation at each level. In particular, its merge heights satisfy $m_T(x,z)\geq\min\{m_T(x,y),m_T(y,z)\}$. This nesting property ensures that pairwise merge heights describe the tree’s component memberships at every level.

Definition: The merge-distortion between two cluster trees $T,T'$ on the same point set and level range is $$ d_M(T,T')=\sup_{x,y\in X}\left|m_T(x,y)-m_{T'}(x,y)\right|. $$ It is the largest absolute difference between corresponding pairwise merge heights.

Merge-distortion is a worst-case comparison: every pair of points counts equally in the supremum, regardless of how common or rare those points are. It is zero precisely when the merge-height functions agree everywhere. Under the same threshold convention, that means the two trees have the same pairwise membership relations at every level.

Level-Wise Membership Disagreement

To compare components at a particular level, compare pairs rather than trying to match component names. Let $$ I_T^\lambda(x,y)=\mathbf{1}\{m_T(x,y)\geq\lambda\}, $$ where $\mathbf{1}\{\cdot\}$ is one when its condition holds and zero otherwise. The relation $I_T^\lambda$ records whether each pair belongs to a common component at level $\lambda$. For a probability distribution $P$ on $X$, define the level-wise disagreement $$ \Delta_\lambda(T,T')=\int_X\int_X \left|I_T^\lambda(x,y)-I_{T'}^\lambda(x,y)\right|\,dP(x)\,dP(y). $$ This is the probability that two independent draws from $P$ have different same-component indicators in the two trees. Components are compared without labels: exchanging their names does not change the disagreement.

For a fixed pair $x,y$, write $l=\min\{m_T(x,y),m_{T'}(x,y)\}$ and $h=\max\{m_T(x,y),m_{T'}(x,y)\}$. If $l<h$, the indicators disagree exactly when $\lambda\in(l,h]$. At $\lambda=l$, both indicators equal one; at $\lambda=h$, the tree with merge height $h$ still has indicator one, while the other has indicator zero. If $l=h$, they never disagree.

Worked Example: One Merge Height Is Too High

Let $X=\{a,b,c\}$, use $H=3$, and let $P$ give probability $1/3$ to each point. In $T$, $a$ and $b$ merge at height $2$, and all three points join at height $1$. In $T'$, $a$ and $b$ merge at height $2.5$, and all three points join at height $1$. Thus $m_T(a,b)=2$, $m_{T'}(a,b)=2.5$, and both trees give height $1$ to the other two distinct pairs.

The largest height error is $0.5$, so $d_M(T,T')=0.5$. The same-component indicators differ for the ordered pairs $(a,b)$ and $(b,a)$ precisely when $\lambda\in(2,2.5]$. Each ordered pair has probability $1/9$, so $\Delta_\lambda(T,T')=2/9$ on that interval and is zero elsewhere. Integrating over levels gives $(2/9)(0.5)=1/9$. In particular, there is no disagreement at $\lambda=2$, but there is disagreement at $\lambda=2.5$.

Probability-Weighted Tree Distance

A single-level comparison can miss errors at other levels. Integrating the disagreement over the full level range gives an average comparison of pairwise merge heights. Define

Definition: The probability-weighted tree distance is $$ d_{1,P}(T,T')=\int_0^H \Delta_\lambda(T,T')\,d\lambda. $$ It measures total level-wise disagreement, weighted by the probability of the affected pairs under $P$.

This comparison depends on $P$, unlike merge-distortion. With discrete $X$, for example, a pair of points that is assigned very little probability contributes little to $d_{1,P}$, even if its merge heights differ substantially.

Theorem: For cluster trees with merge heights in $[0,H]$ and any probability distribution $P$, $$ d_{1,P}(T,T')=\int_X\int_X \left|m_T(x,y)-m_{T'}(x,y)\right|\,dP(x)\,dP(y). $$

Proof. For any two numbers $a,b\in[0,H]$, the indicators $\mathbf{1}\{a\geq\lambda\}$ and $\mathbf{1}\{b\geq\lambda\}$ differ on an interval of length $|a-b|$. More explicitly, if $a<b$, their difference in absolute value is one for $\lambda\in(a,b]$ and zero elsewhere; the case $b<a$ is symmetric, and if $a=b$, it is always zero. Therefore,

|a-b|=\int_0^H \left|\mathbf{1}\{a\geq\lambda\}-\mathbf{1}\{b\geq\lambda\}\right|\,d\lambda.

Apply this identity with $a=m_T(x,y)$ and $b=m_{T'}(x,y)$. The integrand is measurable and bounded by one on the finite interval $[0,H]$, and $P\otimes P$ is a probability measure. Tonelli’s theorem therefore permits exchanging the integrals. The result is

$$ \begin{aligned} \int_0^H\Delta_\lambda(T,T')\,d\lambda &=\int_X\int_X\int_0^H \left|I_T^\lambda(x,y)-I_{T'}^\lambda(x,y)\right| \,d\lambda\,dP(x)\,dP(y)\\ &=\int_X\int_X \left|m_T(x,y)-m_{T'}(x,y)\right|\,dP(x)\,dP(y). \end{aligned} $$ Thus the two expressions are equal. \(\square\)

The identity makes the distinction between the two distances explicit. The supremum $d_M$ gives the largest pairwise error; $d_{1,P}$ averages absolute errors over pairs. Since $P\otimes P$ has total mass one,

0\leq d_{1,P}(T,T')\leq d_M(T,T').

Worked Example: Different Memberships at the Same Level

Again let $X=\{a,b,c\}$, with uniform $P$ and $H=3$. In $T$, $a,b$ merge at height $2$, while $a,c$ and $b,c$ merge at height $1$. In $T'$, $a,c$ merge at height $2$, while $a,b$ and $b,c$ merge at height $1$.

At level $\lambda=1.5$, $T$ has components $\{a,b\}$ and $\{c\}$; $T'$ has components $\{a,c\}$ and $\{b\}$. The pairs $(a,b),(b,a),(a,c),(c,a)$ disagree, each with probability $1/9$, so $\Delta_{1.5}(T,T')=4/9$. The $a,b$ merge heights differ by $1$, as do the $a,c$ heights; the $b,c$ heights agree. Hence $d_M(T,T')=1$, and $$ d_{1,P}(T,T')=\frac{2}{9}(1)+\frac{2}{9}(1)=\frac{4}{9}. $$ The trees have the same collection of merge-height values, but attach those heights to different pairs. Comparing only the values without their point-pair identities would miss this membership error.

What the Distances Guarantee

Both distances obey triangle inequalities, but their zero-distance interpretations differ when the weighted distance is used. The following result records these basic properties. Here “pseudometric” means that the distance is nonnegative, symmetric, and satisfies the triangle inequality, but distinct objects may have distance zero.

Theorem: The merge-distortion $d_M$ is a metric on merge-height functions: it is nonnegative, symmetric, satisfies the triangle inequality, and is zero exactly when the functions agree everywhere. For fixed $P$, $d_{1,P}$ is a pseudometric. It is zero exactly when the two merge-height functions agree $P\otimes P$-almost everywhere.

Proof. Absolute differences are nonnegative and symmetric, so both distances inherit those properties. For any $x,y\in X$, the ordinary triangle inequality gives $$ |m_T(x,y)-m_{T''}(x,y)| \leq |m_T(x,y)-m_{T'}(x,y)| +|m_{T'}(x,y)-m_{T''}(x,y)|. $$ Taking the supremum over $x,y$ proves the triangle inequality for $d_M$. Integrating this same pointwise inequality with respect to $P\otimes P$ proves it for $d_{1,P}$. The supremum is zero exactly when every pointwise absolute difference is zero. The integral of a nonnegative measurable function is zero exactly when that function is zero almost everywhere, giving the stated condition for $d_{1,P}$. In particular, a difference confined to pairs of zero $P\otimes P$-measure is invisible to the weighted distance. $\square$

Worked Example: A Large Error on Rare Pairs

Let $X=\{a,b,c\}$, with $P(a)=0.98$ and $P(b)=P(c)=0.01$, and let $H=3$. In $T$, $a,b$ merge at height $2$, with $c$ joining at height $1$. In $T'$, $a,c$ merge at height $2$, with $b$ joining at height $1$.

The merge-height discrepancies are $1$ for the pair $a,b$, $1$ for the pair $a,c$, and $0$ for $b,c$. Thus $d_M(T,T')=1$. For the weighted distance, each of the first two unordered pairs contributes in both orders. Consequently, $$ d_{1,P}(T,T') =2P(a)P(b)+2P(a)P(c) =2(0.98)(0.01)+2(0.98)(0.01) =0.0392. $$ The worst-case error is large, while the probability-weighted error is smaller because the disagreements involve rare points. This is not a contradiction: the distances answer different comparison questions.

Choosing and Interpreting a Comparison

Use merge-distortion when the aim is to control the largest error in any pairwise merge height. It is appropriate when every part of the tree matters, including branches that carry little probability. Use $d_{1,P}$ when the aim is average performance for pairs drawn from a specified population. The choice of $P$ is part of the definition and interpretation, not a neutral technical detail.

The level-wise quantity $\Delta_\lambda$ answers a different, localized question: at this particular level, what probability mass of ordered pairs has a changed same-component status? It can be useful to report it at levels of substantive interest, while $d_{1,P}$ summarizes disagreement across all levels. Because pairs are ordered in the integral, each unordered pair of distinct points contributes twice; this convention is already reflected in the examples.

Common Mistakes

Reversing the endpoint convention. If the two merge heights are $l<h$, it is tempting to say disagreement occurs on $[l,h)$. But at $l$, both trees still have the pair together under the convention $m\geq\lambda$, while at $h$ only the tree with height $h$ does. The correct interval is $(l,h]$.
Treating an average as a worst-case guarantee. A small $d_{1,P}$ does not rule out a large error on low-probability pairs. The bound $d_{1,P}\leq d_M$ goes in that direction only.
Matching components by their names. Component labels can be exchanged without changing the tree. Compare same-component indicators for pairs instead.
Assuming zero weighted distance means identical trees everywhere. It implies equality only $P\otimes P$-almost everywhere. Differences on probability-zero pairs may remain.

Key takeaway: Merge-distortion controls the largest pairwise merge-height error. Integrating pairwise component disagreement over levels gives the probability-weighted mean absolute merge-height error. The first protects every pair; the second reflects the distribution of pairs being studied.

Check Your Understanding

Use the convention that two points share a component at level $\lambda$ when their merge height is at least $\lambda$.

If a pair has merge heights $1.4$ and $2.1$, at which levels do its same-component indicators differ? What happens at each endpoint?
Why can two trees have the same collection of merge-height values but different component memberships?
Which distance, $d_M$ or $d_{1,P}$, is sensitive to a large error on a pair with very small probability? Explain.
What does $d_{1,P}(T,T')=0$ imply about the merge-height functions, and what does it not necessarily imply?
For uniform probability on three points, only one unordered pair has a merge-height error of $0.3$, and the other two pairs agree. What is the contribution of that error to $d_{1,P}$?

Back to Tutorials