PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
January 7, 20076,301 citations

k-means++: the advantages of careful seeding

View Full Paper
DADavid ArthurSVSergei Vassilvitskii

Key Points

  • This research aims to improve the k-means clustering technique by using a randomized seeding method.
  • Augmented standard k-means with a randomized seeding technique.
  • Measured performance based on accuracy and speed improvements.
  • Conducted experiments comparing traditional k-means and the seeded version.
  • The augmented k-means algorithm is O(log k)-competitive with optimal clustering.
  • Significant improvements in speed and accuracy observed across various scenarios.
  • Demonstrated overall better performance compared to traditional k-means.

Abstract

The k-means method is a widely used clustering technique that seeks to minimize the average squared distance between points in the same cluster. Although it offers no accuracy guarantees, its simplicity and speed are very appealing in practice. By augmenting k-means with a simple, randomized seeding technique, we obtain an algorithm that is O(log k)-competitive with the optimal clustering. Experiments show our augmentation improves both the speed and the accuracy of k-means, often quite dramatically. 1

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Arthur et al. (2007) studied this question.

synapsesocial.com/papers/69f946926f4144a51fee6083https://doi.org/10.5555/1283383.1283494
Ask AI
Helpful
Bookmark
Share
View Full Paper