How slow is the k-means method?
By David Arthur, Sergei Vassilvitskii. SCG '06, 2006
416 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition
View Paper: https://www.semanticscholar.org/paper/a68e042d017f075f085b3a72b22829bc2f15082b
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Andrea Vattani
- Xiatian Zhu
- Engin Kirda
- Sergei Vassilvitskii
- Christopher Krügel
- Paolo Milani Comparetti
- David Arthur
- Ravi Kumar
In Computer Vision and Pattern Recognition
- Xiatian Zhu
- Andrea Vattani
- Shaogang Gong
- Sergei Vassilvitskii
- David Arthur
- Ravi Kumar
- Benjamin Moseley
- Bahman Bahmani
Citations in the corpus
- Scalable K-Means++ (2012, methodology): “Therefore, recent work has focused on improving the initialization procedure: deciding on a better way to initialize the clustering dramatically changes the performance of the Lloyd’s iteration, both in terms of quality and convergence properties.”
- Scalable, Behavior-Based Malware Clustering (2009, background): “Unfortunately, there are no guarantees that the value of i is small (in fact, the number of iterations is super-polynomial in n in the worst-case [10]).”
- k-means++: the advantages of careful seeding (2007, methodology): “The convergence time of Lloyd’s method has been the subject of a recent series of papers [2, 4, 8, 14]; in this work we focus on improving its accuracy.”
- Imbalanced Deep Learning by Minority Class Incremental Rectification (2018, background): “an attribute label by k-means, its operation complexity is super-polynomial with the need for at least 2Ω( √ n) (Ω the lower bound complexity) iterations of cluster refinement on n samples [38].”
- k-means Requires Exponentially Many Iterations Even in the Plane (2008, methodology): “INTRODUCTION The k-means method is one of the most widely used algorithms for geometric clustering.”
- BICO: BIRCH Meets Coresets for k-Means Clustering (2013, neutral): “Then, it runs k-means++ [5] on S.”
- Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms (2018, background): “Based on results for k -means, we must assume that the worst case is superpolynomial like k - means (Arthur and Vassilvitskii, 2006), albeit in practice a “few” iterations are usually enough.”