目录1原理2算法步骤3复杂度4优缺点5合理选择k值
1原理
中小学是我们最常用的基于欧式距离的聚类算法，两个目标的距离越近相似度越高。
因为是2算法步骤，所以k均值的算法步骤如下。
将初始化的k个样本转换为初始集群中心a=a 1，a 2，a k a=a_1，a_2，a_k a=a1，a 2，ak； 针对数据集中每个样本x i x_i xi计算到k个集群中心的距离，并且针对要分类为对应于具有最小距离的集群中心的类的每个类别a j a_j aj，集群中心aj=13ci 3x 3c ixa _ j=(frac () xaj=() c ) I ) ) xaj ) ) ) c ) )重复上述2、3、2步操作，直到达到某个中止条件(反复次数、最小误差的变化等)。 3复杂度取得数据n个m维的数据随机地生成k个m维的点while(t ) for(intI=0； i n； I ) for(intj=0； j k； j )计算从点I到j类的距离for (inti=0； i k； I )1)找到属于自己类的所有数据点)2)将自己的坐标修改为这些数据点的中心点坐标end时间复杂度) o(tknm ) o(tknm ) o ) tknm )，其中t是迭代次数，k是克拉拉
空间复杂性： o
( m ( n + k ) ) O(m(n+k)) O(m(n+k))，其中，k 为簇的数目，m 为样本点维度，n 为样本点数。 4 优缺点 优点 容易理解，聚类效果不错，虽然是局部最优， 但往往局部最优就够了；处理大数据集的时候，该算法可以保证较好的伸缩性；当簇近似tmdxh分布的时候，效果非常不错；算法复杂度低。 缺点 K 值需要人为设定，不同 K 值得到的结果不一样；对初始的簇中心敏感，不同选取方式会得到不同结果；对异常值敏感；样本只能归为一类，不适合多分类任务；不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。 5 合理选择 K 值K 值的选取对 K-means 影响很大，这也是 K-means 最大的缺点，通常有四种方法。
按需选择观察法手肘法Gap Statistics方法1）按需选择
简单地说就是按照建模的需求和目的来选择聚类的个数。比如说，一个游戏公司想把所有玩家做聚类分析，分成顶级、高级、中级、菜鸟四类，那么K=4；如果房地产公司想把当地的商品房分成高中低三档，那么K=3。按需选择虽然合理，但是未必能保证在做K-Means时能够得到清晰的分界线。
2）观察法
就是用肉眼看，看这些点大概聚成几堆。这个方法虽然简单，但是同时也模棱两可。
观察法的另一个缺陷就是：原始数据维数要低，一般是两维（平面散点）或者三维（立体散点），否则人类肉眼则无法观察。对于高维数据，我们通常利用PCA降维，然后再进行肉眼观察。
3）手肘法
手肘法本质上也是一种间接的观察法。这里需要一点K-Means的背景知识。当K-Means算法完成后，我们将得到K个聚类的中心点 M i , i = 1 , 2 , ⋯ , K M_i , i=1,2,⋯,K Mi,i=1,2,⋯,K。以及每个原始点所对应的聚类 C i , i = 1 , 2 , ⋯ , K C_i,i=1,2,⋯,K Ci,i=1,2,⋯,K
。我们通常采用所有样本点到它所在的聚类的中心点的距离的和作为模型的度量，记为 D K D_K DK。
D K = ∑ i = 1 K ∑ X ∈ C i ∣ ∣ X − M i ∣ ∣ D_K=sum^K_{i=1}sum_{X in C_i}||X−Mi|| DK=i=1∑KX∈Ci∑∣∣X−Mi∣∣
这里距离可以采用欧式距离。
对于不同的K，最后我们会得到不同的中心点和聚类，所有会有不同的度量。
我们把上面的例子用不同的K去计算，会得到不同的结果。把K作为横坐标， D K D_K DK
作为纵坐标，我们可以得到下面的折线。
很显然K越大，距离和越小。但是我们注意到K=3是一个拐点，就像是我们的肘部一样，K=1到3下降很快，K=3之后趋于平稳。手肘法认为这个拐点就是最佳的K。
手肘法是一个经验方法，而且肉眼观察也因人而异，特别是遇到模棱两可的时候。相比于直接观察法，手肘法的一个优点是，适用于高维的样本数据。有时候人们也会把手肘法用于不同的度量上，如组内方差组间方差比。
这个方法是源自斯坦福几个machine learning顺心的鞋垫的paper Estimating the number of clusters in a data set via the gap statistic。这里我们要继续使用上面的 D K D_K DK。Gap Statistic的定义为
G a p ( K ) = E ( l o g D k ) − l o g D k Gap(K)=E(logD_k)−logD_k Gap(K)=E(logDk)−logDk
这里 E ( l o g D k ) E(logD_k) E(logDk)指的是 l o g D k logD_k logDk的期望。这个数值通常通过蒙特卡洛模拟产生，我们在样本里所在的矩形区域中（高维的话就是立方体区域）按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做K-Means，从而得到一个 D K D_K DK。如此往复多次，通常20次，我们可以得到20个 l o g D K logD_K logDK。对这20个数值求平均值，就得到了 E ( l o g D K ) E(logD_K) E(logDK)的近似值。最终可以计算Gap Statisitc。而Gap statistic取得最大值所对应的K就是最佳的K。
用上图的例子，我们计算了 K = 1 , 2 , . . 9 K=1,2,..9 K=1,2,..9对应的Gap Statisitc.
Gap Statistic的优点是，我们不再需要肉眼了。我们只需要找到最大gap statistic所对应的K即可。所以这种方法也适用于“批量化作业”。如果我们要做1000次聚类分析，不需要肉眼去看1000次了。所以我个人也倾向于这种方法。
参考链接：
【机器学习】K-means（非常详细）
K-means怎么选K?