5.2.1 K-Means聚类算法
K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。K-Means算法有大量的变体，本节主要介绍传统的K-Means算法。
1.K-Means原理
K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为k个簇，并使簇内的点尽量紧密地连在一起，而让簇间的距离尽量的大。
如果用数据表达式表示，假设簇划分为（C1，C2，…，Ck），则我们的目标是最小化平方误差E：
其中，μi是簇Ci的均值向量，有时也称为质心，表达式为
想直接求上式的最小值并不容易，这是一个NP难的问题，因此只能采用启发式的迭代方法。
K-Means采用的启发式方式很简单，用图5-1就可以形象地进行描述。
图5-1 K-Means算法示例图
图5-1（a）表达了初始的数据集，假设k=2。在图5-1（b）中，随机选择了两个k类所对应的类别质心，即图中的“+”号和“*”号，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为与该样本距离最小的质心的类别。如图5-1（c）所示，经过计算样本与“+”号质心和“*”号质心的距离，可以得到所有样本点的第一轮迭代后的类别。此时我们对当前标记为实点和空心的点分别求其新的质心，如图5-1（d）所示，新的实点质心和空心点质心的位置已经发生了变动。图5-1（e）、（f）重复了我们在图（c）、（d）的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别，如图5-1（f）所示。当然在实际K-Means算法中，我们一般会多次进行图5-1（c）、（d）所示的过程，才能达到最终的比较优的类别。
2.传统K-Means算法流程
首先看看K-Means算法的一些要点。
·对于K-Means算法，首先要注意的是k值的选择，一般来说，我们会根据对数据的先验经验选择一个合适的k值，如果没有什么先验知识，则可以通过交叉验证选择一个合适的k值。
·在确定了k值后，我们需要选择k个初始化的质心，就像图5-1（b）中的随机质心。由于采用的是启发式方法，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心，最好这些质心不能太近。
传统的K-Means算法流程如下：
输入：样本集D=｛x1，x2，…，xm｝，聚类的簇数k，最大迭代次数N。
输出：簇划分C=｛C1，C2，…，Ck｝。
（1）从数据集D中随机选择k个样本作为初始的k个质心向量：｛μ1，μ2，…，μk｝；
（2）对于n=1，2，…，N，(https://www.daowen.com)
①将簇划分C初始化为Ct=∅，t=1，2…，k；
②对于i=1，2，…，m，计算样本xi和各个质心向量μj（j=1，2，…，k）的距离：dij=‖xi-μj‖2，将xi标记为最小的dij所对应的类别λi。此时更新Cλi=Cλi∪｛xi｝；
③对于j=1，2，…，k，对Cj中所有的样本点重新计算新的质心μj=
④如果所有的k个质心向量都没有发生变化，则转到步骤③。
（3）输出簇划分C=｛C1，C2，…，Ck｝。
3.K-Means与KNN的区别
初学者很容易把K-Means和KNN搞混，两者其实差别还是很大的。K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个相同过程，即找出和某一个点最近的点。两者都利用了最近邻（nearest neighbors）的思想。
4.K-Means小结
K-Means是一个简单实用的聚类算法，下面对K-Means的优缺点做一个总结。
K-Means的主要优点有：
（1）原理比较简单，实现也是很容易，收敛速度快；
（2）聚类效果较优；
（3）算法的可解释度比较强；
（4）主要需要调参的参数仅仅是簇数k。
K-Means的主要缺点有：
（1）k值的选取不好把握；
（2）对于不是凸的数据集比较难收敛；
（3）如果各隐含类别的数据不平衡，如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳；
（4）采用迭代方法，得到的结果只是局部最优；
（5）对噪声和异常点比较敏感。