基于K—means的最小生成树聚类算法.pdf

《基于K—means的最小生成树聚类算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4期组合机床与自动化加工技术NO．42014年4月ModularMachineTool&AutomaticManufacturingTechniqueApr．2014文章编号：1001—2265(2014)04—0041—04DOI：10．13462／j．cnki．mmtamt．2014．04．011基于K—means的最小生成树聚类算法术欧阳浩，陈波，黄镇谨，王萌，王智文(广西科技大学计算机学院，广西柳州545006)摘要：传统的K．means算法只能识别出类似球形的数据集，传统的MST聚类算法虽然能识别任意形状的数据集，但对噪声和异常点十分敏感，由此提出了一种将K．means聚

2、类与MST聚类相结合的聚类算法。此算法先使用K．means算法将数据分割成多个小的类似球形的数据集，然后对各个小的数据集的均值点采用MST聚类算法进行聚类分析。实验证明此算法具有较好的抗干扰性，并且可以识别出任意形状分布的数据集。为了评价聚类算法的性能，文中同时提出了一种新的聚类质量评价函数，实验证明此评价函数是有效的。关键词：聚类分析；K．means；最小生成树；质量评价函数中图分类号：TH122：TG65文献标识码：AMSTClusteringAlgorithmBasedonK-meallsOUYANGHao．CHENBo，HUANGZhen-jin，WANGMeng，WANGZ

3、hi—wen(ComputerSchool，GuangxiUniversityofScienceandTechnology，LiuzhouGuangxi545006，China)Abstract：ClassicalK—meansonlycandistinguishsimilarsphere—cluster，classicalMSTclusteringalgorithmcandistinguisharbitrarycluster，butit’Sverysensitivetonoisyandabnormaldata，thepapercombineK—meansandMSTclusteri

4、ngalgorithm．Firstly．K—meansalgorithmdividesdatatomanysimilarminisphere·clusters，andthenMSTclusteringalgorithmdealswithmeanpointsoftheseminisphere—clusters．Resultsshowthatthenewalgorithmhasgoodanti—noisyability，andcandistinguisharbitrarycluster．Inordertoan—alyzethequalityofclustering，thepaperpro

5、videsanewqualityevaluationfunction．Resultsshowthefunc—tioniseffective．Keywords：clusteringanalysis；K—means；MST；qualityevaluationfunctionO引言象划分到不同的簇中，以求目标函数的最小化。其K-means算法¨由于简单、快速的特点，在现实生中，通常采用的目标函数形式为平均误差标准准则活中得到广泛的应用剖。但传统的K．means算法也函数：k存在一些缺陷：①要求预先给定一个确定的k值；E=∑∑IlP—CiJI②对初始聚类中心敏感；③只能发现球形或圆形的簇；i

6、=1PECi④算法对“噪声”和孤立点敏感。1．2最小生成树聚类算法MST聚类算法是对所有的数据点建立最小生最小生成树聚类算法建立在完全图的邻接矩阵基础成树，再去掉最小树的若干个最大边，从而得到多个上。首先需构建赋权完全图。在得到各点的距离的邻接簇。此方法可以发现任意形状的簇，但实际应用中矩阵后，便利用Kruskal或者Prim算法找最小生成树，再容易受到“噪声”的影响。删除掉最小生成树中权值最大的K一1条边。这样将得针对标准K-means算法和MST聚类算法不足，本到K个子树，这K个子树就是K个簇，如图1所示。文做了以下改进：将K．means算法与MST聚类算法结合，可以有效地减少“

7、噪声”对聚类结果的影响，且能发现任意形状的簇。lK．means聚类算法和最小生成树聚类算法1．1K．means聚类算法K．Means算法的核心思想是通过迭代把数据对图1MST聚类收稿日期：2013—08—12；修回日期：2013—09—17十基金项目：广西自然科学基金项目(2013GXNSFAA019336)；广西自然科学基金项目(2013GXNSFBA019280)；广西壮族自治区教育厅项目(201203YB124)；广西科技大学科学基金(校科自1261