Pattern Recognition · 2019 · 449 citations · 74 references
ComputingComputer ScienceAlgorithmsData MiningMachine LearningCluster DetectionDocument ClusteringPattern RecognitionText ClusteringUnsupervised LearningClusteringHeuristic AlgorithmsInitializationK-means Clustering
In this paper, we study what are the most important factors that deteriorate the performance of the k-means algorithm, and how much this deterioration can be overcome either by using a better initialization technique, or by repeating (restarting) the algorithm. Our main finding is that when the clusters overlap, k-means can be significantly improved using these two tricks. Simple furthest point heuristic (Maxmin) reduces the number of erroneous clusters from 15% to 6%, on average, with our clustering benchmark. Repeating the algorithm 100 times reduces it further down to 1%. This accuracy is more than enough for most pattern recognition applications. However, when the data has well separated clusters, the performance of k-means depends completely on the goodness of the initialization. Therefore, if high clustering accuracy is needed, a better algorithm should be used instead.
74
Least squares quantization in PCM
Sheelagh Lloyd · IEEE Transactions on Information Theory · 1982 · 15.6K citations · Full text
Finding groups in data: an introduction to cluster analysis
Choice Reviews Online · 1991 · 10.6K citations