K-Means算法

K-Means算法

一、算法作用:

K-Means算法的主要作用就是帮助我们进行无监督的聚类分析,也就是寻找一组一组相似的簇,在每一个簇里面的数据是比较接近的,而簇和簇之间的差距是比较大的,这就是聚类。

二、算法流程:

  1. 输入样本集D,簇的数目k,最大的迭代次数N。
  2. 给每一个簇选择一个初始的聚类中心。
  3. 将样本集按照最小距离的原则分配到最近的聚类中心,因此划分出每个簇的区域。
  4. 使用每个区域的样本均值更新聚类中心点。
  5. 重复③、④步骤,直到聚类中心点不再变化。
  6. 输出最终的聚类中心和k个簇的划分。

三、算法优缺点:

算法优点:

  1. 加入数据呈类球型分布,且簇间区分明显时则分类效果较好,且收敛较快。
  2. 算法原理简单,易于实现。

算法缺点:

  1. k值的取值十分关键,对于不同的数据集,k的取值没有参考性。
  2. 算法的时间复杂度较高O(DkN),当样本数据十分庞大时,收敛速度会大幅变慢。
  3. 对于孤立点、噪点十分敏感,会对平均值的结果造成很大影响。
  4. 不能很好的处理非类球型的数据,例如凸型数据。
  5. 结果不一定是全局最优,只能保证局部最优。

四、改进措施:

  1. 因为对离群点和噪点敏感,则使用LOF算法去除离群点和噪点后再进行聚类,可以减少离群点和孤立点对聚类效果的影响。
  2. 关于k值的选择问题,传统的K-means算法对初始聚类中心敏感,聚类结果随不同的初始聚类中心而波动.针对K-means聚类算法中随机选取初始聚类中心的缺陷,提出了一种新的基于数据分布选取初始聚类中心的K-Means++算法.

五、算法应用

word格式的公式markdown不支持,放个链接吧

K-means算法