K-means properties on six clustering benchmark datasets
Applied IntelligencePublished 26 July 2018
Pasi Fränti, Sami Sieranoja
Citations511
SJR quartileQ2
SJR score0.93
SNIP1.21
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
The results show that overlap is critical, and that k-means starts to work effectively when the overlap reaches 4% level.
Abstract
This paper has two contributions. First, we introduce a clustering basic benchmark. Second, we study the performance of k-means using this benchmark. Specifically, we measure how the performance depends on four factors: (1) overlap of clusters, (2) number of clusters, (3) dimensionality, and (4) unbalance of cluster sizes. The results show that overlap is critical, and that k-means starts to work effectively when the overlap reaches 4% level.
Keywords
Computer Science
IEEE Transactions on Information TheoryLeast squares quantization in PCM
15,578 Citations1982Sheelagh Lloyd
The corresponding result for any finite number of quanta is derived; that is, necessary conditions are found that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Proceedings of the National Academy of SciencesAn index to quantify an individual's scientific research output
11,535 Citations2005J. E. Hirsch
The index hbar, defined as the number of papers of an individual that have citation count larger than or equal to the citation count of all coauthors of each paper, is proposed as a useful index to characterize the scientific output of a researcher that takes into account the effect of multiple authorship.
k-means++: the advantages of careful seeding
6,303 Citations2007David Arthur, Sergei Vassilvitskii
By augmenting k-means with a very simple, randomized seeding technique, this work obtains an algorithm that is Θ(logk)-competitive with the optimal clustering.
Lecture notes in computer scienceWhen Is “Nearest Neighbor” Meaningful?
2,297 Citations1999Kevin Beyer, Jonathan Goldstein +2 more
The effect of dimensionality on the "nearest neighbor" problem is explored, and it is shown that under a broad set of conditions, as dimensionality increases, the Distance to the nearest data point approaches the distance to the farthest data point.
Journal of the Royal Statistical Society Series A (General)Adaptive Control Processes: A Guided Tour.
2,218 Citations1962E. S. Page, Richard Bellman
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.
Lecture notes in computer scienceOn the Surprising Behavior of Distance Metrics in High Dimensional Space
2,058 Citations2001Charų C. Aggarwal, Alexander Hinneburg +1 more
This paper examines the behavior of the commonly used L k norm and shows that the problem of meaningfulness in high dimensionality is sensitive to the value of k, which means that the Manhattan distance metric is consistently more preferable than the Euclidean distance metric for high dimensional data mining applications.
Theoretical Computer ScienceClustering to minimize the maximum intercluster distance
1,725 Citations1985Teofilo F. Gonzalez
An O(kn) approximation algorithm that guarantees solutions with an objective function value within two times the optimal solution value is presented and it is shown that this approximation algorithm succeeds as long as the set of points satisfies the triangular inequality.
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Genetic K-means algorithm
1,712 Citations1999K. Krishna, M. Narasimha Murty
A novel hybrid genetic algorithm that finds a globally optimal partition of a given data into a specified number of clusters using a classical gradient descent algorithm used in clustering, viz.
Journal of Machine Learning ResearchSupport vector clustering
1,356 Citations2002Asa Ben‐Hur, D. Horn +2 more
A novel clustering method using the approach of support vector machines, where data points are mapped by means of a Gaussian kernel to a high dimensional feature space, where the minimal enclosing sphere is searched for.
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.
Systems Research and Behavioral ScienceA clustering technique for summarizing multivariate data
908 Citations1967Geoffrey H. Ball, D.J. Hall
A practical computing method termed ISODATA, which finds the cluster structure of such data, is described and provides a fit to the data of a set of cluster centers that tends to minimize the sum of the squared distances of each data point from its closest cluster center.
Data Mining and Knowledge DiscoveryBIRCH: A New Data Clustering Algorithm and Its Applications
882 Citations1997Tian Zhang, Raghu Ramakrishnan +1 more
An efficient and scalable data clustering method is proposed, based on a new in-memory data structure called CF-tree, which serves as an in- memory summary of the data distribution, and implemented in a system called BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies), and compared with other available methods.
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.
The Challenges of Clustering High Dimensional Data
503 Citations2004Michael Steinbach, Levent Ertöz +1 more
This chapter provides a short introduction to cluster analysis, and presents a brief overview of several recent techniques, including a more detailed description of recent work of recent which uses a concept-based clustering approach.
A local search approximation algorithm for k-means clustering
497 Citations2002Tapas Kanungo, David M. Mount +4 more
This work considers the question of whether there exists a simple and practical approximation algorithm for k-means clustering, and presents a local improvement heuristic based on swapping centers in and out that yields a (9+ε)-approximation algorithm.
Fast approximate spectral clustering
483 Citations2009Donghui Yan, Ling Huang +1 more
This work develops a general framework for fast approximate spectral clustering in which a distortion-minimizing local transformation is first applied to the data, and develops two concrete instances of this framework, one based on local k-means clustering (KASP) and onebased on random projection trees (RASP).
KoBSON-skop - NasiuFPHubs in Space: Popular Nearest Neighbors in High-Dimensional Data
460 Citations2010Miloš Radovanović, Αλέξανδρος Νανόπουλος +1 more
Pattern RecognitionIterative shrinking method for clustering problems
343 Citations2005Pasi Fränti, Olli Virmajoki
This work proposes an alternative to the merge-based approach to clustering by removing the clusters iteratively one by one until the desired number of clusters is reached, and applies local optimization strategy by always removing the cluster that increases the distortion the least.
KOPS (University of Konstanz)Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering
336 Citations1999Alexander Hinneburg, Daniel A. Keim
A new clustering technique called OptiGrid is developed which is based on constructing an optimal grid-partitioning of the data and has a mathematical basis which is by far more e ectiveness andiency than existing clustering algorithms for highdimensional data.
Machine LearningLetter Recognition Using Holland-Style Adaptive Classifiers
326 Citations1991Peter W. Frey, David J. Slate
This research focused on machine induction techniques for generating IF-THEN classifiers in which the IF part was a list of values for each of the 16 attributes and the THEN part was the correct category, i.e., one of the 26 letters of the alphabet.
Journal of ClassificationInitializing K-means Batch Clustering: A Critical Evaluation of Several Techniques
313 Citations2007Douglas Steinley, Michael J. Brusco
This paper evaluates 12 procedures proposed in the literature and provides recommendations for best practices for K-means clustering and concludes that the choice of starting partitions is all the more important.
IEEE Transactions on Pattern Analysis and Machine IntelligenceFast Agglomerative Clustering Using a k-Nearest Neighbor Graph
308 Citations2006Pasi Fränti, Olli Virmajoki +1 more
A fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations and a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search.
Tutorials in Quantitative Methods for PsychologyThe k-means clustering technique: General considerations and implementation in Mathematica
300 Citations2013Laurence Morissette, Sylvain Chartier
This tutorial presents a simple yet powerful data clustering technique, through three different algorithms: the Forgy/Lloyd, algorithm, the MacQueen algorithm and the Hartigan & Wong algorithm, and an implementation in Mathematica.
Computational GeometryA local search approximation algorithm for k-means clustering
291 Citations2004Tapas Kanungo, David M. Mount +4 more
Theoretical Computer ScienceThe planar<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-means problem is NP-hard
281 Citations2010Meena Mahajan, Prajakta Nimbhorkar +1 more
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)K-Means Clustering Versus Validation Measures: A Data-Distribution Perspective
276 Citations2008Hui Xiong, Junjie Wu +1 more
This paper provides a formal and organized study of the effect of skewed data distributions on K-means clustering and provides the coefficient of variation (CV) as a necessary criterion to validate the clustering results.
Psychological MethodsLocal Optima in K-Means Clustering: What You Don't Know May Hurt You.
263 Citations2003Douglas Steinley
The results suggest the need for some strategy to study the local optima problem for a specific data set or to identify methods for finding "good" starting values that might lead to the best solutions possible.
Data Mining and Knowledge DiscoveryLocally adaptive metrics for clustering high dimensional data
238 Citations2007Carlotta Domeniconi, Dimitrios Gunopulos +4 more
An algorithm is introduced that discovers clusters in subspaces spanned by different combinations of dimensions via local weightings of features, whose values capture the relevance of features within the corresponding cluster.
IEEE Transactions on Knowledge and Data EngineeringSet Matching Measures for External Cluster Validity
187 Citations2016Mohammad Rezaei, Pasi Fränti
A new index called Pair Sets Index (PSI) is introduced based on the analytical comparisons of popular external indexes evaluated and compared when applied to clusterings of different data size, cluster size, and number of clusters.
Pattern Recognition LettersA new algorithm for initial cluster centers in k-means algorithm
186 Citations2011Murat Erişoğlu, Nazif Çalış +1 more
An algorithm to compute initial cluster centers for k-means algorithm is proposed and is applied to several different datasets in different dimension for illustrative purposes and it is observed that the newly proposed algorithm has good performance.
Data & Knowledge EngineeringWB-index: A sum-of-squares based index for cluster validity
167 Citations2014Qinpei Zhao, Pasi Fränti
A more thorough comparison of 12 internal indices is conducted and a summary of the experimental performance of different indices is provided and the sum-of-squares based indices are introduced into automatic keyword categorization, where the indices are specially defined for determining the number of clusters.
The hardness of k-means clustering
166 Citations2008Sanjoy Dasgupta
A discriminative framework for clustering via similarity functions
162 Citations2008Maria-Florina Balcan, Avrim Blum +1 more
A theoretical framework that can be viewed as an analog of the PAC learning model for clustering, where the object of study is a class of (concept, similarity function) pairs, or equivalently, a property the similarity function should satisfy with respect to the ground truth clustering is developed.
Journal of Computational and Graphical StatisticsSimulating Data to Study Performance of Finite Mixture Modeling and Clustering Algorithms
157 Citations2010Ranjan Maitra, Volodymyr Melnykov
The suggested approach involves derivation of and calculation of the exact overlap between every cluster pair, measured in terms of their total probability of misclassification, and then guided simulation of Gaussian components satisfying prespecified overlap characteristics.
IEEE Transactions on Knowledge and Data EngineeringThe Role of Hubness in Clustering High-Dimensional Data
140 Citations2013Nenad Tomašev, Miloš Radovanović +2 more
This paper shows that hubness, i.e., the tendency of high-dimensional data to contain points (hubs) that frequently occur in k-nearest-neighbor lists of other points, can be successfully exploited in clustering, and proposes several hubness-based clustering algorithms.
Plant Leaf Classification using Probabilistic Integration of Shape, Texture and Margin Features
139 Citations2013Charles D. Mallah, James Cope +1 more
This paper introduces a new data set of sixteen samples each of one-hundred plant species; and describes a method designed to work in conditions of small training set size and possibly incomplete extraction of features.
Applied IntelligenceFeature clustering based support vector machine recursive feature elimination for gene selection
135 Citations2017Xiaojuan Huang, Li Zhang +3 more
Experiments on seven public gene expression datasets show that FCSVM-RFE can achieve a better classification performance and lower computational complexity when compared with the state-the-art-of methods, such as SVM- RFE.
Pattern RecognitionCentroid index: Cluster level similarity measure
121 Citations2014Pasi Fränti, Mohammad Rezaei +1 more
This paper introduces a cluster level index called centroid index, which is intuitive, simple to implement, fast to compute and applicable in case of model mismatch as well as to other clustering models beyond the centroid-based k-means.
Clustering: science or art?
120 Citations2011Ulrike von Luxburg, Robert C. Williamson +1 more
It is argued that it will be useful to build a "taxonomy of clustering problems" to identify clustering applications which can be treated in a unified way and that such an effort will be more fruitful than attempting the impossible--developing "optimal" domain-independent clustering algorithms or even classifying clusteringgorithms in terms of how they work.
IEEE Transactions on Fuzzy SystemsThe $K$-Means-Type Algorithms Versus Imbalanced Data Distributions
109 Citations2012Jiye Liang, Liang Bai +2 more
A multicenter clustering algorithm in which multicenters are used to represent each cluster, instead of one single center, is proposed in order to prevent the effect of the “uniform effect” in clustering balanced and imbalanced data.
Pattern Analysis and ApplicationsRandomised Local Search Algorithm for the Clustering Problem
109 Citations2000Pasi Fränti, Juha Kivijärvi
This work introduces a new randomised local search algorithm for the clustering problem that is easy to implement, sufficiently fast, and competitive with the best clustering methods.
ACM Transactions on Modeling and Computer SimulationEfficient and portable combined Tausworthe random number generators
93 Citations1991Shu Tezuka, Pierre L’Ecuyer
This paper proposes three combined Tausworthe random number generators with period length about 1018, whose k-distribution properties are good and which can be implemented in a portable way by applying a battery of statistical tests to these generators.
Journal Of Big DataEfficiency of random swap clustering
82 Citations2018Pasi Fränti
The main results are that the expected time complexity of the random swap algorithm has (1) linear dependency on the number of data vectors, (2) quadratic dependency onThe number of clusters, and (3) inverse dependent on the size of neighborhood.
Knowledge-Based SystemsExploring the uniform effect of FCM clustering: A data distribution perspective
76 Citations2016Kaile Zhou, Shanlin Yang
An organized study of FCM clustering from the perspective of data distribution and finds that FCM has the same uniform effect as K-means, which tends to produce clusters of relatively uniform sizes.
Psychological MethodsThe variance of the adjusted Rand index.
75 Citations2016Douglas Steinley, Michael J. Brusco +1 more
The variance of the adjusted Rand index is provided and it is shown that a normal approximation is appropriate across a wide range of sample sizes and varying numbers of clusters and that confidence intervals based on the normal distribution have desirable levels of coverage and accuracy.
Pattern Recognition LettersGenetic algorithm with deterministic crossover for vector quantization
72 Citations2000Pasi Fränti
A new deterministic crossover method based on the pairwise nearest neighbor method is introduced that shows that high quality codebooks can be obtained within a few minutes instead of several hours as required by the previous GA-based methods.
Leibniz-Zentrum für Informatik (Schloss Dagstuhl)The Hardness of Approximation of Euclidean k-means
70 Citations2015Pranjal Awasthi, Moses Charikar +2 more
The first hardness of approximation for the Euclidean $k-means problem is provided via an efficient reduction from the vertex cover problem on triangle-free graphs: given a triangle- free graph, the goal is to choose the fewest number of vertices which are incident on all the edges.
Journal of Computer ScienceAn Efficient Approach for Computing Silhouette Coefficients
64 Citations2008Moh’d Belal Al- Zoubi, Mohammed Al-Rawi
A proposed approach to compute the silhouette coefficient quickly was presented, based on decreasing the number of addition operations when computing distances and the results were efficient and more than 50% of the CPU time was achieved when applied to different data sets.
Pattern Recognition LettersComparison of clustering methods: A case study of text-independent speaker modeling
63 Citations2011Tomi Kinnunen, Ilja Sidoroff +2 more
Experiments indicate clustering is not a critical task in speaker recognition and the choice of the algorithm should be based on computational complexity and simplicity of the implementation.
Lecture notes in computer scienceA Probabilistic Spell for the Curse of Dimensionality
54 Citations2001Edgar Chávez, Gonzalo Navarro
This paper presents a general probabilistic framework based on stretching the triangle inequality, whose direct effect is a reduction of the effective search radius, and applies it to a particular class of indexing algorithms.
Lecture notes in computer scienceLocally Scaled Density Based Clustering
52 Citations2007Ergun Biçici, Deniz Yüret
The focus of this paper is to automate the process of clustering by making use of the local density information for arbitrarily sized, shaped, located, and numbered clusters.
Proceedings of the AAAI Conference on Artificial IntelligenceWeighted Clustering
48 Citations2021Margareta Ackerman, Shai Ben-David +2 more
This work conducts the first extensive theoretical analysis on the influence of weighted data on standard clustering algorithms in both the partitional and hierarchical settings, characterizing the conditions under which algorithms react to weights.
Dynamic local search for clustering with unknown number of clusters
30 Citations2003Ismo Kärkkäinen, Pasi Fränti
This work proposes a new dynamic local search that solves the number and location of the clusters jointly and finds the results 30 times faster than the brute force approach.
Lecture notes in computer scienceRandom Projection for k-means Clustering
11 Citations2018Sami Sieranoja, Pasi Fränti
This work studies how much the k-means can be improved if initialized by random projections and proposes simple projective indicator that predicts when the projection-heuristic is expected to work well.
AlgorithmsA PTAS For The k-Consensus Structures Problem Under Squared Euclidean Distance
2 Citations2008Shuai Cheng Li, Yen Kaow Ng +1 more
A polynomial-time approximation scheme (PTAS) for the basic clustering problem that has uses in bioinformatics is shown through a simple sampling strategy.