Density Backbone Clustering Algorithm Based on Adaptive Threshold

doi:10.3778/j.issn.1673-9418.2208003

Abstract

Abstract: The existing clustering algorithms are inaccurate to identify arbitrary clusters, sensitive to density changes within clusters, sensitive to outliers and difficult to determine the threshold. An adaptive threshold-constrained density cluster backbone clustering algorithm (DCBAT) is proposed to solve the problems. Firstly, the adaptive reachability density threshold is defined in combination with the skewness coefficient and points density mean. Under the constraint of the threshold, the core points with higher local densities and higher relative distances are grouped according to the reachability, and the initial clusters backbones are obtained. The non-core points are then assigned into the cluster which their nearest neighbors with higher density belong to. Finally, the adaptive density D-value threshold is proposed in combination with D-value mean and scale factor. According to the threshold, the initial cluster is separated at the point where the density varies sharply, and the final clusters are obtained. DCBAT fully considers the internal structure and distribution of the data when clustering, thereby improving the clustering performance. The performance of this algorithm is demonstrated compared with five excellent algorithms k-means,DBSCAN, OPTICS, CFDP and MulSim on eight datasets with various dimensions and types. DCBAT algorithm has the advantages of good recognition of arbitrary clusters, insensitivity to density changes within clusters, insensitivity to outliers and stable clustering result. Its overall performance is superior to comparison algorithms.

Key words: clustering, cluster backbone, reachability adaptive threshold of density, adaptive threshold of density D-value, arbitrary clusters

摘要： 针对现有聚类算法识别任意簇时精度不足、对簇内数据点密度变化敏感、对异常点敏感以及阈值取值难以确定等问题，提出了自适应阈值约束的密度簇主干聚类算法（DCBAT）。该算法首先结合偏度系数和数据点密度均值定义了数据点密度可达自适应阈值，在该阈值的约束下将具有较高局部密度和较高相对距离的核心点按密度可达性分组，进而得到初始簇主干。接着将非核心数据点归并到其密度较大的最近邻所在簇中，得到初始簇。最后结合簇内密度差均值和比例系数定义了密度差自适应阈值，在该阈值的约束下于簇内点密度变化剧烈处拆分初始簇，得到最终簇。DCBAT在充分考虑数据分布特点和内部结构特点的情况下进行聚类，从而提高了聚类性能。与五个优秀算法k-means、DBSCAN、OPTICS、CFDP和MulSim在八个不同维度、不同类型的数据集上的实验结果表明，DCBAT算法具有识别任意簇效果佳、对簇内点密度变化不敏感、对异常点不敏感、聚类结果精确且稳定等特点，综合性能优于对比算法。

关键词: 聚类, 簇主干, 密度可达自适应阈值, 密度差自适应阈值, 任意簇

ZHANG Jinhong, CHEN Mei, ZHANG Chi. Density Backbone Clustering Algorithm Based on Adaptive Threshold[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(12): 2880-2895.

张锦宏, 陈梅, 张弛. 自适应阈值约束的密度簇主干聚类算法[J]. 计算机科学与探索, 2023, 17(12): 2880-2895.

References

[1] GHOSAL A, NANDY A, DAS A K, et al. A short review on different clustering techniques and their applications[J]. Eme-rging Technology in Modelling and Graphics, 2020, 937: 69-83.
[2] EZUGWU A E, IKOTUNA M, OYELADE O O, et al. A comprehensive survey of clustering algorithms: state-of-the-art machine learning applications, taxonomy, challenges, and future research prospects[J]. Engineering Applications of Arti-ficial Intelligence, 2022, 110: 104743.
[3] 陈梅. 面向复杂数据的聚类算法研究[D]. 兰州: 兰州大学, 2016.
CHEN M. Research on clustering algorithm for complex data[D]. Lanzhou: Lanzhou University, 2016.
[4] KRP A, DS A, GFSA B. Clustering cryo-EM images of helical protein polymers for helical reconstructions[J]. Ultramicro-scopy, 2019, 203: 132-138.
[5] NGUYEN T T, KRISHNAKUMARI P, CALVERT S C, et al. Feature extraction and clustering analysis of highway con-gestion[J]. Transportation Research Part C: Emerging Tech-nologies, 2019, 100: 238-258.
[6] CHEN Y W, HUX L, FAN W T, et al. Fast density peak clustering for large scale data based on kNN[J]. Knowledge-Based Systems, 2020, 187: 104824.
[7] 刘苏, 黄纯, 侯帅帅, 等. 基于DDTW距离与DBSCAN算法的户变关系识别方法[J]. 电力系统自动化, 2021, 45(18): 71-77.
LIU S, HUANG C, HOU S S, et al. Identification method for household-transformer relationship based on derivative dynamic time warping distance and density-based spatial clustering of application with noise algorithm[J]. Automa-tion of Electric Power Systems, 2021, 45(18): 71-77.
[8] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Proba-bility, Berkeley, Jun 21-Jul 18, 1965. Berkeley: University of California Press, 1967: 281-297.
[9] ZHANG Q P, COULOIGNER I. A new and efficient k-medoid algorithm for spatial clustering[C]//LNCS 3482: Pro-ceedings of the 2005 International Conference on Compu-tational Science and Its Applications, Singapore, May 9-12, 2005. Berlin, Heidelberg: Springer, 2005: 181-189.
[10] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial data-bases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park: AAAI, 1996: 226-231.
[11] BHATTACHARJEE N, MITRA N. A survey of density based clustering algorithms[J]. Frontiers of Computer Science, 2021, 15(1): 139-165.
[12] ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS: ordering points to identify the clustering structure[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, Philadelphia, Jun 1-3, 1999. New York: ACM, 1999: 49-60.
[13] KARYPIS G, HAN E H, KUMAR V. Chameleon: hierarc-hical clustering using dynamic modeling[J]. IEEE Computer, 1999, 32(8): 68-75.
[14] WANG W H, YANG J J, MUNTZ R. STING: a statistical information grid approach to spatial data mining[C]//Pro-ceedings of the 23rd International Conference on Very Large Data Bases, Athens, Aug 25-29, 1997. San Francisco: Morgan Kaufmann Publishers Inc., 1997: 186-195.
[15] 万佳, 胡大裟, 蒋玉明. 多密度自适应确定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 algo-rithm parameters[J]. Computer Engineering and Applications, 2022, 58(2): 78-85.
[16] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[17] MONATH N, DUBEY K A, GURUGANESH G, et al. Scalable hierarchical agglomerative clustering[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Dis-covery and Data Mining, Singapore, Aug 14-18, 2021. New York: ACM, 2021: 1245-1255.
[18] CHEN M, WEN X F, YANG Z C, et al. MulSim: a novel similar-to-multiple-point clustering algorithm[J]. IEEE Access, 2018, 6: 78225-78237.
[19] 夏鲁宁, 荆继武. SA-DBSCAN:一种自适应基于密度聚类算法[J]. 中国科学院研究生院学报, 2009, 26(4): 530-538.
XIA L N, JING J W. SA-DBSCAN: a self-adaptive density-based clustering algorithm[J]. Journal of the Graduate School of the Chinese Academy of Sciences, 2009, 26(4): 530-538.
[20] 陈昊, 侯慧群, 杨承志, 等. SA-BFSN: 一种自适应基于密度聚类的算法[J]. 计算机工程与应用, 2012, 48(36): 186-189.
CHEN H, HOU H Q, YANG C Z, et al. SA-BFSN: adaptive algorithm based on density clustering[J]. Computer Enginee-ring and Applications, 2012, 48(36): 186-189.
[21] 钱江波, 董逸生. 一种基于广度优先搜索邻居的聚类算法[J]. 东南大学学报(自然科学版), 2004(1): 109-112.
QIAN J B, DONG Y S. A clustering algorithm based on broad first searching neighbors[J]. Journal of Southeast Uni-versity (Natural Science Edition), 2004(1): 109-112.
[22] 马淑华, 尤海荣, 唐亮, 等. 一种自适应的密度峰值聚类算法[J]. 东北大学学报(自然科学版), 2022, 43(6): 761-768.
MA S H, YOU H R, TANG L, et al. An adaptive density peak clustering algorithm[J]. Journal of Northeastern University (Natural Science), 2022, 43(6): 761-768.
[23] 周董, 刘鹏. VDBSCAN: 变密度聚类算法[J]. 计算机工程与应用, 2009, 45(11): 137-141.
ZHOU D, LIU P. VDBSCAN: variable density based clustering algorithm[J]. Computer Engineering and Applica-tions, 2009, 45(11): 137-141.
[24] 陈延伟, 赵兴旺. 基于边界点检测的变密度聚类算法[J]. 计算机应用, 2022, 42(8): 2450-2460.
CHEN Y W, ZHAO X W. Variable density clustering algo-rithm based on border point detection[J]. Computer Appli-cations, 2022, 42(8): 2450-2460.
[25] 孙璐, 梁永全. 融合网格划分和DBSCAN的改进聚类算法[J]. 计算机工程与应用, 2022, 58(14): 73-79.
SUN L, LIANG Y Q. Improved clustering algorithm fusing grid partition and DBSCAN[J]. Computer Engineering and Applications, 2022, 58(14): 73-79.
[26] BEIS J S, LOWE D G. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[C]//Proceedings of the 1997 IEEE Conference on Computer Vision and Pattern Recognition, San Juan, Jun 17-19, 1997. Washington: IEEE Computer Society, 1997: 1000-1006.