[1]CHEN Zhongshang,FENG Ji,YANG Degang,et al.Hybrid neighborhood graph-based hierarchical clustering algorithm for datasets with complex structures[J].CAAI Transactions on Intelligent Systems,2025,20(3):584-593.[doi:10.11992/tis.202407001]
Copy

Hybrid neighborhood graph-based hierarchical clustering algorithm for datasets with complex structures

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 20 Number of periods: 2025 3 Page number: 584-593 Column: 学术论文—机器学习 Public date: 2025-05-05
Title:
Hybrid neighborhood graph-based hierarchical clustering algorithm for datasets with complex structures
Author(s):
CHEN Zhongshang;  FENG Ji;  YANG Degang;  CAI Fapeng
College of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China
Keywords:
cluster analysis; hybrid neighborhood graph; shared natural neighbors; improved natural neighborhood graph; shared natural neighborhood graph; subgraph similarity; complex dataset; data mining
CLC:
TP301
DOI:
10.11992/tis.202407001
Abstract:
Complex structured datasets typically refer to datasets containing clusters of different shapes (including spherical, non-spherical, and manifold shapes), sizes, and densities. The natural neighbor algorithm exhibits limitations in handling datasets with unclear boundaries and varying densities. Particularly, its performance decreases significantly when the dataset contains a significant amount of noise. To address this drawback, we propose a hybrid neighborhood graph-based hierarchical clustering algorithm for datasets with complex structures (HCHNG). We proposed a method of shared natural neighborhood graph, which uses the neighbor relationships to sparse the dataset and reduce the impact of abnormal samples on clustering results. Subsequently, the algorithm divides the dataset into several subgraphs and enhances the processability of variable density data by merging operations. Concurrently, we propose a new method for defining subgraph similarity, which ensures higher similarity between subgraphs of the same class. Additionally, we improve the performance of the natural neighborhood graph in identifying datasets with blurred boundaries. The experimental results reveal that the HCHNG algorithms can recognize variable density spherical datasets and complex datasets containing a large amount of noise. Therefore, our algorithm is more effective than the existing methods in processing datasets with complex structures.
References:
[1] CHENG Zhanhong, TRéPANIER M, SUN Lijun. Probabilistic model for destination inference and travel pattern mining from smart card data[J]. Transportation, 2021, 48(4): 2035-2053.
[2] YOON B, JEONG Y, KIM S. Detecting a risk signal in stock investment through opinion mining and graph-based semi-supervised learning[J]. IEEE access, 2020, 8: 161943-161957.
[3] CAI Shousong, ZHANG Jing. Exploration of credit risk of P2P platform based on data mining technology[J]. Journal of computational and applied mathematics, 2020, 372: 112718.
[4] 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.
[5] 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.
[6] CHEN Yewang, ZHOU Lida, BOUGUILA N, et al. BLOCK-DBSCAN: Fast clustering for large scale data[J]. Pattern recognition, 2021, 109: 107624.
[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] 邵佳, 金百锁. 基于层次聚类的图像分割算法[J]. 计算机应用, 2022, 42(S2): 211-216.
SHAO Jia, JIN Baisuo. Image segmentation algorithm based on hierarchical clustering[J]. Journal of computer applications, 2022, 42(S2): 211-216.
[9] ZHANG Tian, RAMAKRISHNAN R, LIVNY M. BIRCH[J]. ACM SIGMOD record, 1996, 25(2): 103-114.
[10] GUHA S, RASTOGI R, SHIM K. Cure: an efficient clustering algorithm for large databases[J]. Information systems, 2001, 26(1): 35-58.
[11] KARYPIS G, HAN E H, KUMAR V. Chameleon: hierarchical clustering using dynamic modeling[J]. Computer, 1999, 32(8): 68-75.
[12] KARYPIS G, AGGARWAL R, KUMAR V, et al. Multilevel hypergraph partitioning: application in vlsi domain[C]//Proceedings of the 34th Design Automation Conference. Anaheim: IEEE, 1997: 526-529.
[13] 吕端端. 基于最近邻思想的Chameleon聚类算法研究[D]. 西安: 西安理工大学, 2020: 31-49.
LYU Duanduan. Research on Chameleon clustering algorithm based on nearest neighbor idea[D]. Xi’an: Xi’an University of Technology, 2020: 31-49.
[14] CHENG Dongdong, ZHU Qingsheng, HUANG Jinlong, et al. A hierarchical clustering algorithm based on noise removal[J]. International journal of machine learning and cybernetics, 2019, 10(7): 1591-1602.
[15] ARTHUR D, VASSILVITSKII S. k-means++: The advantages of careful seeding[C]//Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2007: 1027-1035.
[16] CHENG Dongdong, HUANG Jinlong, ZHANG Sulan, et al. K-means clustering with natural density peaks for discovering arbitrary-shaped clusters[J]. IEEE transactions on neural networks and learning systems, 2024, 35(8): 11077-11090.
[17] TZORTZIS G, LIKAS A. The MinMax k-means clustering algorithm[J]. Pattern recognition, 2014, 47(7): 2505-2516.
[18] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAAI Press, 1996: 226-231.
[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] GHOLIZADEH N, SAADATFAR H, HANAFI N. K-DBSCAN: an improved DBSCAN algorithm for big data[J]. The journal of supercomputing, 2021, 77(6): 6214-6235.
[21] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[22] TONG Wuning, LIU Sen, GAO Xiaozhi. A density-peak-based clustering algorithm of automatically determining the number of clusters[J]. Neurocomputing, 2021, 458: 655-666.
[23] CHEN Di, DU Tao, ZHOU Jin, et al. A domain density peak clustering algorithm based on natural neighbor[J]. Intelligent data analysis, 27(2): 443-462.
[24] 冯骥. 自然邻居思想概念及其在数据挖掘领域的应用[D]. 重庆: 重庆大学, 2016: 31-89.
FENG Ji. Concept of natural neighbor and its application in data mining[D]. Chongqing: Chongqing University, 2016: 31-89.
[25] 张清华, 周靖鹏, 代永杨, 等. 基于代表点与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.
[26] 位雅, 张正军, 何凯琳, 等. 基于相对密度的密度峰值聚类算法[J]. 计算机工程, 2023, 49(6): 53-61.
WEI Ya, ZHANG Zhengjun, HE Kailin, et al. Density peak clustering algorithm based on relative density[J]. Computer engineering, 2023, 49(6): 53-61.
[27] CHENG Dongdong, LI Ya, XIA Shuyin, et al. A fast granular-ball-based density peaks clustering algorithm for large-scale data[J]. IEEE transactions on neural networks and learning systems, 2024, 35(12): 17202-17215.
[28] LIU Rui, WANG Hong, YU Xiaomei. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information sciences, 2018, 450: 200-226.
[29] CHENG Dongdong, ZHU Qingsheng, HUANG Jinlong, et al. A novel cluster validity index based on local cores[J]. IEEE transactions on neural networks and learning systems, 2019, 30(4): 985-999.
[30] NGUYEN X, EPPS J, BAILEY J. Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance[J]. Properties, normalization and correction for chance, 2009, 10: 2837-2854.
[31] 冯骥, 冉瑞生, 魏延. 基于自然邻居邻域图的无参数离群检测算法[J]. 智能系统学报, 2019, 14(5): 998-1006.
FENG Ji, RAN Ruisheng, WEI Yan. A parameter-free outlier detection algorithm based on natural neighborhood graph[J]. CAAI transactions on intelligent systems, 2019, 14(5): 998-1006.
[32] 周欢欢, 张征, 张琦. 结合共享近邻和共享逆近邻的密度峰聚类[J]. 西华师范大学学报(自然科学版), 2022, 43(1): 108-115.
ZHOU Huanhuan, ZHANG Zheng, ZHANG Qi. Density peak clustering combining shared nearest neighbors and shared inverse neighbors[J]. Journal of China west normal university (natural sciences), 2022, 43(1): 108-115.
[33] JARVIS R A, PATRICK E A. Clustering using a similarity measure based on shared near neighbors[J]. IEEE transactions on computers, 1973, C-22(11): 1025-1034.
[34] ZHANG Jinghui, YANG Lijun, ZHANG Yong, et al. Non-parameter clustering algorithm based on saturated neighborhood graph[J]. Applied soft computing, 2022, 130: 109647.
[35] HUANG Jinlong, ZHU Qingsheng, YANG Lijun, et al. A novel outlier cluster detection algorithm without top-n parameter[J]. Knowledge-based systems, 2017, 121: 32-40.
[36] ZHANG Yuru, DING Shifei, WANG Yanru, et al. Chameleon algorithm based on improved natural neighbor graph generating sub-clusters[J]. Applied intelligence, 2021, 51(11): 8399-8415.
[37] 张辉. 密度峰值点快速搜索聚类算法的研究与改进[D]. 青岛: 山东科技大学, 2019: 32-37.
ZHANG Hui. Research and improvement of fast search clustering algorithm for density peak points[D]. Qingdao: Shandong University of Science and Technology, 2019: 32-37.
[38] 吕莉, 陈威, 肖人彬, 等. 面向密度分布不均数据的加权逆近邻密度峰值聚类算法[J]. 智能系统学报, 2024, 19(1): 165-175.
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.
[39] 陈磊, 吴润秀, 李沛武, 等. 加权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.
[40] DING Shifei, DU Wei, XU Xiao, et al. An improved density peaks clustering algorithm based on natural neighbor with a merging strategy[J]. Information sciences, 2023, 624: 252-276.
[41] CHENG Bifang, BUNDROCK T, WILLIAMS D J. AAC oriental 200 oriental mustard[J]. Canadian journal of plant science, 2018, 98(4): 985-987.
[42] 王赢己. 基于自然邻居的密度峰值聚类算法研究[D]. 哈尔滨: 哈尔滨工程大学, 2021: 50-55.
WANG Yingji. Research on density peak clustering algorithm based on natural neighbors[D]. Harbin: Harbin Engineering University, 2021: 50-55.
[43] 赵嘉, 马清, 肖人彬, 等. 面向流形数据的共享近邻密度峰值聚类算法[J]. 智能系统学报, 2023, 18(4): 719-730.
ZHAO Jia, MA Qing, XIAO Renbin, et al. Density peaks clustering based on shared nearest neighbor for manifold datasets[J]. CAAI transactions on intelligent systems, 2023, 18(4): 719-730.
[44] 谢文波. 基于互惠最近邻的层次聚类算法及其应用研究[D]. 成都: 电子科技大学, 2021: 36-57.
XIE Wenbo. Research on hierarchical clustering algorithm based on reciprocal nearest neighbors and its application[D]. Chengdu: University of Electronic Science and Technology of China, 2021: 36-57.
[45] 程东东. 基于局部核心点的聚类算法与度量研究[D]. 重庆: 重庆大学, 2018: 38-74.
CHENG Dongdong. Research on clustering algorithm and measurement based on local core points[D]. Chongqing: Chongqing University, 2018: 38-74.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems