[1]CHEN Wei,LYU Li,XIAO Renbin,et al.Density peak clustering algorithm based on symmetric neighborhood and micro-cluster merging for mixed datasets[J].CAAI Transactions on Intelligent Systems,2025,20(1):172-184.[doi:10.11992/tis.202311005]
Copy

Density peak clustering algorithm based on symmetric neighborhood and micro-cluster merging for mixed datasets

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 20 Number of periods: 2025 1 Page number: 172-184 Column: 学术论文—人工智能基础 Public date: 2025-01-05
Title:
Density peak clustering algorithm based on symmetric neighborhood and micro-cluster merging for mixed datasets
Author(s):
CHEN Wei1; 2;  LYU Li1; 2;  XIAO Renbin3;  TAN Dekun1; 2;  PAN Zhengxiang4
1. School of Information Engineering, Nanchang Institute of Technology, Nanchang 330099, China;
2. Nanchang Key Laboratory of IoT Perception and Collaborative Computing for Smart City, Nanchang Institute of Technology, Nanchang 330099, China;
3. School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China;
4. School of Computer Science and Engineering, Shandong University Of Science And Technology, Qingdao 266590, China
Keywords:
density peaks clustering; uneven density; manifold data; K near neighbour; inverse close neighbor; symmetric neighborhood; similarity between micro-clusters; micro-cluster merging
CLC:
TP301
DOI:
10.11992/tis.202311005
Abstract:
Mixed data refers to datasets containing uneven density distribution and streaming features. The local density definition of density peak clustering algorithm is apt to ignore the sparsity difference of samples between clusters of uneven density distribution dataset, which leads to misselection of clustering centers; the allocation strategy is based on the Euclidean distance for the allocation of the samples, which is not applicable to the streaming dataset with the same type of clusters in the case of the samples far away, resulting in the samples being misallocated. In this paper, we propose a density peak clustering algorithm based on symmetric neighborhood and micro-cluster merging for mixed datasets algorithm (DPC-SNMM). The algorithm introduces the concept of symmetric neighborhood and redefines the local density by using the logarithmic inverse cumulative method, which effectively improves the identification of clustering centers; at the same time, it proposes a method of selecting the number of micro-clusters based on the difference of densities, which puts the selection of micro-clusters in a reasonable range; moreover, it designs an inter-micro-cluster similarity metric to perform the micro-cluster merging, which avoids the cascading errors generated during the allocation. Experiments show that compared with comparison algorithms, the algorithm in this paper achieves better clustering results on mixed datasets, UCI datasets and image datasets.
References:
[1] ZHANG Wei, DU Lan, LI Liling, et al. Infinite Bayesian one-class support vector machine based on Dirichlet process mixture clustering[J]. Pattern recognition, 2018, 78: 56-78.
[2] ZHANG Jie, YAO Pengpeng, WU H, et al. Automatic color pattern recognition of multispectral printed fabric images[J]. Journal of intelligent manufacturing, 2023, 34(6): 2747-2763.
[3] JAIN A K, DUIN R P W, MAO Jianchang. Statistical pattern recognition: a review[J]. IEEE transactions on pattern analysis and machine intelligence, 2000, 22(1): 4-37.
[4] NIE Chunxiao, SONG Futie. Analyzing the stock market based on the structure of kNN network[J]. Chaos, solitons & fractals, 2018, 113: 148-159.
[5] LIU Xiuwen, FU Jianming, CHEN Yanjiao. Event evolution model for cybersecurity event mining in tweet streams[J]. Information sciences, 2020, 524: 254-276.
[6] HE Song, HE Haochen, XU Wenjian, et al. ICM: a web server for integrated clustering of multi-dimensional biomedical data[J]. Nucleic acids research, 2016, 44(W1): W154-W159.
[7] GAO Chenhui, CHEN Wenzhi, NIE Feiping, et al. Subspace clustering by directly solving discriminative K-means[J]. Knowledge-based systems, 2022, 252: 109452.
[8] HORNG S C, YANG Fengyi, LIN S S. Hierarchical fuzzy clustering decision tree for classifying recipes of ion implanter[J]. Expert systems with applications, 2011, 38(1): 933-940.
[9] LIN Chuan, HAN Guangjie, WANG Tingting, et al. Fast node clustering based on an improved birch algorithm for data collection towards software-defined underwater acoustic sensor networks[J]. IEEE sensors journal, 2021, 21(22): 25480-25488.
[10] CHOI J W, PARK G M, KIM J H. SR-EM: episodic memory aware of semantic relations based on hierarchical clustering resonance network[J]. IEEE transactions on cybernetics, 2022, 52(10): 10339-10351.
[11] WANG Yue fei, JIONG Yu, SU Guo ping, et al. A new outlier detection method based on OPTICS[J]. Sustainable cities and society, 2019, 45: 197-212.
[12] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[13] 陈蔚昌, 赵嘉, 肖人彬, 等. 面向密度分布不均数据的近邻优化密度峰值聚类算法[J]. 控制与决策, 2024, 39(3): 919-928.
CHEN Weichang, ZHAO Jia, XIAO Renbin, et al. Density peaks clustering algorithm with nearest neighbor optimization for data with uneven density distribution[J]. Control and decision, 2024, 39(3): 919-928.
[14] 吕莉, 朱梅子, 康平, 等. 面向分布不均数据的混合近邻密度峰值聚类算法[J/OL]. 控制理论与应用. (2023-11-16)[2024-01-02]. http://kns.cnki.net/kcms/detail/44.1240.TP.20231114.1333.014.html.
LYU Li, ZHU Meizi, KANG Ping, et al. Multiplex neighbor density peaks clustering for uneven density data sets[J/OL]. Control theory & applications. (2023-11-16)[2024-01-02]. http://kns.cnki.net/kcms/detail/44.1240.TP.20231114.1333.014.html.
[15] 吴润秀, 尹士豪, 赵嘉, 等. 基于相对密度估计和多簇合并的密度峰值聚类算法[J]. 控制与决策, 2023, 38(4): 1047-1055.
WU Runxiu, YIN Shihao, ZHAO Jia, et al. Density peaks clustering based on relative density estimating and multi cluster merging[J]. Control and decision, 2023, 38(4): 1047-1055.
[16] 赵嘉, 王刚, 吕莉, 等. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
ZHAO Jia, WANG Gang, LYU Li, et al. Density peaks clustering algorithm based on geodesic distance and cosine mutual reverse nearest neighbors for manifold datasets[J]. Acta electronica sinica, 2022, 50(11): 2730-2737.
[17] TAO Xinmin, GUO Wenjie, REN Chao, et al. Density peak clustering using global and local consistency adjustable manifold distance[J]. Information sciences, 2021, 577: 769-804.
[18] 吕莉, 朱梅子, 康平, 等. 二阶K近邻和多簇合并的密度峰值聚类算法[J]. 吉林大学学报(工学版), 2024, 54(5): 1417-1425.
LYU Li, ZHU Meizi, KANA Ping, et al. Density peaks clustering with second-order K-nearest neighbors and multi-cluster merging[J]. Journal of Jilin University (engineering and technology edition), 2024, 54(5): 1417-1425.
[19] BRYANT A, CIOS K. RNN-DBSCAN: a density-based clustering algorithm using reverse nearest neighbor density estimates[J]. IEEE transactions on knowledge and data engineering, 2018, 30(6): 1109-1121.
[20] WU Chunrong, LEE Jia, ISOKAWA T, et al. Efficient clustering method based on density peaks with symmetric neighborhood relationship[J]. IEEE access, 2019, 7: 60684-60696.
[21] 徐晓, 丁世飞, 孙统风, 等. 基于网格筛选的大规模密度峰值聚类算法[J]. 计算机研究与发展, 2018, 55(11): 2419-2429.
XU Xiao, DING Shifei, SUN Tongfeng, et al. Large-scale density peaks clustering algorithm based on grid screening[J]. Journal of computer research and development, 2018, 55(11): 2419-2429.
[22] DING Shifei, LI Chao, XU Xiao, et al. A sampling-based density peaks clustering algorithm for large-scale data[J]. Pattern recognition, 2023, 136: 109238.
[23] GUO Wenjie, WANG Wenhai, ZHAO Shunping, et al. Density peak clustering with connectivity estimation[J]. Knowledge-based systems, 2022, 243: 108501.
[24] SHI Aiye, ZHAO Jia, TANG Jingjing, et al. Improved density peaks clustering based on firefly algorithm[J]. International journal of bio-inspired computation, 2020, 15(1): 24.
[25] LOTFI A, MORADI P, BEIGY H. Density peaks clustering based on density backbone and fuzzy neighborhood[J]. Pattern recognition, 2020, 107: 107449.
[26] VINH N, EPPS J, BAILEY J. Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance[J]. Journal of machine learning research, 2010, 11(1): 2837-2854.
[27] FOWLKES E B, MALLOWS C L. A method for comparing two hierarchical clusterings[J]. Journal of the American statistical association, 1983, 78(383): 553-569.
[28] JAIN A K, LAW M. Data clustering: a user’s dilemma[C]//Proceedings of the First International conference on pattern recognition and machine intelligence. Heidelberg: Springer, 2005: 1-10.
[29] XU Xiao, DING Shifei, WANG Lijuan, et al. A robust density peaks clustering algorithm with density-sensitive similarity[J]. Knowledge-based systems, 2020, 200: 106028.
[30] 张清华, 周靖鹏, 代永杨, 等. 基于代表点与K近邻的密度峰值聚类算法[J]. 软件学报, 2023, 34(12): 5629-5648.
ZHANG Qinghua, ZHOU Jingpeng, DAI Yongyang, et al. Density peaks clustering algorithm based on representative points and K-nearest neighbors[J]. Journal of software, 2023, 34(12): 5629-5648.
[31] 赵嘉, 陈磊, 吴润秀, 等. K近邻和加权相似性的密度峰值聚类算法[J]. 控制理论与应用, 2022, 39(12): 2349-2357.
ZHAO Jia, CHEN Lei, WU Runxiu, et al. Density peaks clustering algorithm with K-nearest neighbors and weighted similarity[J]. Control theory & applications, 2022, 39(12): 2349-2357.
[32] ZIMMERMAN D W, ZUMBO B D. Relative power of the wilcoxon test, the Friedman test, and repeated-measures ANOVA on ranks[J]. The journal of experimental education, 1993, 62(1): 75-86.
[33] BLAKE C L, MERZ C J. UCI repository of machine learning database[EB/OL]. (2016-12-28)[2023-11-05]. http://archive.ics.uci.edu/ml/index.html.
[34] CHARYTANOWICZ M, NIEWCZAS J, KULCZYCKI P, et al. Complete gradient clustering algorithm for features analysis of X-ray images[M]//Advances in Intelligent and Soft Computing. Berlin: Springer Berlin Heidelberg, 2010: 15-24.
[35] SIGILLITO V G, WING S P, HUTTON L V, et al. Classification of radar returns from the ionosphere using neural networks[J]. Johns Hopkins APL technical digest (applied physics laboratory), 1989, 10(3): 262-266.
[36] DIAS D B, MADEO R C B, ROCHA T, et al. Hand movement recognition for Brazilian sign language: a study using distance-based neural networks[C]//2009 International Joint Conference on Neural Networks. Atlanta: IEEE, 2009: 697-704.
[37] NENE S, NAYAR S, MURASE H. Columbia object image library (COIL-20): CUCS 006 96[R]. Columbia: Department of Computer Science, Columbia University, 1996.
Similar References:

Memo

-

Last Update: 2025-01-05

Copyright © CAAI Transactions on Intelligent Systems