kmeans clustering
Part of a series on 
Machine learning and data mining 

kmeans clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster centers or cluster centroid), serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells. kmeans clustering minimizes withincluster variances (squared Euclidean distances), but not regular Euclidean distances, which would be the more difficult Weber problem: the mean optimizes squared errors, whereas only the geometric median minimizes Euclidean distances. For instance, better Euclidean solutions can be found using kmedians and kmedoids.
The problem is computationally difficult (NPhard); however, efficient heuristic algorithms converge quickly to a local optimum. These are usually similar to the expectation–maximization algorithm for mixtures of Gaussian distributions via an iterative refinement approach employed by both kmeans and Gaussian mixture modeling. They both use cluster centers to model the data; however, kmeans clustering tends to find clusters of comparable spatial extent, while the Gaussian mixture model allows clusters to have different shapes.
The unsupervised kmeans algorithm has a loose relationship to the knearest neighbor classifier, a popular supervised machine learning technique for classification that is often confused with kmeans due to the name. Applying the 1nearest neighbor classifier to the cluster centers obtained by kmeans classifies new data into the existing clusters. This is known as nearest centroid classifier or Rocchio algorithm.
Description[edit]
Given a set of observations (x_{1}, x_{2}, ..., x_{n}), where each observation is a dimensional real vector, kmeans clustering aims to partition the n observations into k (≤ n) sets S = {S_{1}, S_{2}, ..., S_{k}} so as to minimize the withincluster sum of squares (WCSS) (i.e. variance). Formally, the objective is to find:
History[edit]
The term "kmeans" was first used by James MacQueen in 1967,^{[2]} though the idea goes back to Hugo Steinhaus in 1956.^{[3]} The standard algorithm was first proposed by Stuart Lloyd of Bell Labs in 1957 as a technique for pulsecode modulation, although it was not published as a journal article until 1982.^{[4]} In 1965, Edward W. Forgy published essentially the same method, which is why it is sometimes referred to as the Lloyd–Forgy algorithm.^{[5]}
Algorithms[edit]
Standard algorithm (naive kmeans)[edit]
The most common algorithm uses an iterative refinement technique. Due to its ubiquity, it is often called "the kmeans algorithm"; it is also referred to as Lloyd's algorithm, particularly in the computer science community. It is sometimes also referred to as "naïve kmeans", because there exist much faster alternatives.^{[6]}
Given an initial set of k means m_{1}^{(1)}, ..., m_{k}^{(1)} (see below), the algorithm proceeds by alternating between two steps:^{[7]}
 Assignment step: Assign each observation to the cluster with the nearest mean: that with the least squared Euclidean distance.^{[8]} (Mathematically, this means partitioning the observations according to the Voronoi diagram generated by the means.) where each is assigned to exactly one , even if it could be assigned to two or more of them.
 Update step: Recalculate means (centroids) for observations assigned to each cluster.
The objective function in kmeans is the WCSS (within cluster sum of squares). After each iteration, the WCSS decreases and so we have a nonnegative monotonically decreasing sequence. This guarantees that the kmeans always converges, but not necessarily to the global optimum.
The algorithm has converged when the assignments no longer change or equivalently, when the WCSS has become stable. The algorithm is not guaranteed to find the optimum.^{[9]}
The algorithm is often presented as assigning objects to the nearest cluster by distance. Using a different distance function other than (squared) Euclidean distance may prevent the algorithm from converging. Various modifications of kmeans such as spherical kmeans and kmedoids have been proposed to allow using other distance measures.
 Pseudocode
The below pseudocode outlines the implementation of the standard kmeans clustering algorithm. Initialization of centroids, distance metric between points and centroids, and the calculation of new centroids are design choices and will vary with different implementations. In this example pseudocode, argmin is used to find the index of the minimum value.
def k_means_cluster(k, points):
# Initialization: choose k centroids (Forgy, Random Partition, etc.)
centroids = [c1, c2, ..., ck]
# Initialize clusters list
clusters = [[] for _ in range(k)]
# Loop until convergence
converged = false
while not converged:
# Clear previous clusters
clusters = [[] for _ in range(k)]
# Assign each point to the "closest" centroid
for point in points:
distances_to_each_centroid = [distance(point, centroid) for centroid in centroids]
cluster_assignment = argmin(distances_to_each_centroid)
clusters[cluster_assignment].append(point)
# Calculate new centroids
# (the standard implementation uses the mean of all points in a
# cluster to determine the new centroid)
new_centroids = [calculate_centroid(cluster) for cluster in clusters]
converged = (new_centroids == centroids)
centroids = new_centroids
if converged:
return clusters
Initialization methods[edit]
Commonly used initialization methods are Forgy and Random Partition.^{[10]} The Forgy method randomly chooses k observations from the dataset and uses these as the initial means. The Random Partition method first randomly assigns a cluster to each observation and then proceeds to the update step, thus computing the initial mean to be the centroid of the cluster's randomly assigned points. The Forgy method tends to spread the initial means out, while Random Partition places all of them close to the center of the data set. According to Hamerly et al.,^{[10]} the Random Partition method is generally preferable for algorithms such as the kharmonic means and fuzzy kmeans. For expectation maximization and standard kmeans algorithms, the Forgy method of initialization is preferable. A comprehensive study by Celebi et al.,^{[11]} however, found that popular initialization methods such as Forgy, Random Partition, and Maximin often perform poorly, whereas Bradley and Fayyad's approach^{[12]} performs "consistently" in "the best group" and kmeans++ performs "generally well".

1. k initial "means" (in this case k=3) are randomly generated within the data domain (shown in color).

2. k clusters are created by associating every observation with the nearest mean. The partitions here represent the Voronoi diagram generated by the means.

3. The centroid of each of the k clusters becomes the new mean.

4. Steps 2 and 3 are repeated until convergence has been reached.
The algorithm does not guarantee convergence to the global optimum. The result may depend on the initial clusters. As the algorithm is usually fast, it is common to run it multiple times with different starting conditions. However, worstcase performance can be slow: in particular certain point sets, even in two dimensions, converge in exponential time, that is 2^{Ω(n)}.^{[13]} These point sets do not seem to arise in practice: this is corroborated by the fact that the smoothed running time of kmeans is polynomial.^{[14]}
The "assignment" step is referred to as the "expectation step", while the "update step" is a maximization step, making this algorithm a variant of the generalized expectation–maximization algorithm.
Complexity[edit]
Finding the optimal solution to the kmeans clustering problem for observations in d dimensions is:
 NPhard in general Euclidean space (of d dimensions) even for two clusters,^{[15]}^{[16]}
 NPhard for a general number of clusters k even in the plane,^{[17]}
 if k and d (the dimension) are fixed, the problem can be exactly solved in time , where n is the number of entities to be clustered.^{[18]}
Thus, a variety of heuristic algorithms such as Lloyd's algorithm given above are generally used.
The running time of Lloyd's algorithm (and most variants) is ,^{[9]}^{[19]} where:
 n is the number of ddimensional vectors (to be clustered)
 k the number of clusters
 i the number of iterations needed until convergence.
On data that does have a clustering structure, the number of iterations until convergence is often small, and results only improve slightly after the first dozen iterations. Lloyd's algorithm is therefore often considered to be of "linear" complexity in practice, although it is in the worst case superpolynomial when performed until convergence.^{[20]}
 In the worstcase, Lloyd's algorithm needs iterations, so that the worstcase complexity of Lloyd's algorithm is superpolynomial.^{[20]}
 Lloyd's kmeans algorithm has polynomial smoothed running time. It is shown that^{[14]} for arbitrary set of n points in , if each point is independently perturbed by a normal distribution with mean 0 and variance , then the expected running time of kmeans algorithm is bounded by , which is a polynomial in n, k, d and .
 Better bounds are proven for simple cases. For example, it is shown that the running time of kmeans algorithm is bounded by for n points in an integer lattice .^{[21]}
Lloyd's algorithm is the standard approach for this problem. However, it spends a lot of processing time computing the distances between each of the k cluster centers and the n data points. Since points usually stay in the same clusters after a few iterations, much of this work is unnecessary, making the naïve implementation very inefficient. Some implementations use caching and the triangle inequality in order to create bounds and accelerate Lloyd's algorithm.^{[9]}^{[22]}^{[23]}^{[24]}^{[25]}
Optimal number of clusters[edit]
Finding the optimal number of clusters (k) for kmeans clustering is a crucial step to ensure that the clustering results are meaningful and useful.^{[26]} Several techniques are available to determine a suitable number of clusters. Here are some of commonly used methods:
 Elbow method (clustering): This method involves plotting the explained variation as a function of the number of clusters, and picking the elbow of the curve as the number of clusters to use.^{[27]} However, the notion of an "elbow" is not welldefined and this is known to be not reliable.^{[28]}
 Silhouette (clustering): Silhouette analysis measures the quality of clustering and provides an insight into the separation distance between the resulting clusters.^{[29]} A higher silhouette score indicates that the object is well matched to its own cluster and poorly matched to neighboring clusters.
 Gap statistic: The Gap Statistic compares the total within intracluster variation for different values of k with their expected values under null reference distribution of the data.^{[30]} The optimal k is the value that yields the largest gap statistic.
 Davies–Bouldin index: The DaviesBouldin index is a measure of the how much separation there is between clusters.^{[31]} Lower values of the DaviesBouldin index indicate a model with better separation.
 CalinskiHarabasz index: This Index evaluates clusters based on their compactness and separation. The index is calculated using the ratio of betweencluster variance to withincluster variance, with higher values indicate betterdefined clusters.^{[32]}
 Rand index: It calculates the proportion of agreement between the two clusters, considering both the pairs of elements that are correctly assigned to the same or different clusters.^{[33]} Higher values indicate greater similarity and better clustering quality. To provide a more accurate measure, the Adjusted Rand Index (ARI), introduced by Hubert and Arabie in 1985, corrects the Rand Index by adjusting for the expected similarity of all pairings due to chance.^{[34]}
Variations[edit]
 Jenks natural breaks optimization: kmeans applied to univariate data
 kmedians clustering uses the median in each dimension instead of the mean, and this way minimizes norm (Taxicab geometry).
 kmedoids (also: Partitioning Around Medoids, PAM) uses the medoid instead of the mean, and this way minimizes the sum of distances for arbitrary distance functions.
 Fuzzy CMeans Clustering is a soft version of kmeans, where each data point has a fuzzy degree of belonging to each cluster.
 Gaussian mixture models trained with expectation–maximization algorithm (EM algorithm) maintains probabilistic assignments to clusters, instead of deterministic assignments, and multivariate Gaussian distributions instead of means.
 kmeans++ chooses initial centers in a way that gives a provable upper bound on the WCSS objective.
 The filtering algorithm uses kd trees to speed up each kmeans step.^{[35]}
 Some methods attempt to speed up each kmeans step using the triangle inequality.^{[22]}^{[23]}^{[24]}^{[36]}^{[25]}
 Escape local optima by swapping points between clusters.^{[9]}
 The Spherical kmeans clustering algorithm is suitable for textual data.^{[37]}
 Hierarchical variants such as Bisecting kmeans,^{[38]} Xmeans clustering^{[39]} and Gmeans clustering^{[40]} repeatedly split clusters to build a hierarchy, and can also try to automatically determine the optimal number of clusters in a dataset.
 Internal cluster evaluation measures such as cluster silhouette can be helpful at determining the number of clusters.
 Minkowski weighted kmeans automatically calculates cluster specific feature weights, supporting the intuitive idea that a feature may have different degrees of relevance at different features.^{[41]} These weights can also be used to rescale a given data set, increasing the likelihood of a cluster validity index to be optimized at the expected number of clusters.^{[42]}
 Minibatch kmeans: kmeans variation using "mini batch" samples for data sets that do not fit into memory.^{[43]}
 Otsu's method
Hartigan–Wong method[edit]
Hartigan and Wong's method^{[9]} provides a variation of kmeans algorithm which progresses towards a local minimum of the minimum sumofsquares problem with different solution updates. The method is a local search that iteratively attempts to relocate a sample into a different cluster as long as this process improves the objective function. When no sample can be relocated into a different cluster with an improvement of the objective, the method stops (in a local minimum). In a similar way as the classical kmeans, the approach remains a heuristic since it does not necessarily guarantee that the final solution is globally optimum.
Let be the individual cost of defined by , with the center of the cluster.
 Assignment step
 Hartigan and Wong's method starts by partitioning the points into random clusters .
 Update step
 Next it determines the and for which the following function reaches a maximum For the that reach this maximum, moves from the cluster to the cluster .
 Termination
 The algorithm terminates once is less than zero for all .
Different move acceptance strategies can be used. In a firstimprovement strategy, any improving relocation can be applied, whereas in a bestimprovement strategy, all possible relocations are iteratively tested and only the best is applied at each iteration. The former approach favors speed, whether the latter approach generally favors solution quality at the expense of additional computational time. The function used to calculate the result of a relocation can also be efficiently evaluated by using equality^{[44]}
Global optimization and metaheuristics[edit]
The classical kmeans algorithm and its variations are known to only converge to local minima of the minimumsumofsquares clustering problem defined as
Discussion[edit]
Three key features of kmeans that make it efficient are often regarded as its biggest drawbacks:
 Euclidean distance is used as a metric and variance is used as a measure of cluster scatter.
 The number of clusters k is an input parameter: an inappropriate choice of k may yield poor results. That is why, when performing kmeans, it is important to run diagnostic checks for determining the number of clusters in the data set.
 Convergence to a local minimum may produce counterintuitive ("wrong") results (see example in Fig.).
A key limitation of kmeans is its cluster model. The concept is based on spherical clusters that are separable so that the mean converges towards the cluster center. The clusters are expected to be of similar size, so that the assignment to the nearest cluster center is the correct assignment. When for example applying kmeans with a value of onto the wellknown Iris flower data set, the result often fails to separate the three Iris species contained in the data set. With , the two visible clusters (one containing two species) will be discovered, whereas with one of the two clusters will be split into two even parts. In fact, is more appropriate for this data set, despite the data set's containing 3 classes. As with any other clustering algorithm, the kmeans result makes assumptions that the data satisfy certain criteria. It works well on some data sets, and fails on others.
The result of kmeans can be seen as the Voronoi cells of the cluster means. Since data is split halfway between cluster means, this can lead to suboptimal splits as can be seen in the "mouse" example. The Gaussian models used by the expectation–maximization algorithm (arguably a generalization of kmeans) are more flexible by having both variances and covariances. The EM result is thus able to accommodate clusters of variable size much better than kmeans as well as correlated clusters (not in this example). In counterpart, EM requires the optimization of a larger number of free parameters and poses some methodological issues due to vanishing clusters or badlyconditioned covariance matrices. kmeans is closely related to nonparametric Bayesian modeling.^{[52]}
Applications[edit]
kmeans clustering is rather easy to apply to even large data sets, particularly when using heuristics such as Lloyd's algorithm. It has been successfully used in market segmentation, computer vision, and astronomy among many other domains. It often is used as a preprocessing step for other algorithms, for example to find a starting configuration.
Vector quantization[edit]
Vector quantization, a technique commonly used in signal processing and computer graphics, involves reducing the color palette of an image to a fixed number of colors, known as k. One popular method for achieving vector quantization is through kmeans clustering. In this process, kmeans is applied to the color space of an image to partition it into k clusters, with each cluster representing a distinct color in the image. This technique is particularly useful in image segmentation tasks, where it helps identify and group similar colors together.
Example: In the field of computer graphics, kmeans clustering is often employed for color quantization in image compression. By reducing the number of colors used to represent an image, file sizes can be significantly reduced without significant loss of visual quality. For instance, consider an image with millions of colors. By applying kmeans clustering with k set to a smaller number, the image can be represented using a more limited color palette, resulting in a compressed version that consumes less storage space and bandwidth. Other uses of vector quantization include nonrandom sampling, as kmeans can easily be used to choose k different but prototypical objects from a large data set for further analysis.
Cluster analysis[edit]
Cluster analysis, a fundamental task in data mining and machine learning, involves grouping a set of data points into clusters based on their similarity. kmeans clustering is a popular algorithm used for partitioning data into k clusters, where each cluster is represented by its centroid.
However, the pure kmeans algorithm is not very flexible, and as such is of limited use (except for when vector quantization as above is actually the desired use case). In particular, the parameter k is known to be hard to choose (as discussed above) when not given by external constraints. Another limitation is that it cannot be used with arbitrary distance functions or on nonnumerical data. For these use cases, many other algorithms are superior.
Example: In marketing, kmeans clustering is frequently employed for market segmentation, where customers with similar characteristics or behaviors are grouped together. For instance, a retail company may use kmeans clustering to segment its customer base into distinct groups based on factors such as purchasing behavior, demographics, and geographic location. These customer segments can then be targeted with tailored marketing strategies and product offerings to maximize sales and customer satisfaction.
Feature learning[edit]
kmeans clustering has been used as a feature learning (or dictionary learning) step, in either (semi)supervised learning or unsupervised learning.^{[53]} The basic approach is first to train a kmeans clustering representation, using the input training data (which need not be labelled). Then, to project any input datum into the new feature space, an "encoding" function, such as the thresholded matrixproduct of the datum with the centroid locations, computes the distance from the datum to each centroid, or simply an indicator function for the nearest centroid,^{[53]}^{[54]} or some smooth transformation of the distance.^{[55]} Alternatively, transforming the samplecluster distance through a Gaussian RBF, obtains the hidden layer of a radial basis function network.^{[56]}
This use of kmeans has been successfully combined with simple, linear classifiers for semisupervised learning in NLP (specifically for namedentity recognition)^{[57]} and in computer vision. On an object recognition task, it was found to exhibit comparable performance with more sophisticated feature learning approaches such as autoencoders and restricted Boltzmann machines.^{[55]} However, it generally requires more data, for equivalent performance, because each data point only contributes to one "feature".^{[53]}
Example: In natural language processing (NLP), kmeans clustering has been integrated with simple linear classifiers for semisupervised learning tasks such as namedentity recognition]] (NER). By first clustering unlabeled text data using kmeans, meaningful features can be extracted to improve the performance of NER models. For instance, kmeans clustering can be applied to identify clusters of words or phrases that frequently cooccur in the input text, which can then be used as features for training the NER model. This approach has been shown to achieve comparable performance with more complex feature learning techniques such as autoencoders and restricted Boltzmann machines, albeit with a greater requirement for labeled data.
Recent Developments[edit]
Recent advancements in the application of kmeans clustering include improvements in initialization techniques, such as the use of kmeans++ initialization to select initial cluster centroids in a more effective manner. Additionally, researchers have explored the integration of kmeans clustering with deep learning methods, such as convolutional neural networks (CNNs) and recurrent neural networks (RNNs), to enhance the performance of various tasks in computer vision, natural language processing, and other domains.
Relation to other algorithms[edit]
Gaussian mixture model[edit]
The slow "standard algorithm" for kmeans clustering, and its associated expectation–maximization algorithm, is a special case of a Gaussian mixture model, specifically, the limiting case when fixing all covariances to be diagonal, equal and have infinitesimal small variance.^{[58]}^{: 850 } Instead of small variances, a hard cluster assignment can also be used to show another equivalence of kmeans clustering to a special case of "hard" Gaussian mixture modelling.^{[59]}^{: 354, 11.4.2.5 } This does not mean that it is efficient to use Gaussian mixture modelling to compute kmeans, but just that there is a theoretical relationship, and that Gaussian mixture modelling can be interpreted as a generalization of kmeans; on the contrary, it has been suggested to use kmeans clustering to find starting points for Gaussian mixture modelling on difficult data.^{[58]}^{: 849 }
kSVD[edit]
Another generalization of the kmeans algorithm is the kSVD algorithm, which estimates data points as a sparse linear combination of "codebook vectors". kmeans corresponds to the special case of using a single codebook vector, with a weight of 1.^{[60]}
Principal component analysis[edit]
The relaxed solution of kmeans clustering, specified by the cluster indicators, is given by principal component analysis (PCA).^{[61]}^{[62]} The intuition is that kmeans describe spherically shaped (balllike) clusters. If the data has 2 clusters, the line connecting the two centroids is the best 1dimensional projection direction, which is also the first PCA direction. Cutting the line at the center of mass separates the clusters (this is the continuous relaxation of the discrete cluster indicator). If the data have three clusters, the 2dimensional plane spanned by three cluster centroids is the best 2D projection. This plane is also defined by the first two PCA dimensions. Wellseparated clusters are effectively modelled by ballshaped clusters and thus discovered by kmeans. Nonballshaped clusters are hard to separate when they are close. For example, two halfmoon shaped clusters intertwined in space do not separate well when projected onto PCA subspace. kmeans should not be expected to do well on this data.^{[63]} It is straightforward to produce counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.^{[64]}
Mean shift clustering[edit]
Basic mean shift clustering algorithms maintain a set of data points the same size as the input data set. Initially, this set is copied from the input set. All points are then iteratively moved towards the mean of the points surrounding them. By contrast, kmeans restricts the set of clusters to k clusters, usually much less than the number of points in the input data set, using the mean of all points in the prior cluster that are closer to that point than any other for the centroid (e.g. within the Voronoi partition of each updating point). A mean shift algorithm that is similar then to kmeans, called likelihood mean shift, replaces the set of points undergoing replacement by the mean of all points in the input set that are within a given distance of the changing set.^{[65]} An advantage of mean shift clustering over kmeans is the detection of an arbitrary number of clusters in the data set, as there is not a parameter determining the number of clusters. Mean shift can be much slower than kmeans, and still requires selection of a bandwidth parameter.
Independent component analysis[edit]
Under sparsity assumptions and when input data is preprocessed with the whitening transformation, kmeans produces the solution to the linear independent component analysis (ICA) task. This aids in explaining the successful application of kmeans to feature learning.^{[66]}
Bilateral filtering[edit]
kmeans implicitly assumes that the ordering of the input data set does not matter. The bilateral filter is similar to kmeans and mean shift in that it maintains a set of data points that are iteratively replaced by means. However, the bilateral filter restricts the calculation of the (kernel weighted) mean to include only points that are close in the ordering of the input data.^{[65]} This makes it applicable to problems such as image denoising, where the spatial arrangement of pixels in an image is of critical importance.
Similar problems[edit]
The set of squared error minimizing cluster functions also includes the kmedoids algorithm, an approach which forces the center point of each cluster to be one of the actual points, i.e., it uses medoids in place of centroids.
Software implementations[edit]
Different implementations of the algorithm exhibit performance differences, with the fastest on a test data set finishing in 10 seconds, the slowest taking 25,988 seconds (~7 hours).^{[1]} The differences can be attributed to implementation quality, language and compiler differences, different termination criteria and precision levels, and the use of indexes for acceleration.
Free Software/Open Source[edit]
The following implementations are available under Free/Open Source Software licenses, with publicly available source code.
 Accord.NET contains C# implementations for kmeans, kmeans++ and kmodes.
 ALGLIB contains parallelized C++ and C# implementations for kmeans and kmeans++.
 AOSP contains a Java implementation for kmeans.
 CrimeStat implements two spatial kmeans algorithms, one of which allows the user to define the starting locations.
 ELKI contains kmeans (with Lloyd and MacQueen iteration, along with different initializations such as kmeans++ initialization) and various more advanced clustering algorithms.
 Smile contains kmeans and various more other algorithms and results visualization (for java, kotlin and scala).
 Julia contains a kmeans implementation in the JuliaStats Clustering package.
 KNIME contains nodes for kmeans and kmedoids.
 Mahout contains a MapReduce based kmeans.
 mlpack contains a C++ implementation of kmeans.
 Octave contains kmeans.
 OpenCV contains a kmeans implementation.
 Orange includes a component for kmeans clustering with automatic selection of k and cluster silhouette scoring.
 PSPP contains kmeans, The QUICK CLUSTER command performs kmeans clustering on the dataset.
 R contains three kmeans variations.
 SciPy and scikitlearn contain multiple kmeans implementations.
 Spark MLlib implements a distributed kmeans algorithm.
 Torch contains an unsup package that provides kmeans clustering.
 Weka contains kmeans and xmeans.
Proprietary[edit]
The following implementations are available under proprietary license terms, and may not have publicly available source code.
 Ayasdi
 Mathematica
 MATLAB
 OriginPro
 RapidMiner
 SAP HANA
 SAS
 SPSS
 Stata
See also[edit]
 BFR algorithm
 Centroidal Voronoi tessellation
 Head/tail breaks
 k qflats
 kmeans++
 Linde–Buzo–Gray algorithm
 Selforganizing map
References[edit]
 ^ ^{a} ^{b} Kriegel, HansPeter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of runtime evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s1011501610042. ISSN 02191377. S2CID 40772241.
 ^ MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. Retrieved 20090407.
 ^ Steinhaus, Hugo (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (in French). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
 ^ Lloyd, Stuart P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, Stuart P. (1982). "Least squares quantization in PCM" (PDF). IEEE Transactions on Information Theory. 28 (2): 129–137. CiteSeerX 10.1.1.131.1338. doi:10.1109/TIT.1982.1056489. S2CID 10833328. Retrieved 20090415.
 ^ Forgy, Edward W. (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21 (3): 768–769. JSTOR 2528559.
 ^ Pelleg, Dan; Moore, Andrew (1999). "Accelerating exact k means algorithms with geometric reasoning". Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. San Diego, California, United States: ACM Press. pp. 277–281. doi:10.1145/312129.312248. ISBN 9781581131437. S2CID 13907420.
 ^ MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 9780521642989. MR 2012999.
 ^ Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A kMeans Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830.
 ^ ^{a} ^{b} Hamerly, Greg; Elkan, Charles (2002). "Alternatives to the kmeans algorithm that find better clusterings" (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM).
 ^ Celebi, M. E.; Kingravi, H. A.; Vela, P. A. (2013). "A comparative study of efficient initialization methods for the kmeans clustering algorithm". Expert Systems with Applications. 40 (1): 200–210. arXiv:1209.1960. doi:10.1016/j.eswa.2012.07.021. S2CID 6954668.
 ^ Bradley, Paul S.; Fayyad, Usama M. (1998). "Refining Initial Points for kMeans Clustering". Proceedings of the Fifteenth International Conference on Machine Learning.
 ^ Vattani, A. (2011). "kmeans requires exponentially many iterations even in the plane" (PDF). Discrete and Computational Geometry. 45 (4): 596–616. doi:10.1007/s0045401193401. S2CID 42683406.
 ^ ^{a} ^{b} Arthur, David; Manthey, B.; Roeglin, H. (2009). "kmeans has polynomial smoothed complexity". Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). arXiv:0904.1113.
 ^ Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NPhardness of Euclidean sumofsquares clustering". Machine Learning. 75 (2): 245–249. doi:10.1007/s1099400951030.
 ^ Dasgupta, S.; Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". IEEE Transactions on Information Theory. 55 (7): 3229–42. arXiv:0805.1390. doi:10.1109/TIT.2009.2021326. S2CID 666114.
 ^ Mahajan, Meena; Nimbhorkar, Prajakta; Varadarajan, Kasturi (2009). "The Planar kMeans Problem is NPHard". WALCOM: Algorithms and Computation. Lecture Notes in Computer Science. Vol. 5431. pp. 274–285. doi:10.1007/9783642002021_24. ISBN 9783642002014.
 ^ Inaba, M.; Katoh, N.; Imai, H. (1994). Applications of weighted Voronoi diagrams and randomization to variancebased kclustering. Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332–9. doi:10.1145/177424.178042.
 ^ Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008). Introduction to information retrieval. Cambridge University Press. ISBN 9780521865715. OCLC 190786122.
 ^ ^{a} ^{b} Arthur, David; Vassilvitskii, Sergei (20060101). "How slow is the k means method?". Proceedings of the twentysecond annual symposium on Computational geometry. SCG '06. ACM. pp. 144–153. doi:10.1145/1137856.1137880. ISBN 9781595933409. S2CID 3084311.
 ^ Bhowmick, Abhishek (2009). "A theoretical analysis of Lloyd's algorithm for kmeans clustering" (PDF). Archived from the original (PDF) on 20151208. See also here.
 ^ ^{a} ^{b} Phillips, Steven J. (2002). "Acceleration of KMeans and Related Clustering Algorithms". In Mount, David M.; Stein, Clifford (eds.). Acceleration of kMeans and Related Clustering Algorithms. Lecture Notes in Computer Science. Vol. 2409. Springer. pp. 166–177. doi:10.1007/3540456430_13. ISBN 9783540439776.
 ^ ^{a} ^{b} Elkan, Charles (2003). "Using the triangle inequality to accelerate kmeans" (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML).
 ^ ^{a} ^{b} Hamerly, Greg (2010). "Making kmeans even faster". Proceedings of the 2010 SIAM International Conference on Data Mining. pp. 130–140. doi:10.1137/1.9781611972801.12. ISBN 9780898717037.
 ^ ^{a} ^{b} Hamerly, Greg; Drake, Jonathan (2015). "Accelerating Lloyd's Algorithm for kMeans Clustering". Partitional Clustering Algorithms. pp. 41–78. doi:10.1007/9783319092591_2. ISBN 9783319092584.
 ^ Abiodun M. Ikotun, Absalom E. Ezugwu, Laith Abualigah, Belal Abuhaija, Jia Heming, Kmeans clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data, Information Sciences, Volume 622, 2023, Pages 178–210, ISSN 00200255, https://doi.org/10.1016/j.ins.2022.11.139.
 ^ 276. doi:10.1007/BF02289263. S2CID 120467216.
 ^ Schubert, Erich (20230622). "Stop using the elbow criterion for kmeans and how to choose the number of clusters instead". ACM SIGKDD Explorations Newsletter. 25 (1): 36–42. arXiv:2212.12189. doi:10.1145/3606274.3606278. ISSN 19310145.
 ^ Peter J. Rousseeuw (1987). "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis". Computational and Applied Mathematics. 20: 53–65. doi:10.1016/03770427(87)901257.
 ^ Robert Tibshirani; Guenther Walther; Trevor Hastie (2001). "Estimating the number of clusters in a data set via the gap statistic". Journal of the Royal Statistical Society, Series B. 63 (2): 411–423. doi:10.1111/14679868.00293. S2CID 59738652.
 ^ Davies, David L.; Bouldin, Donald W. (1979). "A Cluster Separation Measure". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI1 (2): 224–227. doi:10.1109/TPAMI.1979.4766909. S2CID 13254783.
 ^ Caliński, Tadeusz; Harabasz, Jerzy (1974). "A dendrite method for cluster analysis". Communications in Statistics. 3 (1): 1–27. doi:10.1080/03610927408827101.
 ^ W. M. Rand (1971). "Objective criteria for the evaluation of clustering methods". Journal of the American Statistical Association. 66 (336). American Statistical Association: 846–850. doi:10.2307/2284239. JSTOR 2284239.
 ^ Hubert, L., & Arabie, P. (1985). Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193218. https://doi.org/10.1007/BF01908075
 ^ Kanungo, Tapas; Mount, David M.; Netanyahu, Nathan S.; Piatko, Christine D.; Silverman, Ruth; Wu, Angela Y. (2002). "An efficient kmeans clustering algorithm: Analysis and implementation" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (7): 881–892. doi:10.1109/TPAMI.2002.1017616. S2CID 12003435. Retrieved 20090424.
 ^ Drake, Jonathan (2012). "Accelerated kmeans with adaptive distance bounds" (PDF). The 5th NIPS Workshop on Optimization for Machine Learning, OPT2012.
 ^ Dhillon, I. S.; Modha, D. M. (2001). "Concept decompositions for large sparse text data using clustering". Machine Learning. 42 (1): 143–175. doi:10.1023/a:1007612920971.
 ^ Steinbach, M.; Karypis, G.; Kumar, V. (2000). ""A comparison of document clustering techniques". In". KDD Workshop on Text Mining. 400 (1): 525–526.
 ^ Pelleg, D.; & Moore, A. W. (2000, June). "Xmeans: Extending kmeans with Efficient Estimation of the Number of Clusters". In ICML, Vol. 1
 ^ Hamerly, Greg; Elkan, Charles (2004). "Learning the k in kmeans" (PDF). Advances in Neural Information Processing Systems. 16: 281.
 ^ Amorim, R. C.; Mirkin, B. (2012). "Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in kMeans Clustering". Pattern Recognition. 45 (3): 1061–1075. doi:10.1016/j.patcog.2011.08.012.
 ^ Amorim, R. C.; Hennig, C. (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences. 324: 126–145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039. S2CID 315803.
 ^ Sculley, David (2010). "Webscale kmeans clustering". Proceedings of the 19th international conference on World Wide Web. ACM. pp. 1177–1178. Retrieved 20161221.
 ^ Telgarsky, Matus. "Hartigan's Method: kmeans Clustering without Voronoi" (PDF).
 ^ Piccialli, Veronica; Sudoso, Antonio M.; Wiegele, Angelika (20220328). "SOSSDP: An Exact Solver for Minimum SumofSquares Clustering". INFORMS Journal on Computing. 34 (4): 2144–2162. arXiv:2104.11542. doi:10.1287/ijoc.2022.1166. ISSN 10919856. S2CID 233388043.
 ^ Bagirov, A. M.; Taheri, S.; Ugon, J. (2016). "Nonsmooth DC programming approach to the minimum sumofsquares clustering problems". Pattern Recognition. 53: 12–24. Bibcode:2016PatRe..53...12B. doi:10.1016/j.patcog.2015.11.011.
 ^ Fränti, Pasi (2018). "Efficiency of random swap clustering". Journal of Big Data. 5 (1): 1–21. doi:10.1186/s405370180122y.
 ^ Hansen, P.; Mladenovic, N. (2001). "JMeans: A new local search heuristic for minimum sum of squares clustering". Pattern Recognition. 34 (2): 405–413. Bibcode:2001PatRe..34..405H. doi:10.1016/S00313203(99)002162.
 ^ Krishna, K.; Murty, M. N. (1999). "Genetic kmeans algorithm". IEEE Transactions on Systems, Man, and Cybernetics  Part B: Cybernetics. 29 (3): 433–439. doi:10.1109/3477.764879. PMID 18252317.
 ^ ^{a} ^{b} Gribel, Daniel; Vidal, Thibaut (2019). "HGmeans: A scalable hybrid metaheuristic for minimum sumofsquares clustering". Pattern Recognition. 88: 569–583. arXiv:1804.09813. doi:10.1016/j.patcog.2018.12.022. S2CID 13746584.
 ^ Mirkes, E. M. "Kmeans and kmedoids applet". Retrieved 2 January 2016.
 ^ Kulis, Brian; Jordan, Michael I. (20120626). "Revisiting kmeans: new algorithms via Bayesian nonparametrics" (PDF). ICML. pp. 1131–1138. ISBN 9781450312851.
 ^ ^{a} ^{b} ^{c} Coates, Adam; Ng, Andrew Y. (2012). "Learning feature representations with kmeans" (PDF). In Montavon, G.; Orr, G. B.; Müller, K.R. (eds.). Neural Networks: Tricks of the Trade. Springer.
 ^ Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF). ECCV Workshop on Statistical Learning in Computer Vision.
 ^ ^{a} ^{b} Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). An analysis of singlelayer networks in unsupervised feature learning (PDF). International Conference on Artificial Intelligence and Statistics (AISTATS). Archived from the original (PDF) on 20130510.
 ^ Schwenker, Friedhelm; Kestler, Hans A.; Palm, Günther (2001). "Three learning phases for radialbasisfunction networks". Neural Networks. 14 (4–5): 439–458. CiteSeerX 10.1.1.109.312. doi:10.1016/s08936080(01)000272. PMID 11411631.
 ^ Lin, Dekang; Wu, Xiaoyun (2009). Phrase clustering for discriminative learning (PDF). Annual Meeting of the ACL and IJCNLP. pp. 1030–1038.
 ^ ^{a} ^{b} Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Section 16.1. Gaussian Mixture Models and kMeans Clustering". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York (NY): Cambridge University Press. ISBN 9780521880688.
 ^ Kevin P. Murphy (2012). Machine learning : a probabilistic perspective. Cambridge, Mass.: MIT Press. ISBN 9780262305242. OCLC 810414751.
 ^ Aharon, Michal; Elad, Michael; Bruckstein, Alfred (2006). "KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF). IEEE Transactions on Signal Processing. 54 (11): 4311. Bibcode:2006ITSP...54.4311A. doi:10.1109/TSP.2006.881199. S2CID 7477309.
 ^ Zha, Hongyuan; Ding, Chris; Gu, Ming; He, Xiaofeng; Simon, Horst D. (December 2001). "Spectral Relaxation for kmeans Clustering" (PDF). Neural Information Processing Systems Vol.14 (NIPS 2001): 1057–1064.
 ^ Ding, Chris; He, Xiaofeng (July 2004). "Kmeans Clustering via Principal Component Analysis" (PDF). Proceedings of International Conference on Machine Learning (ICML 2004): 225–232.
 ^ Drineas, Petros; Frieze, Alan M.; Kannan, Ravi; Vempala, Santosh; Vinay, Vishwanathan (2004). "Clustering large graphs via the singular value decomposition" (PDF). Machine Learning. 56 (1–3): 9–33. doi:10.1023/b:mach.0000033113.59016.96. S2CID 5892850. Retrieved 20120802.
 ^ Cohen, Michael B.; Elder, Sam; Musco, Cameron; Musco, Christopher; Persu, Madalina (2014). "Dimensionality reduction for kmeans clustering and low rank approximation (Appendix B)". arXiv:1410.6801 [cs.DS].
 ^ ^{a} ^{b} Little, Max A.; Jones, Nick S. (2011). "Generalized methods and solvers for noise removal from piecewise constant signals. I. Background theory". Proceedings of the Royal Society A. 467 (2135): 3088–3114. doi:10.1098/rspa.2010.0671. PMC 3191861. PMID 22003312.
 ^ Vinnikov, Alon; ShalevShwartz, Shai (2014). "Kmeans Recovers ICA Filters when Independent Components are Sparse" (PDF). Proceedings of the International Conference on Machine Learning (ICML 2014).