基于改进最近邻图的主动聚类方法

doi:10.16451/j.cnki.issn1003-6059.202504004

摘要
图/表
参考文献(35)
相关文章 (8)

全文: PDF (4003 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要

在现代数据分析与机器学习应用中,如何对新采样数据提取关键信息以进行高效分组、标注,是聚类算法面临的核心挑战之一.传统无监督聚类算法缺乏先验信息指导,难以满足复杂任务(如大模型预训练)对高质量数据的需求.主动学习方法可有效提升聚类精度,但高昂的人机交互成本和计算开销限制其实际应用.为此,文中提出基于改进最近邻图的主动聚类方法(Active Clustering with Tailored Nearest Neighbor Graph, ACNNG).ACNNG构造稀疏的最近邻图结构,刻画数据之间的关联.在该图的基础上,综合计算节点拓扑结构中心性和分组不确定性,有效识别关键数据点,并向用户寻求少量成对约束标注,显著提升聚类准确性.此外,ACNNG使用与最近邻图结构协作的高效标签传播机制,利用稀疏图结构实现低成本的标签扩展,大幅降低方法的时空复杂度,提升其在大规模数据处理中的可扩展性.在真实世界数据集与合成数据集上的实验表明,ACNNG不仅能利用较少的成对约束提高聚类准确性,而且运行时间较短,内存消耗较少,在实际场景中具有一定的应用潜力.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	谢文波
	邓涛
	付勋
	陈斌
	邹甜
	王欣

关键词 ：交互式聚类, 主动聚类, 半监督聚类, 成对约束

Abstract：

In modern data analysis and machine learning applications, how to extract critical information from newly acquired data for efficient grouping (clustering) and annotation remains a central challenge for clustering algorithms. Traditional unsupervised clustering algorithms struggle to meet the high-quality data requirements of complex tasks, such as pre-training large models due to the lack of prior information guidance. Active learning methods can effectively improve clustering accuracy, but their practical application is constrained by high human interaction costs and computational overhead. To address these issues, an algorithm of active clustering with tailored nearest neighbor graph(ACNNG) is proposed. A sparse nearest neighbor graph is constructed to model relationships between data points. Based on this graph, the topological centrality and uncertainty of data points are comprehensively computed to effectively identify key data points. A small number of pairwise constraints are collected from users to significantly enhance clustering accuracy. Furthermore, an efficient label propagation mechanism collaborating with the nearest neighbor graph structure is employed. By leveraging the sparse graph structure for low-cost label propagation, ACNNG substantially reduces the spatiotemporal complexity and improves scalability for large-scale data processing. Experiments on real-world and synthetic datasets demonstrate that ACNNG achieves higher clustering accuracy with fewer pairwise constraints, less runtime, and less memory consumption, showcasing its potential for practical applications.

Key words： Interactive Clustering Active Clustering Semi-supervised Clustering Pairwise Constraint

收稿日期: 2025-01-14

ZTFLH:

TP311.13

基金资助:

国家自然科学基金项目(No.62172102)、四川省科技计划项目(No.2024NSFSC1464)、四川省科技创新人才基金项目(No.2022JDRC0009)、西南石油大学自然科学“启航计划”项目(No.2023QHZ010)、西南石油大学研究生教育教学改革与研究项目 (No.2024JGYB024)资助

通讯作者: 谢文波,博士,副教授,主要研究方向为数据挖掘、知识图谱.E-mail:wenboxie@swpu.edu.cn.

作者简介: 邓涛,硕士研究生,主要研究方向为数据挖掘、机器学习.E-mail:dengtao209@163.com.
付勋,硕士研究生,主要研究方向为数据挖掘、主动学习.E-mail:fuxun0529@163.com.
陈斌,博士研究生,主要研究方向为数据挖掘、机器学习.E-mail:chenbin199817@gmail.com.
邹甜,硕士研究生,主要研究方向为数据挖掘、机器学习.E-mail:tianz0520@gmail.com.
王欣,博士,教授,主要研究方向为数据挖掘、数据库.E-mail:xinwang@swpu.edu.cn.

引用本文:

谢文波, 邓涛, 付勋, 陈斌, 邹甜, 王欣. 基于改进最近邻图的主动聚类方法[J]. 模式识别与人工智能, 2025, 38(4): 341-358. XIE Wenbo, DENG Tao, FU Xun, CHEN Bin, ZOU Tian, WANG Xin. Active Clustering with Tailored Nearest Neighbor Graph. Pattern Recognition and Artificial Intelligence, 2025, 38(4): 341-358.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.202504004 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2025/V38/I4/341

[1] CHANG Y P, WANG X, WANG J D, et al. A Survey on Evaluation of Large Language Models. ACM Transactions on Intelligent Systems and Technology, 2024, 15(3). DOI: 10.1145/364128.
[2] 李超,廖红梅,徐晓,等.基于密度分布的鲁棒谱聚类算法.计算机学报, 2024, 47(11): 2645-2663.
(LI C, LIAO H M, XU X, et al. Robust Spectral Clustering Based on Density Distribution. Chinese Journal of Computers, 2024, 47(11): 2645-2663.)
[3] 张胜杰,王一飞,向旺,等.基于变分贝叶斯对比网络的非参数图像聚类方法.模式识别与人工智能, 2023, 36(9): 832-841.
(ZHANG S J, WANG Y F, XIANG W, et al. Nonparametric Image Clustering Based on Variational Bayesian Contrastive Network. Pa-ttern Recognition and Artificial Intelligence, 2023, 36(9): 832-841.)
[4] LI X T, WONG K C.Single-Cell RNA Sequencing Data Interpretation by Evolutionary Multiobjective Clustering. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2020, 17(5):1773-1784.
[5] TAHA K.Semi-supervised and Un-supervised Clustering: A Review and Experimental Evaluation. Information Systems, 2023, 114. DOI: 10.1016/j.is.2023.102178.
[6] LANGE T,LAW M H C,JAIN A K, et al. Learning with Constrained and Unlabelled Data // Proc of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2005. DOI: 10.1109/CVPR.2005.210.
[7] DING S F, HOU H W, XU X, et al. Graph-Based Semi-Supervised Deep Image Clustering with Adaptive Adjacency Matrix. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(12): 18828-18837.
[8] XIONG C M, JOHNSON D M, CORSO J J.Active Clustering with Model-Based Uncertainty Reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, 39(1): 5-17.
[9] BAE J, HELLDIN T, RIVEIRO M, et al. Interactive Clustering: A Comprehensive Review. ACM Computing Surveys, 2020, 53(1). DOI: 10.1145/3340960.
[10] JIANG Z, ZHAN Y Z, MAO Q R, et al. Semi-supervised Clus-tering under a "Compact-Cluster" Assumption. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(5): 5244-5256.
[11] CAI J H, HAO J, YANG H F, et al. A Review on Semi-supervised Clustering. Information Sciences, 2023, 632: 164-200.
[12] SHI Y C, OTTO C, JAIN A K.Face Clustering: Representation and Pairwise Constraints. IEEE Transactions on Information Forensics and Security, 2018, 13(7): 1626-1640.
[13] ABIN A A, VU V V.A Density-Based Approach for Querying Informative Constraints for Clustering. Expert Systems with Applications, 2020, 161. DOI: 10.1016/j.eswa.2020.113690.
[14] BASU S, BANERJEE A, MOONEY R J.Active Semi-supervision for Pairwise Constrained Clustering // Proc of the SIAM International Conference on Data Mining. Philadelphia, USA: SIAM, 2004: 333-344.
[15] ZONG L L, ZHANG X C, LIU X Y.Multi-view Clustering on Unmapped Data via Constrained Non-negative Matrix Factorization. Neural Networks, 2018, 108: 155-171.
[16] OHI A Q, MRIDHA M F, SAFIR F B, et al. AutoEmbedder: A Semi-supervised DNN Embedding System for Clustering. Know-ledge-Based Systems, 2020, 204. DOI: 10.1016/j.knosys.2020.106190.
[17] LI Y C, WANG Y L, YU D J, et al. ASCENT: Active Supervision for Semi-supervised Learning. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(5): 868-882.
[18] YU C Z, HANSEN J H L. Active Learning Based Constrained Clus-tering for Speaker Diarization. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2017, 25(11): 2188-2198.
[19] SUN B C, ZHOU P, DU L, et al. Active Deep Image Clustering. Knowledge-Based Systems, 2022, 252. DOI: 10.1016/j.knosys.2022.109346.
[20] MALLAPRAGADA P K, JIN R, JAIN A K.Active Query Selection for Semi-supervised Clustering // Proc of the 19th Internatio-nal Conference on Pattern Recognition. Washington, USA: IEEE, 2008: 1-4.
[21] ZHOU P, SUN B C, LIU X W, et al. Active Clustering Ensemble with Self-Paced Learning. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(9): 12186-12200.
[22] SHI Y F, YU Z W, CAO W M, et al. Fast and Effective Active Clustering Ensemble Based on Density Peak. IEEE Transactions on Neural Networks and Learning Systems, 2020, 32(8): 3593-3607.
[23] XIONG S C, AZIMI J, FERN X Z.Active Learning of Constraints for Semi-supervised Clustering. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(1): 43-54.
[24] SOUSA H, DE SOUTO M C P, KUROSHU R M, et al. Automatic Recovering the Number k of Clusters in the Data by Active Query Selection // Proc of the 36th Annual ACM Symposium on Applied Computing. New York, USA: ACM, 2021: 1021-1029.
[25] DENG Y J, YUAN Y B, FU H D, et al. Query-Augmented Active Metric Learning. Journal of the American Statistical Association, 2023, 118(543): 1862-1875.
[26] VAN CRAENENDONCK T, DUMANCIC S, BLOCKEEL H.COBRA: A Fast and Simple Method for Active Clustering with Pairwise Constraints // Proc of the 26th International Joint Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2017: 2871-2877.
[27] VAN CRAENENDONCK T, DUMAN?I? S, VAN WOLPUTTE E. COBRAS: Interactive Clustering with Pairwise Queries // Proc of the 17th International Symposium on Advances in Intelligent Data Analysis. Berlin, Germany: Springer, 2018: 353-366.
[28] JIA Y H, LIU H, HOU J H, et al. Pairwise Constraint Propagation with Dual Adversarial Manifold Regularization. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(12): 5575-5587.
[29] YIN J X, PENG S Y, YANG Z J, et al. Hypergraph Based Semi-supervised Symmetric Nonnegative Matrix Factorization for Image Clustering. Pattern Recognition, 2023, 137. DOI: 10.1016/j.patcog.2022.109274.
[30] HUANG S J, JIN R, ZHOU Z H.Active Learning by Querying Informative and Representative Examples. IEEE Transactions on Pa-ttern Analysis and Machine Intelligence, 2014, 36(10): 1936-1949.
[31] YAO W P, YAO W L, YAO D Z, et al. Shannon Entropy and Quantitative Time Irreversibility for Different and Even Contradictory Aspects of Complex Systems. Applied Physics Letters, 2020, 116(1). DOI: 10.1063/1.5133419.
[32] ZHAO N, WANG H, WEN J J, et al. Identifying Critical Nodes in Complex Networks Based on Neighborhood Information. New Journal of Physics, 2023, 25(8). DOI: 10.1088/1367-2630/ace843.
[33] HUBERT L, ARABIE P. Comparing Partitions. Journal of Classification, 1985, 2: 193-218.
[34] DENG X, LIU J L, ZHONG H, et al. A3S: A General Active Clustering Method with Pairwise Constraints. Proceedings of Machine Learning Research, 2024, 235: 10488-10505.
[35] ZENG G J, PENG H, LI A S, et al. Semi-supervised Clustering via Structural Entropy with Different Constraints // Proc of the SIAM International Conference on Data Mining. Philadelphia, USA: SIAM, 2024: 208-216.