1 .传统的k均值算法流程在前一节对k均值的原理进行了初步探讨，这里对k均值的算法进行了总结。
我们先来看看k均值算法的几个要点。
1 )在k均值算法中，首先必须注意k值的选择。 一般来说，我们可以根据数据的先验经验来选择合适的k值，如果没有先验知识的话，可以通过交叉检查来选择合适的k值。
2 )确定k的个数后，需要选择k个初始化的重心，如上图b的随机重心所示。 因为我们是启发式方法，所以k个初始化重心的位置选择会显著影响最后的聚类结果和运行时间，所以需要选择合适的k个重心，希望这些重心不会太近。
现在我们来总结一下传统的k均值算法的流程。
输入为样本集D={x1，x2， xm}D={x1，x2， xm}，集群的集群树k，最大迭代次数n
输出为集群分割C={C1，C2， Ck}C={C1，C2， Ck}
1 )从数据集d中随机选择k个样本作为初始k个重心向量(1，2，k ) (1，2，k ) )。
2 ) n=1，2，对于n
a )将聚类分割c初始化为CT=t=1，2…kct=t=1，2…k
b )对于I=1，2 . m，计算样本xixi与每个质心向量j (j=1，2， k )j ) j=1，2， k )的距离： dij=||Xij||22dij||
c )对于j=1，2，k，针对CjCj中的所有样本点重新计算新的重心j=1| CJ |xcjxj=1| CJ |xcjx (重新计算cjx
e )如果所有的k个重心向量没有变化，则进入步骤3 )
3 )输出集群分类C={C1，C2， Ck}C={C1，C2， Ck}
2. K-Means初始化优化K-Means如上节所述，k个初始化重心的位置选择对最后的聚类结果和运行时间有很大的影响，因此需要选择合适的k个重心。 如果只是完全随机的选择，算法的收敛可能会变慢。 k均值算法是k均值随机初始化质心方法的优化。
用于初始化重心的K-Means的优化策略也如下简单。
a )从输入的数据点集合中随机选择一个点作为第一个聚类中心11
b )对于数据集中的每个点xixi，确定与所选集群中心中最近的集群中心的距离d (Xi (=arg min|| Xir|| 22r=1，2， kselected ) Xi )=aad
c )选择新的数据点作为新的聚类中心。 选择原则上，d(x )d(x )大的点被选择为聚类中心的概率高
d )重复b和c，直到选择k个聚类重心
e )以这k个重心作为初始化重心执行标准的k均值算法
3.k均值距离计算优化elkan k均值传统的k均值算法在每次迭代时都需要计算所有采样点到所有质心的距离，非常耗时。 那么，关于距离的计算有什么可以简单做的吗？ elkan K-Means算法就是在此基础上加以改进的。 其目标是减少不必要的距离计算。 不需要计算的距离是什么呢？
elkan K-Means利用两边之和大于等于第三边以及两边之差小于第三边的三角形性质，减少了距离的计算。
第一个规律是对于一个采样点xx和两个质心j1、j2j1、j2。 如果计算了这两个重心之间的距离d(j1，j2 ) D ) j1，j2 )，通过计算发现了2D(X，j1(D ) j1，j2 )，就可以立即发现D ) X，j2 ) 也就是说，进一步节约了距离计算。
第二个规律是对于一个采样点xx和两个质心j1、j2j1、j2。 d(x，j2 ) max(0，d ) x，j1 ) d ) j1，j2 ) d ) x，j2 ) max ) 0，d ) x，j1 ) d ) j1，j2 ) }。 这也很容易从三角形的性质中得到。
利用以上两个定律，elkan k均值比传统的k均值迭代速度有了很大的提高。 但是，如果我们的样本特征是稀疏的，有缺失值，就不使用这个方法。 此时，如果无法计算某个距离，则无法使用该算法。
4 .大采样优化最小均值在统一k均值算法中计算所有采样点到所有质心的距离。 当样本量达到10万以上，特征达到100个以上时，传统的k均值算法非常耗时，即使加入了elkan k均值优化，仍然需要时间。 在很大的地方
数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。单纯的大雁，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。
在Mini Batch K-Means中，我们会选择一个合适的批样本大小batch size，我们仅仅用batch size个样本来做K-Means聚类。那么这batch size个样本怎么来的？一般是通过无放回的随机采样得到的。
为了增加算法的准确性，我们一般会多跑几次Mini Batch K-Means算法，用得到不同的随机采样集来得到聚类簇，选择其中最优的聚类簇。
5 K-Means与KNN初学者很容易把K-Means和KNN搞混，两者其实差别还是很大的。
K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
6. K-Means小结K-Means是个简单实用的聚类算法，这里对K-Means的优缺点做一个总结。
K-Means的主要优点有：
1）原理比较简单，实现也是很容易，收敛速度快。
2）聚类效果较优。
3）算法的可解释度比较强。
4）主要需要调参的参数仅仅是簇数k。
K-Means的主要缺点有：
1）K值的选取不好把握
2）对于不是凸的数据集比较难收敛
3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
4） 采用迭代方法，得到的结果只是局部最优。
5） 对噪音和异常点比较的敏感。