Selection of <i>K</i> in <i>K</i> -means clustering
Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering SciencePublished 1 January 2005
Duc Truong Pham, Stefan Dimov, Cuong Duc Nguyen
Citations596
SJR quartileQ2
SJR score0.44
SNIP0.89
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Existing methods for selecting the number of clusters for the K-means algorithm are reviewed and a new measure to assist the selection is proposed.
Abstract
The K-means algorithm is a popular data-clustering algorithm. However, one of its drawbacks is the requirement for the number of clusters, K, to be specified before the algorithm is applied. This paper first reviews existing methods for selecting the number of clusters for the algorithm. Factors that affect this selection are then discussed and a new measure to assist the selection is proposed. The paper concludes with an analysis of the results of using the proposed measure to determine the number of clusters for the K-means algorithm for different data sets.
Keywords
Computer Science
Choice Reviews OnlineData mining: concepts and techniques
28,877 Citations2012Jiawei Han, Micheline Kamber +1 more
Data mining is the search for new, valuable, and nontrivial information in large volumes of data, a cooperative effort of humans and computers that is possible to put data-mining activities into one of two categories: Predictive data mining, which produces the model of the system described by the given data set, or Descriptive data mining which produces new, nontrivials information based on the available data set.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn efficient k-means clustering algorithm: analysis and implementation
5,568 Citations2002Tapas Kanungo, David M. Mount +4 more
This work presents a simple and efficient implementation of Lloyd's k-means clustering algorithm, which it calls the filtering algorithm, and establishes the practical efficiency of the algorithm's running time.
X-means: Extending K-means with Efficient Estimation of the Number of Clusters
2,162 Citations2000Dan Pelleg, Andrew Moore
A new algorithm is introduced that eeciently, searches the space of cluster locations and number of clusters to optimize the Bayesian Information Criterion (BIC) or the Akaike Information Criteria (AIC) measure.
Scale-Space Theory in Computer Vision
2,148 Citations1994Tony Lindeberg
Refining Initial Points for K-Means Clustering
999 Citations1998Paul S. Bradley, Usama M. Fayyad
A procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution that allows the iterative algorithm to converge to a “better” local minimum.
Pattern Recognition LettersAn empirical comparison of four initialization methods for the K-Means algorithm
859 Citations1999José M. Peña, José A. Lozano +1 more
The results suggest that the Kaufman initialization method induces to the K-Means algorithm a more desirable behaviour with respect to the convergence speed than the random initialization method.
ACM SIGKDD Explorations NewsletterWhy so many clustering algorithms
597 Citations2002Vladimir Estivill‐Castro
It is argued that there are many clustering algorithms, because the notion of "cluster" cannot be precisely defined, and comparisons must take into account a careful understanding of the inductive principles involved.
ACM SIGMOD RecordCluster validity methods
530 Citations2002Maria Halkidi, Yannis Batistakis +1 more
This paper presents a review of the clustering validity and methods based on external and internal criteria and discusses the cluster validity approaches based on internal and external criteria.
Syracuse University Libraries (Syracuse University)An efficient k-means clustering algorithm
493 Citations1997Khaled Alsabti, Sanjay Ranka +1 more
Alternatives to the k-means algorithm that find better clusterings
425 Citations2002Greg Hamerly, Charles Elkan
It is shown that the k-harmonic means method is superior on simple low-dimensional synthetic datasets and image segmentation tasks, and that having a soft membership function is essential for finding high-quality clusterings, but having a non-constant data weight function is useful also.
Convergence Properties of the K-Means Algorithms
388 Citations1994Léon Bottou, Yoshua Bengio
It is shown that the K-Means algorithm actually minimizes the quantization error using the very fast Newton algorithm.
Accelerating exact<i>k</i>-means algorithms with geometric reasoning
377 Citations1999Dan Pelleg, Andrew Moore
New algorithms for the k-means clustering problem are presented that use the kd-tree data structure to reduce the large number of nearest-neighbor queries issued by the traditional algorithm.
Pattern Recognition LettersOn finding the number of clusters
146 Citations1999Ravi Kothari, Dax Pitts
A novel approach to finding the number of clusters in data based on the minimization of a regularized cost function that identifies the neighborhood as a scale parameter and obtains thenumber of cluster centers at varying values of the scale parameter.
Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering ScienceAn Incremental K-means algorithm
90 Citations2004Duc Truong Pham, Stefan Dimov +1 more
An incremental version of the K-means algorithm that is also based on distortion reduction through cluster centre movement but is not so sensitive to inaccuracies in distortion estimation is proposed in this paper.
Neural Processing LettersThe LBG-U Method for Vector Quantization – an Improvement over LBG Inspired from Neural Networks
86 Citations1997Bernd Fritzke
It can be proved that LBG-U terminates in a finite number of steps, and experiments with artificial data demonstrate significant improvements in terms of RMSE over LBG combined with only modestly higher computational costs.
Pattern Recognition LettersNew methods for the initialisation of clusters
80 Citations1996Moh'd B. Al-Daoud, Stuart Roberts
In this article, two initialisation methods are developed that are particularly suited to problems involving very large data sets and good results are obtained.
Data Mining and Knowledge DiscoveryFast and Robust General Purpose Clustering Algorithms
72 Citations2004Vladimir Estivill‐Castro, Jianhua Yang
This work proposes an algorithm that remains very efficient, generally applicable, multidimensional but is more robust to noise and outliers by using medians rather than means as estimators for the centers of clusters.
Lecture notes in computer scienceExtended K-means with an Efficient Estimation of the Number of Clusters
63 Citations2000Tsunenori Ishioka
A non-hierarchal clustering algorithm that can determine the optimal number of clusters by using iterations of k-means and a stopping rule based on BIC and with no prior information about the number of clusters is presented.
Alternatives to the k-means algorithm that find better clusterings
58 Citations2002Greg Hamerly, Charles Elkan
Computers & Mathematics with ApplicationsNumerical studies of MacQueen's k-means algorithm for computing the centroidal voronoi tessellations
23 Citations2002Qiang Du, Tak-Win Wong
A probabilistic algorithm for the computation of the centroidal Voronoi tessellation which is a Voronoa tessellingation of a given set such that the associated generating points are centroids (centers of mass) of the corresponding Vor onoi regions.