[1]LYU Li,CHEN Wei,XIAO Renbin,et al.Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets[J].CAAI Transactions on Intelligent Systems,2024,19(1):165-175.[doi:10.11992/tis.202212015]
Copy
Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
19
Number of periods:
2024 1
Page number:
165-175
Column:
学术论文—人工智能基础
Public date:
2024-01-05
- Title:
- Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets
- Keywords:
- density peak clustering; uneven density distribution; reverse nearest neighbor; shared reverse nearest neighbor; sample similarity; local density; distribution strategy; data mining
- CLC:
- TP301
- DOI:
- 10.11992/tis.202212015
- Abstract:
- For data with uneven density distribution, the density peak clustering algorithm disregards the sparsity difference among intercluster samples, causing an inaccurate selection of the cluster center. Moreover, the allocation strategy easily divides the samples in sparse areas into dense areas by mistake, leading to a poor clustering effect. Therefore, the density peak clustering algorithm based on the weighted reverse nearest neighbor (DPC-WR) against datasets with uneven density distribution is proposed in this paper. First, the weight coefficient based on the sigmoid function is introduced to the local density formula to increase the weight of samples in sparse areas. Combined with the concept of reverse nearest neighbor, the local density of samples is then redesigned to improve the recognition rate of cluster centers effectively. Second, an improved sample similarity strategy is introduced, which utilizes reverse nearest neighbors and shares this neighbor’s information between samples to increase the similarity of samples in the same cluster. This effectively solves the problem of sample allocation error in sparse areas. Experiments on uneven density distribution, complex morphology, and UCI datasets show that the clustering effect of the DPC-WR algorithm outperforms that of IDPC-FA, FNDPC, FKNN-DPC, DPC, and DPCSA algorithms.
- References:
-
[1] SZALONTAI B, DEBRECZENY M, FINTOR K, et al. SVD-clustering, a general image-analyzing method explained and demonstrated on model and Raman micro-spectroscopic maps[J]. Scientific reports, 2020, 10: 4238.
[2] 程鹏宇, 赵嘉, 韩龙哲, 等. 双向多尺度LSTM的短时温度预测[J]. 江西师范大学学报(自然科学版), 2022, 46(2): 134–139
CHENG Pengyu, ZHAO Jia, HAN Longzhe, et al. The short-term temperature prediction based on bidirectional multi-scale LSTM[J]. Journal of Jiangxi normal university (natural science edition), 2022, 46(2): 134–139
[3] LI Chunlin, BAI Jingpan. Automatic content extraction and time-aware topic clustering for large-scale social network on cloud platform[J]. The journal of supercomputing, 2019, 75(5): 2890–2924.
[4] MIRZAL A. Statistical analysis of microarray data clustering using NMF, spectral clustering, kmeans, and GMM[J]. IEEE/ACM transactions on computational biology and bioinformatics, 2022, 19(2): 1173–1192.
[5] ZHAO Yuan, FANG Zhaoyu, LIN Cuixiang, et al. RFCell: a gene selection approach for scRNA-seq clustering based on permutation and random forest[J]. Frontiers in genetics, 2021, 12: 665843.
[6] TAVALLALI P, TAVALLALI P, SINGHAL M. K-means tree: an optimal clustering tree for unsupervised learning[J]. The journal of supercomputing, 2021, 77(5): 5239–5266.
[7] CHU Zhenyue, WANG Weifeng, LI Bangzhun, et al. An operation health status monitoring algorithm of special transformers based on BIRCH and Gaussian cloud methods[J]. Energy reports, 2021, 7: 253–260.
[8] BUREVA V, POPOV S, TRANEVA V, et al. Generalized net model of cluster analysis using CLIQUE: clustering in quest[J]. International journal bioautomation, 2019, 23(2): 131–138.
[9] REN Jie, WANG Zulin, XU Mai, et al. An EM-based user clustering method in non-orthogonal multiple access[J]. IEEE transactions on communications, 2019, 67(12): 8422–8434.
[10] ZHU Qidan, TANG Xiangmeng, ELAHI A. Application of the novel harmony search optimization algorithm for DBSCAN clustering[J]. Expert systems with applications, 2021, 178: 115054.
[11] ZHANG En, LI Huimin, HUANG Yuchen, et al. Practical multi-party private collaborative k-means clustering[J]. Neurocomputing, 2022, 467: 256–265.
[12] ZHANG Tian, RAMAKRISHNAN R, LIVNY M. Birch[J]. ACM SIGMOD record, 1996, 25(2): 103–114.
[13] AGRAWAL R, GEHRKE J, GUNOPULOS D, et al. Automatic subspace clustering of high dimensional data for data mining applications[C]//Proceedings of the 1998 ACM SIGMOD international conference on Management of data. Seattle: ACM, 1998: 94?105.
[14] DEMPSTER A P, LAIRD N M, RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the royal statistical society:series B (methodological), 1977, 39(1): 1–22.
[15] ESTER M. A density-based Algorithm for discovering clusters in large spatial databases with noise[C]//KDD ’96: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. Oregon: AAAI Press, 1996: 226?231.
[16] RODRIGUEZ A, LAIO A. Machine learning. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492–1496.
[17] 吕莉, 朱梅子, 康平, 等. 二阶K近邻和多簇合并的密度峰值聚类算法[J/OL]. 吉林大学学报(工学版). (2023?01?31)[2023?07?13]. https://kns.cnki.net/kcms/detail/22.1341.t.20230131.1100. 005. html.
LYU Li, ZHU Meizi, KANG Ping, et al. Density peaks clustering with second-order K-nearest neighbors and multi-cluster merging[J/OL]. Journal of Jilin University (engineering and technology edition). (2023?01?31) [2023?07?13]. https://kns.cnki.net/kcms/detail/22.1341.t.20230131.1100.005.html.
[18] SUN Lin, QIN Xiaoying, DING Weiping, et al. Nearest neighbors-based adaptive density peaks clustering with optimized allocation strategy[J]. Neurocomputing, 2022, 473: 159–181.
[19] 赵嘉, 陈磊, 吴润秀, 等. 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
[20] 吴润秀, 尹士豪, 赵嘉, 等. 基于相对密度估计和多簇合并的密度峰值聚类算法[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
[21] DING Jiajun, HE Xiongxiong, YUAN Junqing, et al. Community detection by propagating the label of center[J]. Physica A:statistical mechanics and its applications, 2018, 503: 675–686.
[22] 赵嘉, 王刚, 吕莉, 等. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[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
[23] 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, 2017, 30(6): 1109–1121.
[24] 陈磊, 吴润秀, 李沛武, 等. 加权K近邻和多簇合并的密度峰值聚类算法[J]. 计算机科学与探索, 2022, 16(9): 2163–2176
CHEN Lei, WU Runxiu, LI Peiwu, et al. Weighted K-nearest neighbors and multi-cluster merge density peaks clustering algorithm[J]. Journal of frontiers of computer science and technology, 2022, 16(9): 2163–2176
[25] ZHAO Jia, TANG Jingjing, SHI Aiye, et al. Improved density peaks clustering based on firefly algorithm[J]. International journal of bio-inspired computation, 2020, 15(1): 24.
[26] DU Mingjing, DING Shifei, XUE Yu. A robust density peaks clustering algorithm using fuzzy neighborhood[J]. International journal of machine learning and cybernetics, 2018, 9(7): 1131–1140.
[27] YU Donghua, LIU Guojun, GUO Maozu, et al. Density peaks clustering based on weighted local density sequence and nearest neighbor assignment[J]. IEEE access, 2019, 7: 34301–34317.
[28] VINH N X, 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: 2837–2854.
[29] 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.
[30] 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.
[31] 肖人彬. 面向复杂系统的群集智能[M]. 北京: 科学出版社, 2013.
[32] 肖人彬, 冯振辉, 王甲海. 群体智能的概念辨析与研究进展及应用分析[J]. 南昌工程学院学报, 2022, 41(1): 1–21
XIAO Renbin, FENG Zhenhui, WANG Jiahai. Collective intelligence: conception, research progresses and application analyses[J]. Journal of Nanchang institute of technology, 2022, 41(1): 1–21
[33] 张曦, 李璠, 付雪峰, 等. 随机学习萤火虫算法优化的模糊软子空间聚类算法[J]. 江西师范大学学报(自然科学版), 2021, 45(2): 137–144
ZHANG Xi, LI Fan, FU Xuefeng, et al. The fuzzy soft subspace clustering algorithm optimized by random learning firefly algorithm[J]. Journal of Jiangxi normal university (natural science edition), 2021, 45(2): 137–144
[34] 肖人彬, 陈峙臻. 从群智能优化到群智能进化[J]. 南昌工程学院学报, 2023, 42(1): 1–10
XIAO Renbin, CHEN Zhizhen. From swarm intelligence optimization to swarm intelligence evolution[J]. Journal of Nanchang institute of technology, 2023, 42(1): 1–10
[35] 赵嘉, 谢智峰, 吕莉, 等. 深度学习萤火虫算法[J]. 电子学报, 2018, 46(11): 2633–2641
ZHAO Jia, XIE Zhifeng, LYU Li, et al. Firefly algorithm with deep learning[J]. Acta electronica sinica, 2018, 46(11): 2633–2641
- Similar References:
Memo
-
Last Update:
1900-01-01