[1]陈仲尚,冯骥,杨德刚,等.基于混合邻域图的复杂结构数据集层次聚类算法[J].智能系统学报,2025,20(3):584-593.[doi:10.11992/tis.202407001]
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]
点击复制
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]
基于混合邻域图的复杂结构数据集层次聚类算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
20
期数:
2025年第3期
页码:
584-593
栏目:
学术论文—机器学习
出版日期:
2025-05-05
- Title:
- Hybrid neighborhood graph-based hierarchical clustering algorithm for datasets with complex structures
- Keywords:
- cluster analysis; hybrid neighborhood graph; shared natural neighbors; improved natural neighborhood graph; shared natural neighborhood graph; subgraph similarity; complex dataset; data mining
- 分类号:
- TP301
- 摘要:
- 复杂结构数据集通常指包含不同形状(如球形、非球形、流形)、大小和密度的簇的数据集。自然邻居算法在处理边界模糊、密度变化的数据集时存在局限性，特别是在数据集中含有大量噪声时，其性能会显著下降。针对这些问题，本文提出一种基于混合邻域图的复杂结构数据集层次聚类算法(hybrid neighborhood graph-based hierarchical clustering algorithm for datasets with complex structures, HCHNG)。该方法提出一种共享自然邻域图方法，通过邻居关系稀疏数据集以减少噪声样本对聚类结果的影响。随后，HCHNG将数据集划分为子图并加以合并，这一策略增强了算法处理变密度数据集的能力，同时，定义一种新的子图相似性度量方法，提高同类子图间的相似性。此外，对自然邻域图进行改进，以提升其在识别边界模糊数据集时的性能。在具有复杂结构的人工数据集和真实数据集上的对比实验表明，本文算法不仅能有效识别变密度球形数据集，而且在含有大量噪声的复杂数据集中也拥有优越的性能，在处理具有复杂结构的数据集时比现有方法高效。
- 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.
- 相似文献/References:
-
[1]刘秀梅,赵克勤.基于联系数的不确定空情意图识别[J].智能系统学报,2012,7(5):450.
LIU Xiumei,ZHAO Keqin.Inference method on intention with uncertain aerial information based on the connection number[J].CAAI Transactions on Intelligent Systems,2012,7():450.
[2]尹宁,刘富,张玉.采用最小误差阈值分割算法的基因芯片图像分析[J].智能系统学报,2013,8(1):28.[doi:10.3969/j.issn.1673-4785.201207015]
YIN Ning,LIU Fu,ZHANG Yu.Image analysis of gene chip using minimum error threshold segmentation algorithm[J].CAAI Transactions on Intelligent Systems,2013,8():28.[doi:10.3969/j.issn.1673-4785.201207015]
[3]卿铭,孙晓梅.一种新的聚类有效性函数:模糊划分的模糊熵[J].智能系统学报,2015,10(1):75.[doi:10.3969/j.issn.1673-4785.201410004]
QING Ming,SUN Xiaomei.A new clustering effectiveness function: fuzzy entropy of fuzzy partition[J].CAAI Transactions on Intelligent Systems,2015,10():75.[doi:10.3969/j.issn.1673-4785.201410004]
[4]王德文,孙志伟.一种基于内存计算的电力用户聚类分析方法[J].智能系统学报,2015,10(4):569.[doi:10.3969/j.issn.1673-4785.201411011]
WANG Dewen,SUN Zhiwei.A method for cluster analysis of electric power consumers based on in-memory computing[J].CAAI Transactions on Intelligent Systems,2015,10():569.[doi:10.3969/j.issn.1673-4785.201411011]
[5]张永库,尹灵雪,孙劲光.基于改进的遗传算法的模糊聚类算法[J].智能系统学报,2015,10(4):627.[doi:10.3969/j.issn.1673-4785.201503033]
ZHANG Yongku,YIN Lingxue,SUN Jinguang.Fuzzy clustering algorithm based on the improved genetic algorithm[J].CAAI Transactions on Intelligent Systems,2015,10():627.[doi:10.3969/j.issn.1673-4785.201503033]
[6]郑婷婷,桑小双,马斌斌.犹豫模糊集的α-截集及其应用[J].智能系统学报,2017,12(3):362.[doi:10.11992/tis.201704026]
ZHENG Tingting,SANG Xiaoshuang,MA Binbin.α-cut sets of hesitant fuzzy sets and their applications[J].CAAI Transactions on Intelligent Systems,2017,12():362.[doi:10.11992/tis.201704026]
[7]冯冰,李绍滋.中医脉诊信号的无监督聚类分析研究[J].智能系统学报,2018,13(4):564.[doi:10.11992/tis.201703030]
FENG Bing,LI Shaozi.Unsupervised clustering analysis of human-pulse signal in traditional Chinese medicine[J].CAAI Transactions on Intelligent Systems,2018,13():564.[doi:10.11992/tis.201703030]
[8]赵晓晓,周治平.结合稀疏表示与约束传递的半监督谱聚类算法[J].智能系统学报,2018,13(5):855.[doi:10.11992/tis.201703013]
ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J].CAAI Transactions on Intelligent Systems,2018,13():855.[doi:10.11992/tis.201703013]
[9]秦海菲,杜军平.酒店在线评论数据的特征挖掘[J].智能系统学报,2018,13(6):1006.[doi:10.11992/tis.201806016]
QIN Haifei,DU Junping.Feature mining based on online hotel review[J].CAAI Transactions on Intelligent Systems,2018,13():1006.[doi:10.11992/tis.201806016]
[10]储德润,周治平.公理化模糊共享近邻自适应谱聚类算法[J].智能系统学报,2019,14(5):897.[doi:10.11992/tis.201810002]
CHU Derun,ZHOU Zhiping.Shared nearest neighbor adaptive spectral clustering algorithm based on axiomatic fuzzy set theory[J].CAAI Transactions on Intelligent Systems,2019,14():897.[doi:10.11992/tis.201810002]
备注/Memo
收稿日期:2024-7-1。
基金项目:重庆市教委科学技术研究项目 (KJZD-M202300502, KJQN201800539).
作者简介:陈仲尚，硕士研究生，主要研究方向为数据挖掘。E-mail: chenzhongshang@foxmail.com。;冯骥，副教授，博士，计算机与信息科学院副院长，主要研究方向为数据挖掘、人工智能。主持及参与国家自然科学基金、省部级项目等10余项。发表学术论文10余篇。E-mail: jifeng@cqnu.edu.cn。;杨德刚，教授，博士，主要研究方向为智能算法、神经网络、复杂网络。主持及参与国家自然科学基金、省部级项目等20余项。发表学术论文50余篇。E-mail: yangdg@cqnu.edu.cn。
通讯作者:冯骥. E-mail：jifeng@cqnu.edu.cn
更新日期/Last Update:
1900-01-01