Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (14): 105-114.DOI: 10.3778/j.issn.1002-8331.1812-0094

Previous Articles     Next Articles

DBSCAN Clustering Algorithm Based on Adaptive Bee Colony Optimization

HU Jian1, ZHU Haiwan2, MAO Yimin2   

  1. 1.College of Applied Science, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China
    2.School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China
  • Online:2019-07-15 Published:2019-07-11

基于自适应蜂群优化的DBSCAN聚类算法

胡  健1,朱海湾2,毛伊敏2   

  1. 1.江西理工大学 应用科学学院,江西 赣州 341000
    2.江西理工大学 信息工程学院,江西 赣州 341000

Abstract: Aiming at unreasonable global parameter settings, the difficulty of parameter selection and the impossibility of identifying overlapping modules based on density clustering algorithm DBSCAN, to overcome the disadvantage of slow convergence and being vulnerable to trap in local optima of artificial bees colony algorithm, this paper proposes a modified density-based clustering method based on the artificial bee colony optimization, named IABC-DBSCAN. First, a truncation-championship selection mechanism is proposed by combining the truncation selection mechanism and the tournament selection mechanism to enhance the diversity of the population and avoid falling into the local optimum when following bees search nectar source. Second, adaptive step strategy is designed to dynamically adjust the search behaviors of following bees, which strengthens the ability of finding the local solution of following bees and improves the clustering speed. Finally, the improved artificial bees colony is used to dynamic adjust DBSCAN’s optimal parameter, the nectar source of ABC algorithm is corresponding to the specified parameter [ε], where [ε] represents the maximum radius of a neighborhood, the income level of nectar stands for the performance of clustering. It is run on a number of test functions and data sets, which verifies the proposed algorithm. The experimental results show that the new algorithm not only overcomes the shortcoming of two original algorithm, but also the harmonic mean value of precision and recall gets greatly improved.

Key words: Density-Based Spatial Clustering of Application with Noise(DBSCAN) algorithm, artificial bee colony optimization, truncation-championship selection mechanism, adaptive step strategy, clustering

摘要: 针对传统的DBSCAN(Density-Based Spatial Clustering of Application with Noise,DBSCAN)聚类算法全局参数设置不合理、参数选取困难、无法识别重叠模块的问题,以及人工蜂群优化算法(Artificial Bees Colony,ABC)后期收敛速度慢、易陷入局部最优等缺陷进行了研究,提出一种基于自适应人工蜂群优化DBSCAN的聚类算法IABC-DBSCAN。该算法将截断选择机制与锦标赛选择机制相结合,提出一种截断-锦标赛选择机制(Truncation-Championship Selection Mechanism,TCSM),以增强种群多样性、避免跟随蜂选择蜜源陷入局部最优的缺陷;提出一种自适应步长策略(Adaptive Step Strategy,ASS)动态调整跟随蜂的搜索方式,以提高算法局部搜索能力和聚类速度;根据改进的IABC算法动态调节DBSCAN算法中的最优参数,将蜜源位置对应[ε]邻域,蜜源的适应度大小对应DBSCAN的聚类效果,并在多种测试函数和数据集上进行验证。实验结果表明,该算法不仅有效克服ABC和DBSCAN算法的缺陷,且正确率和召回率均有较大提高。

关键词: DBSCAN算法, 人工蜂群优化算法, 截断-锦标赛选择机制, 自适应步长策略, 聚类