On the Consistency of Quick Shift

Quick Shift is a popular mode-seeking and clustering algorithm. We present finite sample statistical consistency guarantees for Quick Shift on mode and cluster recovery under mild distributional assumptions. We then apply our results to construct a consistent modal regression algorithm.


Introduction
Quick Shift [16] is a clustering and mode-seeking procedure that has received much attention in computer vision and related areas. It is simple and proceeds as follows: it moves each sample to its closest sample with a higher empirical density if one exists in a τ radius ball, where the empirical density is taken to be the Kernel Density Estimator (KDE). The output of the procedure can thus be seen as a graph whose vertices are the sample points and a directed edge from each sample to its next point if one exists. Furthermore, it can be seen that Quick Shift partitions the samples into trees which can be taken as the final clusters, and the root of each such tree is an estimate of a local maxima.
Quick Shift was designed as an alternative to the better known mean-shift procedure [4,5]. Mean-shift performs a gradient ascent of the KDE starting at each sample until -convergence. The samples that correspond to the same points of convergence are in the same cluster and the points of convergence are taken to be the estimates of the modes. Both procedures aim at clustering the data points by incrementally hill-climbing to a mode in the underlying density. Some key differences are that Quick Shift restricts the steps to sample points and has the extra τ parameter. In this paper, we show that Quick Shift can surprisingly attain strong statistical guarantees without the second-order density assumptions required to analyze mean-shift.
We prove that Quick Shift recovers the modes of an arbitrary multimodal density at a minimax optimal rate under mild nonparametric assumptions. This provides an alternative to known procedures with similar statistical guarantees; however such procedures only recover the modes but fail to inform us how to assign the sample points to a mode which is critical for clustering. Quick Shift on the other hand recovers both the modes and the clustering assignments with statistical consistency guarantees. Moreover, Quick Shift's ability to do all of this has been extensively validated in practice.
A unique feature of Quick Shift is that it has a segmentation parameter τ which allows practioners to merge clusters corresponding to certain less salient modes of the distribution. In other words, if a local mode is not the maximizer of its τ -radius neighborhood, then its corresponding cluster will become merged to that of another mode. Current consistent mode-seeking procedures [6,12] fail to allow one to control such segmentation. We give guarantees on how Quick Shift does this given an arbitrary setting of τ .
We show that Quick Shift can also be used to recover the cluster tree. In cluster tree estimation, the known procedures with the strongest statistical consistency guarantees include Robust Single Linkage (RSL) [2] and its variants e.g. [13,7]. We show that Quick Shift attains similar guarantees.
Thus, Quick Shift, a simple and already popular procedure, can simultaneously recover the modes with segmentation tuning, provide clustering assignments to the appropriate mode, and can estimate the cluster tree of an unknown density f with the strong consistency guarantees. No other procedure has been shown to have these properties.
Then we use Quick Shift to solve the modal regression problem [3], which involves estimating the modes of the conditional density f (y|X) rather than the mean as in classical regression. Traditional approaches use a modified version of mean-shift. We provide an alternative using Quick Shift which has precise statistical consistency guarantees under much more mild assumptions. The procedure returns one tree, whose head is the sample with highest empirical density. Right: τ set to a lower value. The edges with length greater than τ are no longer present when compared to the left. We are left with three clusters.

Setup
Let X [n] = {x 1 , ..., x n } be n i.i.d. samples drawn from distribution F with density f over the uniform measure on R d . Assumption 1 (Hölder Density). f is Hölder continuous on compact support x ∈ X and some 0 < α ≤ 1 and C α > 0.
The next assumption says that the level sets are continuous w.r.t. the level in the following sense where we denote the -interior of A as A := {x ∈ A, inf y∈∂A d(x, y) ≥ } (∂A is the boundary of A): Assumption 2 (Uniform Continuity of Level Sets). For each > 0, there exists δ > 0 such that for 0 < λ ≤ λ ≤ ||f || ∞ with |λ − λ | < δ, then L f (λ) ⊆ L f (λ ). Remark 1. Procedures that try to incrementally move points to nearby areas of higher density will have difficulties in regions where there is little or no change in density. The above assumption is a simple and mild formulation which ensures there are no such flat regions. Remark 2. Note that our assumptions are quite mild when compared to analyses of similar procedures like mean-shift, which require at least second-order smoothness assumptions. Interestingly, we only require Hölder continuity.

KDE Bounds
We next give uniform bounds on KDE required to analyze Quick Shift. Definition 3. Define kernel function K : R d → R ≥0 where R ≥0 denotes the non-negative real numbers such that R d K(u)du = 1. We make the following mild regularity assumptions on K. Assumption 3. (Spherically symmetric, non-increasing, and exponential decays) There exists nonincreasing function k : R ≥0 → R ≥0 such that K(u) = k(|u|) for u ∈ R d and there exists ρ, C ρ , t 0 > 0 such that for t > t 0 , k(t) ≤ C ρ · exp(−t ρ ). Remark 3. These assumptions allow the popular kernels such as Gaussian, Exponential, Silverman, uniform, triangular, tricube, Cosine, and Epanechnikov. Definition 4 (Kernel Density Estimator). Given a kernel K and bandwidth h > 0 the KDE is defined by Here we provide the uniform KDE bound which will be used for our analysis, established in [11]. Lemma 1.
[ ∞ bound for α-Hölder continuous functions. Theorem 2 of [11]] There exists positive constant C depending on f and K such that the following holds with probability at least

Mode Estimation
In this section, we give guarantees about the local modes returned by Quick Shift. We make the additional assumption that the modes are local maxima points with negative-definite Hessian. This assumption leads to the following.
which contains x 0 and does not intersect with other modes.
The next assumption ensures that the level sets don't become arbitrarily thin as long as we are sufficiently away from the modes. Assumption 5.
[Level Set Regularity] For each σ, r > 0, there exists η > 0 such that the following holds for all connected components We next give the result about mode recovery for Quick Shift. It says that as long as τ is small enough, then as the number of samples grows, the roots of the trees returned by Quick Shift will bijectively correspond to the true modes of f and the estimation errors will match lower bounds established by Tsybakov [15] up to logarithmic factors. We defer the proof to Theorem 2 which is a generalization of the following result. Theorem 1 (Mode Estimation guarantees for Quick Shift). Let τ < r M /2 and Assumptions 1, 2, 3, 4, and 5 hold. Choose h such that (log n) 2/ρ · h → 0 and log n/(nh d ) → 0 as n → ∞. Let M be the heads of the trees in G (returned by Algorithm 1). There exists constant C depending on f and K such that for n sufficiently large, with probability at least 1 − 1/n, and |M| = | M|. In particular, taking h ≈ n −1/(4+d) optimizes the above rate to d(M, M) = O(n −1/(4+d) ). This matches the minimax optimal rate for mode estimation up to logarithmic factors.
We now give a stronger notion of mode that fits better for analyzing the role of τ . In the last result, it was assumed that the practitioner wished to recover exactly the modes of the density f by taking τ sufficiently small. Now, we analyze the case where τ is intentionally set to a particular value so that Quick Shift produces segmentations that group modes together that are in close proximity to higher density regions.
In other words, an (r, δ) + -mode is a mode that is also a maximizer in a larger ball of radius r by at least δ when outside of the region where there is quadratic decay and smoothness (B(x 0 , r M )). An (r, δ) − -mode is a mode that is not the maximizer in its radius r ball by a margin of at least δ.
The next result shows that Algorithm recovers the (τ + , δ) + -modes of f and excludes the (τ − , δ) −modes of f . The proof is in the appendix. Theorem 2. (Generalization of Theorem 1) Let δ, > 0 and suppose Assumptions 1, 2, 3, 4, and 5 hold. Let h ≡ h(n) be chosen such that h → 0 and log n/(nh d ) → 0 as n → ∞. Then there exists C > 0 depending on f and K such that the following holds for n sufficiently large with probability Moreover, | M| ≤ |M| − |M − τ − ,δ |. In particular, taking → 0 and δ → 0 gives us an exact characterization of the asymptotic behavior of Quick Shift in terms of mode recovery.

Assignment of Points to Modes
In this section, we give guarantees on how the points are assigned to their respective modes. We first give the following definition which formalizes how two points are separated by a wide and deep valley. Definition 6. x 1 , x 2 ∈ X are (r s , δ)-separated if there exists a set S such that every path from x 1 and x 2 intersects with S and sup x∈S+B(0,rs) Lemma 3. Suppose Assumptions 1, 2, 3, 4, and 5 hold. Let τ < r s /2 and choose h such that (log n) 2/ρ · h → 0 and log n/(nh d ) → 0 as n → ∞. Let G be the output of Algorithm 1. The following holds with probability at least 1 − 1/n for n sufficiently large depending on f , K, δ, and τ uniformly in all x 1 , x 2 ∈ X . If x 1 and x 2 are (r s , δ)-separated, then there cannot exist a directed path from x 1 to x 2 in G.
Proof. Suppose that x 1 and x 2 are (r s , δ)-separated (with respect to set S) and there exists a directed path from x 1 to x 2 in G. Given our choice of τ , there exists some point x ∈ G such that x ∈ S+B(0, r s ) and x is on the path from x 1 to x 2 . We have f (x) < f (x 1 )−δ. Choose n sufficiently large such that by Lemma 1, , which means a directed path in G starting from x 1 cannot contain x, a contradiction. The result follows. The results in this section will show that in such cases, these pairs of points will not be assigned to the same cluster.
This leads to the following consequence about how samples are assigned to their respective modes. Theorem 3. Assume the same conditions as Lemma 3. The following holds with probability at least 1 − 1/n for n sufficiently large depending on f , K, δ, and τ uniformly in x ∈ X and x 0 ∈ M. For each x ∈ X and x 0 ∈ M, if x and x 0 are (r s , δ)-separated, then x will not be assigned to the tree corresponding to x 0 from Theorem 1. Remark 4. In particular, taking δ → 0 and r s → 0 gives us guarantees for all points which have a unique mode in which it can be assigned to.
We now give a more general version of (r s , δ)-separation, in which the condition holds if every path between the two points dips down at some point. The same results as the above extend for this definition in a straightforward manner. Definition 7. x 1 , x 2 ∈ X are (r s , δ)-weakly-separated if there exists a set S, with x 1 , x 2 ∈ S + B(0, r s ), such that every path P from x 1 and x 2 satisifes the following. (1) P ∩ S = ∅ and (2) sup x∈P∩S+B(0,rs) where x 1 , x 2 are defined as follows. Let P 1 be the path obtained by starting at x 1 and following P until it intersects S, and P 2 be the path obtained by following P starting from the last time it intersects S until the end. Then x 1 and x 2 are points which respectively attain the highest values of f on P 1 and P 2 .

Cluster Tree Recovery
The connected components of the level sets as the density level varies forms a hierarchical structure known as the cluster tree. Definition 8 (Cluster Tree). The cluster tree of f is given by Definition 9. Let G(λ) be the subgraph of G with vertices x ∈ X [n] such that f h (x) > λ and edges between pairs of vertices which have corresponding edges in G. LetG(λ) be the sets of vertices corresponding to the connected components of G(λ).

Definition 10.
Suppose that A is a collection of sets of points in R d . Then define Link(A, δ) to be the result of repeatedly removing pairs A 1 , A 2 ∈ A from A (A 1 = A 2 ) that satisfy inf a1∈A1 inf a2∈A2 ||a 1 − a 2 || < δ and adding A 1 ∪ A 2 to A until no such pairs exist.
Parameter settings for Algorithm 2: Suppose that τ ≡ τ (n) is chosen as a function of n such such that τ → 0 as n → ∞, τ (n) ≥ (log 2 n/n) 1/d and h ≡ h(n) is chosen such that h → 0 and log n/(nh d ) → 0 as n → ∞.
The following is the main result of this section, the proof is in the appendix.  Shift's output to samples have empirical density above a certain threshold and connecting nearby clusters, then this approximates the connected components of the true density level set. Moreover, we give guarantees that such points will be assigned to clusters which correspond to modes within its connected component.

Modal Regression
Suppose that we have joint density f (X, y) on R d × R w.r.t. to the Lebesgue measure. In modal regression, we are interested in estimating the modes of the conditional f (y|X = x) given samples from the joint distribution. Initialize directed graph G with vertices Y and no edges. Theorem 5 (Consistency of Quick Shift Modal Regression). Suppose that τ ≡ τ (n) is chosen as a function of n such such that τ → 0 as n → ∞, τ (n) ≥ (log 2 n/n) 1/d and h ≡ h(n) is chosen such that h → 0 and log n/(nh d+1 ) → 0 as n → ∞. Let M x be the modes of the conditional density f (y|X = x) and M x be the output of Algorithm 3. Then with probability at least 1 − 1/n uniformly in x such that f (y|X = x) and K satisfies Assumptions 1, 2, 3, 4, and 5,

Related Works
Mode Estimation. Perhaps the most popular procedure to estimate the modes is mean-shift; however, it has proven quite difficult to analyze. Arias-Castro et al. [1] made much progress by utilizing dynamical systems theory to show that mean-shift's updates converge to the correct gradient ascent steps. The recent work of Dasgupta and Kpotufe [6] was the first to give a procedure which recovers the modes of a density with minimax optimal statistical guarantees in a multimodal density. They do this by using a top-down traversal of the density levels of a proximity graph, borrowing from work in cluster tree estimation. The procedure was shown to recover exactly the modes of the density at minimax optimal rates.
In this work, we showed that Quick Shift attains the same guarantees while being a simpler approach than known procedures that attain these guarantees [6,12]. Moreover unlike these procedures, Quick Shift also assigns the remaining samples to their appropriate modes. Furthermore, Quick Shift also has a segmentation tuning parameter τ which allows us to merge the clusters of modes that are not maximal in its τ -radius neighborhood into the clusters of other modes. This is useful as in practice, one may not wish to pick up every single local maxima, especially when there are local maxima that can be grouped together by proximity. We formalized the segmentation of such modes and identify which modes get returned and which ones become merged into other modes' clusters by Quick Shift.
Cluster Tree Estimation. Work on cluster tree estimation has a long history. Some early work on density based clustering by Hartigan [9] modeled the clusters of a density as the regions {x : f (x) ≥ λ} for some λ. This is called the density level-set of f at level λ. The cluster tree of f is the hierarchy formed by the infinite collection of these clusters over all λ. Chaudhuri and Dasgupta [2] introduced Robust Single Linkage (RSL) which was the first cluster tree estimation procedure with precise statistical guarantees. Shortly after, Kpotufe and Luxburg [13] provided an estimator that ensured false clusters were removed using used an extra pruning step. Interestingly, Quick Shift does not require such a pruning step, since the points near cluster boundaries naturally get assigned to regions with higher density and thus no spurious clusters are formed near these boundaries. Sriperumbudur and Steinwart [14], Jiang [10], Wang et al. [17] showed that the popular DBSCAN algorithm [8] also estimates these level sets. Eldridge et al. [7] introduced the merge distortion metric for cluster tree estimates, which provided a stronger notion of consistency. We use their framework to analyze Quick Shift and show that this simple estimator is consistent in merge distortion. Modal Regression. Nonparametric modal regression [3] is an alternative to classical regression, where we are interested in estimating the modes of the conditional density f (y|X = x) rather than the mean. Current approaches primarily use a modification of mean-shift; however analysis for mean-shift require higher order smoothness assumptions. Using Quick Shift instead for modal regression requires less regularity assumptions while having consistency guarantees.

Conclusion
We provided consistency guarantees for Quick Shift under mild assumptions. We showed that Quick Shift recovers the modes of a density from a finite sample with minimax optimal guarantees. The approach of this method is considerably different from known procedures that attain similar guarantees. Moreover, Quick Shift allows tuning of the segmentation and we provided an analysis of this behavior. We also showed that Quick Shift can be used as an alternative for estimating the cluster tree which contrasts with current approaches which utilize proximity graph sweeps. We then constructed a procedure for modal regression using Quick Shift which attains strong statistical guarantees.

Cluster Tree Estimation Proofs
Lemma 5 (Minimality). The following holds with probability at least 1 − 1/n. If A is a connected component of {x ∈ X : f (x) ≥ λ}, then A ∩ X [n] is contained in the same component in C f (λ − ) for any > 0 as n → ∞.
Proof. It suffices to show that for each x ∈ A, there exists x ∈ B(x, τ /2) ∩ X [n] such that f h (x ) > λ − . Given our choice of τ , it follows by Lemma 7 of [2] that B(x, τ /2) ∩ X [n] is non-empty for n sufficiently large. Let x ∈ B(x, τ /2) ∩ X [n] . Choose n sufficiently large such that by Lemma 1, we where the last inequality holds for n sufficiently large so that τ is sufficiently small. Thus, we have f h (x ) > λ − , as desired.
Lemma 6 (Separation). Suppose that A and B are distinct connected components of {x ∈ X : f (x) ≥ λ} which merge at {x ∈ X : f (x) ≥ µ}. Then A ∩ X [n] and B ∩ X [n] are separated in C f (µ + ) for any > 0 as n → ∞.
Proof. It suffices to assume that λ = µ + . Let A and B be the connected components of {x ∈ X : f (x) ≥ µ + /2} which contain A and B respectively. By the uniform continuity of f , there existsr > 0 such that A + B(0, 3r) ⊆ A . We have sup x∈A \(A+B(0,r)) f (x) = µ + − for some > 0.
Choose n sufficiently large such that by Lemma 1, we have sup x∈X | f h (x) − f (x)| < /2. Thus, sup x∈A \(A+B(0,r)) f h (x) < µ + − /2. Hence, points in C f (µ + ) cannot belong to A \ (A + B(0,r)). Since A also contains A + B(0, 3r), it means that there cannot be a path from A to B with points of empirical density at least µ + with all edges of length less thanr. The result follows by taking n sufficiently large so that τ <r, as desired.
Proof of Theorem 4. By the regularity assumptions on f and Theorem 2 of [7], we have that Algorithm 2 has both uniform minimality and uniform separation (defined in [7]), which implies convergence in merge distortion.

Modal Regression Proofs
Proof of Theorem 5. There are two directions to show. (1) ifŷ ∈ M x thenŷ is a consistent estimator of some mode y 0 ∈ M x . (2) For each mode, y 0 ∈ M, there exists a uniqueŷ ∈ M which estimates it.