基于改进和声搜索的自适应DBSCAN算法

doi:10.3778/j.issn.1002-8331.2307-0184

摘要/Abstract

摘要： DBSCAN算法作为一种经典的聚类算法被广泛地应用于各领域，但由于其参数的自适应性较差，应用效果完全取决于参数的设置。基于此，提出了基于改进和声搜索的自适应DBSCAN算法，以提高DBSCAN算法的自适应性。算法采用K-平均最近邻算法优化初始种群，从而改善初始种群质量，为后续的进化计算提供优质解；设计了基于双差分的更新算子，提升算法的搜索能力；采用两种更新策略结构避免算法过早收敛，提高和声搜索算法的寻优能力进而全面提升DBSCAN算法的自适应性。采用多种数据集并设计对比实验验证提出的算法。实验结果表明，提出的算法具有更佳的识别能力和自适应性。

关键词: 自适应DBSCAN, 和声搜索, 参数优化, 更新算子

Abstract: As a classical clustering algorithm, DBSCAN algorithm is widely used in various fields. However, due to the poor adaptability of its parameters, the application effect depends entirely on the setting of parameters. Based on this, an adaptive DBSCAN algorithm based on improved harmony search is proposed to improve the adaptability of DBSCAN algorithm. The algorithm first uses the K-means nearest neighbor algorithm to optimize the initial population, thereby improving the quality of the initial population and providing a high-quality solution for subsequent evolutionary calculations. Secondly, an update operator based on double difference is designed to improve the search ability of the algorithm. Thirdly, two update strategy structures are used to avoid premature convergence of the algorithm, improve the optimization ability of the harmony search algorithm, and comprehensively improve the adaptability of the DBSCAN algorithm. Finally, a variety of datasets are used and comparative experiments are designed to verify the proposed algorithm. Experimental results show that the proposed algorithm has better recognition ability and adaptability.

Key words: adaptive DBSCAN, harmony search, parameter optimization, update operator

孟祥辉, 魏照坤, 张笑菊, 韩志凤. 基于改进和声搜索的自适应DBSCAN算法[J]. 计算机工程与应用, 2024, 60(6): 147-154.

MENG Xianghui, WEI Zhaokun, ZHANG Xiaoju, HAN Zhifeng. Adaptive DBSCAN Algorithm Based on Improved Harmony Search[J]. Computer Engineering and Applications, 2024, 60(6): 147-154.

参考文献

[1] BíL M, ANDRá?IK R, JANO?KA Z. Identification of hazardous road locations of traffic accidents by means of kernel density estimation and cluster significance evaluation[J]. Accident Analysis & Prevention, 2013, 55: 265-273.
[2] LEE P H, TORNG C C, LIN C H, et al. Control chart pattern recognition using spectral clustering technique and support vector machine under gamma distribution[J]. Computers & Industrial Engineering, 2022, 171: 108437.
[3] YANG S, WU J, XU Y, et al. Revealing heterogeneous spatiotemporal traffic flow patterns of urban road network via tensor decomposition-based clustering approach[J]. Physica A: Statistical Mechanics and Its Applications, 2019, 526: 120688.
[4] ZHOU Y, DAAMEN W, VELLINGA T, et al. Ship classification based on ship behavior clustering from AIS data[J]. Ocean Engineering, 2019, 175: 176-187.
[5] NAGARAJAN G, DHINESH BABU L D. Missing data imputation on biomedical data using deeply learned clustering and L2 regularized regression based on symmetric uncertainty[J]. Artificial Intelligence in Medicine, 2022, 123: 102214.
[6] RAHMAN M A, ANG L M, SENG K P. Clustering biomedical and gene expression datasets with kernel density and unique neighborhood set based vein detection[J]. Information Systems, 2020, 91: 101490.
[7] LIU X, HU C, LI P. Automatic segmentation of overlapped poplar seedling leaves combining Mask R-CNN and DBSCAN[J]. Computers and Electronics in Agriculture, 2020, 178: 105753.
[8] RUST D L, STEWART R D, WERNER T J. The duluth international airport aviation business cluster: the impact of COVID-19 and the CARES act[J]. Research in Transportation Economics, 2021, 89: 101135.
[9] 周治平, 王杰锋, 朱书伟, 等. 一种改进的自适应快速AF-DBSCAN聚类算法[J]. 智能系统学报, 2016, 11(1): 93-98.
ZHOU Z P, WANG J F, ZHU S W, et al. An improved adaptive and fast AF-DBSCAN clustering algorithm[J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 93-98.
[10] BOONCHOO T, AO X, LIU Y, et al. Grid-based DBSCAN: indexing and inference[J]. Pattern Recognition, 2019, 90: 271-284.
[11] KARAMI A, JOHANSSON R. Choosing DBSCAN parameters automatically using differential evolution[J]. International Journal of Computer Applications, 2014, 91.
[12] JIANG H, LI J, YI S, et al. A new hybrid method based on partitioning-based DBSCAN and ant clustering[J]. Expert Systems with Applications, 2011, 38(8): 9373-9381.
[13] LAI W H, ZHOU M R, HU F, et al. A new DBSCAN parameters determination method based on improved MVO[J]. IEEE Access, 2019, 7: 104085-104095.
[14] MAHDAVI M, FESANGHARY M, DAMAMGIR E. An improved harmony search algorithm for solving optimization problems[J]. Applied Mathematics and Computation, 2007, 188(2): 1567-1579.
[15] OMRAN M G H, MAHDAVI M. Global-best harmony search[J]. Applied Mathematics and Computation, 2008, 198(2): 643-656.
[16] PAN Q K, SUGANTHAN P N, TASGETIREN M F, et al. A self-adaptive global best harmony search algorithm for continuous optimization problems[J]. Applied Mathematics and Computation, 2010, 216(3): 830-848.
[17] DAS S, MUKHOPADHYAY A, ROY A, et al. Exploratory power of the harmony search algorithm: analysis and improvements for global numerical optimization[J]. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), 2011, 41(1): 89-106.
[18] ZOU D, GAO L, WU J, et al. A novel global harmony search algorithm for reliability problems[J]. Computers & Industrial Engineering, 2010, 58(2): 307-316.
[19] LI H C, ZHOU K Q, MO L P, et al. Weighted fuzzy production rule extraction using modified harmony search algorithm and BP neural network framework[J]. IEEE Access, 2020, 8: 186620-186637.
[20] MAHMOUDI S M, RAD M M, OCHBELAGH D R. Hybrid of the fuzzy logic controller with the harmony search algorithm to PWR in-core fuel management optimization[J]. Nuclear Engineering and Technology, 2021, 53(11): 3665-3674.
[21] LOOR A S, BIDGOLI M R, HAMMID M. Optimization and buckling of rupture building beams reinforced by steel fibers on the basis of adaptive improved harmony search-harmonic differential quadrature methods[J]. Case Studies in Construction Materials, 2021, 15: e00647.
[22] GUPTA S. Enhanced harmony search algorithm with non-linear control parameters for global optimization and engineering design problems[J]. Engineering with Computers, 2022, 38(4): 3539-3562.
[23] ZHU Q, TANG X, ELAHI A. Application of the novel harmony search optimization algorithm for DBSCAN clustering[J]. Expert Systems with Applications, 2021, 178: 115054.
[24] 万佳, 胡大裟, 蒋玉明. 多密度自适应确定DBSCAN算法参数的算法研究[J]. 计算机工程与应用, 2022, 58(2): 78-85.
WAN J, HU D S, JIANG Y M. Research on method of multi-density self-adaptive determination of DBSCAN algorithm parameters[J]. Computer Engineering and Applications, 2022, 58(2): 78-85.
[25] 李文杰, 闫世强, 蒋莹, 等. 自适应确定DBSCAN算法参数的算法研究[J]. 计算机工程与应用, 2019, 55(5): 1-7.
LI W J, YAN S Q, JIANG Y, et al. Research on method of self-adaptive determination of DBSCAN algorithm parameters[J]. Computer Engineering and Applications, 2019, 55(5): 1-7.
[26] 张文宇, 治瑜, 秦乐. 基于改进天牛群优化的DBSCAN聚类算法[J]. 统计与决策, 2022, 38(10): 20-25.
ZHANG W Y, ZHI Y, QIN L. DBSCAN clustering algorithm based on improved beetle swarm optimization[J]. Statistics and Decision, 2022, 38(10): 20-25.
[27] LIN M, WANG Z, CHEN D, et al. Particle swarm-differential evolution algorithm with multiple random mutation[J]. Applied Soft Computing, 2022, 120: 108640.