一种基于扩展区域查询的密度聚类算法  

Density clustering algorithm based on extended range query

作　　者：杨杰明[1] 吴启龙[1] 曲朝阳[1] 张慧莉 蔺洪文 吕正卓 

机构地区：[1]东北电力大学信息工程学院,吉林吉林132012 [2]吉林供电公司信息通信分公司,吉林吉林132000

出　　处：《计算机应用研究》2017年第10期2938-2941,2992,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(51277023);吉林省科技发展计划资助项目(20140204071GX)

摘　　要：针对DBSCAN算法中最小点数和最大邻域半径难以确定、算法时间开销大、对起始数据点的选择比较敏感,以及难以发现不同密度下的邻近簇等问题,提出一种基于扩展区域查询的密度聚类算法(GISN-DBSCAN)。该方法首先提出扩展区域查询算法,随后采用最近邻域和反最近邻域的邻域关系,建立每个点的k-影响空间域;最后提出一种异常点判定函数,使得算法能够准确地识别边界点和噪声点。实验结果表明,GISN-DBSCAN算法能够有效地解决DBSCAN算法的不足。There are several troublesome limitations of DBSCAN： a）parameters have to be set; b）the time consumption is intolerable in expansion ; e） it is sensitive to the density of starting points ; d） it is difficult to identify the adjacent clusters of different densities. This paper proposed an enhanced and efficient density clustering algorithm based on extended range query named GISN-DBSCAN. Firstly, it proposed an extended range query algorithm based on fixed-grids to reduce the time overhead of searching the nearest neighborhood. Then it used the nearest neighbors and reverse nearest neighbors to establish the k- influence space neighborhood of each point. Finally, it presented a computational method of k-outlierness function to distinguish the border points and noise points accurately. Experimental results demonstrate that GISN-DBSCAN can address the drawbacks of DBSCAN algorithm and identify the border points and noise points effectively.

关 键 词：密度聚类算法 扩展区域查询 k-影响空间域 边界点检测 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]