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

doi:10.16451/j.cnki.issn1003-6059.202504004

Abstract
Figure/Table
References (35)
Related Citation (8)

Download: PDF (4003 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

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

Received: 14 January 2025

ZTFLH:

TP311.13

Fund:

National Natural Science Foundation of China(No.62172102), Sichuan Science and Technology Program(No.2024NSFSC1464), Sichuan Scientific Innovation Fund(No.2022JDRC0009), Natural Science Starting Project of Southwest Petroleum University(No.2023QHZ010), Graduate Education and Teaching Reform Research Project of Southwest Petroleum University(No.2024JGYB024)

Corresponding Authors: XIE Wenbo, Ph.D., associate professor. His research interests include data mining and knowledge graph.

About author:: DENG Tao, Master student. His research interests include data mining and machine learning.FU Xun, Master student. His research interests include data mining and active lear-ning.CHEN Bin, Ph.D. candidate. His research interests include data mining and machine learning.ZOU Tian, Master student. Her research interests include data mining and machine learning.WANG Xin, Ph.D., professor. His research interests include data mining and databases.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	XIE Wenbo
	DENG Tao
	FU Xun
	CHEN Bin
	ZOU Tian
	WANG Xin

Cite this article:

XIE Wenbo,DENG Tao,FU Xun等. Active Clustering with Tailored Nearest Neighbor Graph[J]. Pattern Recognition and Artificial Intelligence, 2025, 38(4): 341-358.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.202504004 OR http://manu46.magtech.com.cn/Jweb_prai/EN/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.