资源描述：
《一种最小生成树聚类算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、小型微型计算机系统2009年5月第5期JournalofChineseComputerSystemsVol30No.52009一种最小生成树聚类算法王小乐,刘青宝,陆昌辉,侯东风(国防科学技术大学信息系统与管理学院,湖南长沙410073)E-mai:lwx-l54@163.com摘要:现有的聚类算法都不能在输入较少参数的情况下得到任意形状任意密度的类.提出一种最小生成树的聚类算法,该算法不但能解决上述问题,还能处理高维数据,发现异常点,且具有扩展性.针对该算法提出一个目标函数,该函数根据对象的类属情况和相似度统计信息来判别聚类效果的
2、质量.最后,通过实验验证了该算法的聚类质量很好,目标函数具有良好的收敛性.关键词:聚类;相似度量;最小生成树;聚类目标函数中图分类号:TP391文献标识码:A文章编号:1000-1220(2009)05-0877-06MinimumSpanningTreeClusteringAlgorithmWANGXiao-le,LIUQing-bao,LUChang-hu,iHOUDong-feng(CollegeofInformationSystemandManagement,NationalUniversityofDefe
3、nseTechnology,Changsha410073,China)Abstract:Theexistingclusteringalgorithmcannotdiscoverclusterswitharbitraryshapeandmult-idensityusingfewparameters.InthispaperwepresentanewclusteringalgorithmnamedMSTClustwhichisbasedonminimumspanningtree.TheMSTClustcandis-coverclustersw
4、itharbitraryshapeandmult-idensity,candisposemultidimensionaldata,candetectouterpointandhaveagoodex-pansibility.InallusiontoMSTClustweproposeanobjectivefunctionwhichreferstostatisticalInformationoftheweightofedgesinminimumspanningtree.Finallytheexperimentalresultshowedthe
5、effectivenessandefficiencyofMSTClustandprovedthattheob-jectivefunctionhavegoodastringency.Keywords:clustering;similaritymeasure;minimumspanningtree;clusteringobjectivefunction1引言定.因此本文在总结现有基于MST的聚类算法和层次聚类算法的基础上,提出了一种将MST中相邻的边,根据权值大小聚类是机器学习和数据挖掘领域中的一项重要研究课题,广泛应用于模式识别和图像
6、处理中,其目的是把一个对象集分解或划分成不同的类,使同一个类中的对象尽可能彼此相似,不同类之间的对象尽可能不同.文献[1]对现有的聚类算法进行了全面总结,算法的分类如图1所示.基于图的聚类是用结点表示对象,用结点之间边的权值来表示对象之间的相似(相异)度,根据边权值的大小,分割权值较大的边,从而形成聚类.首先,构建一个无环加权图;然后,通过边的权值大小和控制参数决定合并或分裂对象集;最后,形成的子图就是一个类,用一个检验函数检验同一类内的凝聚性和不同类之间的分离性.目前基于图的聚类算法有:最[2][3][4]小生成树算法,最小割树聚类算
7、法,优势集聚类算法,[5]共享邻近图聚类算法等.现有的基于最小生成树(MinimumSpanningTree简称[1]图1聚类算法分类图MST)的聚类算法是一种分裂算法,它是根据MST中边的权Fig.1Theclassificationchartofclusteringalgorithms[1]值大小,断开权值大的边形成一个森林,森林中每棵树就是一逐步合并的聚类算法:MSTClust(AMinimumSpanningTree个聚类.算法时间复杂度为o(mlogn)(m为边数,n为顶点ClusteringArithmetic),并且设
8、计了一个聚类质量检验函数[2]数),能够处理任意形状和高维数据聚类问题.但这种基于(即目标函数),当目标函数达到最小时聚类结果为最佳.最MST聚类算法不能处理任意密度的情况,并且参数难以确后通过实验证明了该
