On clusterings-good, bad and spectral
2002
374 citations
Abstract
We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results regarding the quality of the clustering found by a popular spectral algorithm. One proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.
Keywords
Cluster analysisMeasure (data warehouse)HeuristicComputer scienceSpectral clusteringSimple (philosophy)Quality (philosophy)AlgorithmArtificial intelligenceMathematicsData mining
Affiliated Institutions
Related Publications
On clusterings
We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is sh...
The Effectiveness of Lloyd-Type Methods for the k-Means Problem
We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitio...
Objective Criteria for the Evaluation of Clustering Methods
Abstract Many intuitively appealing methods have been suggested for clustering data, however, interpretation of their results has been hindered by the lack of objective criteria...
A Convergence Theorem for the Fuzzy ISODATA Clustering Algorithms
In this paper the convergence of a class of clustering procedures, popularly known as the fuzzy ISODATA algorithms, is established. The theory of Zangwill is used to prove that ...
How fast is the k-means method?
We present polynomial upper and lower bounds on the number of iterations performed by the k-means method (a.k.a. Lloyd's method) for k-means clustering. Our upper bounds are pol...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 367-377
- Citations
- 374
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
374
OpenAlex
Cite This
Ramachandran Kannan,
S. Vempala,
A. Veta
(2002).
On clusterings-good, bad and spectral.
, 367-377.
https://doi.org/10.1109/sfcs.2000.892125
Identifiers
- DOI
- 10.1109/sfcs.2000.892125