Constrained Propagation Self-Adaptived Semi-Supervised Non-Negative Matrix Factorization Clustering Algorithm

doi:10.3778/j.issn.1002-8331.2310-0218

Abstract

Abstract: Symmetric non-negative matrix factorization (NMF) can naturally capture the embedded clustering structure in the graph representation. It is an important method for linear and nonlinear data clustering applications. However, it is sensitive to the initialization of variables, and the quality of the initialization matrix greatly affects the clustering performance. In semi-supervised clustering, it faces the challenge of learning a more discriminative representation from limited labeled data. This paper introduces a constrained propagation self-adaptive self-supervised non-negative matrix factorization clustering algorithm (CPS3NMF) to solve the above problems. The algorithm propagates finite constraints to unconstrained data points, constructing a similarity matrix imbued with constraint information. The resultant similarity matrix serves the role of a non-negative symmetric matrix decomposition in SNMF and functions as graph regularization for the assignment matrix, fully utilizing the limited constraint information to preserve the geometrical structure of data space. Concurrently, leveraging the sensitivity of initial features in SNMF, the algorithm employs adaptively learned weights to rank the quality of multiple initial matrices. By integrating results from multiple clustering attempts, it progressively enhances the performance of semi-supervised clustering. Experiments on 6 public datasets show that the proposed CPS3NMF algorithm outperforms other state-of-the-art algorithms, proving its effectiveness in semi-supervised clustering.

Key words: symmetric non-negative matrix factorization, semi-supervised learning, constraint propagation, clustering

摘要： 对称非负矩阵分解（SNMF）能够自然地捕获图表示中嵌入的聚类结构，是线性和非线性数据聚类应用的重要方法。但其对变量的初始化较敏感，初始化矩阵的质量好坏会较大地影响聚类性能，且在半监督聚类中面临着从有限的标记数据中学习更具辨别力表示的挑战。针对以上问题，提出了一种约束传播自适应半监督非负矩阵分解聚类算法（constrained propagation self-adaptived semi-supervised non-negative matrix factorization clustering algorithm，CPS3NMF）。该算法将有限约束传播到无约束数据点，构建出带有约束信息的相似矩阵，所获得的相似矩阵充当SNMF中分解的非负对称矩阵，还用于对分配矩阵进行图正则化，充分利用约束信息来保存数据空间的几何结构。同时结合SNMF对初始化特征的敏感性，使用自适应学习的权重对多个初始化矩阵的质量进行排序，集成多次聚类结果来逐步提高半监督聚类性能。在6个公开数据集上进行实验表明所提出的CPS3NMF算法优于其他先进算法，证明了其在半监督聚类中的有效性。

关键词: 对称非负矩阵分解, 半监督学习, 约束传播, 聚类

ZHU Tuoji, LIN Haoshen, ZHAO Weihao, WANG Jing, YANG Xiaojun. Constrained Propagation Self-Adaptived Semi-Supervised Non-Negative Matrix Factorization Clustering Algorithm[J]. Computer Engineering and Applications, 2024, 60(13): 81-91.

朱拓基, 林浩申, 赵伟豪, 王靖, 杨晓君. 约束传播自适应半监督非负矩阵分解聚类算法[J]. 计算机工程与应用, 2024, 60(13): 81-91.

References

[1] LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[C]//Advances in Neural Information Processing Systems, 2000.
[2] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788-791.
[3] DING C, HE X F, SIMON H D. On the equivalence of nonnegative matrix factorization and spectral clustering[C]//Proceedings of the 2005 SIAM International Conference on Data Mining, 2005: 606-610.
[4] CAI D, HE X F, HAN J W, et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 33(8): 1548-1560.
[5] 刘家骥, 包崇明, 周丽华, 等. 图正则化非负矩阵分解的异质网社区发现[J]. 计算机工程与应用, 2020, 56(21): 131-138.
LIU J J, BAO C M, ZHOU L H, et al. Community detecting method based on non-negative matrix factorization with graph regular term in heterogeneous information networks[J]. Computer Engineering and Applications, 2020, 56(21): 131-138.
[6] HUANG S D, XU Z L, KANG Z, et al. Regularized nonnegative matrix factorization with adaptive local structure learning[J]. Neurocomputing, 2020, 382: 196-209.
[7] LIU H F, WU Z H, LI X L, et al. Constrained nonnegative matrix factorization for image representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 34(7): 1299-1311.
[8] WANG D, GAO X B, WANG X M. Semi-supervised nonnegative matrix factorization via constraint propagation[J]. IEEE Transactions on Cybernetics, 2015, 46(1): 233-244.
[9] LI H R, GAO Y L, LIU J M, et al. Semi-supervised graph regularized nonnegative matrix factorization with local coordinate for image representation[J]. Signal Processing: Image Communication, 2022, 102: 116589.
[10] 刘兴建, 杨晓夫, 胡磊. 基于非负矩阵分解的半监督模型用于多层网络聚类[J]. 计算机与现代化, 2023(2): 83-88.
LIU X J, YANG X F, HU L. A semi-supervised model with non-negative matrix factorization for multiplex network clustering[J]. Computer and Modernization, 2023(2): 83-88.
[11] BABAEE M, TSOUKALAS S, BABAEE M, et al. Discriminative nonnegative matrix factorization for dimensionality reduction[J]. Neurocomputing, 2016, 173: 212-223.
[12] XING Z W, WEN M, PENG J G, et al. Discriminative semi-supervised non-negative matrix factorization for data clustering[J]. Engineering Applications of Artificial Intelligence, 2021, 103: 104289.
[13] PENG S Y, SER W, CHEN B, et al. Robust semi-supervised nonnegative matrix factorization for image clustering[J]. Pattern Recognition, 2021, 111: 107683.
[14] 高海燕, 刘万金, 黄恒君. 鲁棒自适应对称非负矩阵分解聚类算法[J]. 计算机应用研究, 2023, 40(4): 1024-1029.
GAO H Y, LIU W J, HUANG H J. Robust self-adaptived symmetric nonnegative matrix factorization clustering algorithm[J]. Application Research of Computers, 2023, 40(4): 1024-1029.
[15] KUANG D, DING C, PARK H. Symmetric nonnegative matrix factorization for graph clustering[C]//Proceedings of the 2012 SIAM International Conference on Data Mining, 2012: 106-117.
[16] KABIR K L, CHENNUPATI G, VANGARA R, et al. Decoy selection in protein structure determination via symmetric non-negative matrix factorization[C]//Proceedings of the 2020 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2020: 23-28.
[17] MA Y Y, ZHAO J M, MA Y J. MHSNMF: multi-view hessian regularization based symmetric nonnegative matrix factorization for microbiome data analysis[J]. BMC Bioinformatics, 2020, 21: 1-18.
[18] LUO X, LIU Z G, JIN L, et al. Symmetric nonnegative matrix factorization-based community detection models and their convergence analysis[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 33(3): 1203-1215.
[19] JIA Y H, LIU H, HOU J H, et al. Self-supervised symmetric nonnegative matrix factorization[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2021, 32(7): 4526-4537.
[20] YANG L, CAO X C, JIN D, et al. A unified semi-supervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics, 2014, 45(11): 2585-2598.
[21] ZHANG X C, ZONG L L, LIU X Y, et al. Constrained clustering with nonnegative matrix factorization[J]. IEEE Transactions on Neural Networks and Learning Systems, 2015, 27(7): 1514-1526.
[22] LAN L, LIU T L, ZHANG X, et al. Label propagated nonnegative matrix factorization for clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(1): 340-351.
[23] LIU J M, WANG Y C, MA J, et al. Constrained nonnegative matrix factorization based on label propagation for data representation[J]. IEEE Transactions on Artificial Intelligence, 2024, 5(2): 590-601.
[24] HUANG D, WANG C D, LAI J H. Locally weighted ensemble clustering[J]. IEEE Transactions on Cybernetics, 2017, 48(5): 1460-1473.
[25] DIETTERICH T G. Ensemble methods in machine learning[C]//Proceedings of the International Workshop on Multiple Classifier Systems. Berlin, Heidelberg: Springer, 2000: 1-15.
[26] BIAN Y J, CHEN H H. When does diversity help generali-
zation in classification ensembles?[J]. IEEE Transactions on Cybernetics, 2021, 52(9): 9059-9075.
[27] FIGUEIREDO M A T, BIOUCAS-DIAS J M, NOWAK R D. Majorization-minimization algorithms for wavelet-based image restoration[J]. IEEE Transactions on Image Processing, 2007, 16(12): 2980-2991.
[28] SUN Y, BABU P, PALOMAR D P. Majorization-minimization algorithms in signal processing, communications, and machine learning[J]. IEEE Transactions on Signal Processing, 2016, 65(3): 794-816.