一、kmeans简介
k-means：无监督学习算法，用于将给定训练样本D划分成k个类，用Ck表示。
算法原理：
(1) 随机选取k个中心点；
(2) 在第j次迭代中，对于每个样本点，选取最近的中心点，归为该类；
(3) 更新中心点为每类的均值；
(4) j<-j+1 ,重复(2)(3)迭代更新，直至误差小到某个值或者到达一定的迭代步数，误差不变.
空间复杂度 o(N)
时间复杂度 o(I*K*N)
其中N为样本点个数，K为中心点个数，I为迭代次数
算法流程伪代码
kmeans优缺点
优点：
（1）计算时间短，速度快
（2）容易解释和理解
（3）聚类效果中上
（4）适用于高维
缺点：
（1）对噪声点和孤立点很敏感(通过k-centers算法可以解决)
（2）聚类个数k初始值需提前确定
（3）初始聚类中心的不同选择可能导致完全不同的聚类结果，即产生局部最优解。
（4）需要样本存在均值
二、k-means优化
1. k均值的k值如何选取？
(1) 数据的先验知识，或者数据进行简单分析能得到
(2)基于结构的算法：根据类内距离、类间距离进行度量，如计算类内距离/类间距离，比值越小聚类效果越好；再如使用平均轮廓系数，越趋近于1，聚类效果越好。
(3)基于变化的算法：即定义一个函数，随着K的改变，认为在正确的K时会产生极值。如Gap Statistic论文，参考：gap statistic
(4)基于一致性矩阵的算法：相同k时重复多次进行聚类试验，检测聚类结果是否一致，即温。
(5)基于层次聚类：基于合并或分裂的思想，在一定情况下停止聚类从而利用层次聚类的结果获得K。
(6)交叉验证的方法，一般k都不会太大，如2-10之间.
for k in (2-10)
重复多次聚类，评价聚类效果（轮廓系数，DBI）和稳定性
选择最优的k
附：轮廓系数定义
轮廓系数结合了凝聚度和分离度，其计算步骤如下：
对于第 i 个对象，计算它到所属簇中所有其他对象的平均距离，记 ai （体现凝聚度）;
对于第 i 个对象和不包含该对象的任意簇，计算该对象到给定簇中所有对象的平均距离，记 bi （体现分离度）;
第 i 个对象的轮廓系数为 si = (bi-ai)/max(ai, bi);
从上面可以看出，轮廓系数取值为[-1, 1]，其值越大越好，且当值为负时，表明 ai<bi, 样本被分配到错误的簇中，聚类结果不可接受。对于接近0的结果，则表明聚类结果有重叠的情况。
4.k均值的初始聚类中心如何选取？
（1）基于kmeans++：聚类中心中心的距离一般都比较远
（2） 基于层次聚类： 先选用层次聚类进行初始聚类，当层次聚类达到终止条件时，将此时的K个簇的聚类中心Ck作为来作为kmeans的初始聚类中心点。关于层次聚类的停止条件，也可以根据每次迭代时的聚类效果进行度量，如平均轮廓系数、DBI系数等，当达到一定指标停止聚类，得到k个簇，或者一直聚类到一个簇，每次迭代都计算聚类性能指标，最后根据效果择优选择一个最好的k，将其聚类中心作为kmeans的初始聚类中心。
