利用模拟退火提高均值算法的聚类精度

Kmeans算法是一种非监督聚类算法,由于原理简单而在业界被广泛使用,一般在实践中遇到聚类问题往往会优先使用Kmeans尝试一把看看结果。本人在工作中对Kmeans有过多次实践,进行过用户行为聚类(MapReduce版本)、图像聚类(MPI版本)等。然而在实践中发现初始点选择与聚类结果密切相关,如果初始点选取不当,聚类结果将很差。为解决这一问题,本博文尝试将模拟退火这一启发式算法与Kmeans聚类相结合,实践表明这种方法具有较好效果,已经在实际工作中推广使用。

1 Kmeans算法原理

K-MEANS算法: 输入:聚类个数k,以及包含 n个数据对象的数据。 输出:满足方差最小标准的k个聚类。

处理流程:

  • (1)  从 n个数据对象选择 k 个对象作为初始聚类中心;
  • (2)  循环(3)到(4)直到每个聚类不再发生变化为止;
  • (3)  根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;
  • (4)  重新计算每个(有变化)聚类的均值(中心对象)

1.1 Step 1

1.2 Step 2

1.3 Step 3

1.4 Step 4

1.5 Step 5

2 初始点与聚类结果的关系

K means的结果与初始点的选择密切相关,往往陷于局部最优。

2.1 例子

下面以一个实际例子来讲初始点的选择对聚类结果的影响。首先3个中心点(分别是红绿蓝三点)被随机初始化,所有的数据点都还没有进行聚类,默认全部都标记为红色,如下图所示:

迭代最终结果如下:

如果初始点为如下:

最终会收敛到这样的结果:

3 解决方法

那怎么解决呢?一般在实际使用中,我们会随机初始化多批初始中心点,然后对不同批次的初始中心点进行聚类,运行完后选择一个相对较优的结果。这种方法不仅不够自动,而且有较大概率得不到较优的结果。目前,研究较多的是将模拟退火、遗传算法等启发式算法与Kmeans聚类相结合,这样能大大降低陷于局部最优的困境。下图就是模拟退火的算法流程图。

4 实战

“纸上得来终觉浅,绝知此事要躬行”,仅知道原理而不去实践永远不能深刻掌握某一知识。本人实现了基于模拟退火的Kmeans算法以及普通的Kmeans算法,以便进行比较分析。

4.1 实验步骤

1)首先我们随机生成二维数据点以便用于聚类。

2)基于原生的Kmeans得到的结果。

3)基于模拟退火的Kmeans得到的结果

4.2 结论

由上图的实验结果可以看出,基于模拟退火的Kmeans所得的总体误差准则结果为:19309.9。

而普通的Kmeans所得的总体误差准则结果为:23678.8。

可以看出基于模拟退火的Kmeans所得的结果较好,当然,此算法的复杂度较高,收敛所需的时间较长,尤其是在大数据环境下。

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

1 2 收藏 4 评论

关于作者:占利军

阿里巴巴RDC长期招聘资深Java研发工程师&技术专家,有意者私信联系!一个专注于后端架构、算法的工程师 个人经历: 2015 至今 阿里巴巴; 2013-2015 美团; 2010-2013 中科院(硕士); 2006-2010 浙大(本科) 个人主页 · 我的文章 · 37 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 您好,我是一名学生,最近一直也在看kmeans 的知识,看了您的这篇文章,但是还是不太理解是如何实现的,希望能够学习一下您的源码,感谢
    我邮箱是dd2013xidain@163.com 谢谢

    • 占利军 研发 2015/08/11

      抱歉,这个源码暂时不便公开,望能理解,你可以通过文章自己实现下,也不难的

  • 我们用过粒子群优化做KMeans的优化。效果也不错的。

跳到底部
返回顶部