K-means聚类 - 版本历史

Gyt666：Gyt666移动页面K-means聚类 k-means clustering至K-means聚类覆盖重定向

2024-06-03T07:40:17Z

Gyt666移动页面K-means聚类 k-means clustering至K-means聚类覆盖重定向

2024年6月3日 (一) 07:38 Gyt666

2024-06-03T07:38:26Z

薄荷：/* 简介 */

2020-04-21T16:15:23Z

简介

薄荷：/* 变体 */

2020-04-21T16:14:15Z

变体

薄荷：/* 标准算法（朴素k-means） */

2020-04-21T16:13:39Z

标准算法（朴素k-means）

薄荷：/* 标准算法（朴素k-means） */

2020-04-21T16:11:30Z

标准算法（朴素k-means）

薄荷：/* 算法 */

2020-04-21T16:10:59Z

算法

薄荷：/* 标准算法（朴素k-means） */

2020-04-21T16:10:21Z

标准算法（朴素k-means）

2020年4月21日 (二) 16:09 薄荷

2020-04-21T16:09:23Z

薄荷：/* 标准算法（朴素k-means） */

2020-04-21T16:08:46Z

标准算法（朴素k-means）

←上一版本		2024年6月3日 (一) 07:38的版本
第5行：		第5行：


−	k-~~means算法是~~[[硬聚类]]算法，是典型的'''基于原型的目标函数聚类'''方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。k-means算法是很典型的基于距离的聚类算法，采用'''距离'''作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。k-means算法通常以[[欧式距离]]作为[[相似度测度]]。算法采用'''误差平方'''和'''准则函数'''作为聚类准则函数。	+	k-means算法（k-means clustering）是[[硬聚类]]算法，是典型的'''基于原型的目标函数聚类'''方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。k-means算法是很典型的基于距离的聚类算法，采用'''距离'''作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。k-means算法通常以[[欧式距离]]作为[[相似度测度]]。算法采用'''误差平方'''和'''准则函数'''作为聚类准则函数。

	==简介==		==简介==

←上一版本		2020年4月21日 (二) 16:15的版本
第15行：		第15行：


−	~~算法过程如下：~~	+	'''算法过程'''如下：

	（1）从 <math> N </math>个文档随机选取<math> K </math>个文档作为质心		（1）从 <math> N </math>个文档随机选取<math> K </math>个文档作为质心

@@ 第132行： / 第132行： @@
 * 通过在集群之间交换点来逃避局部最优。<ref name="hartigan19792" />
 * [[球形k均值聚类 Spherical k-means clustering]]算法适用于文本数据。<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&ndash;175 |doi=10.1023/a:1007612920971 |doi-access=free }}</ref>
-* 分层变体，例如[[二分k均值 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 | url = | journal = KDD Workshop on Text Mining | volume = 400 | issue = 1| pages = 525–526 }}</ref>[[X均值聚类  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]". In ''ICML'', Vol. 1</ref>和[[G均值聚类 G-means clustering]]<ref>{{cite journal | last1 = Hamerly | first1 = Greg | last2 = Elkan | first2 = Charles | year = 2004 | title =  | url = | journal = Advances in Neural Information Processing Systems | volume = 16 | issue = | page = 281 }}</ref> 反复拆分聚类以构建层次结构，还可以尝试自动确定数据集中聚类的最佳数量。
+* 分层变体，例如[[二分k均值 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 | url = | journal = KDD Workshop on Text Mining | volume = 400 | issue = 1| pages = 525–526 }}</ref>[[X均值聚类  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]". In ''ICML'', Vol. 1</ref>和[[G均值聚类 G-means clustering]]<ref>{{cite journal | last1 = Hamerly | first1 = Greg | last2 = Elkan | first2 = Charles | year = 2004 | url = | journal = Advances in Neural Information Processing Systems | volume = 16 | issue = | page = 281 }}</ref> 反复拆分聚类以构建层次结构，还可以尝试自动确定数据集中聚类的最佳数量。
 * 内部集群评估方法（例如集群轮廓）可以帮助确定集群的数量。
 * [[Minkowski加权k均值 Minkowski weighted k-means]]：自动计算聚类特定的特征权重，支持直观的想法，即一个特征在不同的特征上可能具有不同的相关度。<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&ndash;1075 |doi=10.1016/j.patcog.2011.08.012 }}</ref>这些权重还可以用于重新缩放给定的数据集，增加了在预期的群集数下优化群集有效性指标的可能性。<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&ndash;145 |arxiv=1602.06989 |doi=10.1016/j.ins.2015.06.039 }}</ref>
 * Mini-batch k-means：针对不适合内存的数据集使用“mini batch”样本。<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 |accessdate=2016-12-21 |booktitle=Proceedings of the 19th international conference on World Wide Web }}</ref>
 ===Hartigan-Wong方法===

←上一版本		2020年4月21日 (二) 16:13的版本
第84行：		第84行：
	最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ k-means算法”,也被称为[[劳埃德算法 Lloyd's algorithm]]，特别是在计算机科学界。有时也称为“朴素k-means”，因为存在更快的替代方法。<ref>{{Cite journal\|last=Pelleg\|first=Dan\|last2=Moore\|first2=Andrew\|date=1999\|title=Accelerating exact k -means algorithms with geometric reasoning\|url=http://portal.acm.org/citation.cfm?doid=312129.312248\|journal=Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '99\|language=en\|location=San Diego, California, United States\|publisher=ACM Press\|pages=277–281\|doi=10.1145/312129.312248\|isbn=9781581131437}}</ref>		最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ k-means算法”,也被称为[[劳埃德算法 Lloyd's algorithm]]，特别是在计算机科学界。有时也称为“朴素k-means”，因为存在更快的替代方法。<ref>{{Cite journal\|last=Pelleg\|first=Dan\|last2=Moore\|first2=Andrew\|date=1999\|title=Accelerating exact k -means algorithms with geometric reasoning\|url=http://portal.acm.org/citation.cfm?doid=312129.312248\|journal=Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '99\|language=en\|location=San Diego, California, United States\|publisher=ACM Press\|pages=277–281\|doi=10.1145/312129.312248\|isbn=9781581131437}}</ref>

−	给定一个初始的k均值m<sub>1</sub><sup>（1</sup>），...，m<sub>k</sub><sup>（1）</sup>（见下文），该算法通过以下两个步骤交替进行：<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 \|chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>	+	给定一个初始的k均值m<sub>1</sub><sup>（1</sup>），...，m<sub>k</sub><sup>（1）</sup>（见下文），该算法通过以下两个步骤交替进行：<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 \|ref=mackay2003 \|chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>

@@ 第82行： / 第82行： @@
 ===标准算法（朴素k-means）===
-最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ k-means算法”,也被称为[[劳埃德算法 Lloyd's algorithm]]，特别是在计算机科学界。有时也称为“朴素k-means”，因为存在更快的替代方法。<ref>{{Cite journal|last=Pelleg|first=Dan|last2=Moore|first2=Andrew|date=1999|title=Accelerating exact k -means algorithms with geometric reasoning|url=http://portal.acm.org/citation.cfm?doid=312129.312248|journal=Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '99|language=en|location=San Diego, California, United States|publisher=ACM Press|pages=277–281|doi:10.1145/312129.312248|isbn:9781581131437}}</ref>
+最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ k-means算法”,也被称为[[劳埃德算法 Lloyd's algorithm]]，特别是在计算机科学界。有时也称为“朴素k-means”，因为存在更快的替代方法。<ref>{{Cite journal|last=Pelleg|first=Dan|last2=Moore|first2=Andrew|date=1999|title=Accelerating exact k -means algorithms with geometric reasoning|url=http://portal.acm.org/citation.cfm?doid=312129.312248|journal=Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '99|language=en|location=San Diego, California, United States|publisher=ACM Press|pages=277–281|doi=10.1145/312129.312248|isbn=9781581131437}}</ref>
 给定一个初始的k均值m<sub>1</sub><sup>（1</sup>），...，m<sub>k</sub><sup>（1）</sup>（见下文），该算法通过以下两个步骤交替进行：<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&ndash;292 |chapter=Chapter 20. An Example Inference Task: Clustering |mr=2012999 |ref=mackay2003 |chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>

←上一版本	2024年6月3日 (一) 07:40的版本
（没有差异）

@@ 第106行： / 第106行： @@
 '''初始化方法'''
-常用的初始化方法包括Forgy方法和随机分区方法。<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 |booktitle=Proceedings of the eleventh international conference on Information and knowledge management (CIKM) }}</ref>Forgy方法从数据集中随机选择k个观测值，并将其用作初始均值。随机分区方法首先为每个观测值随机分配一个聚类，然后进入更新步骤，从而计算初始均值作为聚类的随机分配点的质心。Forgy方法趋向于散布初始均值，而随机分区将所有均值都靠近数据集的中心。根据Hamerly等人的观点，<ref name="hamerly4"></ref>对于诸如[[K调和均值 K-harmonic means]]和[[模糊k均值 fuzzy k-means]]的算法，通常首选随机分配方法。为了期望最大化和标准如果采用k-means算法，则最好使用Forgy初始化方法。<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&ndash;210 |arxiv=1209.1960 |doi=10.1016/j.eswa.2012.07.021 }}</ref> 然而，Celebi等人的一项综合研究<ref>{{Cite conference |last1=Bradley |first1=Paul S. |last2=Fayyad |first2=Usama M. |year=1998 |title=Refining Initial Points for ''k''-Means Clustering |book-title=Proceedings of the Fifteenth International Conference on Machine Learning }}</ref>发现，流行的初始化方法（例如：Forgy，Random Partition和Maximin）通常效果较差，而Bradley和Fayyad提出的方法<ref>{{Cite conference |last1=Bradley |first1=Paul S. |last2=Fayyad |first2=Usama M. |year=1998 |title=Refining Initial Points for ''k''-Means Clustering |book-title=Proceedings of the Fifteenth International Conference on Machine Learning }}</ref>在表现优秀，k-means++表现一般。
+常用的初始化方法包括Forgy方法和随机分区方法。<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 |booktitle=Proceedings of the eleventh international conference on Information and knowledge management (CIKM) }}</ref>Forgy方法从数据集中随机选择k个观测值，并将其用作初始均值。随机分区方法首先为每个观测值随机分配一个聚类，然后进入更新步骤，从而计算初始均值作为聚类的随机分配点的质心。Forgy方法趋向于散布初始均值，而随机分区将所有均值都靠近数据集的中心。根据Hamerly等人的观点，<ref name="hamerly4"></ref>对于诸如[[K调和均值 K-harmonic means]]和[[模糊k均值 fuzzy k-means]]的算法，通常首选随机分配方法。为了期望最大化和标准如果采用k-means算法，则最好使用Forgy初始化方法。<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&ndash;210 |arxiv=1209.1960 |doi=10.1016/j.eswa.2012.07.021 }}</ref> 然而，Celebi等人的一项综合研究<ref>{{Cite conference |last1=Bradley |first1=Paul S. |last2=Fayyad |first2=Usama M. |year=1998 |title=Refining Initial Points for ''k''-Means Clustering |book-title=Proceedings of the Fifteenth International Conference on Machine Learning }}</ref>发现，流行的初始化方法（例如：Forgy，Random Partition和Maximin）通常效果较差，而Bradley和Fayyad提出的方法<ref>{{Cite conference |last1=Bradley |first1=Paul S. |last2=Fayyad |first2=Usama M. |year=1998 |title=Refining Initial Points for ''k''-Means Clustering |book-title=Proceedings of the Fifteenth International Conference on Machine Learning }}</ref>在表现优秀，k-means++表现一般。
 <gallery class="center" widths="300px" heights="300px" caption="标准算法演示">
@@ 第116行： / 第116行： @@
-该算法不能保证收敛到全局最优，其结果可能取决于初始簇。由于该算法通常速度很快，因此通常会在不同的起始条件下多次运行该算法。然而，最坏情况下的性能可能会很慢：特别是某些点集，甚至在两个维度，会聚指数时间，即{{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&ndash;616 |doi=10.1007/s00454-011-9340-1 }}</ref> 这些点集似乎在实践中似乎没有出现：k-means的平滑运行时间是多项式，这一事实得到了证实。<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 |booktitle=Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS) |arxiv=0904.1113 }}</ref>
+该算法不能保证收敛到全局最优，其结果可能取决于初始簇。由于该算法通常速度很快，因此通常会在不同的起始条件下多次运行该算法。然而，最坏情况下的性能可能会很慢：特别是某些点集，甚至在两个维度，会聚指数时间，即{{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&ndash;616 |doi=10.1007/s00454-011-9340-1 }}</ref> 这些点集似乎在实践中似乎没有出现：k-means的平滑运行时间是多项式，这一事实得到了证实。<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 |booktitle=Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS) |arxiv=0904.1113 }}</ref>
 “分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，这使得该算法成为广义期望最大化算法的变体。

@@ 第128行： / 第128行： @@
 * 用[[期望最大化算法 expectation-maximization algorithm]]（EM算法）训练的[[高斯混合模型]]确保对群集依据概率分配（非确定性分配）和多元高斯分布（非均值）。
 * k-means++选择初始中心的方式可以为WCSS目标提供可证明的上限。
-* [[过滤算法 filtering algorithm]]使用[[kd树 kd-trees]]来提高每个k-means的步长。<ref>{{cite journal |last1=Kanungo |first1=Tapas |last2=Mount |first2=David M. |authorlink2=David Mount |authorlink3=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&ndash;892 |doi=10.1109/TPAMI.2002.1017616 |accessdate=2009-04-24 }}</ref>
+* [[过滤算法 filtering algorithm]]使用[[kd树 kd-trees]]来提高每个k-means的步长。<ref>{{cite journal |last1=Kanungo |first1=Tapas |last2=Mount |first2=David M. |last3=Netanyahu |first3=Nathan S. |last4=Piatko |first4=Christine D. |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&ndash;892 |doi=10.1109/TPAMI.2002.1017616 |accessdate=2009-04-24 }}</ref>
 * 一些方法尝试使用三角形不等式来加快每个k-means步骤。<ref name="phillips2">{{Cite book |title=Acceleration of ''k''-Means and Related Clustering Algorithms |volume=2409 |last=Phillips |first=Steven J. |date=2002-01-04 |publisher=Springer Berlin Heidelberg |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 |booktitle=Proceedings of the Twentieth International Conference on Machine Learning (ICML) }}</ref><ref name="hamerly22">{{Cite journal |title=Making ''k''-means even faster |last=Hamerly |first=Greg |citeseerx=10.1.1.187.3017 }}</ref><ref name="hamerly32">{{cite book |last1=Hamerly |first1=Greg |last2=Drake |first2=Jonathan |date=2015 |title=Accelerating Lloyd's algorithm for ''k''-means clustering |journal=Partitional Clustering Algorithms |pages=41–78 |doi=10.1007/978-3-319-09259-1_2 |isbn=978-3-319-09258-4 }}</ref><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="hartigan19792" />

@@ 第84行： / 第84行： @@
 最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ k-means算法”,也被称为[[劳埃德算法 Lloyd's algorithm]]，特别是在计算机科学界。有时也称为“朴素k-means”，因为存在更快的替代方法。<ref>{{Cite journal|last=Pelleg|first=Dan|last2=Moore|first2=Andrew|date=1999|title=Accelerating exact k -means algorithms with geometric reasoning|url=http://portal.acm.org/citation.cfm?doid=312129.312248|journal=Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '99|language=en|location=San Diego, California, United States|publisher=ACM Press|pages=277–281|doi=10.1145/312129.312248|isbn=9781581131437}}</ref>
-给定一个初始的k均值m<sub>1</sub><sup>（1</sup>），...，m<sub>k</sub><sup>（1）</sup>（见下文），该算法通过以下两个步骤交替进行：<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&ndash;292 |chapter=Chapter 20. An Example Inference Task: Clustering |mr=2012999 |ref=mackay2003 |authorlink=David MacKay (scientist) |chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>
+给定一个初始的k均值m<sub>1</sub><sup>（1</sup>），...，m<sub>k</sub><sup>（1）</sup>（见下文），该算法通过以下两个步骤交替进行：<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&ndash;292 |chapter=Chapter 20. An Example Inference Task: Clustering |mr=2012999 |ref=mackay2003 |chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>
@@ 第99行： / 第99行： @@
 ::<math>m^{(t+1)}_i = \frac{1}{\left|S^{(t)}_i\right|} \sum_{x_j \in S^{(t)}_i} x_j </math>。
-当分配不再更改时，该算法已收敛。该算法不能保证找到最佳值。<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&ndash;108 |jstor=2346830 }}</ref>
+当分配不再更改时，该算法已收敛。该算法不能保证找到最佳值。<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&ndash;108 |jstor=2346830 }}</ref>
 该算法通常表示为按距离将对象分配给最近的群集。使用除（平方）[[欧氏距离]]以外的其他距离函数可能会阻止算法收敛。已经提出的改进的k-means算法，如[[spherical k-means]]和[[k-medoids]]，使用了其他距离度量。
@@ 第119行： / 第119行： @@
 “分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，这使得该算法成为广义期望最大化算法的变体。
 ===变体===