k-means

原理：

初始随机选取k个中心点；遍历每个样本，选取距离该样本最近的中心点，归为该类；更新中心点为每类的均值；迭代(2)(3)，直至达到迭代次数或误差小于阈值

 

适用条件：

不适用于非凸面形状的簇或大小差别很大的簇

需要实现确定簇数 / 对初始质心和离群点敏感 / 局部最优解(SSE为非凸函数）

 

k的确定：

行业经验确定 vs. 数据的真实聚类数

Elbow method:

核心指标：SSE (预测值为样本点，真实值为质心，SSE为所有样本的聚类误差）核心思想：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓。SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数

轮廓系数法：

核心指标：轮廓系数（样本点到其它某簇所有样本的平均距离，样本点到同簇其它样本的平均聚类）核心思想：轮廓系数取值范围为:[-1,1]，其值越大，聚类效果越好；求出所有样本的轮廓系数后再求平均得到平均轮廓系数，平均轮廓系数最大的k就是最佳聚类数

对比：轮廓系数法相比手肘法，在凝聚度基础上，引入了分离度，从而考虑到了聚类划分的程度，但同时会存在凝聚度和分离度都较大且分离度相对凝聚度大得多的情况，从而导致SSE较大（因此轮廓系数法确定的k值不一定最优）

 

sklearn参数：

n_clusters：The number of clusters to form as well as the number of centroids to generate. (default=8)init: 质心初始化方案 (default=’k-means++’) ‘random’: choose n_clusters observations (rows) at random from data'k-means++'：基本思想是初始的聚类中心之间的相互距离要尽可能的远 (speed up convergence)多维数组 (ndarray)：should be of shape (n_clusters, n_features)n_init：Number of time the k-means algorithm will be run with different centroid seeds. The final results will be the best output of n_init consecutive runs (default=10)max_iter：Maximum number of iterations of the k-means algorithm for a single run. (default=300)algorithm: auto / full / elkan

 

Notes

收敛：

      向某一值靠近

      "函数的收敛与否与凹凸性没有直接关系，因为存在收敛到局部最优的可能，比如kmeans就经常出现这样的情况。因为每一次迭代都可以计算出一个目标函数的值，只需要证明这个目标函数的级数是单调有界的，就可以说明目标函数收敛。当然，这个收敛并不能保证每次都达到全局最优解。只有在目标函数为凸的情况下才能保证收敛后的结果是全局最优。分析损失函数的凹凸性，最终极的办法就是根据凸函数的定义来进行证明。有些情况下这个这种证明会复杂一些，可以根据一些简单的几何性质进行分析，比如l-1 norm和 l-2norm都是convex的，但是l-0 norm却不是，这个直接从函数的几何性质就可以观察出来。再比如说在二次优化问题中，只需要满足变量的二阶导数是正定矩阵就可以保证目标函数是凸函数，所以只需要二次项的系数为正定矩阵就可以了。"

      google机器学习

 

Reference

K-means聚类最优k值的选取