An accelerated K-means clustering algorithm using selection and erasure rules

Suiang Shyan Lee*, Chih_Ching Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


The K-means method is a well-known clustering algorithm with an extensive range of applications, such as biological classification, disease analysis, data mining, and image compression. However, the plain K-means method is not fast when the number of clusters or the number of data points becomes large. A modified K-means algorithm was presented by Fahim et al. (2006). The modified algorithm produced clusters whose mean square error was very similar to that of the plain K-means, but the execution time was shorter. In this study, we try to further increase its speed. There are two rules in our method: a selection rule, used to acquire a good candidate as the initial center to be checked, and an erasure rule, used to delete one or many unqualified centers each time a specified condition is satisfied. Our clustering results are identical to those of Fahim et al. (2006). However, our method further cuts computation time when the number of clusters increases. The mathematical reasoning used in our design is included.

Original languageEnglish
Pages (from-to)761-768
Number of pages8
JournalJournal of Zhejiang University: Science C
Issue number10
StatePublished - 1 Oct 2012


  • Acceleration
  • Erasure
  • K-means clustering
  • Selection
  • Vector quantization

Fingerprint Dive into the research topics of 'An accelerated K-means clustering algorithm using selection and erasure rules'. Together they form a unique fingerprint.

Cite this