一种基于边缘度密度距的聚类算法-论文.pdf

《一种基于边缘度密度距的聚类算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4l卷第8期计算机科学Vo1．41No．82014年8月ComputerScienceAug2014一种基于边缘度密度距的聚类算法吴明晖张红喜。金苍宏蔡文明(浙江大学城市学院计算机科学与工程学系杭州310015)(浙江大学计算机科学与技术学院杭州310O27)摘要传统网格聚类算法聚类质量低，而密度聚类算法时间复杂度高。针对两类算法各自的缺点，结合它们的聚类思想提出了一种新的聚类算法。该算法提出了边缘度密度距作为新的密度度量，并在此基础上逐步确定了类的定义和聚类过程的定义。算法前期通过网格划分操作统计记录了待聚类数据的初始

2、信息，以供随后的点近邻统计使用。在寻找聚类中心点时使用了桶排序的策略，使得算法能快速地选出下一个聚类中心点。随后的聚类步骤是迭代搜索并检验当前类中未检验的七近邻是否满足密度可达性来完成聚类。理论分析和实验测试的结果表明，该算法不仅保持了较高的聚类精度，而且有接近线性的低时间复杂度。关键词聚类，网格，密度，Caed，Dbscan，Kmeans中图法分类号TP391文献标识码ADOI10．11896／j．issn．1002—137X．2014．08．052ClusterAlgorithmBasedonEdgeDensityDi

3、stanceWUMing-huiZHANGHong-xi’JINGCang-hongCAIWen-ming2(DepartmentofComputerScienceandEngineering，ZhejiangUniversityCityCollege，Hangzhou310015，China)(CollegeofComputerScienceandTechnology，ZhejiangUniversity，Hangzhou310027，China)。AbstractClusteringalgorithmsbasedong

4、ridhaveadrawbackoflowclusteringprecision，andmostclusteringalgo—rithmsbasedondensityhavehightimecomplexity．Inordertoimproveclusteringperformance，aclusteralgorithmbasedonedgedensitydistancewasproposedinthispaper．Thenewclusteralgorithmmakesnewdefinitionsofdensityandc

5、ategory．Intheclusteringprocess，dataaredividedintogridsandsomeinitialinformationisrecordedfirstlyfortheoperationoffindingknearpoints．Thenintheprocessoffindinganewclusteringcenter，amethodcomefrombucketsortisused，whichmakesitfasttofindtheclusteringcenter．Asubsequentp

6、rocedureistoiterativelyanalyseknearpointsofonecategorytojudgewhethertheyaredensityaccessible．Analysisintheoryandresultofexperimentsshowthattheproposedalgorithmhasbothhighqualityinclusteringresultandlowtimecomplexity．KeywordsCluster，Grid，Density，Caed，Dbscan，Kmeans密

7、度的方法、基于网格的方法以及基于模型的方法。上述算1前言法中，基于密度的方法和基于网格的方法是两种较为常用的随着互联网的兴起和发展，数据挖掘近年来受到各界的聚类算法。基于密度的聚类算法的指导思想就是：只要一个广泛关注。聚类算法作为一种非监督的分类方法，是数据挖区域中的点的密度大过某个阈值，就把它加到与之相近的聚掘技术中发现数据规律和数据分布最重要的方法之一[1]，是类中。基于密度的聚类算法(如Dbscan)的优点在于：抗噪音揭示数据的规则、发现数据相似性和区别性的有效途径[。性强，能克服基于距离的算法只能发现“类圆形”的聚

8、类的缺从大量的数据中挖掘数据的信息已经成为一种有力的商业竞点，能识别任意形状的类_7]。基于网格的聚类方法采用一个争。通过聚类，人们能够识别数据密集和稀疏的区域，因而发多维度的网格数据结构，它将空间量化为有限数目的单元，所现数据的分布模式0；聚类分析技术可以帮助人们更快地找有的聚类操作都在网格上进行。与