K-Means算法

K-Means是一种聚簇算法，也是最简单的无监督学习算法之一，基本思想是开始先粗略的分类，然后按照某种最优的原则修改不合理的分类，直至分类的比较合理为止，形成最终的分类结果。

K-Means算法是实践中最为常用的算法之一，在处理大数据量方面有绝对优势，而且可以取得较好的效果。K-Means算法是一种优化算法，它以最小化某个目标函数为优化准则，不断进行迭代，迭代的结果往往不是全局最优，而是局部最优，除非K个初始凝聚点选的恰到好处。

K-Means聚类基本步骤如下：

Step1: 确定K值以及初始化聚类中心，选取K个初始凝聚点，做为欲形成的中心（最简单的方法就是K的值自己确定，但必须小于数据集个数，然后从数据集中选取K个数据做为初始聚类中心）；

Step2: 计算每个数据到K个初始凝聚点的距离，将每个数据和最近的凝聚点分到一组，形成K个初始分类；

Step3: 计算初始分类的重心（或均值），做为新的凝聚点，重新计算每个数据到分类重心（或均值）的距离，将每个数据和最近的凝聚点分为一组；

Step4: 重复进行Step2和Step3，直到分类的重心或均值没有明显变化为止。

 

K-Means算法的主要影响因素：

（1）聚类个数K的确定

K值的大小以及K个初始凝聚点，作为K-Means算法的输入参数，对最终聚类结果又很大的影响，但是并没有公认的确定K值和初始凝聚点的方法，聚类的最终结果，无论是每个类内数据的个数，还是每一类别最终的质心，都依赖于初始凝聚点的选择。

         （2）初始凝聚点的选择

初始凝聚点是一批有代表性的点，是欲形成类的中心，初始凝聚点直接决定初始分类，对分类结果有很大的影响，由于初始凝聚点的不同，其最终分类结果也会出现不同。最好的选择是K个初始凝聚点之间的距离尽可能大。

初始凝聚点大体可以分为两种类型：用实际数据做为初始凝聚点和合成点作为初始凝聚点，前者是从数据集中直接抽取，而后者是经过计算才能获得，后者与前者相比，初始凝聚点的的代表性往往要高。

         （3）变量相关性

K-Means算法计算欧式距离来测量数据的远近，但欧式距离没有考虑变量间的相关性，因此K-Means聚类对变量间的相关性极端敏感，在聚类分析前需要对变量进行相关性分析。可以利用主成分分析法提取有相关关系的原始变量线性组合的主成分，把这些主成分和与任何变量都不相关的变量一起作为K-Means聚类分析的输入变量。

 

来自“邢留伟”的硕士论文