Nonnegative Matrix Factorization with Joint Regularization of Manifold Learning and Pairwise Constraints

doi:10.3778/j.issn.1673-9418.1902011

Abstract

Abstract:

In order to handle semi-supervised clustering scenarios where only part of the pairwise constraint information is available in the target dataset, on the basis of nonnegative matrix factorization (NMF) architecture, this paper proposes a nonnegative matrix factorization-based clustering algorithm using joint regularization of manifold learning and pairwise constraints (NMF-JRMLPC) by learning given pairwise constraint knowledge and using manifold regularization theory. On the one hand, graph Laplacian is introduced to depict the manifold structure information contained in a large number of unlabeled samples, and on the other hand, the must-link or cannot-link pair-constraint rules among known samples are integrated into the target optimization design, which greatly improves the clustering performance of the algorithm. In addition, the [l2,1] norm based loss function design also helps to optimize the robustness of NMF-JRMLPC. Experimental results on eight real datasets confirm the validity of the proposed method.

Key words: clustering, nonnegative matrix factorization (NMF), manifold regularization, pairwise constraints, semi-supervised learning

摘要：

为处理目标数据集仅有部分成对约束信息可用的半监督聚类场景，基于非负矩阵分解（NMF）架构，通过学习给定成对约束知识和运用流形正则化理论提出了流形学习与成对约束联合正则化非负矩阵分解聚类方法（NMF-JRMLPC）。该方法一方面引入图拉普拉斯以刻画大量无标记样本蕴含的流形结构信息，另一方面将已知样本间的must-link或cannot-link成对约束规则融入目标优化设计，在很大程度上提高了所得算法的聚类性能。此外基于[l2,1]范数的损失函数设计也有助于优化NMF-JRMLPC的鲁棒性。在八个真实数据集上的实验结果证实了所提方法的有效性。

关键词: 聚类, 非负矩阵分解（NMF）, 流形正则化, 成对约束, 半监督学习

CAO Jiawei, QIAN Pengjiang. Nonnegative Matrix Factorization with Joint Regularization of Manifold Learning and Pairwise Constraints[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(7): 1211-1220.

曹佳伟，钱鹏江. 流形学习与成对约束联合正则化非负矩阵分解[J]. 计算机科学与探索, 2020, 14(7): 1211-1220.

References

[1] Ding C H Q, He X F. Cluster structure of K-means clustering via principal component analysis[C]//LNCS 3056: Proceedings of the 8th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Sydney, May 26-28, 2004. Berlin, Heidelberg: Springer, 2004: 414-418.
[2] Johnson S C. Hierarchical clustering schemes[J]. Psycho-metrika, 1967, 32(3): 241-254.
[3] Yu X F, Ge H W. Potential clustering by automatic determi-nation of cluster centers[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(6): 1004-1012.于晓飞, 葛洪伟. 自动确定聚类中心的势能聚类算法[J]. 计算机科学与探索, 2018, 12(6): 1004-1012.
[4] Luxburg U V. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 14(4): 395-416.
[5] Xiao W Q, Yao S J, Wu S M. Top-N collaborative filtering recommendation algorithm based on user spectrum clus-tering[J]. Computer Engineering and Applications, 2018, 54(7): 138-143.肖文强, 姚世军, 吴善明. 基于用户谱聚类的Top-N协同过滤推荐算法[J]. 计算机工程与应用, 2018, 54(7): 138-143.
[6] Guo W T, Xia L M. Human activity recognition based on multi-view nonnegative matrix factorization[J]. Computer Engi-neering and Applications, 2018, 54(16): 37-43.郭炜婷, 夏利民. 基于多视角非负矩阵分解的人体行为识别[J]. 计算机工程与应用, 2018, 54(16): 37-43.
[7] Cai X, Nie F P, Huang H. Multi-view K-means clustering on big data[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, Aug 3-9, 2013. Menlo Park: AAAI, 2013: 2598-2604.
[8] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788-791.
[9] Li T, Ding C H Q. The relationships among various nonne-gative matrix factorization methods for clustering[C]//Pro-ceedings of the 6th IEEE International Conference on Data Mining, Hong Kong, China, Dec 18-22, 2006. Washington: IEEE Computer Society, 2007: 362-371.
[10] Ding C H Q, Li T, Jordan M I. Convex and semi-nonnegative matrix factorizations[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(1): 45-55.
[11] Huang S D, Xu Z L, Wang F. Nonnegative matrix factoriza-tion with adaptive neighbors[C]//Proceedings of the 17th IEEE International Joint Conference on Neural Networks, Anchorage, May 14-19, 2017. Washington: IEEE Computer Society, 2017: 486-493.
[12] Kong D G, Ding C H Q, Huang H. Robust nonnegative matrix factorization using L21-norm[C]//Proceedings of the 20th ACM International Conference on Information and Know-ledge Management, Glasgow, Oct 24-28, 2011. New York: ACM, 2011: 673-682.
[13] Cai D, He X F, Wu X Y, et al. Non-negative matrix factori-zation on manifold[C]//Proceedings of the 8th IEEE Inter-national Conference on Data Mining, Pisa, Dec 15-19, 2008. Washington: IEEE Computer Society, 2008: 63-72.
[14] Cai D, He X F, Han J W, et al. Graph regularized non-negative matrix factorization for data representation[J]. IEEE Transac-tions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560.
[15] Huang J, Nie F P, Huang H, et al. Robust manifold nonne-gative matrix factorization[J]. ACM Transactions on Know-ledge Discovery from Data, 2014, 8(3): 1-21.
[16] Chapelle O, Schlkopf B, Zien A. Semi-supervised learning[J]. IEEE Transactions on Neural Networks, 2009, 20(3): 542.
[17] Qian P J, Jiang Y Z, Wang S T, et al. Affinity and penalty jointly constrained spectral clustering with all-compatibility, flexibility, and robustness[J]. IEEE Transactions on Neural Networks and Learning Systems, 2017, 28(5): 1123-1138.
[18] Qian P J, Xi C, Xu M, et al. SSC-EKE: semi-supervised classification with extensive knowledge exploitation[J]. Infor-mation Sciences, 2018, 422: 51-76.
[19] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: a geometric framework for learning from labeled and unlabeled examples[J]. Journal of Machine Learning Research, 2006, 7(1): 2399-2434.
[20] Wang S, Siskind J M. Image segmentation with ratio cut[J]. IEEE Transactions on Pattern Analysis and Machine Intel-ligence, 2003, 25(6): 675-690.
[21] Shi J B, Malik J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intel-ligence, 2000, 22(8): 888-905.
[22] Parlett B N. The rayleigh quotient iteration and some genera-lizations for nonnormal matrices[J]. Mathematics of Com-putation, 1974, 28(127): 679-693.
[23] Liu S T, Luo X L. A method based on Rayleigh quotient gradient flow for extreme and interior eigenvalue problems[J]. Linear Algebra & Its Applications, 2010, 432(7): 1851-1863.
[24] Yuan M, Lin Y. Model selection and estimation in regression with grouped variables[J]. Journal of the Royal Statistical Society, 2006, 68(1): 49-67.
[25] Allab K, Labiod L, Nadif M. Simultaneous spectral data embedding and clustering[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(12): 6396-6401.
[26] Lin Z, Chen M, Ma Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. arXiv:1009.5055, 2010.
[27] Jing L P, Ng M K, Huang J Z. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(8): 1026-1041.
[28] Liu J, Mohammed J, Carter J, et al. Distance-based clustering of CGH data[J]. Bioinformatics, 2006, 22(16): 1971-1978.