基于模拟退火的K调和均值聚类算法.pdf

计算机系统应用http://www.c-s-a.org.cn2011年第20卷第7期

基于模拟退火的K调和均值聚类算法①

刘国丽，甄晓敏
(河北工业大学计算机科学与软件学院，天津300401)

摘要：K均值算法是最通用的划分聚类算法，然而它有高度依赖初始值和收敛于局部最小的缺点，K调和均值
算法采用数据点与所有聚类中心的距离的调和平均替代了数据点与聚类中心的最小距离，解决了K均值算法对
初值敏感的问题。这样虽然解决初始值敏感问题，局部最小收敛问题仍然存在。为了获得全局最优解，提出一
种新的算法：基于模拟退火算法的K调和均值聚类。该算法将一种优秀的随机搜索算法——模拟退火算法引入
K调和均值聚类，来解决局部最小收敛的问题，并将改进后的算法用于IRIS数据集的聚类分析，聚类结果与K
均值算法结果对比，证明了改进算法的优越性。
关键词：聚类；K均值；调和均值；模拟退火；局部最小

K-HarmonicMeansClusteringwithSimulatedAnnealing
LIUGuo-Li,ZHENXiao-Min
(DepartmentofComputerScienceandSoftware,HebeiUniversityofTechnology,Tianjin300401,China)

Abstract:K-meansalgorithmisafrequently-usedmethodsofpartitionclustering.However,itgreatlydependsonthe
initialvaluesandconvergestolocalminimum.InK-harmonicmeansclustering,harmonicmeansfuctionwhichapply
distancefromthedatapointtoallclusteringcentersisusedtosolvestheproblemthatclusteringresultissensitivetothe
initialvalveinsteadoftheminimumdistance.Althoughtheproblemaboveissolved,theproblemconvergedtolocal
minimumisstillexisted.Inordertoobtainaglonaloptimalsolution,inthispaper,anewalgorithmcalledK-harmonic
meansclusteringalgorithmwithsimulatedannealingwasproposed.Thisalhorithmisintroducedintosimulated
annealingtosolvethetheproblemsoflocalminimum.ThenthealgorithmwasusedtoanalyseIRISdatasetandgeta
conclutionthatthenewalgorithmgetaglonaloptimalsolutionandreachedadesiredeffect.
Keywords:clustering;K-means;K-Harmonicmeans;simulatedannealing;localminimum

1引言（SA）算法相结合而成的新算法，这种新算法称为基
K均值（KM）算法是一种简单高效的聚类算法，于模拟退火的K调和均值（SAKHM）聚类算法。
实际应用价值很高，因此很多学者对K均值算法的研
究非常感兴趣，他们试图从不同的角度来改善K均值2K调和均值聚类算法
算法，使它能够有更好的效果。现在已经有了许多对2.1K均值算法
K均值改进的方法，有基于密度蚂蚁思想的K均值算KM算法是一种常用的基于划分的聚类算法,是最
法,基于分层聚类的K均值算法，基于粗糙集的K均早提出的较为经典的聚类算法。算法以k为参数,把n
值聚类算法，基于遗传算法的K均值聚类；另外还有个数据对象分为k个类,使类内具有较高的相似度,而
引入学习特征权值、最小生成树原理、三角不等式原类间有较低的相似度。这里相似度的计算采用欧几里
理以及核学习方法来改进K均值的算法。本文研究并德距离,类的中心则用类中对象的平均值来表示。KM
改进了一种由K调和均值（KHM）算法和模拟退火算法思想简单、易实现,而且收敛速度较快,具有可伸缩

①收稿时间:2010-10-26;收到修改稿时间:2010-12-03

90研究开发ResearchandDevelopment
2011年第20卷第7期http://www.c-s-a.org.cn计算机系统应用

性和高效率性;但是也有两个缺点：算法结果依