一张图就让你理解K-Means算法！！
K-Means是无监督学习中最经典的聚类算法
一、什么是无监督学习？什么是聚类？
无监督学习简单来说就是没有标签变量，即没有y值，仅仅依靠特征变量x进行学习。通常以“是否有标签变量y”区别于监督学习，例如之前所讲的决策树模型便是监督学习算法。
下图为监督学习
下图为无监督学习
聚类是将相似的对象归到同一个簇中，几乎可以应用于所有对象，聚类的对象越相似，聚类效果越好。聚类与分类的不同之处在于分类预先知道所分的类到底是什么，而聚类则预先不知道目标，但是可以通过簇识别（cluster identification）告诉我们这些簇到底都是什么。
简单地说，聚类将数据集中的样本划分为若干个不想交的子集，每个子集称为一个“簇”。通过这样的划分，每个簇可能就对应着一些潜在的概念或类别。
二、K-Means算法四大步骤
步骤一：聚类中心的初始化
步骤二：循环所有样本，判断每个样本的簇分配
步骤三：根据样本的簇分配，定义新的聚类中心
步骤四：循环步骤二、三，直至每个点的簇分配结果不再变化
上图就是K-Means算法最简单的图示，圆点为样本，叉为聚类中心。
请各位童鞋结合步骤一至四看多几次GIF图，以便于理解其中细节，因为下面将会对该图进行展开讲解。
三、K-Means算法全过程代码详解
1、读取数据
讲解的数据为两列数据，并以x1、x2进行标识，共有80个样本量
2、编写聚类中心初始化函数
首先是聚类中心数量的确定，常将聚类中心数量称为K值，那如何确定k值，在这里暂不讲解，现只能说根据数据与需求共同确定，有时候需求提出就直接将k值定为5，有时候是根据数据进行指标判断等等，这个问题将会以一个小节点详说。
其次是聚类中心初始位置的确立，图GIF中是随意的两个位置，而正常流程则是从样本的数据随机挑选k个样本作为初始聚类中心。所以这就会因为不同的初始聚类中心，产生不同的聚类结果，为避免这种情况，个人建议通过多次随机聚类，取最优的聚类结果为准。以下是聚类中心初始化函数的代码：
# 使用随机样例初始化质心(从dataset 中 调取质心)
def initCentroids(dataSet,k):
# k是指用户设定的k个种子点
# dataSet - 此处为mat对象
numSamples,dim = dataSet.shape
# numSample - 行，此处代表数据集数量 dim - 列，此处代表维度，例如只有xy轴的，dim=2 numSamples=80
centroids = np.zeros((k, dim)) # 产生k行，dim列零矩阵
for i in range(k):
index = int(np.random.uniform(0, numSamples)) # 给出一个服从均匀分布的在0~numSamples之间的整数
centroids[i, :] = dataSet[index, :] # 第index行作为种子点（质心）
return centroids3、循环所有样本，判断每个样本的簇分配
这一步考察的内容也是，首先需要计算样本点到两个聚类中心的距离，K-Means算法中常用闵可夫斯基距离，此刻K=2即为欧氏距离公式如下：
其实也就是在初中学习的点与点之间的距离，代码如下：
# 计算欧式距离
def euclDistance(vector1,vector2):
return np.sqrt(sum(pow(vector2-vector1,2))) # pow()是自带函数
接着判断样本点离哪个聚类中心的距离最短，则该聚类中心为该样本点的簇，依次循环所有样本，直至所有样本完成簇分配，代码如下：
while clusterChanged:
clusterChanged = False
## for each sample
for i in xrange(numSamples):
minDist = 100000.0 # 最小距离
minIndex = 0 # 最小距离对应的点群
for j in range(k):
distance = euclDistance(centroids[j, :], dataSet[i, :]) # 计算到数据的欧式距离
if distance < minDist: # 如果距离小于当前最小距离
minDist = distance # 则最小距离更新
minIndex = j # 对应的点群也会更新
## step 3: update its cluster
if clusterAssment[i, 0] != minIndex: # 如当前数据不属于该点群
clusterChanged = True # 聚类操作需要继续4、重新设定聚类中心
在完成所有样本点簇分配后，将所有同一类簇的样本取其均值，则均值所对应的点为下一轮计算的聚类中心。
5、以新的聚类中心，重复3、4步骤，直至所有样本的簇分配不再发生变化，此时聚类完毕，同时代价函数达到最低值。
代价函数即为所有样本点到簇距离总和，也是误差的平方和，它代表着聚类效果的误差大小，值越低则误差越小，就意味着聚类效果越好
四、聚类K参数问题及效果评估
首先最为重要的参数，聚类中心个数k的选取
第一种情况，k值由需求已确定，这时候无需考虑太多，纯暴力法计算K-means聚类效果。
第二种情况，肘击法。如下图，X轴为K值，Y轴为代价函数总和，在这里不是选取误差最小索对应的K值，而是选取一个适当的K，同时模型的误差是可接受的。所以肘击法就顾名思义，可以将曲线理解成我们的手臂，则最优点的就是我们手臂的肘，下图最优点为K=4。
第三种情况，根据轮廓系数sihouette coefficient大小进行判断，轮廓系数结合了聚类的凝聚度（Cohesion）和分离度（Separation），用于评估聚类的效果。该值处于-1~1之间，值越大，表示聚类效果越好。具体的计算方法我也不太清楚，毕竟还是挺复杂的。但是可以直接调用python机器学习包sklearn直接计算，代码如下：
在样本数据不变的情况下，效果评估方面实际与K值的选取密切相关，可以作为参考效果的指标除了轮廓系数sihouette coefficient外，还有Calinski-Harabaz等等，具体可参考 https://blog.****.net/kevinelstri/article/details/71416207。
五、总结
其实还有几个方面可以写，比如聚类效果可视化的实现，如何直接调用sklearn模块实现K-means聚类，如何改进K-means算法等等。有点懒就在此不进行详述了。
重点：只是应用的话，直接调用sklearn的包就行了