Clustering Based on Pairwise Distances When the Data is of Mixed Dimensions
Author:
- 17 February 2011
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 57 (3) , 1692-1706
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 some emblematic methods based on pairwise distances: a simple algorithm based on the extraction of connected components in a neighborhood graph; hierarchical clustering with single linkage; and the spectral clustering method of Ng, Jordan, and Weiss. 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 and third 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 51 references indexed in Scilit:
- Foundations of a Multi-way Spectral Clustering Framework for Hybrid Linear ModelingFoundations of Computational Mathematics, 2009
- A survey of kernel and spectral methods for clusteringPattern Recognition, 2008
- A graph-based estimator of the number of clustersESAIM: Probability and Statistics, 2007
- Fast multiscale clustering and manifold identificationPattern Recognition, 2006
- Connect the dots: how many random points can a regular curve pass through?Advances in Applied Probability, 2005
- Performance guarantees for hierarchical clusteringJournal of Computer and System Sciences, 2005
- Detection of non-random patterns in cosmological gravitational clusteringAstronomy & Astrophysics, 2001
- The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1]dAdvances in Applied Probability, 1997
- Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detectionStatistics & Probability Letters, 1997
- Percolation technique for galaxy clusteringThe Astrophysical Journal, 1993