K均值聚类算法

0. 简介:

聚类是一种无监督的学习方式,它将相似的对象归到同一个簇中。聚类算法几乎可以应用于所有的对象,簇内的对象越相似,聚类的效果越好;

 

1. 优缺点

  • 优点:容易实现;
  • 缺点:可能收敛到局部最小值,在大规模数据上面收敛比较慢;
  • 数据:数值型数据;

 

2. 算法伪代码

 

3. 度量聚类效果的方法:

  1. SSE(Sum of Squared Error,误差平方和)。
    1. SSE值越小表示数据点越接近它们的质心;
    2. 增加k值肯定能降低SSE值;
  2. 对聚类结果的改进
    1. 拆分:将具有最大SSE值得簇划分成两个簇。具体实现可以将最大簇包含的点过滤出来并在这些点上运行k-均值算法,其中的k设置为2;
    2. 合并:为了保持簇的总数不变,可以将两个簇进行合并;有两种合并的方法;
      1. 合并最近的质心:计算所有质心之间的距离,然后合并距离最近的两个点来实现;
      2. 合并两个使得SSE增幅最小的质心:合并两个簇然后计算总的SSE值;

 

4. 二分K-均值算法(bisecting K-means)

为了克服k均值算法收敛于局部最小值的问题,可以使用二分K-均值算法(bisecting K-means)。该算法首先将所有的点作为一个簇,然后将该簇一分为二,之后选择其中的一个簇进行划分直到得到用户指定的簇数目为止;选择哪一个簇取决于对其划分是否可以最大程度降低SSE的值;

伪代码如下:

 

5. 参考代码

6. 参考文献

  • 《机器学习实战》中文版

 

此条目发表在NLP&ML分类目录。将固定链接加入收藏夹。

发表评论