基于SA算法的k-means聚类算法的改进

秦福高 王文琴 孙悦娟 蔡志玲

(1.常州工学院计算机信息工程学院，江苏 常州 213002;2.常州工学院教务处，江苏 常州 213002;3.河海大学计算机及信息工程学院，江苏 南京 210098)

基于SA算法的k-means聚类算法的改进

秦福高1王文琴1孙悦娟2蔡志玲3

(1.常州工学院计算机信息工程学院，江苏 常州 213002;2.常州工学院教务处，江苏 常州 213002;3.河海大学计算机及信息工程学院，江苏 南京 210098)

传统的k-means聚类算法常陷入局部最优，需要事先输入聚类数，这样会造成原有算法失效或聚类结果不准确。在研究现有聚类算法的基础上，使用ε-最近邻法剔除孤立点，提出一种改进的基于模拟退火算法的、具有自适应功能的k-means聚类算法。实验结果证明，提出的算法是可行的、有效的。

聚类;k-means算法;模拟退火算法;自适应性

0 引言

聚类分析是数据挖掘中常用的重要技术，其目的是把数据集中的对象划分成数个有意义的簇，通过分析各个簇的结果，获得数据中所隐藏的、未知的、令人感兴趣的信息。目前，聚类分析被广泛应用于市场研究、模式识别等多个领域。

传统的k-means聚类算法在收敛速度、全局优化以及自适应等方面都存在着局限性，现在许多研究人员尝试将启发式算法引入聚类分析，借助随机搜索算法找到全局最优解。通过研究发现，将启发式算法中的SA(Simulated Annealing，模拟退火)算法和k-means算法结合，可以改进聚类算法陷入局部最优的问题，但随着信息量和数据复杂程度的增加，算法本身能否做到自适应，也成为考虑的重点。如果算法在聚类过程中能够增加自学习能力，自动实现分组，则容易得到全局优化和算法准确度的均衡点，于是提出了改进的基于SA算法的k-means聚类算法。

1 传统的k-means算法及其缺点

1.1 k-means算法的思想

1.2 k-means算法的步骤

Step1 输入簇的数目k、包含n个数据的数据集D以及迭代终止条件ε。

Step2 从数据集D中任意选择k个对象作为初始中心点。

Step3 根据剩余对象到中心点的距离，将其分配到最近的簇，计算平方误差值E1。

Step4 重新计算聚类中心点，根据对象到各个中心点的距离，将其分配到最近的簇，计算平方误差值E2。

Step5 如果|E1-E2|≤ε，则迭代结束，输出k个簇，否则，E2值赋予E1，转入Step4。

1.3 k-means算法的缺点

k-means算法是基于距离的经典的聚类算法，其优点是简单、快速、易懂，对于密集型数据，聚类效果好，处理大数据集时，具有相对可伸缩性和高效性，但是该算法也存在许多缺点:

①对于“噪音”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。

②不适于发现非凸面形状的簇，或者大小差别很大的簇，因为簇采用对象的均值作为中心点。

③初始中心点选择不当，容易使算法陷入局部最优状态。不同的初始值，可能会导致不同的聚类结果。

④要求用户必须事先输入要生成的簇的数目k。很多情况下，k值只能靠人为经验进行设定，使聚类结果过于主观。

2 一种基于SA算法的k-means聚类算法

2.1 SA算法

SA算法[2]是基于 Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性，物理退火过程主要包括加温过程、等温过程和冷却过程。

SA算法类似于物理退火过程，对给定的初始解S和初始温度T，从其邻域中随机产生另一个解S1，计算△J=J(S1)- J(S)，若△J＜0或者概率P在指定范围内，则接受新解。对于温度T的每一个取值，算法持续进行“产生新解→判断→接受或舍弃”的迭代过程，迭代次数由控制参数L决定，整个过程对应着固体在某一恒定温度下趋于热平衡的过程，最终温度趋向于稳定值，对应着问题的最终解。

2.2 SA算法与k-means算法的结合

传统k-means算法的终止条件是目标函数值不再改变，如果初始中心点选在局部最小值周围，就可能陷入局部最优。SA算法的终止条件是聚类中心点不再变化，算法与初始中心点的选择关系不大，同时算法能以概率P进行随机搜索，避免局部最优，最终能以概率1收敛到全局最优值。Selim等人[3]首先将模拟退火的全局寻优思想应用到聚类领域，于是后人常常将模拟退火机制引入聚类分析，将其与k-means算法结合，利用SA算法的全局寻优能力来弥补k-means算法容易陷入局部最优的不足。

基于SA算法的k-means聚类算法的处理过程:将k-means算法聚类结果作为初始解，初始目标函数值作为初始温度T，对当前解重复“产生新解→计算目标函数差→接受或舍弃新解”的迭代过程，并逐步降低T值，算法终止时当前解为近似最优解。这种算法开始时以最快的速度找到相对较优的区域，然后进行更精确的搜索，最终找到全局最优解。

将SA算法与k-means算法进行结合，确实可以改进聚类算法陷入局部最优的问题，但是随着信息量和数据复杂程度的增加，算法能否做到自适应，也成为评判算法优劣的标准。如果算法在聚类过程中能够进行孤立点检测、初始聚类个数及中心点确定，那么在实现全局优化聚类的同时，可以一并提高算法的自适应性，所以此算法有待进一步改进。

3 改进的基于SA算法的k-means聚类算法

3.1 ε-最近邻法剔除孤立点

自适应算法在聚类前并不知道初始中心点，因此无法用基于距离的方法检测孤立点，必须用基于密度的方法检测孤立点。结合k-最近邻算法和基于密度的聚类算法，提出ε-最近邻法。

ε-最近邻法，就是检查给定对象的半径领域中的近邻数目，若近邻数大于给定阈值，则该对象称为核心对象，否则称为孤立点。处理时将核心对象标志为正常数据，孤立点标志为异常点，异常点不再对其进行聚类。

3.2 自适应思想

基于SA算法的k-means聚类方法在聚类分析时需要用户输入聚类的数目，主观性太强，且聚类结果对输入的参数敏感，这使得聚类的质量难以保证。为了提高算法的自适应性，自动对相似的数据进行聚类，确定聚类数目，引入蚁群算法。

将待聚类的n个数据随机地散布到空间中，然后将m个蚂蚁分布到这个空间内，并以概率P随机移动，当一只蚂蚁遇到一个待聚类数据xi时便将其拾起并继续随机运动，若运动路径附近的数据xj与背负的数据的相似性d(xi，xj)高于设定的阈值ε，则将其放置在该位置，然后继续移动，重复上述数据搬运过程。

3.3 数据二元化

对于正常数据 xi和xj，若两者之间的距离d(xi，xj)大于给定阈值 L，则 d(xi，xj)标为0，否则标为1，建立对象间的二元矩阵。

3.4 算法的步骤

Step1 设定阈值ε，L，N和概率P。

Step2 用ε-最近邻法剔除异常点，若对象的近邻数大于给定阈值N，则标为正常数据，若小于N，则标为异常点。

Step3 对数据进行二元化处理，若正常数据xi和xj之间的距离d(xi，xj)大于给定阈值L，则标为0，否则标为1，建立对象间的二元矩阵。

Step4 预聚类，任选一个对象xi，考察二元化矩阵，将标为1的对象和xi归为一类，依次进行直到遇到0为止，最终确定聚类个数k。

Step5 对划分的初始类，计算每个类中对象的均值作为初始中心点。

Step6 对类中的非中心点，基于模拟退火依概率P搜索法，用k-means算法将其赋给距离最近的类，并更新中心点。

Step7 比较2次聚类中心有无变化，若无变化，转Step8，否则转Step6。

Step8 终止算法，计算最终类的相似度与相异度比值，即算法紧致度，输出聚类数目、聚类中心点、算法紧致度。

4 实验结果及分析

4.1 实验结果

实验使用的数据分析平台是SAS系统，编程环境是VS6.0，通过同一个有50个对象的测试数据集分别对传统的k-means算法、基于SA算法的k-means算法、基于蚁群算法的k-means算法以及本文提出的改进的基于SA算法的k-means算法进行实验，共采集10组数据，如表1所示。

4.2 实验分析

根据表1的实验数据，在测试数据集相同的情况下，与其他3种算法相比，综合来看，本文提出的算法迭代次数较少，有明显的优势，说明收敛速度快，算法性能好;新算法的紧致度较好，算法整体上稳定而准确;新算法产生的类数目与基于蚁群算法的k-means算法基本一致，与另外2种算法相比，聚类的数目相差不大，自适应效果较好。

第3组中新算法的紧致度出现了意外，通过分析发现测试的数据对象空间分布极不规律，有的类呈非球状簇，这也证明了基于距离的聚类算法在处理非球状簇时确实存在困难。

表1 4种算法实验数据

5 结语

从实验结果看，改进的基于SA算法的 kmeans算法与传统的k-means聚类算法相比，改变了传统的k-means聚类算法在收敛速度、全局优化以及自适应等方面存在的不足。该算法在实现全局优化聚类的同时，较好地解决了孤立点检测、初始聚类个数及中心点确定的问题，提高了算法的自适应性。

[1]Jiawei Han，Micheline Kamber.数据挖掘概念与技术[M].范明，孟小峰，译.北京:机械工业出版社，2007:203-204.

[2]Metropolis N，Rosenbluth A，Rosenbluth M，et al.Equation of State Calculations by Fast Computing Machines[J].Journal of Chemical Physics，1953，21(6):1087 -1092.

[3]Selim S Z，Alsultan K.A Simulated Annealing Algorithm for the Clustering Problem[J].Patterm Recognition，1991，24(10):1003-1008.

Improvement of k-means Clustering Algorithm Based on Simulated Annealing Algorithm

QIN Fu-gao1WANG Wen-qin1SUN Yue-juan2CAI Zhi-ling3

(1.School of Computer＆ Information Engineering，Changzhou Institute of Technology，Changzhou 213002;
2.Teaching Affairs Office，Changzhou Institute of Technology，Changzhou 213002;
3.College of Computer and Information Engineering，Hohai University，Nanjing 210098)

The problem of traditional k-means clustering algorithm is that it often falls into local optimum，and needs to input clustering parameters ahead of time，which causes some disabled or inaccurate clustering results.On the basis of current clustering algorithm research，this paper proposes a kind of improved k-means clustering algorithm based on simulated annealing.The algorithm is adaptive and may remove the outliers by ε-nearest neighbor method.And its feasibility and effectiveness are proved by the experiment results.

clustering;k-means algorithm;simulated annealing algorithm;adaptability

TP311.13

A

1671-0436(2011)03/04-0021-04

2011-05-27

秦福高(1973— )，男，硕士，讲师。

责任编辑:唐海燕