Generalized density clustering

Alessandro Rinaldo; Larry Wasserman

Source-linked AI summary

Generalized density clustering

Alessandro Rinaldo, Larry Wasserman

arXiv:0907.3454v3Jul 20, 2009math.ST

TL;DR

The paper addresses density clustering when clusters are sharply defined, lower-dimensional, or lack an ordinary density. It develops generalized clustering methods, bandwidth-selection procedures, stability analysis, and a graph algorithm that recovers high-density clusters.

Problem
Density clustering should handle sharply defined clusters, including point-mass or lower-dimensional clusters, for which smoothness or even existence of an ordinary density is unsuitable.
Method
The paper defines generalized density clusters, derives estimator convergence rates, studies stability, proposes two data-driven bandwidth methods, and uses a depth-first search on a ρ-nearest neighborhood graph.
Results
The true clusters can be recovered using a density estimator with a large bandwidth, without assuming that the true density is smooth or even exists.
Takeaways & Limitations
Generalized density clustering permits accurate high-dimensional clustering of sharply defined or lower-dimensional structures, with graph-based recovery of high-density clusters.
Takeaways & Limitations
When a small amount of mass lies just outside a cluster, the formal rate can become slow in high dimensions despite finite-sample behavior remaining close to the sharp case.

Abstract

from arXiv · show

We study generalized density-based clustering in which sharply defined clusters such as clusters on lower-dimensional manifolds are allowed. We show that accurate clustering is possible even in high dimensions. We propose two data-based methods for choosing the bandwidth and we study the stability properties of density clusters. We show that a simple graph-based algorithm successfully approximates the high density clusters.

1. Introduction.

The paper develops density clustering that permits nonsmooth, nonexistent, lower-dimensional, and sharply defined distributions, while targeting accurate clustering in high dimensions. It uses mollified densities, data-driven bandwidth selection, stability analysis, and a graph-based algorithm to recover or approximate high-density clusters.

Mollified density framework: Mollifying the distribution with a kernel produces a full-dimensional density whose high-density components contain the true clusters.The resulting cluster overestimation has zero probability under the stated conditions.
Rates and estimation: The kernel density estimator converges uniformly at O((log n/n)^(1/2)) almost everywhere under a fixed bandwidth, independently of dimension.The fixed-bandwidth bias does not adversely affect clustering.
Contributions: The paper studies convergence rates, two data-driven bandwidth-selection methods, and the stability properties of density clusters.These contributions address both statistical estimation and practical smoothing choices.
Motivation and scope: The proposed density-clustering notion allows clusters on lower-dimensional manifolds or single points, including distributions without a usual density.This avoids assumptions such as density smoothness or boundedness that exclude sharply defined clusters.
Computational approximation: A depth-first search on the ρ-nearest neighborhood graph of estimated high-density observations effectively recovers high-density clusters.The graph connects observations when they share a ball of radius ρ, then extracts connected components.

2. Settings and assumptions.

The paper defines density clusters for distributions that may lack smooth or even ordinary Lebesgue densities, including lower-dimensional supports and point masses. It uses mollification, level-set risks, structural assumptions, and empirical density estimates to analyze estimation and clustering.

Level set clusters: The geometric density can be infinite on lower-dimensional support and need not be a probability density, but it can still recover the support.The paper fixes a level λ below the supremum of the geometric density and studies the corresponding level set and clusters.
Level set clusters: Clusters are connected components of high-density regions and may be lower-dimensional manifolds or single points.The number of clusters is not assumed known, and lower-dimensional support components can themselves form clusters.
Mollification: Mollification convolves P with a bandwidth-h kernel, producing a full-dimensional, smoother density that approximates P as h approaches zero.The mollified measure has support S ⊕ B(0,h), inherits kernel smoothness, and converges weakly to P as h → 0.
Estimation and computation: The estimator uses connected components of the estimated high-density set to estimate the target clusters, but exact connectivity can be computationally difficult.Determining whether two points share a cluster requires finding or ruling out paths that remain above the density threshold.
Risk: Risk is assessed through level-set loss and excess mass, whose maximizer is the true level set in the standard formulation.When the distribution has a component singular with respect to Lebesgue measure, the true level set is no longer necessarily the unique excess-mass minimizer.
Assumptions: The analysis assumes separation, bias, and variance conditions, with a support-dimension condition that is satisfied for sufficiently small bandwidths on rectifiable lower-dimensional components.The constants may depend on ambient dimension and can materially affect finite-sample performance even when asymptotic rates are unchanged.
Condition (C1): A sufficient condition gives γ = 1 when the density of p(X) is bounded away from zero and infinity near λ, and regular Lipschitz densities satisfy this for almost every level.Exceptional behavior can arise at discontinuities or where the gradient vanishes or becomes unbounded.
Sharp clusters: For sharp clusters, the mollified clusters contain the true clusters and differ from them by a set of zero probability.This supports using mollified densities even when the original distribution includes point masses or lower-dimensional components.

3. Rates of convergence.

The paper derives convergence rates for level-set and excess-mass clustering risks under generalized density-clustering assumptions. The rates improve for lower-dimensional supports and can become dimension-independent for sharp clusters or suitable biased-cluster objectives.

Rates of convergence.: The analysis establishes consistency rates for level-set and excess-mass risks using deterministic bandwidths before treating data-driven bandwidths.The rates rely on kernel-estimation control and conditions governing clustering bias.
Rates of convergence.: Higher support dimension parameter θ values, corresponding to lower-dimensional supports, yield faster excess-mass convergence rates.The paper links θ to the dimension of the support of P.
Rates of convergence.: For sharp clusters or lower-dimensional supports, the level-set risk can achieve the dimension-independent rate O(1/n).This occurs when γ = ∞ and the relevant set difference is empty or has zero Lebesgue measure.
Rates of convergence.: The expected proportion of sample points incorrectly assigned as clusters or noise vanishes at the same rate as the stated clustering result.This is given as a corollary of Theorem 10.
Rates of convergence.: Biased-cluster objectives can yield rates O((log n/n)^(γβ/(2β+d))) for level-set risk and O((log n/n)^((γ+1)β/(2β+d))) for excess-mass risk.These rates use hn = (log n/n)^(1/(2β+d)) and εn = Ω((log n/n)^(β/(2β+d))).

4. Choosing the bandwidth.

The paper proposes two data-driven bandwidth-selection methods for density clustering: excess-mass maximization and cluster stability. The excess-mass method adapts to unknown noise and support-dimension parameters, while small samples can make data splitting variable.

4. Choosing the bandwidth.: L2 cross-validation is unsuitable when P may have atoms because it can select bandwidth h = 0.The paper therefore develops two alternative data-driven methods.
4.1. Excess mass.: The resulting cross-validation procedure adapts to the unknown parameters γ and θ, including the unknown dimension of the support of P.The bandwidth grid is constructed so optimization over it adapts to both parameters.
4.1. Excess mass.: The excess-mass method splits the data and chooses the bandwidth by maximizing an empirical excess-mass estimate over a random class of estimated level sets.The random class is indexed by candidate bandwidths.
4.1. Excess mass.: For small sample sizes, data splitting may produce highly variable bandwidth choices and may not work well.The paper suggests repeatedly splitting the data and combining estimates as an alternative.
4.2. Stability.: A second method selects the bandwidth using a stability criterion computed from density estimates and an independent empirical distribution.The stability construction uses separate data subsets for the density estimates and evaluation.

1. Sharp clusters.

The sharp-cluster setting uses a mixture model in which components are uniform on compact full-dimensional sets and a spherical kernel is employed.

1. Sharp clusters.: The model represents P as a mixture whose components are uniform on compact sets Sj of full dimension d.The mixture weights are denoted by πj.
1. Sharp clusters.: A spherical kernel is used in the sharp-cluster construction.

2. Spherical Kernel.

The stability analysis characterizes bandwidth-dependent clustering instability and motivates a stability-based bandwidth rule, while identifying oversmoothing risks when λ > 0.

The instability graph is typically unimodal, with Ξ(0) = Ξ(∞) = 0, so minimizing instability is not meaningful.
Under conditions 1–4, the expected instability is zero at h = 0 and for h ≥ h∗, while remaining bounded by 1/2 for intermediate bandwidths.
The stability rule selects a bandwidth that does not converge to zero because it targets variability reduction rather than bias from large bandwidths.
For λ > 0, large bandwidths can create instability peaks when a mode of ph(x) approaches λ, causing the original rule to seriously oversmooth.
The modified stability rule starts searching above h0, the bandwidth maximizing instability, but its detailed theoretical analysis is not pursued.

5. Approximating the clusters.

The paper approximates high-density clusters by thresholding a kernel density estimate and finding connected components in a ρ-nearest-neighborhood graph. Under regularity conditions and suitable parameters, this graph recovers cluster counts and memberships with high probability.

The method replaces computationally difficult exact connected-component calculations with a fast, easy-to-implement graph procedure.
The algorithm computes a kernel density estimate, builds a ρ-nearest-neighborhood graph on points above λ, and finds its connected components by depth-first search.
With appropriately chosen ρ, the graph algorithm recovers the true number of clusters and matches sampled points to those clusters with high probability as n →∞.
Theoretical guarantees depend on regularity conditions for the smoothed densities and geometric assumptions governing the support and level-set boundaries.

6. Examples.

The examples compare instability and excess-mass bandwidth selection across one-dimensional, lower-dimensional, and 20-dimensional data. Both methods recover the intended level sets or clusters in the reported examples, with the modified instability rule avoiding oversmoothing in the one-dimensional case.

6.1. A one dimensional example.: The modified bandwidth rule succeeds where the original rule oversmooths the estimator and produces no points above the target level.For λ = 0.3, the modified rule selects the first vertical-line bandwidth and works correctly, whereas the original rule selects an oversmoothed bandwidth.
6.1. A one dimensional example.: Both instability and excess-mass methods recover the level set and clusters in the one-dimensional comparison with λ = 0.3.The comparison uses instability and excess mass as functions of log bandwidth and estimated excess-mass risk, respectively.
6.3. Two moons.: Both methods recover the clusters for data combining a noisy fuzzy stick with a spiral supported on a lower-dimensional curve.The excess-mass method uses the smallest bandwidth maximizing excess mass when the risk equals 1 for large bandwidths.
6.3. Two moons.: Both methods recover clusters for two half-moons embedded in R20, although only the first two coordinates are plotted.The example demonstrates the reported clustering result in a 20-dimensional setting.

7. Discussion.

The discussion recommends evaluating a range of density levels and selecting a bandwidth separately for each level. It also identifies stability selection as promising but requiring further study, while noting possible connections to spectral clustering.

7. Discussion.: A different bandwidth should be chosen for each λ because the optimal bandwidth depends on λ and tends to zero as λ increases.The discussion recommends computing results over a range of λ values in practice.
7. Discussion.: The stability method appears to work well for density clustering, unlike the reported behavior for k-means clustering.The authors state that the stability method deserves further scrutiny under more general conditions.
7. Discussion.: The stability measure’s behavior under more general conditions remains insufficiently understood.This is identified as a direction for further research.
7. Discussion.: The paper notes potential connections between its density-clustering framework and spectral clustering methods.The discussion presents this as an area of connection rather than a developed result.

8. Proofs.

The proofs establish risk and convergence results by controlling kernel-density level sets and excess mass under separate full-dimensional and lower-dimensional support cases. They also provide finite-sample bandwidth-selection bounds and a stability-based analysis.

8. Proofs.: The proofs distinguish full-dimensional and lower-dimensional support because the resulting level-set and excess-mass bounds differ between these cases.This case split appears explicitly in both the level-set and excess-mass analyses.
8. Proofs.: The level-set risk bound is zero for lower-dimensional support and bounded by max{C1,C3}(ε^γ + h^ξ) when the support contains a full-dimensional set.The proof combines separate lower- and full-dimensional support arguments with empirical level-set controls.
8. Proofs.: The excess-mass risk is bounded at a rate proportional to λC2h^θ for lower-dimensional support, with a separate bound for full-dimensional support.The proof treats the two support cases separately before deriving convergence rates.
8. Proofs.: The bandwidth-selection proof bounds expected excess risk using an empirical-process argument over the candidate bandwidth class.The argument invokes Talagrand’s inequality and an adaptation of Györfi et al.’s empirical-process proof strategy.
8. Proofs.: The stability analysis begins with zero instability at bandwidth zero and uses compactness to control behavior at sufficiently large bandwidths.The proof states Ξ(0) = 0 and notes a simplification when h is at least the support diameter.
8. Proofs.: A geometric boundary condition yields a positive ε(ρ,τ) under conditions (C2) and (G).This is stated as Lemma 19’s conclusion.

APPENDIX: THE GEOMETRIC DENSITY

The appendix defines a geometric density for mixtures supported on disjoint compact rectifiable sets of possibly different dimensions. This density can be infinite on lower-dimensional components, but its level sets provide the object used for clustering.

APPENDIX: THE GEOMETRIC DENSITY: Hausdorff measure and rectifiability provide the geometric framework for describing lower-dimensional supports embedded in R^d.The appendix notes that lower-dimensional rectifiable sets can be represented almost everywhere as unions of C1 embedded submanifolds.
APPENDIX: THE GEOMETRIC DENSITY: The model assumes a finite mixture of probability measures on disjoint compact connected supports with possibly different integral Hausdorff dimensions.Each component is a rectifiable Radon measure, and the number, supports, dimensions, and mixing probabilities are not assumed known.
APPENDIX: THE GEOMETRIC DENSITY: The geometric density is infinite almost everywhere on lower-dimensional support components and finite on full-dimensional components.The appendix states these as the two principal cases in Proposition 20.
APPENDIX: THE GEOMETRIC DENSITY: The geometric density is zero outside the support, while the set where it is infinite has zero Lebesgue measure.These properties are listed alongside the dimension-dependent density behavior.
APPENDIX: THE GEOMETRIC DENSITY: For clustering, the relevant task is estimating the geometric-density level sets rather than the mixture-component densities.The appendix explicitly separates the geometric density from the mixture densities for this purpose.