转载

利用模拟退火提高Kmeans的聚类精度

http://www.cnblogs.com/LBSer/p/4605904.html

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

利用模拟退火提高Kmeans的聚类精度

1.2 Step 2

利用模拟退火提高Kmeans的聚类精度

1.3 Step 3

利用模拟退火提高Kmeans的聚类精度

1.4 Step 4

利用模拟退火提高Kmeans的聚类精度

1.5 Step 5

利用模拟退火提高Kmeans的聚类精度

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

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

利用模拟退火提高Kmeans的聚类精度

2.1 例子

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

利用模拟退火提高Kmeans的聚类精度

迭代最终结果如下：

利用模拟退火提高Kmeans的聚类精度

如果初始点为如下：

利用模拟退火提高Kmeans的聚类精度

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

利用模拟退火提高Kmeans的聚类精度

3 解决方法

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

利用模拟退火提高Kmeans的聚类精度