资源描述：
《基于网格和最近邻居的聚类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第17卷第1期计算机辅助工程Vol.17No.12008年3月ComputerAidedEngineeringMar.2008文章编号:1006-0871(2008)0120081206基于网格和最近邻居的聚类算法陈义如,孙广中,许胤龙(中国科学技术大学省部共建高性能计算与应用重点实验室,合肥230027)摘要:针对目前已有的聚类算法不能很好地处理包含不同密度的簇数据,或者不能很好地区分相邻的密度相差不大的簇的问题,提出1种新的基于严格最近邻居和共享最近邻居的聚类算法.通过构造共享严格最近邻图,使样本点在密度一致的区域保持连接,而在密度不同的相
2、邻区域断开连接,并尽可能去除噪声点和孤立点.该算法可以处理包含有不同密度的簇数据,而且在处理高维数据时具有较低的时间复杂度.实验结果证明,该算法能有效找出不同大小、形状和密度的聚类.关键词:聚类算法;相似度;密度;网格;最近邻居中图分类号:TP301.6文献标志码:AClusteringalgorithmbasedongridandnearestneighborsCHENYiru,SUNGuangzhong,XUYinlong(AnhuiProvince2MOSTKeyCo2LabofHighPerformanceComputingandits
3、Application,Univ.ofSci.&Tech.ofChina,Hefei230027,China)Abstract:Duetothefactthatthecurrentclusteringalgorithmscannotperformwellwhileprocessingclusteringdatasetswhichcontainclusterswithdifferentdensitiesordistinguishingadjacentclusterswithsimilardensities,anewclusteringalgori
4、thmisproposedbasedonstrictnearestneighborsandsharednea2restneighbors.Thealgorithmkeepsthelinksinregionsofuniformdensityandbreaksthelinksinregionsofdifferentdensityandremovesthenoisesandisolatedpointsbyconstructingthesharedstrictnearestneighborgraph.Itprocessesdatasetscontain
5、ingclusterswithdifferentdensitiesandhaslowtimecom2plexitywhiledealingwithhighdimensionaldata.Theexperimentresultsprovethatthealgorithmcaneffi2cientlyfindclusterswithdifferingshapes,sizesanddensities.Keywords:clusteringalgorithm;similarity;density;grid;nearestneighbor[1][2][3
6、][4]means,STING,DBSCAN和Chameleon等都0引言从不同的角度对大规模、高维数据库进行分析,但各聚类是将数据对象分组成为多个类或簇,在同有优势和不足.一个簇中的对象之间具有较高相似度,而不同簇中如何找出不同大小、形状和密度的聚类,并且处的对象差别较大.聚类分析是数据挖掘重要的研究理好噪音和孤立点,确定聚类的个数,这些仍然是目领域之一,针对聚类已提出许多有效的算法,如K2前面临的挑战.我们发现,现有的聚类算法在处理的收稿日期:2007202228修回日期:2007204205基金项目:国家自然科学基金(60533020)作
7、者简介:陈义如(1983—),男,江西九江人,硕士,研究方向为数据挖掘和并行计算,(E2mail)chenyiru23@gmail.com;孙广中(1978—),男,安徽蚌埠人,讲师,博士,研究方向为机器学习、数据挖掘和并行计算,(E2mail)gzsun@ustc.edu.cn©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net82计算机辅助工程2008年2数据集中存在以下几个问题:(1)包含有不同密度要O(n
8、)的时间.通过分析还会发现,Chameleon算的簇;(2)包含有相连着密度相差不太大的簇;(3)法把类从相连的密度相差不大的簇中区分出来的能包含有大
