Consistent procedures for cluster tree estimation and pruning

Introduction

Our formalism of the cluster tree (Section 2.2) and our notion of consistency follow early work on clustering, in particular that of Hartigan (1981). Much subsequent work has been devoted to estimating the connected components of a single level set; see, for example, Polonik (1995), Tsybakov (1997) and, more recently, Maier et al. (2009), Rigollet and Vert (2009), Rinaldo and Wasserman (2010), and Singh et al. (2009). In contrast to these results, the present work is concerned with the simultaneous estimation of all level sets of an unknown density: recovering the cluster tree as a whole.

Are there hierarchical clustering algorithms which converge to the cluster tree? Previous theory work (Hartigan, 1981, Penrose, 1995) has provided partial consistency results for the well-known single-linkage clustering algorithm, while other work (Wishart, 1969) has suggested ways to overcome the deficiencies of this algorithm by making it more robust, but without proofs of convergence. In this paper, we propose a novel way to make single-linkage more robust, while retaining most of its elegance and simplicity (see Figure 3). We establish its finite-sample rate of convergence (Theorem 3.3); the centerpiece of our argument is a result on continuum percolation (Theorem 4.7). This also implies consistency in the sense of Hartigan.

We then give an alternative procedure based on the $k$-nearest neighbor graph of the sample (see Figure 4). Such graphs are widely used in machine learning, and interestingly there is still much to understand about their expressiveness. We show that by successively removing points from this graph, we can create a hierarchical clustering that also converges to the cluster tree, at roughly the same rate as the linkage-based scheme (Theorem 3.4).

Next, we use tools from information theory to give a lower bound on the problem of cluster tree estimation (Theorem 6.1), which matches our upper bounds in its dependence on most of the parameters of interest.

The convergence results for our two hierarchical clustering procedures nevertheless leave open the possibility that the trees they produce contain spurious branching. This is a well-studied problem in the cluster tree literature, and we address it with a pruning method (Figure 9) that preserves the consistency properties of the tree estimators while providing finite-sample guarantees on the removal of false clusters (Theorem 7.5). This procedure is based on simple intuition that can carry over to other cluster tree estimators.

Definitions and previous work

We start by considering the more general context of clustering. While clustering procedures abound in statistics and machine learning, it remains largely unclear whether clusters in finite data—for instance, the clusters returned by a particular procedure—reveal anything meaningful about the underlying distribution from which the data is sampled. Understanding what statistical estimation based on a finite data set reveals about the underlying distribution is a central preoccupation of statistics and machine learning; however this kind of analysis has proved elusive in the case of clustering, except perhaps in the case of density-based clustering.

Consider for instance $k$-means, possibly the most popular clustering procedure in use today. If this procedure returns $k$ clusters on an $n$-sample from a distribution $f$, what do these clusters reveal about $f$? Pollard (1981) proved a basic consistency result: if the algorithm always finds the global minimum of the $k$-means cost function (which, incidentally, is NP-hard and thus computationally intractable in general; see Dasgupta and Freund (2009), Theorem 3), then as $n\rightarrow\infty$, the clustering is the globally optimal $k$-means solution for $f$, suitably defined. Even then, it is unclear whether the best $k$-means solution to $f$ is an interesting or desirable quantity in settings outside of vector quantization.

Our work, and more generally work on density-based clustering, relies on meaningful formalisms of how a clustering of data generalizes to unambiguous structures of the underlying distribution. The main such formalism is that of the cluster tree.

2 The cluster tree

We start with notions of connectivity. A path $P$ in $S\subset{\mathcal{X}}$ is a continuous function $P:\rightarrow S$. If $x=P(0)$ and $y=P(1)$, we write $x\stackrel{{\scriptstyle P}}{{\leadsto}}y$ and we say that $x$ and $y$ are connected in $S$. This relation – “connected in $S$” – is an equivalence relation that partitions $S$ into its connected components. We say $S\subset{\mathcal{X}}$ is connected if it has a single connected component.

The cluster tree is a hierarchy each of whose levels is a partition of a subset of ${\mathcal{X}}$, which we will occasionally call a subpartition of ${\mathcal{X}}$. Write \Pi({\mathcal{X}})=\{\mbox{subpartitions of{\mathcal{X}}}\}.

Pick any $\lambda^{\prime}\leq\lambda$. Then:

3 Notion of convergence and previous work

For each $i$, set $r_{2}(x_{i})$ to the distance from $x_{i}$ to its nearest neighbor.

Construct a graph $G_{r}$ with nodes $\{x_{i}:r_{2}(x_{i})\leq r\}$.

Include edge $(x_{i},x_{j})$ if $\|x_{i}-x_{j}\|\leq r$.

Hartigan (1981) has shown that single linkage is consistent in one dimension (that is, for $d=1$). But he also demonstrates, by a lovely reduction to continuum percolation, that this consistency fails in higher dimension $d\geq 2$. The problem is the requirement that $A\cap X_{n}\subset A_{n}$: by the time the clusters are large enough that one of them contains all of $A$, there is a reasonable chance that this cluster will be so big as to also contain part of $A^{\prime}$.

With this insight, Hartigan defines a weaker notion of fractional consistency, under which $A_{n}$ (resp, $A_{n}^{\prime}$) need not contain all of $A\cap X_{n}$ (resp, $A^{\prime}\cap X_{n}$), but merely a sizeable chunk of it – and ought to be very close (at distance $\rightarrow 0$ as $n\rightarrow\infty$) to the remainder. He then shows that single linkage achieves this weaker consistency for any pair $A,A^{\prime}$ for which the ratio

is sufficiently large. More recent work by Penrose (1995) closes the gap and shows fractional consistency whenever this ratio is $>1$.

A more robust version of single linkage has been proposed by Wishart (1969): when connecting points at distance $r$ from each other, only consider points that have at least $k$ neighbors within distance $r$ (for some $k>2$). Thus initially, when $r$ is small, only the regions of highest density are available for linkage, while the rest of the data set is ignored. As $r$ gets larger, more and more of the data points become candidates for linkage. This scheme is intuitively sensible, but Wishart does not provide a proof of convergence. Thus it is unclear how to set $k$, for instance.

Several papers (Rigollet and Vert, 2009, Maier et al., 2009, Singh et al., 2009, Rinaldo and Wasserman, 2010) have recently considered the problem of recovering the connected components of $\{x:f(x)\geq\lambda\}$ for a user-specified $\lambda$: the flat version of our problem. Most similar to the work in this paper is the algorithm of Maier et al. (2009), which uses the $k$-nearest neighbor graph of the data. These level set results invariably require niceness conditions on the specific level set being recovered, often stated in terms of the smoothness of the boundary of clusters , and/or regularity conditions on the density $f$ on clusters of the given level set. It is unclear whether these conditions hold for all level sets of a general density, in other words how restrictive these conditions are in the context of recovering the entire cluster tree. In contrast, under mild requirements on the distribution, our conditions on the recovered level sets hold for any level set as the sample size $n$ increases. The main distributional requirement for consistency is that of continuity of the density $f$ on a compact support ${\mathcal{X}}$.

A related issue that has received quite a lot of attention is that of pruning a cluster tree estimate: removing spurious clusters. A recent result of Rinaldo et al. (2012) gives meaningful statistical guarantees, but is based on the cluster tree of an empirical density estimate, which is algorithmically problematic as discussed earlier. Stuetzle and Nugent (2010) have an appealing top-down scheme for estimating the cluster tree, along with a post-processing step (called runt pruning) that helps identify modes of the distribution. The consistency of this method has not yet been established. We provide a consistent pruning procedure for both our procedures.

The present results are based in part on earlier conference versions, namely Chaudhuri and Dasgupta (2010) and Kpotufe and von Luxburg (2011). The result of Chaudhuri and Dasgupta (2010) analyzes the consistency of the first cluster tree estimator (see next section) but provides no pruning method for the estimator. The result of Kpotufe and von Luxburg (2011) analyzes the second cluster tree estimator and shows how to prune it. However the pruning method is tuned to this second estimator and works only under strict Hölder continuity requirements on the density. The present work first provides a unified analysis of both estimators using techniques developed in Chaudhuri and Dasgupta (2010). Second, building on insight from Kpotufe and von Luxburg (2011), we derive a new pruning method which proveably works for either estimator without Hölder conditions on the distribution. In particular, the pruned version of either cluster tree estimate remains consistent under mild uniform continuity assumptions. The main finite-sample pruning result of Theorem 7.5 requires even milder conditions on the density than required for consistency.

Algorithms and results

The first algorithm we consider in this paper is a generalization of Wishart’s scheme and of single linkage, shown in Figure 3. It has two free parameters: $k$ and $\alpha$. For practical reasons, it is of interest to keep these as small as possible. We provide finite-sample convergence rates for all $1\leq\alpha\leq 2$ and we can achieve $k\sim d\log n$ if $\alpha\geq\sqrt{2}$. Our rates for $\alpha=1$ force $k$ to be much larger, exponential in $d$. It is an open problem to determine whether the setting ($\alpha=1,k\sim d\log n$) yields consistency.

Conceptually, the algorithm creates a series of graphs $G_{r}=(V_{r},E_{r})$ satisfying a nesting property: $r\leq r^{\prime}\ \ \ \Rightarrow\ \ \ V_{r}\subset V_{r^{\prime}}\mbox{\ and \ }E_{r}\subset E_{r^{\prime}}.$ A point is admitted into $G_{r}$ only if it has $k$ neighbors within distance $r$; when $r$ is small, this picks out the regions of highest density, roughly. The edges of $G_{r}$ are between all pairs of points within distance $\alpha r$ of each other.

In practice, the only values of $r$ that matter are those corresponding to interpoint distances within the sample, and thus the algorithm is efficient. A further simplification is that the graphs $G_{r}$ don’t need to be explicitly created. Instead, the clusters can be generated directly using Kruskal’s algorithm, as is done for single linkage.

The second algorithm we study (Figure 4) is based on the $k$-nearest neighbor graph of the samples. There are two natural ways to define this graph, and we will analyze the sparser of the two, the mutual $k$-NN graph, which we shall denote $G^{{\rm NN}}$. Our results hold equally for the other variant.

One way to think about the second hierarchical clustering algorithm is that it creates the $k$-nearest neighbor graph on all the data samples, and then generates a hierarchy by removing points from the graph in decreasing order of their $k$-NN radius $r_{k}(x_{i})$. The resulting graphs $G^{{\rm NN}}_{r}$ have the same nodes as the corresponding $G_{r}$ but have potentially fewer edges: $E^{{\rm NN}}_{r}\subset E_{r}$. This makes them more challenging to analyze.

The first consideration is that a cluster is hard to identify if it contains a thin “bridge” that would make it look disconnected in a small sample. To control this, we consider a “buffer zone” of width $\sigma$ around the clusters.

$Z_{\sigma}$ is a full-dimensional set, even if $Z$ itself is not.

Second, the ease of distinguishing two clusters $A$ and $A^{\prime}$ depends inevitably upon the separation between them. To keep things simple, we’ll use the same $\sigma$ as a separation parameter.

Under this definition, $A_{\sigma}$ and $A^{\prime}_{\sigma}$ must lie within ${\mathcal{X}}$, otherwise the right-hand side of the inequality is zero. $S_{\sigma}$ need not be contained in ${\mathcal{X}}$.

2 Consistency and rate of convergence

There is an absolute constant $C$ such that the following holds. Pick any $0<\delta,\epsilon<1$, and run Algorithm 1 on a sample $X_{n}$ of size $n$ drawn from $f$, with settings

Then there is a mapping $r:[0,\infty)\rightarrow[0,\infty)$ such that the following holds with probability at least $1-\delta$. Consider any pair of connected subsets $A,A^{\prime}\subset{\mathcal{X}}$ such that $A,A^{\prime}$ are $(\sigma,\epsilon)$-separated for $\epsilon$ and some $\sigma>0$. Let $\lambda=\inf_{x\in A_{\sigma}\cup A^{\prime}_{\sigma}}f(x)$. If $n\ \geq\ \frac{k}{v_{d}(\sigma/2)^{d}\lambda}\left(1+\frac{\epsilon}{2}\right),\text{ then:}$

Separation. $A\cap X_{n}$ is disconnected from $A^{\prime}\cap X_{n}$ in $G_{r(\lambda)}$.

Connectedness. $A\cap X_{n}$ and $A^{\prime}\cap X_{n}$ are each connected in $G_{r(\lambda)}$.

The two parts of this theorem – separation and connectedness – are proved in Sections 4.1 and 4.2, respectively.

A similar result holds for Algorithm 2 under stronger requirements on $k$.

Theorem 3.3 applies also to Algorithm 2, provided the following additional condition on $k$ is met: $k\geq\frac{\Lambda}{\lambda}\cdot Cd\log n\cdot\log\frac{1}{\delta},$ where $\Lambda=\sup_{x\in{\mathcal{X}}}f(x)$.

In the analysis section, we give a lower bound (Lemma 5.3) that shows why this dependence on $\Lambda/\lambda$ is needed.

Finally, we point out that these finite-sample results imply consistency (Definition 2.3): as $n\rightarrow\infty$, take $k_{n}=(d\log n)/\epsilon_{n}^{2}$ with any schedule of $\left\{\epsilon_{n}\right\}$ such that $\epsilon_{n}\rightarrow 0$ and $k_{n}/n\rightarrow 0$. Under mild uniform continuity conditions, any two connected components $A,A^{\prime}$ of $\{f\geq\lambda\}$ are $(\sigma,\epsilon)$-separated for some $\sigma,\epsilon>0$ (see appendix); thus they are identified given large enough $n$.

Analysis of Algorithm 1

We also invoke uniform convergence over half-balls: each of these is the intersection of a ball with a halfspace through its center. Using uniform Bernstein-type bounds, we derive basic inequalities which we use repeatedly.

We denote this uniform convergence over balls and half-balls as event $E_{o}$.

See appendix. $C_{\delta}=2C_{o}\log(2/\delta)$, where $C_{o}$ is the absolute constant from Lemma C.2. ∎

We will typically preface other results by a statement like “Assume $E_{o}$.” It is to be understood that $E_{o}$ occurs with probability at least $1-\delta$ over the random sample $X_{n}$, where $\delta$ is henceforth fixed. The constant $C_{\delta}$ will keep reappearing through the paper.

For any cluster $A\subset{\mathcal{X}}$, there is a certain scale $r$ at which every data point in $A$ appears in $G_{r}$. What is this $r$?

Assume $E_{o}$. Pick any set $A\subset{\mathcal{X}}$, and let $\lambda=\inf_{x\in A_{\sigma}}f(x)$. If $r<\sigma$ and $v_{d}r^{d}\lambda\ \geq\ \frac{k}{n}+\frac{C_{\delta}}{n}\sqrt{kd\log n},$ then $G_{r}$ contains every point in $A_{\sigma-r}\cap X_{n}$.

Any point $x\in A_{\sigma-r}$ has $f(B(x,r))\geq v_{d}r^{d}\lambda$; and thus, by Lemma 4.1, has at least $k$ neighbors within radius $r$. ∎

In order to show that two separate clusters $A$ and $A^{\prime}$ get distinguished in the cluster tree, we need to exhibit a scale $r$ at which every point in $A$ and $A^{\prime}$ is active, but there is no path from $A$ to $A^{\prime}$.

Assume $E_{o}$. Suppose sets $A,A^{\prime}\subset{\mathcal{X}}$ are $(\sigma,\epsilon)$-separated by set $S$, and let $\lambda=\inf_{x\in A_{\sigma}\cup A^{\prime}_{\sigma}}f(x)$. Pick $0<r<\sigma$ such that

$G_{r}$ contains all points in $(A_{\sigma-r}\cup A^{\prime}_{\sigma-r})\cap X_{n}$.

$G_{r}$ contains no points in $S_{\sigma-r}\cap X_{n}$.

If $r<2\sigma/(\alpha+2)$, then $A\cap X_{n}$ is disconnected from $A^{\prime}\cap X_{n}$ in $G_{r}$.

Part (a) is directly from Lemma 4.2. For (b), any point $x\in S_{\sigma-r}$ has $f(B(x,r))<v_{d}r^{d}\lambda(1-\epsilon)$; and thus, by Lemma 4.1, has strictly fewer than $k$ neighbors within distance $r$.

For (c), since points in $S_{\sigma-r}$ are absent from $G_{r}$, any path from $A$ to $A^{\prime}$ in that graph must have an edge across $S_{\sigma-r}$. But any such edge has length at least $2(\sigma-r)>\alpha r$ and is thus not in $G_{r}$. ∎

Define $r(\lambda)$ to be the value of $r$ for which $v_{d}r^{d}\lambda=\frac{k}{n}+\frac{C_{\delta}}{n}\sqrt{kd\log n}$.

The conditions of Lemma 4.3 are satisfied by $r=r(\lambda)$ if $r(\lambda)<2\sigma/(\alpha+2)$ and $k\geq 4C_{\delta}^{2}(d/\epsilon^{2})\log n$.

2 Connectedness

We need to show that points in $A$ (and similarly $A^{\prime}$) are connected in $G_{r(\lambda)}$. First we state a simple bound (proved in the appendix) that works if $\alpha=2$ and $k\sim d\log n$; later we consider smaller $\alpha$.

Assume $E_{o}$. Let $A$ be a connected set in ${\mathcal{X}}$ with $\lambda=\inf_{x\in A_{\sigma}}f(x)$. Suppose $1\leq\alpha\leq 2$. Then $A\cap X_{n}$ is connected in $G_{r}$ whenever $r\leq 2\sigma/(2+\alpha)$ and

Comparing this to the definition of $r(\lambda)$, we see that choosing $\alpha=1$ would entail $k\geq 2^{d}$, which is undesirable. We can get a more reasonable setting of $k\sim d\log n$ by choosing $\alpha=2$, but we’d like $\alpha$ to be as small as possible. A more refined argument shows that $\alpha\approx\sqrt{2}$ is enough.

Assume $E_{o}$. Let $A$ be a connected set in ${\mathcal{X}}$ with $\lambda=\inf_{x\in A_{\sigma}}f(x)$. Suppose $\alpha\geq\sqrt{2}$. Then $A\cap X_{n}$ is connected in $G_{r}$ whenever $r\leq\sigma/2$ and

Recall that a half-ball is the intersection of an open ball and a halfspace through the center of the ball. Formally, it is defined by a center $\mu$, a radius $r$, and a unit direction $u$:

We will describe any such set as “the half of $B(\mu,r)$ in direction $u$”. If the half-ball lies entirely in $A_{\sigma}$, its probability mass is at least $(1/2)v_{d}r^{d}\lambda$. By uniform convergence bounds (Lemma 4.1), if $v_{d}r^{d}\lambda\geq(4C_{\delta}d\log n)/n$, then every such half-ball within $A_{\sigma}$ contains at least one data point.

Pick any $x,x^{\prime}\in A\cap X_{n}$; there is a path $P$ in $A$ with $x\stackrel{{\scriptstyle P}}{{\leadsto}}x^{\prime}$. We’ll identify a sequence of data points $x_{0}=x,x_{1},x_{2},\ldots$, ending in $x^{\prime}$, such that for every $i$, point $x_{i}$ is active in $G_{r}$ and $\|x_{i}-x_{i+1}\|\leq\alpha r$. This will confirm that $x$ is connected to $x^{\prime}$ in $G_{r}$.

To begin with, recall that $P$ is a continuous function from $$into$A$. For any point$y\in{\mathcal{X}}$, define$N(y)$to be the portion of$$whose image under$P$lies in$B(y,r)$: that is,$N(y)=\{0\leq z\leq 1:P(z)\in B(y,r)\}$. If$y$is within distance$r$of$P$, then$N(y)$is nonempty. Define$\pi(y)=P(\sup N(y))$, the furthest point along the path within distance$r$of$y$ (Figure 5, left).

The sequence $\left\{x_{i}\right\}$ is defined iteratively; $x_{0}=x$, and for $i=0,1,2,\ldots:$

If $\|x_{i}-x^{\prime}\|\leq\alpha r$, set $x_{i+1}=x^{\prime}$ and stop.

By construction, $x_{i}$ is within distance $r$ of path $P$ and hence $N(x_{i})\neq\emptyset$.

Let $B$ be the open ball of radius $r$ around $\pi(x_{i})$. The half of $B$ in direction $x_{i}-\pi(x_{i})$ contains a data point; this is $x_{i+1}$ (Figure 5, right).

The process eventually stops since each $\pi(x_{i+1})$ is further along path $P$ than $\pi(x_{i})$; formally, $\sup N(x_{i+1})>\sup N(x_{i})$. This is because $\|x_{i+1}-\pi(x_{i})\|<r$, so by continuity of the function $P$, there are points further along $P$ (beyond $\pi(x_{i})$) whose distance to $x_{i+1}$ is still $<r$. Thus $x_{i+1}$ is distinct from $x_{0},x_{1},\ldots,x_{i}$. Since there are finitely many data points, the process must terminate, so the sequence $\left\{x_{i}\right\}$ constitutes a path from $x$ to $x^{\prime}$.

Each $x_{i}$ lies in $A_{r}\subseteq A_{\sigma-r}$ and is thus active in $G_{r}$ under event $E_{o}$ (Lemma 4.2). Finally, the distance between successive points is $\displaystyle\|x_{i}-x_{i+1}\|^{2}$

where the second-last inequality is from the definition of half-ball. ∎

To complete the proof of Theorem 3.3, take $k\geq 4C_{\delta}^{2}(d/\epsilon^{2})\log n$. The relationship that defines $r=r(\lambda)$ (Definition 4.4) then implies

This shows that clusters at density level $\lambda$ emerge when the growing radius $r$ of the cluster tree algorithm reaches roughly $(k/(\lambda v_{d}n))^{1/d}$. In order for $(\sigma,\epsilon)$-separated clusters to be distinguished, the one additional requirement of Lemma 4.3 and Theorem 4.7 is that $r=r(\lambda)$ be at most $\sigma/2$; this is what yields the final lower bound on $n$.

Analysis of Algorithm 2

The second cluster tree estimator (Figure 4), based on the $k$-nearest neighbor graph of the data points, satisfies the same guarantees as the first, under a more generous setting of $k$.

Let $G^{{\rm NN}}_{r}$ be the $k$-NN graph at radius $r$. We have already observed that $G^{{\rm NN}}_{r}$ has the same vertices as $G_{r}$, and a subset of its edges. Therefore, if clusters are separated in $G_{r}$, they are certainly separated in $G^{{\rm NN}}_{r}$: the separation properties of Lemma 4.3 carry over immediately to the new estimator. What remains is to establish a connectedness property, an analogue of Theorem 4.7, for these potentially much sparser graphs.

We’ll first confirm that $r_{o}$ is, indeed, a lower bound on the radii $r_{k}(\cdot)$.

Assume $E_{o}$. If $k\geq 4C_{\delta}^{2}d\log n$, then $r_{k}(x)>r_{o}$ for all $x$.

Pick any $x$ and consider the ball $B(x,r_{o})$. By definition of $r_{o}$,

where the last inequality is from the condition on $k$. Under $E_{o}$ (Lemma 4.1), we then get $f_{n}(B(x,r_{o}))<k/n$; therefore $r_{k}(x)>r_{o}$. ∎

Now we present an analogue of Theorem 4.7.

Assume $E_{o}$. Let $A$ be a connected set in ${\mathcal{X}}$, with $\lambda=\inf_{x\in A_{\sigma}}f(x)$. Suppose $\alpha\geq\sqrt{2}$. Then $A\cap X_{n}$ is connected in $G^{{\rm NN}}_{r}$ whenever $r+r_{o}\leq\sigma$ and

We’ll consider events at two different scales: a small radius $r_{o}$, and the potentially larger radius $r$ from the theorem statement.

Let’s start with the small scale. The lower bound on $k$ yields

As in Theorem 4.7, this implies that every half-ball of radius $r_{o}$ within $A_{\sigma}$ contains at least one data point.

Let $x$ and $x^{\prime}$ be any two points in $A\cap X_{n}$. As in Theorem 4.7, we can find a finite sequence of data points $x=x_{0},x_{1},\ldots,x_{p}=x^{\prime}$ such that for each $i$, two key conditions hold: (i) $\|x_{i}-x_{i+1}\|\leq\alpha r_{o}$ and (ii) $x_{i}$ lies within distance $r_{o}$ of $A$.

Now let’s move to a different scale $r\leq\sigma-r_{o}$. Since each $x_{i}$ lies in $A_{r_{o}}\subseteq A_{\sigma-r}$, we know from Lemma 4.2 that all $x_{i}$ are active in $G^{{\rm NN}}_{r}$ given the lower bound on $v_{d}r^{d}\lambda$. The edges $(x_{i},x_{i+1})$ are also present, because

using Lemma 5.1 and the bound on $k$. Hence $x$ is connected to $x^{\prime}$ in $G^{{\rm NN}}_{r}$. ∎

It is straightforward to check that $r(\lambda)$ is always $\geq r_{o}$, and Theorem 3.4 follows immediately.

2 A lower bound on neighborhood cardinality

The result for $k$-nearest neighbor graphs requires a larger setting of $k$ than our earlier result; in particular, $k$ needs to exceed the ratio $\Lambda/\lambda$. We now show that this isn’t just a looseness in our bound, but in fact a necessary condition for these types of graphs.

Recall that the mutual $k$-NN graph contains all the data points, and puts an edge between points $x$ and $x^{\prime}$ if $\|x-x^{\prime}\|\leq\alpha\min(r_{k}(x),r_{k}(x^{\prime}))$ (the $\alpha$ is our adaptation). We will assume $1\leq\alpha\leq 2$, as is the case in all our upper bounds.

Consider the density shown in Figure 6, consisting of two dense regions, $A$ and $C$, bridged by a less dense region $B$. Each region is of width $L=1/(\lambda+2\Lambda)$. We’ll show that the mutual $k$-NN graph of a sample from this distribution is likely to be disconnected. Specifically, with probability at least $1/2$, there will be no edges between $A$ and $B\cup C$.

To this end, fix any $n\geq\Lambda/\lambda$, and define $\Delta=1/(4n\lambda)<L$. Consider the leftmost portion of $B$ of length $\Delta$. The probability that a random draw from $f$ falls in this region is $\Delta\lambda=1/(4n)$. Therefore, the probability that no point falls in this region is $(1-1/(4n))^{n}\geq 3/4$. Call this event $E_{1}$.

Next, divide $A$ into intervals of length $\Delta,2\Delta,4\Delta$, and so on, starting from the right. We’ll show that with probability at least $3/4$, the right half of each such interval contains at least $k+1$ points; call this event $E_{2}$. To see why, let’s focus on one particular interval, say that of length $2^{i}\Delta$. The probability that a random point falls in the right half of this interval is $2^{i-1}\Delta\Lambda\geq 2^{i+3}k/n$. Therefore, the number of points in this region is $\geq 2^{i+3}k$ in expectation, and by a Chernoff bound, is $\geq k+1$ except with probability $<\exp(-2^{i+1}k)$. Taking a union bound over all the intervals yields an overall failure probability of at most $1/4$.

With probability at least $1/2$, events $E_{1}$ and $E_{2}$ both occur. Whereupon, for any point in $A$, its nearest neighbor in $B\cup C$ is at least twice as far as its $k$ nearest neighbors in $A$. Thus the mutual $k$-NN graph has no edges between $A$ and $B\cup C$. ∎

This constraint on $k$ is unpleasant, and it would be interesting to either find mild smoothness assumptions on $f$, or better, modified notions of $k$-NN graph, that render it unnecessary.

Lower bound

We have shown that the two cluster tree algorithms distinguish pairs of clusters that are $(\sigma,\epsilon)$-separated. The number of samples required to capture clusters at density $\geq\lambda$ is, by Theorem 3.3,

We’ll now show that this dependence on $\sigma$, $\lambda$, and $\epsilon$ is optimal. The only room for improvement, therefore, is in constants involving $d$.

Consider any algorithm that is given $n\geq 100$ i.i.d. samples $X_{n}$ from some $f_{i}\in F$ and, with probability at least $3/4$, outputs a tree in which the smallest cluster containing $A_{i}\cap X_{n}$ is disjoint from the smallest cluster containing $A_{i}^{\prime}\cap X_{n}$. Then

Given the parameters $d,\sigma,\epsilon,\lambda$, we will construct a space ${\mathcal{X}}$ and a finite family of densities $F=\{f_{i}\}$ on ${\mathcal{X}}$. We will then argue that any cluster tree algorithm that is able to distinguish $(\sigma,\epsilon)$-separated clusters must be able, when given samples from some $f_{i}$, to determine the identity of $I$. The sample complexity of this latter task can be lower-bounded using Fano’s inequality (Appendix D): it is $\Omega((\log|F|)/\theta)$, for

where $K(\cdot,\cdot)$ is Kullback-Leibler divergence.

𝑐1𝜎4(c+1)\sigma$4\sigma<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mn>8</mn><mi>σ</mi></mrow><annotation encoding="application/x-tex">8\sigma</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">8</span><span class="mord mathnormal" style="margin-right:0.0359em;">σ</span></span></span></span></span>12\sigma<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mi>τ</mi><mi>σ</mi></mrow><annotation encoding="application/x-tex">\tau\sigma</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.1132em;">τ</span><span class="mord mathnormal" style="margin-right:0.0359em;">σ</span></span></span></span></span>x_{1}$axis A family of densities on ${\mathcal{X}}$. The family $F$ contains $c-1$ densities $f_{1},\ldots,f_{c-1}$ which coincide on most of the support ${\mathcal{X}}$ and differ on parts of ${\mathcal{X}}_{0}$. Each density $f_{i}$ is piecewise constant as described below. Items (ii) and (iv) describe the pieces that are common to all densities in $F$.

Density $\lambda(1-\epsilon)$ on $(4\sigma i+\sigma,4\sigma i+3\sigma)\times\tau\sigma B_{d-1}$.

Balls of mass $1/(2c)$ centered at locations $4\sigma,8\sigma,\ldots,4c\sigma$ along the $x_{1}$-axis: each such ball is of radius $\tau-1<\sigma$, and the density on these balls is $1/(2c\cdot v_{d}(\tau-1)^{d})\geq\lambda$. We refer to these as mass balls.

Density $\lambda$ on the remainder of ${\mathcal{X}}_{0}$: this is the union of the cylinder segments $[0,4\sigma i+\sigma]\times\tau\sigma B_{d-1}$ and $[4\sigma i+3\sigma,4(c+1)\sigma]\times\tau\sigma B_{d-1}$ minus the mass balls. Since the cross-sectional area of the cylinder is $v_{d-1}(\tau\sigma)^{d-1}$, the total mass here is at most $\lambda\tau^{d-1}v_{d-1}\sigma^{d}(4(c+1)-2)$.

The remaining mass is at least $1/2-8\lambda v_{d-1}\sigma^{d}(c+1)$; we will be careful to choose $c$ so that this is nonnegative. The remaining mass is placed on ${\mathcal{X}}_{1}$ in some fixed manner that does not vary between densities in $F$.

Here is a sketch of $f_{i}$. The low-density region of width $2\sigma$ is centered at $4\sigma i+2\sigma$ on the $x_{1}$-axis, and contains no mass balls.

For any $i\neq j$, the densities $f_{i}$ and $f_{j}$ differ only on the cylindrical sections $(4\sigma i+\sigma,4\sigma i+3\sigma)\times\sigma B_{d-1}$ and $(4\sigma j+\sigma,4\sigma j+3\sigma)\times\sigma B_{d-1}$, which are disjoint, contain no mass ball, and each have volume $2\tau^{d-1}v_{d-1}\sigma^{d}$. Thus

(using $\ln(1-x)\geq-2x$ for $0<x\leq 1/2$). This is an upper bound on the $\theta$ in the Fano bound.

Clusters and separators. Now define the clusters and separators as follows: for each $1\leq i\leq c-1$,

$A_{i}$ is the tubular segment $[\sigma,4\sigma i]\times(\tau-1)\sigma$,

$A_{i}^{\prime}$ is the tubular segment $[4\sigma(i+1),4(c+1)\sigma-\sigma]\times(\tau-1)\sigma$, and

$S_{i}=\{4\sigma i+2\sigma\}\times\sigma B_{d-1}$ is the cross-section of the cylinder at location $4\sigma i+2\sigma$.

Thus $A_{i}$ and $A_{i}^{\prime}$ are $d$-dimensional sets while $S_{i}$ is a $(d-1)$-dimensional set. It can be seen that, for density $f_{i}$, $A_{i}$ and $A_{i}^{\prime}$ are $(\sigma,\epsilon)$-separated, and $\inf_{x\in A_{i,\sigma}\cup A^{\prime}_{i,\sigma}}f_{i}(x)\geq\lambda$.

Now that the various structures are defined, we still need to argue that if an algorithm is given a sample $X_{n}$ from some $f_{i}$ (where $i$ is unknown), and is able to separate $A_{i}\cap X_{n}$ from $A^{\prime}_{i}\cap X_{n}$, then it can effectively infer the identity of $i$. This has sample complexity $\Omega((\log c)/\theta)$.

Let’s set $c$ to be a small constant, say $c=6$. Then, even a small sample $X_{n}$ of $n\geq 100$ points is likely (with probability at least $3/4$, say), to contain points from all of the $c$ mass balls, each of which has mass $1/(2c)$. Suppose the algorithm even knows in advance that the underlying density is one of the $c-1$ choices in $F$, and is subsequently able (with probability at least $3/4$) to separate $A_{i}$ from $A_{i}^{\prime}$. To do this, it must connect all the points from mass balls within $A_{i}$, and all the points from mass balls within $A_{i}^{\prime}$, and yet keep these two groups apart. In short, this algorithm must be able to determine (with overall probability at least $1/2$) the segment $(4\sigma i+\sigma,4\sigma i+3\sigma)$ of lower density, and hence the identity of $i$.

We can thus apply Fano’s inequality to conclude that we need

for some absolute constant $C_{2}$. The last equality comes from the formula $v_{d}=\pi^{d/2}/\Gamma((d/2)+1)$, whereupon $v_{d-1}=O(v_{d}d^{1/2})$.

This is almost the bound in the theorem statement, short a logarithmic term. To finish up, we now switch to a larger value of $c$:

and apply the same construction. We have already established that we need $n=\Omega(c/\epsilon^{2})$ samples, so assume $n$ is at least this large. Then, for small enough $\epsilon$, it is very likely that when the underlying density is $f_{i}$, the sample $X_{n}$ will contain the four point masses at $4\sigma$, $4\sigma i$, $4\sigma(i+1)$, and $4(c+1)\sigma$. Therefore, the clustering algorithm must connect the point at $4\sigma$ to that at $4\sigma i$ and the point at $4\sigma(i+1)$ to that at $4(c+1)\sigma$, while keeping the two groups apart. Therefore, this algorithm can determine $i$. Applying Fano’s inequality gives $n=\Omega((\log c)/\theta)$, which is the bound in the theorem statement. ∎

Pruning

Hartigan’s notion of consistency (Definition 2.3) requires distinct clusters to be distinguished, but does not guard against fragmentation within a cluster. Consider, for instance, the density shown in Figure 6. Under Hartigan-consistency, in the limit, the cluster tree must include a cluster that contains all of $A$ and a separate, disjoint cluster that contains all of $C$. But the tree is allowed to break $A$ into further subregions. To be concrete, suppose we draw a sample from that density and receive four points from each of $A$ and $C$. Figure 7, left, shows a possible cluster tree on these samples that meets the consistency requirement. However, we’d prefer the one on the right. Formally we want to avoid or remove false clusters as defined below.

Let $A_{n}$ and $A_{n}^{\prime}$ be the vertices of two separate connected components (potentially at different levels) in the cluster tree returned by an algorithm. We call $A_{n}$ and $A_{n}^{\prime}$ false clusters if they are part of the same connected component of the level set $\left\{x:f(x)\geq\min_{x^{\prime}\in A_{n}\cup A_{n}^{\prime}}f(x^{\prime})\right\}$.

This problem is generally addressed in the literature by making assumptions about the size of true clusters. Real clusters are assumed to be large in some sense, for instance in terms of their mass (Maier et al., 2009), or excess massThe excess mass of a component $A$ at level $\lambda$ is generally defined as $\int_{A}(f(x)-\lambda)\,dx$. (Stuetzle and Nugent, 2009). However, relying on size can be misleading in practice, as is illustrated in Figure 8. It turns out that, building on the results of the previous sections, there is a simple way to treat spurious clusters independent of their size.

The above intuition is likely to extend to cluster tree procedures other than the ones discussed here. The main requirement on the cluster tree estimate is that points in $A$ (as discussed above) be connected at some nearby level in the tree.

2 Separation

Assume $E_{o}$. Consider two sets $A,A^{\prime}\subset{\mathcal{X}}$, and let $\lambda=\inf_{x\in A_{\sigma}\cup A^{\prime}_{\sigma}}f(x)$. Suppose there exists a separator set $S$ such that

Any path in ${\mathcal{X}}$ from $A$ to $A^{\prime}$ intersects $S$.

3 Connectedness

We now turn to the main result of this section, namely that the pruning procedure reconnects incorrectly fragmented clusters. Recall the intuition detailed above. We first have to argue that points with similar density make their first appearance at nearby levels $r$ of the empirical tree. From the analysis of the previous sections, we know that a point $x$ is present at level $r(f(x))$, roughly speaking. We now need to show that it cannot appear at a level too much smaller than this.

These assertions about single points are true only if the density doesn’t vary too dramatically in their vicinity. In what follows, we will quantify the smoothness at scale $\sigma$ by the constant

Assume $E_{o}$. Pick any $x$ and let $f_{\sigma}(x)=\inf_{x^{\prime}\in B(x,\sigma)}f(x^{\prime})$. Suppose

Then $r\leq\sigma/2$, implying $f(B(x,r))\leq v_{d}r^{d}(f_{\sigma}(x)+L_{\sigma})$. Using the first inequality and Lemma 4.1, we have $f_{n}(B(x,r))<k/n$, that is $r<r_{k}(x)$. ∎

Next, by combining the above lower-bound on $r_{k}(x)$ with our previous results on connectedness for both types of algorithms, we obtain the following pruning guarantees.

Let $A$ be any connected component of $\{x\in{\mathcal{X}}:f(x)\geq\lambda\}$. We’ll show that $A\cap X_{n}$ is connected in $G_{r}$ (or $G^{\rm NN}_{r}$) after pruning, from which the lemma follows immediately.

Define $\lambda_{\sigma}=\inf_{x\in A_{\sigma}}f(x)\geq\inf_{x\in A}f(x)-L_{\sigma}\geq\lambda-L_{\sigma}$. Recall from Definition 4.4 that $r(\lambda_{\sigma})$ is the value of $r$ for which $v_{d}r^{d}\lambda_{\sigma}=\frac{k}{n}+\frac{C_{\delta}}{n}\sqrt{kd\log n}$. The first condition in the lemma statement thus implies that $r(\lambda_{\sigma})\leq\sigma/2$. The second condition, together with Theorem 4.7 or Theorem 5.2, implies that $A\cap X_{n}$ is connected at level $r(\lambda_{\sigma})$ of $G$ or $G^{\rm NN}$.

The separation and connectedness results of this section can now be combined into the following theorem.

Then the following holds with probability at least $1-\delta$. Define

or in the case of Algorithm 2, the maximum of this quantity and $(\Lambda/k)Cd\log n\cdot\log(1/\delta)$, where $\Lambda=\sup_{x\in{\mathcal{X}}}f(x)$.

Recovery of true clusters: Consider any two sets $A,A^{\prime}\subset{\mathcal{X}}$, and suppose $\lambda=\inf_{x\in A_{\sigma}\cup A^{\prime}_{\sigma}}f(x)\geq\lambda_{o}$. Suppose there exists a set $S$ such that

Any path in ${\mathcal{X}}$ from $A$ to $A^{\prime}$ intersects $S$.

Final remarks

Both cluster tree algorithms are variations on standard estimators, but carefully control the neighborhood size $k$ and make use of a novel parameter $\alpha$ to allow more edges at every scale $r$. The analysis relies on $\alpha$ being at least $\sqrt{2}$, and on $k$ being at least $d\log n$. Is it possible to dispense with $\alpha$ (that is, to use $\alpha=1$) while maintaining this setting of $k$?