Clustering Based on Pairwise Distances When the Data is of Mixed Dimensions
Preprint
Abstract
In the context of clustering, we consider a generative model in a Euclidean ambient space with clusters of different shapes, dimensions, sizes and densities. In an asymptotic setting where the number of points becomes large, we obtain theoretical guaranties for a few emblematic methods based on pairwise distances: a simple algorithm based on the extraction of connected components in a neighborhood graph; the spectral clustering method of Ng, Jordan and Weiss; and hierarchical clustering with single linkage. The methods are shown to enjoy some near-optimal properties in terms of separation between clusters and robustness to outliers. The local scaling method of Zelnik-Manor and Perona is shown to lead to a near-optimal choice for the scale in the first two methods. We also provide a lower bound on the spectral gap to consistently choose the correct number of clusters in the spectral method.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear ModelingFoundations of Computational Mathematics, 2009
- Spectral Curvature Clustering (SCC)International Journal of Computer Vision, 2008
- Approximate range searching in higher dimensionComputational Geometry, 2008
- A survey of kernel and spectral methods for clusteringPattern Recognition, 2008
- A graph-based estimator of the number of clustersESAIM: Probability and Statistics, 2007
- Performance guarantees for hierarchical clusteringJournal of Computer and System Sciences, 2005
- On clusterings-good, bad and spectral2002
- Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning treesBioinformatics, 2002
- Minimax nonparametric classification .I. Rates of convergenceIEEE Transactions on Information Theory, 1999
- Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detectionStatistics & Probability Letters, 1997