计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (20): 80-85.

• 大数据与云计算 • 上一篇    下一篇

基于动态近邻的DBSCAN算法

李  阳,马  骊,樊锁海   

  1. 暨南大学 信息科学技术学院,广州 510632
  • 出版日期:2016-10-15 发布日期:2016-10-14

Improved DBSCAN clustering algorithm based on dynamic neighbor

LI Yang, MA Li, FAN Suohai   

  1. School of Information Science and Technology, Jinan University, Guangzhou 510632, China
  • Online:2016-10-15 Published:2016-10-14

摘要: 针对DBSCAN算法聚类参数敏感不易获取、参数固定无法适应密度不均匀数据等问题。提出了动态近邻的概念,即聚类参数随密度动态变化。设计了用于调整动态参数的近邻规模演化算法,即通过限制相对密度变化率,逐步调整近邻规模。最后根据动态的近邻规模,重新定义了DBSCAN算法核心对象的概念,并设计了基于动态近邻的DN-DBSCAN算法。仿真结果表明,DN-DBSCAN能够有效识别非凸及密度分布不均匀的数据样本,聚类效果优于传统DBSCAN算法和其他经典改进算法。

关键词: 动态近邻, DBSCAN算法, [K]近邻, 近邻密度, 相对密度变化率

Abstract: DBSCAN is a classic density-based clustering algorithm. DBSCAN algorithm has many flaws, for example: difficult to obtain sensitive parameter, can’t adapt to uneven density data because of the fixed parameter. The concept of dynamic neighbors is proposed, namely parameters changed with dynamic density. The neighbor scale evolution algorithm is designed to adjust the dynamic parameters, namely by limiting the relative density gradient, adjust the neighbor size step by step. Finally, according to the size of dynamic neighbors, it redefines the concept of core object, and designs the DN-DBSCAN algorithm. The simulation result shows that DN-DBSCAN can effectively identify the no convex and uneven distribution of density data samples, the clustering effect is better than the traditional DBSCAN algorithm and other classical improved algorithms.

Key words: dynamic neighbor, DBSCAN algorithm, [k]-nearest neighbor, neighbor density, relative density gradient