7,129
个编辑
更改
跳到导航
跳到搜索
第5行：
第5行： − + − k个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。+ 第17行：
第17行： − + 第27行：
第27行： − + − （1）选择k个初始中心点，例如<math> c[0] = data[0],…c[k-1] = data[k-1]</math> ；+ − + − + − + 第46行：
第46行： − + 第54行：
第54行： − （1）从n个数据对象任意选择 k 个对象作为初始聚类中心；+ 第62行：
第62行： − + − 首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。+ 第73行：
第73行： − + − + − + − + 第87行：
第87行： − + − + − + − + 第105行：
第105行： − 该算法不能保证收敛到全局最优，其结果可能取决于初始簇。由于该算法通常速度很快，因此通常会在不同的起始条件下多次运行该算法。然而，最坏情况下的性能可能会很慢：特别是某些点集，甚至在两个维度，会聚指数时间，即2 Ω（Ñ）。[13]这些点集似乎在实践中似乎没有出现：k-means的平滑运行时间是多项式，这一事实得到了证实。[14]+ + 第116行：
第117行： − + − + − + − + − + − + − + + − + 第136行：
第138行： − + 第144行：
第146行： − + + − + 第156行：
第159行： − + − + − + − 在（半）监督学习或无监督学习中，，k-means聚类被用作特征学习(或[[字典学习]])的一个步骤。[46]基本方法是：+ − + − +
无编辑摘要
k-means算法是[[硬聚类]]算法，是典型的'''基于原型的目标函数聚类'''方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。k-means算法是很典型的基于距离的聚类算法，采用'''距离'''作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。K-means算法通常以[[欧式距离]]作为[[相似度测度]]。算法采用'''误差平方'''和'''准则函数'''作为聚类准则函数。
k-means算法是[[硬聚类]]算法，是典型的'''基于原型的目标函数聚类'''方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。k-means算法是很典型的基于距离的聚类算法，采用'''距离'''作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。k-means算法通常以[[欧式距离]]作为[[相似度测度]]。算法采用'''误差平方'''和'''准则函数'''作为聚类准则函数。
==简介==
==简介==
k-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
k-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。
<math> k </math>个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一步中是随机的选取任意<math> k </math>个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。
::<math>V=\sum_{i=1}^k \sum_{x_j\in S_i} ({x_j -\mu_{i})}^2</math>
::<math>V=\sum_{i=1}^k \sum_{x_j\in S_i} ({x_j -\mu_{i})}^2</math>
算法过程如下：
算法过程如下：
（1）从 N 个文档随机选取 K 个文档作为质心
（1）从 <math> N </math>个文档随机选取<math> K </math>个文档作为质心
（2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类
（2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类
具体如下：
具体如下：
输入：<math>k</math> ,<math>data[n]</math>
输入：<math> k </math> ,<math> data[n] </math>
（1）选择<math> k </math>个初始中心点，例如<math> c[0] = data[0],…c[k-1] = data[k-1]</math> ；
（2）对于<math>data[0]….data[n]</math>，分别与<math>c[0]…c[k-1]</math>比较，假定与<math>c[i]</math>差值最少，就标记为<math>i</math>；
（2）对于<math> data[0]….data[n] </math>，分别与<math> c[0]…c[k-1] </math>比较，假定与<math> c[i] </math>差值最少，就标记为<math> i </math>；
（3）对于所有标记为i点，重新计算<math>c[i]={ 所有标记为i的data[j]之和 }/标记为i的个数</math>；
（3）对于所有标记为i点，重新计算<math> c[i]={ 所有标记为i的data[j]之和 }/标记为i的个数</math>；
（4）重复(2)(3)，直到所有<math>c[i]</math>值的变化小于给定阈值。
（4）重复(2)(3)，直到所有<math> c[i] </math>值的变化小于给定阈值。
==历史==
==历史==
==工作原理==
==工作原理==
输入：聚类个数<math>k</math>，以及包含n个数据对象的数据库。
输入：聚类个数<math> k </math>，以及包含n个数据对象的数据库。
输出：满足方差最小标准的k个聚类。
输出：满足方差最小标准的k个聚类。
'''处理流程'''
'''处理流程'''
（1）从<math> n </math>个数据对象任意选择<math> k </math>个对象作为初始聚类中心；
（2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（4）重复(2)(3)，直到每个聚类不再发生变化为止
（4）重复(2)(3)，直到每个聚类不再发生变化为止
k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means算法接受输入量<math> k </math>；然后将<math> n </math>个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
'''工作过程'''
'''工作过程'''
首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。<math> k </math>个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
==算法==
==算法==
===标准算法（朴素k-means）===
===标准算法（朴素k-means）===
最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ k-means算法”,也被称为[[劳埃德算法 Lloyd's algorithm]]，特别是在计算机科学界。有时也称为“朴素k-means”，因为存在更快的替代方法。[6]
最常见的算法使用迭代优化技术。由于它的普遍性，它通常被称为“ 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>（见下文），该算法通过以下两个步骤交替进行：[7]
给定一个初始的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 |authorlink=David MacKay (scientist) |chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf }}</ref>
'''分配步骤'''：将每个观测值分配给具有最接近均值的聚类：具有最小二乘[[欧氏距离]]的聚类。[8]（从数学上讲，这意味着根据通过该方法生成的Voronoi图划分观察结果。）
'''分配步骤'''：将每个观测值分配给具有最接近均值的聚类：具有最小二乘欧氏距离的聚类。<ref>Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.</ref> （从数学上讲，这意味着根据通过该方法生成的Voronoi图划分观察结果。）
<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \|^2 \le \big \| x_p - m^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\}</math>，
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \|^2 \le \big \| x_p - m^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\}</math>，
每个在哪里<math>x_p</math>被分配给正好一个<math>S^{(t)}</math>，即使可以将其分配给其中两个或多个。
每个在哪里<math>x_p</math>被分配给正好一个<math>S^{(t)}</math>，即使可以将其分配给其中两个或多个。
'''更新步骤'''：重新计算分配给每个聚类的观测值的均值（质心）。
'''更新步骤'''：重新计算分配给每个聚类的观测值的均值（质心）。
<math>m^{(t+1)}_i = \frac{1}{\left|S^{(t)}_i\right|} \sum_{x_j \in S^{(t)}_i} x_j </math>。
::<math>m^{(t+1)}_i = \frac{1}{\left|S^{(t)}_i\right|} \sum_{x_j \in S^{(t)}_i} x_j </math>。
当分配不再更改时，该算法已收敛。该算法不能保证找到最佳值。[9]
当分配不再更改时，该算法已收敛。该算法不能保证找到最佳值。<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>
该算法通常表示为按距离将对象分配给最近的群集。使用除（平方）[[欧氏距离]]以外的其他距离函数可能会阻止算法收敛。已经提出的改进的k-means算法，如[[spherical k-means]]和[[K-medoids]]，使用了其他距离度量。
该算法通常表示为按距离将对象分配给最近的群集。使用除（平方）[[欧氏距离]]以外的其他距离函数可能会阻止算法收敛。已经提出的改进的k-means算法，如[[spherical k-means]]和[[k-medoids]]，使用了其他距离度量。
'''初始化方法'''
'''初始化方法'''
常用的初始化方法包括Forgy方法和随机分区方法。[10]Forgy方法从数据集中随机选择k个观测值，并将其用作初始均值。随机分区方法首先为每个观测值随机分配一个聚类，然后进入更新步骤，从而计算初始均值作为聚类的随机分配点的质心。Forgy方法趋向于散布初始均值，而随机分区将所有均值都靠近数据集的中心。根据Hamerly等人的观点，[10]对于诸如[[K调和均值 K-harmonic means]]和[[模糊k均值 fuzzy k-means]]的算法，通常首选随机分配方法。为了期望最大化和标准如果采用k-means算法，则最好使用Forgy初始化方法。然而，Celebi等人的一项综合研究[11]发现，流行的初始化方法（例如：Forgy，Random Partition和Maximin）通常效果较差，而Bradley和Fayyad提出的方法[12]在表现优秀，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–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. |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>发现，流行的初始化方法（例如：Forgy，Random Partition和Maximin）通常效果较差，而Bradley和Fayyad提出的方法[12]在表现优秀，k-means++表现一般。
<gallery class="center" widths="300px" heights="300px" caption="标准算法演示">
<gallery class="center" widths="300px" heights="300px" caption="标准算法演示">
该算法不能保证收敛到全局最优，其结果可能取决于初始簇。由于该算法通常速度很快，因此通常会在不同的起始条件下多次运行该算法。然而，最坏情况下的性能可能会很慢：特别是某些点集，甚至在两个维度，会聚指数时间，即<math> 2<sup>Ω(<var>n</var>)</sup></math>。<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 }}</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>
“分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，这使得该算法成为广义期望最大化算法的变体。
“分配”步骤被称为“期望步骤”，而“更新步骤”是最大化步骤，这使得该算法成为广义期望最大化算法的变体。
===变体===
===变体===
* 用[[期望最大化算法 expectation-maximization algorithm]]（EM算法）训练的[[高斯混合模型]]确保对群集依据概率分配（非确定性分配）和多元高斯分布（非均值）。
* 用[[期望最大化算法 expectation-maximization algorithm]]（EM算法）训练的[[高斯混合模型]]确保对群集依据概率分配（非确定性分配）和多元高斯分布（非均值）。
* k-means++选择初始中心的方式可以为WCSS目标提供可证明的上限。
* k-means++选择初始中心的方式可以为WCSS目标提供可证明的上限。
* [[过滤算法 filtering algorithm]]使用[[kd树 kd-trees]]来提高每个k-means的步长。[28]
* [[过滤算法 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–892 |doi=10.1109/TPAMI.2002.1017616 |accessdate=2009-04-24 }}</ref>
* 一些方法尝试使用三角形不等式来加快每个k-means步骤。[24] [25] [26] [29] [27]
* 一些方法尝试使用三角形不等式来加快每个k-means步骤。<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" />
* 通过在集群之间交换点来逃避局部最优。[9]
* 通过在集群之间交换点来逃避局部最优。<ref name="hartigan19792" />
* [[球形k均值聚类 Spherical k-means clustering]]算法适用于文本数据。[30]
* [[球形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–175 |doi=10.1023/a:1007612920971 |doi-access=free }}</ref>
* 分层变体，例如[[二分k均值 Bisecting k-means]]，[31] [[X均值聚类 X-means clustering]][32]和[[G均值聚类 G-means clustering]][33] 反复拆分聚类以构建层次结构，还可以尝试自动确定数据集中聚类的最佳数量。
* 分层变体，例如[[二分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> 反复拆分聚类以构建层次结构，还可以尝试自动确定数据集中聚类的最佳数量。
* 内部集群评估方法（例如集群轮廓）可以帮助确定集群的数量。
* 内部集群评估方法（例如集群轮廓）可以帮助确定集群的数量。
* [[Minkowski加权k均值 Minkowski weighted k-means]]：自动计算聚类特定的特征权重，支持直观的想法，即一个特征在不同的特征上可能具有不同的相关度。[34]这些权重还可以用于重新缩放给定的数据集，增加了在预期的群集数下优化群集有效性指标的可能性。[35]
* [[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–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–145 |arxiv=1602.06989 |doi=10.1016/j.ins.2015.06.039 }}</ref>
* Mini-batch k-means：针对不适合内存的数据集使用“mini batch”样本。[36]
* 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方法===
===Hartigan-Wong方法===
Hartigan和Wong的方法[9]提供了k-means算法的一种变体，它随着不同的解决方案更新而朝着最小平方和问题的局部最小值发展。该方法是一种局部搜索，只要此过程可以改善目标函数，它就会反复尝试将样本重新放置到其他聚类中。如果无法通过改善目标将任何样本重定位到其他群集中，则该方法将停止（以局部最小值计）。以与经典k-means类似的方式，该方法仍然是一种启发式方法，因为它不一定保证最终解是全局最优的。
Hartigan和Wong的方法<ref name="hartigan19792" /> 提供了k-means算法的一种变体，它随着不同的解决方案更新而朝着最小平方和问题的局部最小值发展。该方法是一种局部搜索，只要此过程可以改善目标函数，它就会反复尝试将样本重新放置到其他聚类中。如果无法通过改善目标将任何样本重定位到其他群集中，则该方法将停止（以局部最小值计）。以与经典k-means类似的方式，该方法仍然是一种启发式方法，因为它不一定保证最终解是全局最优的。
让<math>\varphi(S_j) </math>成为<math>S_j</math>被定义为<math>\sum_{x \in S_j} (x - \mu_j)^2</math>，带有<math>\mu_j</math>集群的中心。
让<math>\varphi(S_j) </math>成为<math>S_j</math>被定义为<math>\sum_{x \in S_j} (x - \mu_j)^2</math>，带有<math>\mu_j</math>集群的中心。
<math>\Delta(m,n,x) = \varphi(S_n) + \varphi(S_m) - \varphi(S_n \smallsetminus \{ x \} ) - \varphi(S_m \cup \{ x \} )</math>。
::<math>\Delta(m,n,x) = \varphi(S_n) + \varphi(S_m) - \varphi(S_n \smallsetminus \{ x \} ) - \varphi(S_m \cup \{ x \} )</math>。
为了 <math>x,n,m</math>达到最低要求 <math>x</math>从集群中移出<math>S_n</math>到集群<math>S_m</math>。
为了 <math>x,n,m</math>达到最低要求 <math>x</math>从集群中移出<math>S_n</math>到集群<math>S_m</math>。
可以使用不同的移动接受策略。在“ 第一改进”策略中，可以应用任何改进的重定位，而在“ 最佳改进”策略中，所有可能的重定位都经过迭代测试，并且每次迭代仅应用最佳方法。前一种方法有利于速度，而后一种方法是否通常以牺牲额外的计算时间为代价而有利于解决方案质量。<math>\Delta</math>使用等式也可以有效地计算重定位的结果[37]
可以使用不同的移动接受策略。在“ 第一改进”策略中，可以应用任何改进的重定位，而在“ 最佳改进”策略中，所有可能的重定位都经过迭代测试，并且每次迭代仅应用最佳方法。前一种方法有利于速度，而后一种方法是否通常以牺牲额外的计算时间为代价而有利于解决方案质量。<math>\Delta</math>使用等式也可以有效地计算重定位的结果[37]
<math>\Delta(x,n,m) = \frac{ \mid S_n \mid }{ \mid S_n \mid - 1} \cdot \lVert \mu_n - x \rVert^2 -
::<math>\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>。
\frac{ \mid S_m \mid }{ \mid S_m \mid + 1} \cdot \lVert \mu_m - x \rVert^2</math>。
==k-means算法缺点==
==k-means算法缺点==
#在k-means算法中K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是k-means算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目K，例如[[ISODATA算法]]。关于k-means算法中聚类数目K值的确定在文献中，是根据方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分熵来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵的RPCL算法，并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。
#在k-means算法中K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是k-means算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目K，例如[[ISODATA算法]]。关于k-means算法中聚类数目K值的确定在文献中，是根据方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分熵来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵的RPCL算法，并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。
#在k-means算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为k-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。
#在k-means算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为k-means算法的一个主要问题。对于该问题的解决，许多算法采用[[遗传算法（GA）]]，例如文献中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。
#从k-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的k-means算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
#从k-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的k-means算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
===[[矢量量化]]===
===[[矢量量化]]===
k-means源于信号处理，至今仍在该领域中得到使用。例如，在计算机图形学中，颜色量化是将图像的调色板缩小为固定数量的颜色k的任务。该k-means算法可以很容易地用于此任务，并产生有竞争力的结果。这种方法的一个用例是图像分割。向量量化的其他用途还包括非随机采样，因为k-means可以轻松地用于从大型数据集中选择k个不同但原型的对象进行进一步分析。
k-means源于信号处理，至今仍在该领域中得到使用。例如，在计算机图形学中，颜色量化是将图像的调色板缩小为固定数量的颜色k的任务。该k-means算法可以很容易地用于此任务，并产生有竞争力的结果。这种方法的一个用例是图像分割。向量量化的其他用途还包括非随机采样，因为k-means可以轻松地用于从大型数据集中选择<math> k </math>个不同但原型的对象进行进一步分析。
===聚类分析===
===聚类分析===
在聚类分析中，可以使用k-means算法将输入数据集划分为 k 个分区（集群）。
在聚类分析中，可以使用k-means算法将输入数据集划分为<math> k </math>个分区（集群）。
但是，k-means算法本身不是很灵活，因此用途有限（除了上述矢量量化是k-means算法期望的使用情况）。特别地，当没有外部约束时，已知参数k难以选择。另一个限制是它不能同其他距离函数或非数值数据一起使用。在此情况下，一些其他的算法更具优势。
但是，k-means算法本身不是很灵活，因此用途有限（除了上述矢量量化是k-means算法期望的使用情况）。特别地，当没有外部约束时，已知参数<math> k </math>难以选择。另一个限制是它不能同其他距离函数或非数值数据一起使用。在此情况下，一些其他的算法更具优势。
===特征学习===
===特征学习===
在（半）监督学习或无监督学习中，k-means聚类被用作特征学习(或[[字典学习]])的一个步骤。<ref name="Coates20122">{{cite encyclopedia |year=2012 |title=Learning feature representations with ''k''-means |encyclopedia=Neural Networks: Tricks of the Trade |publisher=Springer |url=https://cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf |last2=Ng |first2=Andrew Y. |last1=Coates |first1=Adam |editors=Montavon, G.; Orr, G. B.; Müller, K.-R. }}</ref>基本方法是：
首先使用输入的训练数据（无需标记）训练k-means聚类表示。然后，将输入投影到新的特征空间中，使用“编码”函数（例如基准与基准位置的基准矩阵乘积）计算质心之间的距离,，或者简单地使用指标函数最近的质心[46] [47]或距离的平滑转换。[48]或者，通过[[高斯RBF变换]]样本群集距离，获得径向基函数网络的隐藏层。[49]
首先使用输入的训练数据（无需标记）训练k-means聚类表示。然后，将输入投影到新的特征空间中，使用“编码”函数（例如基准与基准位置的基准矩阵乘积）计算质心之间的距离,，或者简单地使用指标函数最近的质心<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>或距离的平滑转换。<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) |archiveurl=https://web.archive.org/web/20130510120705/http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf |archivedate=2013-05-10 }}</ref>或者，通过[[高斯RBF变换]]样本群集距离，获得径向基函数网络的隐藏层。<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>
k-means的这种使用已成功地与简单的线性分类器相结合，用于NLP（专门用于命名实体识别）[50]和计算机视觉中的半监督学习。在用于对象识别时，它可以通过更复杂的特征学习方法（例如自动编码器和受限的Boltzmann机器）表现出可比的性能。[48]但是，为了达到相同的效果，它通常需要更多的数据支持，因为每个数据点仅有助于一个“功能”。[46]
k-means的这种使用已成功地与简单的线性分类器相结合，用于NLP（专门用于命名实体识别）<ref>{{cite conference |last1=Lin |first1=Dekang |last2=Wu |first2=Xiaoyun |year=2009 |title=Phrase clustering for discriminative learning |url=http://www.aclweb.org/anthology/P/P09/P09-1116.pdf |conference=Annual Meeting of the [[Association for Computational Linguistics|ACL]] and IJCNLP |pages=1030–1038 }}</ref>和计算机视觉中的半监督学习。在用于对象识别时，它可以通过更复杂的特征学习方法（例如自动编码器和受限的Boltzmann机器）表现出可比的性能。<ref name="coates20112" />但是，为了达到相同的效果，它通常需要更多的数据支持，因为每个数据点仅有助于一个“功能”。<ref name="Coates20122" />
==与其他算法关系==
==与其他算法关系==