Content deleted Content added
m →Free: correct R function name |
TokenByToken (talk | contribs) category |
||
| (646 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{Short description|Vector quantization algorithm minimizing the sum of squared deviations}}
{{Distinguish|k-nearest neighbors algorithm}}
{{Machine learning}}
'''''k''-means clustering''' is a method of [[vector quantization]], originally from [[signal processing]], that aims to [[partition of a set|partition]] ''n'' observations into ''k'' clusters in which each observation belongs to the [[cluster (statistics)|cluster]] with the nearest [[mean]] (cluster centers or cluster [[centroid]]). This results in a partitioning of the data space into [[Voronoi cell]]s. ''k''-means clustering minimizes within-cluster variances ([[squared Euclidean distance]]s), 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 [[k-medians clustering|''k''-medians]] and [[k-medoids|''k''-medoids]].
The problem is computationally difficult ([[NP-hardness|NP-hard]]); however, efficient [[heuristic algorithm]]s converge quickly to a [[local optimum]]. These are usually similar to the [[expectation–maximization algorithm]] for [[mixture model|mixtures]] of [[Gaussian distribution]]s via an iterative refinement approach employed by both ''k-means'' and ''Gaussian mixture modeling''. They both use cluster centers to model the data; however, ''k''-means clustering tends to find clusters of comparable spatial extent, while the Gaussian mixture model allows clusters to have different shapes.
The unsupervised ''k''-means algorithm has a loose relationship to the [[k-nearest neighbor|''k''-nearest neighbor classifier]], a popular supervised [[machine learning]] technique for classification that is often confused with ''k''-means due to the name. Applying the 1-nearest neighbor classifier to the cluster centers obtained by ''k''-means classifies new data into the existing clusters. This is known as [[nearest centroid classifier]] or [[Rocchio algorithm]].
== Description ==
Given a set of observations {{math|('''x'''<sub>1</sub>, '''x'''<sub>2</sub>, ..., '''x'''<sub>''n''</sub>)}}, where each observation is a <math>d</math>-dimensional real vector, ''k''-means clustering aims to partition the ''n'' observations into {{mvar|k}} ({{math|≤ ''n''}}) sets {{math|1='''S''' = {''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S<sub>k</sub>''}<nowiki/>}} so as to minimize the within-cluster sum of squares (WCSS) (i.e. [[variance]]). Formally, the objective is to find:
<math display="block">\mathop\operatorname{arg\,min}_\mathbf{S} \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2 = \mathop\operatorname{arg\,min}_\mathbf{S} \sum_{i=1}^k |S_i| \operatorname{Var} S_i </math>
where '''''μ'''<sub>i</sub>'' is the mean (also called centroid) of points in <math>S_i</math>, i.e.
<math display="block">\boldsymbol{\mu_i} = \frac{1}{|S_i|}\sum_{\mathbf x \in S_i} \mathbf x, </math>
<math>|S_i|</math> is the size of <math>S_i</math>, and <math>\|\cdot\| </math> is the usual [[Norm (mathematics)|''L''<sup>2</sup> norm]] . This is equivalent to minimizing the pairwise squared deviations of points in the same cluster:
<math display="block"> \mathop\operatorname{arg\,min}_\mathbf{S} \sum_{i=1}^{k} \, \frac{1}{ |S_i|} \, \sum_{\mathbf{x}, \mathbf{y} \in S_i} \left\| \mathbf{x} - \mathbf{y} \right\|^2</math>
The equivalence can be deduced from identity <math display="inline">|S_i|\sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2 = \frac{1}{2} \sum_{\mathbf{x},\mathbf{y} \in S_i}\left\|\mathbf x - \mathbf y\right\|^2</math>. Since the total variance is constant, this is equivalent to maximizing the sum of squared deviations between points in ''different'' clusters (between-cluster sum of squares, BCSS).<ref name=":12">{{cite journal |last1=Kriegel |first1=Hans-Peter |author-link=Hans-Peter Kriegel |last2=Schubert |first2=Erich |last3=Zimek |first3=Arthur |author-link3=Arthur Zimek |year=2016 |title=The (black) art of runtime evaluation: Are we comparing algorithms or implementations? |journal=Knowledge and Information Systems |volume=52 |issue=2 |pages=341–378 |doi=10.1007/s10115-016-1004-2 |s2cid=40772241 |issn=0219-1377 }}</ref> This deterministic relationship is also related to the [[law of total variance]] in probability theory.
== History ==
The term "''k''-means" was first used by James MacQueen in 1967,<ref name="macqueen19672">{{cite conference |last=MacQueen |first=J. B. |year=1967 |title=Some Methods for classification and Analysis of Multivariate Observations |url=http://projecteuclid.org/euclid.bsmsp/1200512992 |conference=Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability |publisher=University of California Press |volume=1 |pages=281–297 |mr=0214227 |zbl=0214.46201 |access-date=2009-04-07 }}</ref> though the idea goes back to [[Hugo Steinhaus]] in 1956.<ref>{{cite journal |last=Steinhaus |first=Hugo |author-link=Hugo Steinhaus |year=1957 |title=Sur la division des corps matériels en parties |journal=Bull. Acad. Polon. Sci. |language=fr |volume=4 |issue=12 |pages=801–804 |mr=0090073 |zbl=0079.16403 }}</ref> The standard algorithm was first proposed by Stuart Lloyd of [[Bell Labs]] in 1957 as a technique for [[pulse-code modulation]], although it was not published as a journal article until 1982.<ref name="lloyd19572">{{cite journal |last=Lloyd |first=Stuart P. |year=1957 |title=Least square quantization in PCM |journal=Bell Telephone Laboratories Paper }} Published in journal much later: {{cite journal |last=Lloyd |first=Stuart P. |year=1982 |title=Least squares quantization in PCM |url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf |journal=[[IEEE Transactions on Information Theory]] |volume=28 |issue=2 |pages=129–137 |doi=10.1109/TIT.1982.1056489 |access-date=2009-04-15 |citeseerx=10.1.1.131.1338 |s2cid=10833328 }}</ref> In 1965, Edward W. Forgy published essentially the same method, which is why it is sometimes referred to as the Lloyd–Forgy algorithm.<ref name="forgy652">{{Cite journal |first=Edward W. |last=Forgy |year=1965 |title=Cluster analysis of multivariate data: efficiency versus interpretability of classifications |journal=Biometrics |volume=21 |issue=3 |pages=768–769 |jstor=2528559 }}</ref>
== Algorithms ==
=== Standard algorithm (naive ''k''-means) ===
[[File:K-means_convergence.gif|right|thumb|Convergence of ''k''-means]]
The most common algorithm uses an iterative refinement technique. Due to its ubiquity, it is often called "the ''k''-means 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 ''k''-means", because there exist much faster alternatives.<ref>{{Cite book | last1=Pelleg|first1=Dan | last2=Moore|first2=Andrew |title=Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining |chapter=Accelerating exact ''k'' -means algorithms with geometric reasoning | date=1999 | chapter-url=http://portal.acm.org/citation.cfm?doid=312129.312248 | language=en|___location=San Diego, California, United States | publisher=ACM Press | pages=277–281 | doi=10.1145/312129.312248 | isbn=9781581131437 | s2cid=13907420}}</ref>
Given an initial set of {{math|''k''}} means {{math|''m''<sub>1</sub><sup>(1)</sup>, ..., ''m<sub>k</sub>''<sup>(1)</sup>}} (see below), the algorithm proceeds by alternating between two steps:<ref>{{Cite book |url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html |title=Information Theory, Inference and Learning Algorithms |last=MacKay |first=David |publisher=Cambridge University Press |year=2003 |isbn=978-0-521-64298-9 |pages=284–292 |chapter=Chapter 20. An Example Inference Task: Clustering |mr=2012999 |ref=mackay2003 |author-link=David MacKay (scientist) |chapter-url=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>
# '''Assignment step''': Assign each observation to the cluster with the nearest mean (centroid): that with the least squared [[Euclidean distance]].<ref>Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.</ref> (Mathematically, this means partitioning the observations according to the [[Voronoi diagram]] generated by the means.) <math display="block">S_i^{(t)} = \left \{ x_p : \left \| x_p - m^{(t)}_i \right \|^2 \le \left \| x_p - m^{(t)}_j \right \|^2 \ \forall j, 1 \le j \le k \right\},</math> where each <math>x_p</math> is assigned to exactly one <math>S^{(t)}</math>, even if it could be assigned to two or more of them.
# '''Update step''': Recalculate means ([[centroid]]s) for observations assigned to each cluster. This is also called refitting. <math display="block">m^{(t+1)}_i = \frac{1}{\left|S^{(t)}_i\right|} \sum_{x_j \in S^{(t)}_i} x_j </math>
The objective function in ''k''-means is the WCSS (within cluster sum of squares). After each iteration, the WCSS monotonically decreases, giving a nonnegative monotonically decreasing sequence. This guarantees that the ''k''-means 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 optimal cluster assignment.<ref name="hartigan19792">{{Cite journal |last1=Hartigan |first1=J. A. |last2=Wong |first2=M. A. |year=1979 |title=Algorithm AS 136: A ''k''-Means Clustering Algorithm |journal=[[Journal of the Royal Statistical Society, Series C]] |volume=28 |issue=1 |pages=100–108 |jstor=2346830 }}</ref>
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 ''k''-means such as spherical ''k''-means and [[k-medoids|''k''-medoids]] have been proposed to allow using other distance measures.
;Pseudocode
The below pseudocode outlines the implementation of the standard ''k''-means 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, <code>distance()</code> returns the distance between the specified points.
'''function''' kmeans(k, points) '''is'''
// Initialize centroids
centroids ← list of k starting centroids
converged ← false
'''while''' converged == false '''do'''
// Create empty clusters
clusters ← list of k empty lists
// Assign each point to the nearest centroid
'''for''' i ← 0 '''to''' length(points) - 1 '''do'''
point ← points[i]
closestIndex ← 0
minDistance ← distance(point, centroids[0])
'''for''' j ← 1 '''to''' k - 1 '''do'''
d ← '''distance'''(point, centroids[j])
'''if''' d < minDistance '''THEN'''
minDistance ← d
closestIndex ← j
clusters[closestIndex].'''append'''(point)
// Recalculate centroids as the mean of each cluster
newCentroids ← empty list
'''for''' i ← 0 '''to''' k - 1 '''do'''
newCentroid ← '''calculateCentroid'''(clusters[i])
newCentroids.'''append'''(newCentroid)
// Check for convergence
'''if''' newCentroids == centroids '''THEN'''
converged ← true
'''else'''
centroids ← newCentroids
'''return''' clusters
==== Initialization methods ====
Commonly used initialization methods are Forgy and Random Partition.<ref name="hamerly4">{{Cite conference |last1=Hamerly |first1=Greg |last2=Elkan |first2=Charles |year=2002 |title=Alternatives to the ''k''-means algorithm that find better clusterings |url=http://people.csail.mit.edu/tieu/notebook/kmeans/15_p600-hamerly.pdf |book-title=Proceedings of the eleventh international conference on Information and knowledge management (CIKM) }}</ref> 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.,<ref name="hamerly4" /> the Random Partition method is generally preferable for algorithms such as the ''k''-harmonic means and fuzzy ''k''-means. For expectation maximization and standard ''k''-means algorithms, the Forgy method of initialization is preferable. A comprehensive study by Celebi et al.,<ref>{{cite journal |last1=Celebi |first1=M. E. |last2=Kingravi |first2=H. A. |last3=Vela |first3=P. A. |year=2013 |title=A comparative study of efficient initialization methods for the ''k''-means clustering algorithm |journal=[[Expert Systems with Applications]] |volume=40 |issue=1 |pages=200–210 |arxiv=1209.1960 |doi=10.1016/j.eswa.2012.07.021 |s2cid=6954668 }}</ref> however, found that popular initialization methods such as Forgy, Random Partition, and Maximin often perform poorly, whereas Bradley and Fayyad's approach<ref>{{Cite conference |last1=Bradley |first1=Paul S. |last2=Fayyad |first2=Usama M. |author-link2=Usama Fayyad |year=1998 |title=Refining Initial Points for ''k''-Means Clustering |book-title=Proceedings of the Fifteenth International Conference on Machine Learning }}</ref> performs "consistently" in "the best group" and [[k-means++|''k''-means++]] performs "generally well".
<gallery class="center" widths="150px" caption="Demonstration of the standard algorithm">
File:K Means Example Step 1.svg|1. ''k'' initial "means" (in this case ''k''=3) are randomly generated within the data ___domain (shown in color).
File:K Means Example Step 2.svg|2. ''k'' clusters are created by associating every observation with the nearest mean. The partitions here represent the [[Voronoi diagram]] generated by the means.
File:K Means Example Step 3.svg|3. The [[centroid]] of each of the ''k'' clusters becomes the new mean.
File:K Means Example Step 4.svg|4. Steps 2 and 3 are repeated until convergence has been reached.
</gallery>
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, worst-case performance can be slow: in particular certain point sets, even in two dimensions, converge in exponential time, that is {{math|2<sup>Ω(<var>n</var>)</sup>}}.<ref>{{cite journal |last=Vattani |first=A. |year=2011 |title=k-means requires exponentially many iterations even in the plane |url=http://cseweb.ucsd.edu/users/avattani/papers/kmeans-journal.pdf |journal=[[Discrete and Computational Geometry]] |volume=45 |issue=4 |pages=596–616 |doi=10.1007/s00454-011-9340-1 |s2cid=42683406 |doi-access=free }}</ref> These point sets do not seem to arise in practice: this is corroborated by the fact that the [[Smoothed analysis|smoothed]] running time of ''k''-means is polynomial.<ref name="Arthur, David; Manthey, B.; Roeglin, H. 20092">{{cite conference |last1=Arthur |first1=David |last2=Manthey |first2=B. |last3=Roeglin |first3=H. |year=2009 |title=k-means has polynomial smoothed complexity |book-title=Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS) |arxiv=0904.1113 }}</ref>
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 ===
* [[NP-hard]] in general [[Euclidean space]] (of ''d'' dimensions) even for two clusters,<ref>{{cite journal |last1=Aloise |first1=D. |last2=Deshpande |first2=A. |last3=Hansen |first3=P. |last4=Popat |first4=P. |year=2009 |title=NP-hardness of Euclidean sum-of-squares clustering |journal=[[Machine Learning (journal)|Machine Learning]] |volume=75 |issue=2 |pages=245–249 |doi=10.1007/s10994-009-5103-0 |doi-access=free }}</ref><ref>{{cite journal |last1=Dasgupta |first1=S. |last2=Freund |first2=Y. |date=July 2009 |title=Random Projection Trees for Vector Quantization |journal=IEEE Transactions on Information Theory |volume=55 |issue=7 |pages=3229–42 |arxiv=0805.1390 |doi=10.1109/TIT.2009.2021326 |bibcode=2009ITIT...55.3229D |s2cid=666114 }}</ref>
* [[NP-hard]] for a general number of clusters ''k'' even in the plane,<ref>{{cite book |last1=Mahajan |first1=Meena |author1-link=Meena Mahajan|last2=Nimbhorkar |first2=Prajakta |last3=Varadarajan |first3=Kasturi |title=WALCOM: Algorithms and Computation |chapter=The Planar k-Means Problem is NP-Hard |year=2009 |series=Lecture Notes in Computer Science |volume=5431 |pages=274–285 |doi=10.1007/978-3-642-00202-1_24 |isbn=978-3-642-00201-4 }}</ref>
* if ''k'' and ''d'' (the dimension) are fixed, the problem can be exactly solved in time <math>O(n^{dk+1})</math>, where ''n'' is the number of entities to be clustered.<ref>{{cite conference |last1=Inaba |first1=M. |last2=Katoh |first2=N. |last3=Imai |first3=H. |year=1994 |title=Applications of weighted Voronoi diagrams and randomization to variance-based ''k''-clustering |conference=[[Symposium on Computational Geometry|Proceedings of 10th ACM Symposium on Computational Geometry]] |pages=332–9 |doi=10.1145/177424.178042 |doi-access=free }}</ref>
Thus, a variety of [[heuristic algorithm]]s such as Lloyd's algorithm given above are generally used.
The running time of Lloyd's algorithm (and most variants) is <math>O(n k d i)</math>,<ref name="hartigan19792" /><ref>{{Cite book |title=Introduction to information retrieval |last1=Manning |first1=Christopher D. |date=2008 |publisher=Cambridge University Press |last2=Raghavan |first2=Prabhakar |last3=Schütze |first3=Hinrich |isbn=978-0521865715 |oclc=190786122 }}</ref> where:
* ''n'' is the number of ''d''-dimensional vectors (to be clustered)
* ''k'' the number of clusters
* ''i'' the number of iterations needed until convergence.
* In the worst-case, Lloyd's algorithm needs <math>i = 2^{\Omega(\sqrt{n})}</math> iterations, so that the worst-case complexity of Lloyd's algorithm is [[Time complexity#Superpolynomial time|superpolynomial]].<ref name=":02" />
* Lloyd's ''k''-means algorithm has polynomial smoothed running time. It is shown that<ref name="Arthur, David; Manthey, B.; Roeglin, H. 20092" /> for arbitrary set of ''n'' points in <math>[0,1]^d</math>, if each point is independently perturbed by a normal distribution with mean {{math|0}} and variance <math>\sigma^2</math>, then the expected running time of {{mvar|k}}-means algorithm is bounded by <math>O( n^{34} k^{34} d^8 \log^4(n) / \sigma^6 )</math>, which is a polynomial in {{mvar|n}}, {{mvar|k}}, {{mvar|d}} and <math>1/\sigma</math>.
* Better bounds are proven for simple cases. For example, it is shown that the running time of ''k''-means algorithm is bounded by <math>O(dn^4M^2)</math> for {{mvar|n}} points in an [[integer lattice]] <math>\{1, \dots, M\}^d</math>.<ref>{{Cite web |title=A theoretical analysis of Lloyd's algorithm for ''k''-means clustering |url=https://gautam5.cse.iitk.ac.in/opencs/sites/default/files/final.pdf |first=Abhishek |last=Bhowmick |year=2009 |archive-url=https://web.archive.org/web/20151208140946/https://gautam5.cse.iitk.ac.in/opencs/sites/default/files/final.pdf |archive-date=2015-12-08}} See also [https://www.researchgate.net/publication/267854906_A_theoretical_analysis_of_Lloyd's_algorithm_for_k-means_clustering here].</ref>
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.<ref name="yinyangKmeans">{{Cite conference |last1=Ding |first1=Yufei |last2=Zhao |first2=Yue |last3=Shen |first3=Xipeng |last4=Musuvathi |first4=Madan |last5=Mytkowiczyear |first5=Todd |title=Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup |url=https://research.csc.ncsu.edu/picture/publications/papers/icml15.pdf |book-title=Proceedings of the Thirty Second International Conference on Machine Learning (ICML) }}</ref><ref name="hartigan19792" /><ref name="phillips2">{{Cite book |title=Acceleration of ''k''-Means and Related Clustering Algorithms |volume=2409 |last=Phillips |first=Steven J. |date=2002 |publisher=Springer |isbn=978-3-540-43977-6 |editor-last=Mount |editor-first=David M. |series=Lecture Notes in Computer Science |pages=166–177 |doi=10.1007/3-540-45643-0_13 |editor-last2=Stein |editor-first2=Clifford |chapter=Acceleration of K-Means and Related Clustering Algorithms }}</ref><ref name="elkan2">{{Cite conference |last=Elkan |first=Charles |year=2003 |title=Using the triangle inequality to accelerate ''k''-means |url=http://www-cse.ucsd.edu/~elkan/kmeansicml03.pdf |book-title=Proceedings of the Twentieth International Conference on Machine Learning (ICML) }}</ref><ref name="hamerly22">{{cite book |first=Greg |last=Hamerly |chapter=Making k-means even faster |title=Proceedings of the 2010 SIAM International Conference on Data Mining |date=2010 |isbn=978-0-89871-703-7 |pages=130–140 |doi=10.1137/1.9781611972801.12}}</ref><ref name="hamerly32">{{cite book |last1=Hamerly |first1=Greg |last2=Drake |first2=Jonathan |title=Partitional Clustering Algorithms |chapter=Accelerating Lloyd's Algorithm for k-Means Clustering |date=2015 |pages=41–78 |doi=10.1007/978-3-319-09259-1_2 |isbn=978-3-319-09258-4 }}</ref>
=== Optimal number of clusters ===
{{main|Determining the number of clusters in a data set}}
Finding the optimal number of clusters (''k'') for ''k''-means clustering is a crucial step to ensure that the clustering results are meaningful and useful.<ref>Abiodun M. Ikotun, Absalom E. Ezugwu, Laith Abualigah, Belal Abuhaija, Jia Heming, K-means clustering algorithms: A comprehensive review, variants analysis, and advances in the era of big data, Information Sciences, Volume 622, 2023, Pages 178–210, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2022.11.139.
</ref> 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.<ref>276. doi:10.1007/BF02289263. S2CID 120467216.</ref> However, the notion of an "elbow" is not well-defined and this is known to be unreliable.<ref>Schubert, Erich (2023-06-22). "Stop using the elbow criterion for k-means 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 1931-0145.</ref>
* [[Silhouette (clustering)]]: Silhouette analysis measures the quality of clustering and provides an insight into the separation distance between the resulting clusters.<ref>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/0377-0427(87)90125-7.</ref> 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 intra-cluster variation for different values of k with their expected values under null reference distribution of the data.<ref>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/1467-9868.00293. S2CID 59738652.</ref> The optimal k is the value that yields the largest gap statistic.
* [[Davies–Bouldin index]]: The Davies-Bouldin index is a measure of the how much separation there is between clusters.<ref>Davies, David L.; Bouldin, Donald W. (1979). "A Cluster Separation Measure". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224–227. doi:10.1109/TPAMI.1979.4766909. S2CID 13254783.</ref> Lower values of the Davies-Bouldin index indicate a model with better separation.
* [[Calinski-Harabasz index]]: This Index evaluates clusters based on their compactness and separation. The index is calculated using the ratio of between-cluster variance to within-cluster variance, with higher values indicate better-defined clusters.<ref>Caliński, Tadeusz; Harabasz, Jerzy (1974). "A dendrite method for cluster analysis". Communications in Statistics. 3 (1): 1–27. doi:10.1080/03610927408827101.</ref>
* [[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.<ref>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.</ref> 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.<ref>Hubert, L., & Arabie, P. (1985).
Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193-218.
https://doi.org/10.1007/BF01908075</ref>
=== Variations ===
* [[Jenks natural breaks optimization]]: ''k''-means applied to univariate data
* [[K-medians clustering|''k''-medians clustering]] uses the median in each dimension instead of the mean, and this way minimizes <math>L_1</math> norm ([[Taxicab geometry]]).
* [[K-medoids|''k''-medoids]] (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 clustering#Fuzzy c-means clustering|Fuzzy C-Means Clustering]] is a soft version of
* [[Mixture model#Gaussian mixture model|Gaussian mixture]] models trained with [[
* [[K-means++|''k''-means++]] chooses initial centers in a way that gives a provable upper bound on the
* The filtering algorithm uses [[k-d tree|''k''-d tree]]s to speed up each ''k''-means step.<ref>{{cite journal |last1=Kanungo |first1=Tapas |last2=Mount |first2=David M. |author-link2=David Mount |author-link3=Nathan Netanyahu |last3=Netanyahu |first3=Nathan S. |last4=Piatko |first4=Christine D. |author4-link=Christine Piatko |last5=Silverman |first5=Ruth |last6=Wu |first6=Angela Y. |year=2002 |title=An efficient ''k''-means clustering algorithm: Analysis and implementation |url=http://www.cs.umd.edu/~mount/Papers/pami02.pdf |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=24 |issue=7 |pages=881–892 |doi=10.1109/TPAMI.2002.1017616 |bibcode=2002ITPAM..24..881K |s2cid=12003435 |access-date=2009-04-24 |archive-date=2009-10-07 |archive-url=https://web.archive.org/web/20091007160354/http://www.cs.umd.edu/~mount/Papers/pami02.pdf |url-status=dead }}</ref>
* Some methods attempt to speed up each ''k''-means step using the [[triangle inequality]].<ref name="phillips2" /><ref name="elkan2" /><ref name="hamerly22" /><ref>{{Cite journal |last=Drake |first=Jonathan |date=2012 |title=Accelerated ''k''-means with adaptive distance bounds |url=http://opt.kyb.tuebingen.mpg.de/papers/opt2012_paper_13.pdf |journal=The 5th NIPS Workshop on Optimization for Machine Learning, OPT2012 }}</ref><ref name="hamerly32" />
* Escape local optima by swapping points between clusters.<ref name="hartigan19792" />
* The Spherical ''k''-means clustering algorithm is suitable for textual data.<ref>{{Cite journal |last1=Dhillon |first1=I. S. |last2=Modha |first2=D. M. |year=2001 |title=Concept decompositions for large sparse text data using clustering |journal=Machine Learning |volume=42 |issue=1 |pages=143–175 |doi=10.1023/a:1007612920971 |doi-access=free }}</ref>
* Hierarchical variants such as Bisecting ''k''-means,<ref>{{cite journal | last1 = Steinbach | first1 = M. | last2 = Karypis | first2 = G. | last3 = Kumar | first3 = V. | year = 2000 | title = "A comparison of document clustering techniques". In | journal = KDD Workshop on Text Mining | volume = 400 | issue = 1| pages = 525–526 }}</ref> [[X-means clustering]]<ref>Pelleg, D.; & Moore, A. W. (2000, June). "[http://cs.uef.fi/~zhao/Courses/Clustering2012/Xmeans.pdf X-means: Extending ''k''-means with Efficient Estimation of the Number of Clusters] {{Webarchive|url=https://web.archive.org/web/20160909085805/http://cs.uef.fi/~zhao/Courses/Clustering2012/Xmeans.pdf |date=2016-09-09 }}". In ''ICML'', Vol. 1</ref> and G-means clustering<ref>{{cite journal | last1 = Hamerly | first1 = Greg | last2 = Elkan | first2 = Charles | year = 2004 | title = Learning the k in k-means | url =http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf | journal = [[Advances in Neural Information Processing Systems]] | volume = 16 | page = 281 }}</ref> [[Hierarchical clustering#Divisive clustering|repeatedly split clusters to build a hierarchy]], and can also try to automatically determine the optimal number of clusters in a dataset.
* [[Cluster analysis#Internal evaluation|Internal cluster evaluation]] measures such as [[Silhouette (clustering)|cluster silhouette]] can be helpful at [[Determining the number of clusters in a data set|determining the number of clusters]].
* Minkowski weighted ''k''-means automatically calculates cluster specific feature weights, supporting the intuitive idea that a feature may have different degrees of relevance at different features.<ref>{{Cite journal |last1=Amorim |first1=R. C. |last2=Mirkin |first2=B. |year=2012 |title=Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in ''k''-Means Clustering |journal=Pattern Recognition |volume=45 |issue=3 |pages=1061–1075 |doi=10.1016/j.patcog.2011.08.012 }}</ref> These weights can also be used to re-scale a given data set, increasing the likelihood of a cluster validity index to be optimized at the expected number of clusters.<ref>{{Cite journal |last1=Amorim |first1=R. C. |last2=Hennig |first2=C. |year=2015 |title=Recovering the number of clusters in data sets with noise features using feature rescaling factors |journal=Information Sciences |volume=324 |pages=126–145 |arxiv=1602.06989 |doi=10.1016/j.ins.2015.06.039 |s2cid=315803 }}</ref>
* Mini-batch ''k''-means: ''k''-means variation using "mini batch" samples for data sets that do not fit into memory.<ref>{{Cite conference |last=Sculley |first=David |date=2010 |title=Web-scale ''k''-means clustering |url=http://dl.acm.org/citation.cfm?id=1772862 |publisher=ACM |pages=1177–1178 |access-date=2016-12-21 |book-title=Proceedings of the 19th international conference on World Wide Web }}</ref>
* [[Otsu's method]]
=== Hartigan–Wong method ===
[[John A. Hartigan|Hartigan]] and Wong's method<ref name="hartigan19792" /> provides a variation of ''k''-means algorithm which progresses towards a local minimum of the minimum sum-of-squares problem with different solution updates. The method is a [[Local search (optimization)|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 ''k''-means, the approach remains a heuristic since it does not necessarily guarantee that the final solution is globally optimum.
Let <math>\varphi(S_j) </math> be the individual cost of <math>S_j</math> defined by <math display="inline">\sum_{x \in S_j} (x - \mu_j)^2</math>, with <math>\mu_j</math> the center of the cluster.
;Assignment step: Hartigan and Wong's method starts by partitioning the points into random clusters <math>\{ S_j \}_{j \in \{1, \cdots k\}}</math>.
;Update step: Next it determines the <math>n,m \in \{1, \ldots, k \}</math> and <math>x \in S_n</math> for which the following function reaches a maximum <math display="block">\Delta(m,n,x) = \varphi(S_n) + \varphi(S_m) - \varphi(S_n \setminus \{ x \} ) - \varphi(S_m \cup \{ x \} ).
</math> For the <math>x,n,m</math> that reach this maximum, <math>x</math> moves from the cluster <math>S_n</math> to the cluster <math>S_m</math>.
;Termination: The algorithm terminates once <math>\Delta(m,n,x)</math> is less than zero for all <math>x,n,m</math>.
Different move acceptance strategies can be used. In a ''first-improvement'' strategy, any improving relocation can be applied, whereas in a ''best-improvement'' 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 <math>\Delta</math> used to calculate the result of a relocation can also be efficiently evaluated by using equality<ref name=":22">{{Cite web |url=http://proceedings.mlr.press/v9/telgarsky10a/telgarsky10a.pdf |title=Hartigan's Method: ''k''-means Clustering without Voronoi |last=Telgarsky |first=Matus }}</ref>
<math display="block">\Delta(x,n,m) = \frac{ \mid S_n \mid }{ \mid S_n \mid - 1} \cdot \lVert \mu_n - x \rVert^2 -
\frac{ \mid S_m \mid }{ \mid S_m \mid + 1} \cdot \lVert \mu_m - x \rVert^2.</math>
=== Global optimization and meta-heuristics ===
The classical ''k''-means algorithm and its variations are known to only converge to local minima of the minimum-sum-of-squares clustering problem defined as
<math display="block"> \mathop\operatorname{arg\,min}_\mathbf{S} \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2 .</math>
Many studies have attempted to improve the convergence behavior of the algorithm and maximize the chances of attaining the global optimum (or at least, local minima of better quality). Initialization and restart techniques discussed in the previous sections are one alternative to find better solutions. More recently, global optimization algorithms based on [[branch-and-bound]] and [[semidefinite programming]] have produced ‘’provenly optimal’’ solutions for datasets with up to 4,177 entities and 20,531 features.<ref>{{Cite journal |last1=Piccialli |first1=Veronica |last2=Sudoso |first2=Antonio M. |last3=Wiegele |first3=Angelika |date=2022-03-28 |title=SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering |url=http://pubsonline.informs.org/doi/10.1287/ijoc.2022.1166 |journal=INFORMS Journal on Computing |volume=34 |issue=4 |language=en |pages=2144–2162 |doi=10.1287/ijoc.2022.1166 |arxiv=2104.11542 |s2cid=233388043 |issn=1091-9856}}</ref> As expected, due to the [[NP-hardness]] of the subjacent optimization problem, the computational time of optimal algorithms for ''k''-means quickly increases beyond this size. Optimal solutions for small- and medium-scale still remain valuable as a benchmark tool, to evaluate the quality of other heuristics. To find high-quality local minima within a controlled computational time but without optimality guarantees, other works have explored [[metaheuristics]] and other [[global optimization]] techniques, e.g., based on incremental approaches and convex optimization,<ref name=bagirov16>{{Cite journal|last1= Bagirov |first1=A. M. |last2=Taheri |first2=S. |last3=Ugon|first3=J.|year=2016 |title= Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems | journal= Pattern Recognition |volume=53 |pages=12–24 |doi= 10.1016/j.patcog.2015.11.011 | bibcode = 2016PatRe..53...12B }}</ref> random swaps<ref name=franti18>{{Cite journal |last1= Fränti |first1=Pasi |year=2018 |title= Efficiency of random swap clustering |journal= Journal of Big Data |volume=5 |issue=1|pages=1–21 |article-number=13 |doi= 10.1186/s40537-018-0122-y|doi-access=free }}</ref> (i.e., [[iterated local search]]), [[variable neighborhood search]]<ref>{{Cite journal |last1= Hansen |first1=P. |last2=Mladenovic |first2=N. |year=2001 |title= J-Means: A new local search heuristic for minimum sum of squares clustering|journal=Pattern Recognition |volume=34 |issue=2|pages=405–413 | doi= 10.1016/S0031-3203(99)00216-2 | bibcode=2001PatRe..34..405H }}</ref> and [[genetic algorithm]]s.<ref>{{Cite journal |last1=Krishna |first1=K. |last2=Murty |first2=M. N. |year=1999 |title=Genetic k-means algorithm |journal= IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics |volume=29 |issue=3|pages=433–439 |doi= 10.1109/3477.764879|pmid=18252317 |url=https://www.researchgate.net/publication/5600582}}</ref><ref name=gribel19>{{Cite journal |last1= Gribel |first1=Daniel | last2=Vidal |first2=Thibaut| year=2019 |title= HG-means: A scalable hybrid metaheuristic for minimum sum-of-squares clustering |journal=Pattern Recognition |volume=88 |pages=569–583 |doi= 10.1016/j.patcog.2018.12.022 | arxiv=1804.09813 |s2cid=13746584 }}</ref> It is indeed known that finding better local minima of the minimum sum-of-squares clustering problem can make the difference between failure and success to recover cluster structures in feature spaces of high dimension.<ref name=gribel19 />
== Discussion ==
[[File:K-
[[File:
[[File:
Three key features of ''k''-means that make it efficient are often regarded as its biggest drawbacks:
* [[Euclidean distance]] is used as a [[Metric (mathematics)|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 ''k''-means, it is important to run diagnostic checks for [[Determining the number of clusters in a data set|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 ''k''-means is its cluster model. The concept is based on spherical clusters that are separable
The result of ''k''-means can
== Applications ==
''k''-means 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 ===
{{Main|Vector quantization}}
[[Vector quantization]], a technique commonly used in signal processing and computer graphics, involves reducing the [[palette (computing)|color palette]] of an image to a fixed number of colors, known as ''k''. One popular method for achieving [[vector quantization]] is through ''k''-means clustering. In this process, ''k''-means 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.[[File:Rosa_Gold_Glow_2_small_noblue.png|right|frame|Example image with only red and green channel (for illustration purposes)]]
[[File:Rosa_Gold_Glow_2_small_noblue_color_space.png|right|thumb|250x250px|Vector quantization of colors present in the image above into Voronoi cells using ''k''-means]]
Example: In the field of [[computer graphics]], ''k''-means 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 ''k''-means clustering with ''k'' set to a smaller number, the image can be represented using a more limited [[palette (computing)|color palette]], resulting in a compressed version that consumes less storage space and bandwidth. Other uses of vector quantization include [[sampling (statistics)|non-random sampling]], as ''k''-means can easily be used to choose ''k'' different but prototypical objects from a large data set for further analysis.
=== Cluster analysis ===
{{Main|Cluster analysis}}
[[Cluster analysis]], a fundamental task in data mining and [[machine learning]], involves grouping a set of data points into clusters based on their similarity. ''k''-means clustering is a popular algorithm used for partitioning data into k clusters, where each cluster is represented by its centroid.
However, the pure ''k''-means 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 non-numerical data. For these use cases, many other algorithms are superior.
Example: In marketing, ''k''-means clustering is frequently employed for [[market segmentation]], where customers with similar characteristics or behaviors are grouped together. For instance, a retail company may use ''k''-means 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 ===
{{Main|Feature learning}}
''k''-means clustering has been used as a [[feature learning]] (or [[dictionary learning]]) step, in either ([[semi-supervised learning|semi-]])[[supervised learning]] or [[unsupervised learning]].<ref name="Coates20122">{{cite book |year=2012 |chapter=Learning feature representations with ''k''-means |title=Neural Networks: Tricks of the Trade |publisher=Springer |chapter-url=https://cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf |last2=Ng |first2=Andrew Y. |last1=Coates |first1=Adam |editor=Montavon, G. |editor2=Orr, G. B. |editor3=Müller, K.-R. |editor3-link=Klaus-Robert Müller}}</ref> The basic approach is first to train a ''k''-means 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 matrix-product 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,<ref name="Coates20122" /><ref>{{cite conference |last1=Csurka |first1=Gabriella |last2=Dance |first2=Christopher C. |last3=Fan |first3=Lixin |last4=Willamowski |first4=Jutta |last5=Bray |first5=Cédric |year=2004 |title=Visual categorization with bags of keypoints |url=https://www.cs.cmu.edu/~efros/courses/LBMV07/Papers/csurka-eccv-04.pdf |conference=ECCV Workshop on Statistical Learning in Computer Vision }}</ref> or some smooth transformation of the distance.<ref name="coates20112">{{cite conference |last1=Coates |first1=Adam |last2=Lee |first2=Honglak |last3=Ng |first3=Andrew Y. |year=2011 |title=An analysis of single-layer networks in unsupervised feature learning |url=http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf |url-status=dead |conference=International Conference on Artificial Intelligence and Statistics (AISTATS) |archive-url=https://web.archive.org/web/20130510120705/http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf |archive-date=2013-05-10 }}</ref> Alternatively, transforming the sample-cluster distance through a [[Radial basis function|Gaussian RBF]], obtains the hidden layer of a [[radial basis function network]].<ref name="schwenker2">{{cite journal |last1=Schwenker |first1=Friedhelm |last2=Kestler |first2=Hans A. |last3=Palm |first3=Günther |year=2001 |title=Three learning phases for radial-basis-function networks |journal=Neural Networks |volume=14 |issue=4–5 |pages=439–458 |citeseerx=10.1.1.109.312 |doi=10.1016/s0893-6080(01)00027-2 |pmid=11411631 }}</ref>
This use of ''k''-means has been successfully combined with simple, [[linear classifier]]s for semi-supervised learning in [[
Example: In [[natural language processing]] (NLP), ''k''-means clustering has been integrated with simple linear classifiers for semi-supervised learning tasks such as [[named-entity recognition]] (NER). By first clustering unlabeled text data using ''k''-means, meaningful features can be extracted to improve the performance of NER models. For instance, ''k''-means clustering can be applied to identify clusters of words or phrases that frequently co-occur 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 [[autoencoder]]s and restricted [[Boltzmann machine]]s, albeit with a greater requirement for labeled data.
=== Recent Developments ===
Recent advancements in the application of ''k''-means clustering include improvements in initialization techniques, such as the use of [[k-means++|''k''-means++]] initialization to select initial cluster centroids in a more effective manner. Additionally, researchers have explored the integration of ''k''-means clustering with deep learning methods, such as [[convolutional neural network]]s (CNNs) and [[recurrent neural network]]s (RNNs), to enhance the performance of various tasks in [[computer vision]], [[natural language processing]], and other domains.
=== Gaussian mixture model ===
{{Main|Gaussian mixture model}}
The slow "standard algorithm" for ''k''-means 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.<ref name=":0">{{Cite book |title=Numerical Recipes: The Art of Scientific Computing |last1=Press |first1=W. H. |last2=Teukolsky |first2=S. A. |last3=Vetterling |first3=W. T. |last4=Flannery |first4=B. P. |publisher=Cambridge University Press |year=2007 |isbn=978-0-521-88068-8 |edition=3rd |___location=New York (NY) |chapter=Section 16.1. Gaussian Mixture Models and ''k''-Means Clustering |chapter-url=http://apps.nrbook.com/empanel/index.html#pg=842 }}</ref>{{Rp|850}} Instead of small variances, a hard cluster assignment can also be used to show another equivalence of ''k''-means clustering to a special case of "hard" Gaussian mixture modelling.<ref>{{Cite book|title=Machine learning : a probabilistic perspective|last=Kevin P. Murphy|publisher=MIT Press|year=2012|isbn=978-0-262-30524-2|___location=Cambridge, Mass.|oclc=810414751}}</ref>{{Rp|354|at=11.4.2.5}} This does not mean that it is efficient to use Gaussian mixture modelling to compute ''k''-means, but just that there is a theoretical relationship, and that Gaussian mixture modelling can be interpreted as a generalization of ''k''-means; on the contrary, it has been suggested to use ''k''-means clustering to find starting points for Gaussian mixture modelling on difficult data.<ref name=":0" />{{Rp|849}}
=== ''k''-SVD ===
{{Main|k-SVD}}
Another generalization of the ''k''-means algorithm is the ''k''-SVD algorithm, which estimates data points as a sparse linear combination of "codebook vectors". ''k''-means corresponds to the special case of using a single codebook vector, with a weight of 1.<ref>{{Cite journal |last1=Aharon |first1=Michal |author1-link=Michal Aharon |last2=Elad |first2=Michael |last3=Bruckstein |first3=Alfred |year=2006 |title=K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation |url=http://www.cs.technion.ac.il/FREDDY/papers/120.pdf |journal=IEEE Transactions on Signal Processing |volume=54 |issue=11 |pages=4311 |bibcode=2006ITSP...54.4311A |doi=10.1109/TSP.2006.881199 |s2cid=7477309 |archive-date=2019-12-02 |access-date=2019-12-02 |archive-url=https://web.archive.org/web/20191202222055/http://www.cs.technion.ac.il/FREDDY/papers/120.pdf |url-status=dead }}</ref>
===
{{Main|Principal component analysis}}
The relaxed solution of {{math|<var>k</var>}}-means clustering, specified by the cluster indicators, is given by principal component analysis (PCA).<ref>{{cite journal |first1=Hongyuan |last1=Zha |first2=Chris |last2=Ding |first3=Ming |last3=Gu |first4=Xiaofeng |last4=He |first5=Horst D. |last5=Simon |date=December 2001 |title=Spectral Relaxation for ''k''-means Clustering |url=http://ranger.uta.edu/~chqding/papers/Zha-Kmeans.pdf |journal=Neural Information Processing Systems Vol.14 (NIPS 2001) |pages=1057–1064 }}</ref><ref>{{cite journal |first1=Chris |last1=Ding |first2=Xiaofeng |last2=He |date=July 2004 |title=K-means Clustering via Principal Component Analysis |url=http://ranger.uta.edu/~chqding/papers/KmeansPCA1.pdf |pages=225–232 |journal=Proceedings of International Conference on Machine Learning (ICML 2004) }}</ref> The intuition is that ''k''-means describe spherically shaped (ball-like) clusters. If the data has 2 clusters, the line connecting the two centroids is the best 1-dimensional 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 2-dimensional plane spanned by three cluster centroids is the best 2-D projection. This plane is also defined by the first two PCA dimensions. Well-separated clusters are effectively modelled by ball-shaped clusters and thus discovered by ''k''-means. Non-ball-shaped clusters are hard to separate when they are close. For example, two half-moon shaped clusters intertwined in space do not separate well when projected onto PCA subspace. ''k''-means should not be expected to do well on this data.<ref>{{cite journal |last1=Drineas |first1=Petros |first2=Alan M. |last2=Frieze |first3=Ravi |last3=Kannan |first4=Santosh |last4=Vempala |first5=Vishwanathan |last5=Vinay |year=2004 |title=Clustering large graphs via the singular value decomposition |url=http://www.cc.gatech.edu/~vempala/papers/dfkvv.pdf |journal=Machine Learning |volume=56 |issue=1–3 |pages=9–33 |doi=10.1023/b:mach.0000033113.59016.96 |s2cid=5892850 |access-date=2012-08-02 |doi-access=free }}</ref> It is straightforward to produce counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.<ref>{{cite arXiv |eprint=1410.6801 |class=cs.DS |first1=Michael B. |last1=Cohen |first2=Sam |last2=Elder |title=Dimensionality reduction for ''k''-means clustering and low rank approximation (Appendix B) |year=2014|first3=Cameron |last3=Musco |first4=Christopher |last4=Musco |first5=Madalina |last5=Persu }}</ref>
=== Mean shift clustering ===
{{Main|Mean shift}}
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, ''k''-means 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 ''k''-means, 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.<ref name="Little20112">{{cite journal |last1=Little |first1=Max A. |last2=Jones |first2=Nick S. |year=2011 |title=Generalized methods and solvers for noise removal from piecewise constant signals. I. Background theory |url=https://doi.org/10.1098/rspa.2010.0671 |journal=[[Proceedings of the Royal Society A]] |volume=467 |issue=2135 |pages=3088–3114 |bibcode= 2011RSPSA.467.3088L|doi=10.1098/rspa.2010.0671 |pmc=3191861 |pmid=22003312}}</ref> An advantage of mean shift clustering over ''k''-means 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 ''k''-means, and still requires selection of a bandwidth parameter.
=== Independent component analysis ===
{{Main|Independent component analysis}}
Under sparsity assumptions and when input data is pre-processed with the [[whitening transformation]], ''k''-means produces the solution to the linear independent component analysis (ICA) task. This aids in explaining the successful application of ''k''-means to [[#Feature learning|feature learning]].<ref>{{cite journal|first1=Alon |last1=Vinnikov |first2=Shai |last2=Shalev-Shwartz |year=2014 |title=K-means Recovers ICA Filters when Independent Components are Sparse |url=http://www.cs.huji.ac.il/~shais/papers/KmeansICA_ICML2014.pdf |journal=Proceedings of the International Conference on Machine Learning (ICML 2014) }}</ref>
=== Bilateral filtering ===
{{Main|Bilateral filter}}
''k''-means implicitly assumes that the ordering of the input data set does not matter. The bilateral filter is similar to ''k''-means 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.<ref name="Little20112" /> 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 ==
The set of squared error minimizing cluster functions also includes the [[k-medoids|''k''-medoids]] algorithm, an approach which forces the center point of each cluster to be one of the actual points, i.e., it uses [[medoid]]s in place of [[centroid]]s.
== Software implementations ==
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).<ref name=":12" /> 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 ===
The following implementations are available under [[Free and open-source software|Free/Open Source Software]] licenses, with publicly available source code.
* [[Accord.NET]] contains C# implementations for ''k''-means, ''k''-means++ and ''k''-modes.
* [[
* [[Android (operating system)#Open-source community|AOSP]] contains a Java implementation for ''k''-means.
* [[CrimeStat]] implements two spatial ''k''-means algorithms, one of which allows the user to define the starting locations.
* [[ELKI]] contains ''k''-means (with Lloyd and MacQueen iteration, along with different initializations such as ''k''-means++ initialization) and various more advanced clustering algorithms.
* Smile contains ''k''-means and various more other algorithms and results visualization (for java, kotlin and scala).
* [[
* [[KNIME]] contains nodes for ''k''-means and ''k''-medoids.
* [[Apache Mahout|Mahout]] contains a [[MapReduce]] based ''k''-means.
* [
* [[GNU Octave|Octave]] contains ''k''-means.
* [
* [[Orange (software)|Orange]] includes a component for ''k''-means clustering with automatic selection of ''k'' and cluster silhouette scoring.
* [[PSPP]] contains ''k''-means, The QUICK CLUSTER command performs ''k''-means clustering on the dataset.
* [[R (programming language)|R]] contains three ''k''-means variations.
* [[SciPy]] and [[scikit-learn]] contain multiple ''k''-means implementations.
* [[Apache Spark|Spark]] MLlib implements a distributed ''k''-means algorithm.
* [[Torch (machine learning)|Torch]] contains an ''unsup'' package that provides ''k''-means clustering.
* [[Weka (machine learning)|Weka]] contains ''k''-means
===
The following implementations are available under [[Proprietary software|proprietary]] license terms, and may not have publicly available source code.
{{div col|colwidth=10em}}
* Ayasdi
* [[Mathematica]]
* [[MATLAB]]
* [[Origin (data analysis software)|OriginPro]]
* [[RapidMiner]]
* [[SAP HANA]]
* [[SAS System|SAS]]
* [[SPSS]]
* [[Stata]]
{{div col end}}
== See also ==
* [[K-medoids]]
* [[BFR algorithm]]
* [[Centroidal Voronoi tessellation]]
* [[
* [[DBSCAN]]
* [[Head/tail breaks]]
* [[k q-flats|''k'' ''q''-flats]]
* [[k-means++|''k''-means++]]
* [[Linde–Buzo–Gray algorithm]]
* [[Self-organizing map]]
== References ==
{{Reflist
{{DISPLAYTITLE:''k''-means clustering}}
{{DEFAULTSORT:K-Means Clustering}}
[[Category:
[[Category:
[[Category:Unsupervised learning]]
| |||