K-means 算法属于基于划分的聚类方法,是一种最简单的无监督学习算法,也是十大经典数据挖掘算法之一。
K-means 算法通过迭代来实现,其基本思想为:每次确定 K 个中心点,将各节点归属到与之最近的中心点所代表的 cluster,然后确定新的中心点,并继续聚类,直到聚类结果不再变化停止迭代。

K 值的选取:
算法中 K 值需要事先给定,但这个K值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。

初始中心点的选取:
初始聚类中心点唯一地决定了聚类结果,因此其选择对聚类结果有很大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果,这也是 K-means 算法的一个主要问题。

K-means 算法并不能保证得到的解为全局最优解,通常得到的是一个局部最优解。

K-means 算法确定的 K 个 cluster 达到平方误差最小。当聚类是密集的,且类与类之间区别明显时,效果比较好。对于处理大数据集,这个算法是高效和可扩展的,时间复杂度可达到最优。

改进算法:

  • K-means 要手工输入类数目,对初始值的设置很敏感,所以有了 K-means++、intelligent K-means、genetic K-means;
  • K-means 对噪声和离群值非常敏感,所以有了 K-medoids 和 K-medians;
  • K-means 只用于numerical类型数据,不适用于 categorical 类型数据,所以 K-modes;
  • K-means 不能解决非凸(non-convex)数据,所以有了 kernel K-means。