Manifold regularized nonnegative matrix factorization based on clean data

doi:10.11772/j.issn.1001-9081.2021060962

Abstract

Abstract:

The existing Nonnegative Matrix Factorization （NMF） algorithms are often designed based on Euclidean distance， which makes the algorithms sensitive to noise. In order to enhance the robustness of these algorithms， a Manifold Regularized Nonnegative Matrix Factorization based on Clean Data （MRNMF/CD） algorithm was proposed. In MRNMF/CD algorithm， the low-rank constraints， manifold regularization and NMF technologies were seamlessly integrated， which makes the algorithm perform relatively excellent. Firstly， by adding the low-rank constraints， MRNMF/CD can recover clean data from noisy data and obtain the global structure of the data. Secondly， in order to use the local geometric structure information of the data， manifold regularization was incorporated into the objective function by MRNMF/CD. In addition， an iterative algorithm for solving MRNMF/CD was proposed， and the convergence of this solution algorithm was analyzed theoretically. Experimental results on ORL， Yale and COIL20 datasets show that MRNMF/CD algorithm has better accuracy than the existing algorithms including k-means， Principal Component Analysis （PCA）， NMF and Graph Regularized Nonnegative Matrix Factorization （GNMF）.

Key words: low rank constraint, Nonnegative Matrix Factorization (NMF), manifold regularization, robustness, clean data

摘要：

现有的非负矩阵分解（NMF）算法往往基于欧氏距离来设计目标函数，对噪声比较敏感。为了增强算法的鲁棒性，提出一种基于干净数据的流形正则化非负矩阵分解（MRNMF/CD）算法。在MRNMF/CD算法中，把低秩约束、流形正则化和NMF技术无缝地融为一体，使算法性能较为优异。首先，通过添加低秩约束，MRNMF/CD可以从噪声数据中恢复干净数据，并获得数据的全局结构；其次，为了利用数据的局部几何结构信息，MRNMF/CD把流形正则化融入目标函数中。此外，还提出了一种求解MRNMF/CD的迭代算法，并从理论上分析了该求解算法的收敛性。在ORL、Yale和COIL20数据集上的实验结果表明，MRNMF/CD算法比现有的k-means、主成分分析（PCA）、NMF和图正则化非负矩阵分解（GNMF）算法具有更好的识别准确性。

关键词: 低秩约束, 非负矩阵分解, 流形正则化, 鲁棒性, 干净数据

CLC Number:

TP391.4

Hua LI, Guifu LU, Qinru YU. Manifold regularized nonnegative matrix factorization based on clean data[J]. Journal of Computer Applications, 2021, 41(12): 3492-3498.

李华, 卢桂馥, 余沁茹. 基于干净数据的流形正则化非负矩阵分解[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3492-3498.

Figures/Tables 8

Tab. 1 Running time comparison of different algorithms on ORL dataset

算法	运行时间/s	算法	运行时间/s
PCA	0.03	GNMF	3.05
NMF	0.05	MRNMF/CD	35.86

Tab. 2 Experimental datasets and their characteristics

数据集	样本量 $n$	特征量 $m$	类数
ORL	400	1 024	40
Yale	165	1 024	15
COIL20	1 440	1 024	20

Tab. 2 Experimental datasets and their characteristics

数据集	样本量 $n$	特征量 $m$	类数
ORL	400	1 024	40
Yale	165	1 024	15
COIL20	1 440	1 024	20

Fig. 1 Some examples of images in datasets ORL， Yale and COIL20

Tab. 3 Clustering results comparison on ORL dataset

C	ACC					NMI
C	k-means	PCA	NMF	GNMF	MRNMF/CD	k-means	PCA	NMF	GNMF	MRNMF/CD
均值	39.50	37.00	35.60	52.70	64.61	41.05	38.90	37.25	57.35	77.24
8	18.25	18.00	17.50	51.75	72.37	18.25	18.00	17.50	55.75	77.96
16	34.25	29.50	27.75	51.75	65.87	34.25	29.75	27.75	56.75	76.68
24	41.25	41.00	39.75	52.25	61.67	42.50	41.50	40.50	56.75	76.35
32	50.25	47.25	45.25	57.75	61.91	53.25	51.50	48.25	62.00	77.24
40	53.50	49.25	47.75	50.00	61.25	57.00	53.75	52.25	62.00	77.97

Tab. 4 Clustering results on Yale dataset

C	ACC					NMI
C	k-means	PCA	NMF	GNMF	MRNMF/CD	k-means	PCA	NMF	GNMF	MRNMF/CD
均值	28.48	28.61	28.73	39.76	48.90	28.85	29.45	29.70	41.33	42.33
3	13.33	12.12	16.97	42.42	69.09	13.33	12.12	16.97	43.03	40.83
6	21.82	22.42	22.42	38.79	48.18	21.82	22.42	22.42	40.61	38.14
9	28.48	31.52	30.91	38.18	47.17	28.48	31.52	30.91	40.61	45.30
12	39.39	38.79	36.97	39.39	41.29	40.00	39.39	37.58	41.21	43.63
15	39.39	38.18	36.36	40.00	38.79	40.61	41.82	40.61	41.21	43.74

Tab. 5 Clustering results on COIL20 dataset

C	ACC					NMI
C	k-means	PCA	NMF	GNMF	MRNMF/CD	k-means	PCA	NMF	GNMF	MRNMF/CD
均值	42.69	40.78	43.75	62.46	59.91	43.78	41.96	44.29	65.21	64.63
4	20.00	20.00	20.00	62.43	71.53	20.00	20.00	20.00	66.53	58.12
8	33.68	30.49	30.90	60.49	68.51	33.68	30.49	30.90	62.99	67.86
12	44.10	43.89	47.08	62.50	59.72	44.10	43.96	47.08	66.32	69.05
16	55.21	52.85	56.67	64.86	49.74	56.46	54.93	56.81	65.83	62.52
20	60.49	56.67	64.10	62.01	50.07	64.65	60.42	66.67	64.38	65.59

Fig. 2 Influence of each parameter on accuracy in MRNMF/CD algorithm

Fig. 3 Convergence curves of MRNMF/CD algorithm on datasets Yale， COIL20 and ORL

References 32

1	MAATEN L VAN DER， POSTMA E O， HERIK J VAN DEN. Dimensionality reduction： a comparative review［EB/OL］. ［2021-03-10］..
2	DOUIK A， HASSIBI B. Non-negative matrix factorization via low-rank stochastic manifold optimization［C］// Proceedings of the 2020 Information Theory and Applications Workshop. Piscataway： IEEE， 2020： 1-5. 10.1109/ita50056.2020.9244937
3	SHANG R H， SONG J Z， JIAO L C， et al. Double feature selection algorithm based on low-rank sparse non-negative matrix factorization［J］. International Journal of Machine Learning and Cybernetics， 2020， 11（8）： 1891-1908. 10.1007/s13042-020-01079-6
4	HAEFFELE B D， VIDAL R. Structured low-rank matrix factorization： global optimality， algorithms， and applications［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2020， 42（6）： 1468-1482. 10.1109/tpami.2019.2900306
5	TAO D P， JIN L W， YANG Z， et al. Rank preserving sparse learning for Kinect based scene classification［J］. IEEE Transactions on Cybernetics， 2013， 43（5）： 1406-1417. 10.1109/tcyb.2013.2264285
6	YE R Z， LI X L. Compact structure hashing via sparse and similarity preserving embedding［J］. IEEE Transactions on Cybernetics， 2016， 46（3）： 718-729. 10.1109/tcyb.2015.2414299
7	FANG X Z， XU Y， LI X L， et al. Locality and similarity preserving embedding for feature selection［J］. Neurocomputing， 2014， 128： 304-315. 10.1016/j.neucom.2013.08.040
8	ZHU X F， LI X L， ZHANG S C. Block-row sparse multiview multilabel learning for image classification［J］. IEEE Transactions on Cybernetics， 2016， 46（2）： 450-461. 10.1109/tcyb.2015.2403356
9	TURK M， PENTLAND A. Eigenfaces for recognition［J］. Journal of Cognitive Neuroscience， 1991， 3（1）： 71-86. 10.1162/jocn.1991.3.1.71
10	LEE D D， SEUNG H S. Algorithms for non-negative matrix factorization［C］// Proceedings of the 13th International Conference on Neural Information Processing Systems.Cambridge： MIT Press， 2000： 535-541.
11	LEE D D， SEUNG H S. Learning the parts of objects by non-negative matrix factorization［J］. Nature， 1999， 401（6755）： 788-791. 10.1038/44565
12	PAATERO P， TAPPER U. Positive matrix factorization： a non‐negative factor model with optimal utilization of error estimates of data values［J］. Environmetrics， 1994， 5（2）： 111-126. 10.1002/env.3170050203
13	HOYER P O. Non-negative sparse coding［C］// Proceedings of the 12th IEEE Workshop on Neural Networks for Signal Processing. Piscataway： IEEE， 2002： 557-565. 10.1109/nnsp.2002.1030067
14	GU Q Q， ZHOU J. Local learning regularized nonnegative matrix factorization［C］// Proceedings of the 21st International Joint Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2009： 1046-1051. 10.5244/c.23.9
15	WANG J Z， ZHAO R， WANG Y， et al. Locality constrained graph optimization for dimensionality reduction［J］. Neurocomputing， 2017， 245： 55-67. 10.1016/j.neucom.2017.03.046
16	WEN J， FANG X Z， XU Y， et al. Low-rank representation with adaptive graph regularization［J］. Neural Networks， 2018， 108： 83-96. 10.1016/j.neunet.2018.08.007
17	MENG Y， SHANG R H， JIAO L C， et al. Dual-graph regularized non-negative matrix factorization with sparse and orthogonal constraints［J］. Engineering Applications of Artificial Intelligence， 2018， 69： 24-35. 10.1016/j.engappai.2017.11.008
18	万源，陈晓丽，张景会，等. 低秩稀疏图嵌入的半监督特征选择［J］. 中国图象图形学报， 2018， 23（9）： 1316-1325. 10.11834/jig.170570
	WAN Y， CHEN X L， ZHANG J H， et al. Semi-supervised feature selection based on low-rank sparse graph embedding［J］. Journal of Image and Graphics， 2018， 23（9）： 1316-1325. 10.11834/jig.170570
19	TIAN M， LENG C C， WU H N， et al. Total variation constrained graph-regularized convex non-negative matrix factorization for data representation［J］. IEEE Signal Processing Letters， 2020， 28： 126-130. 10.1109/lsp.2020.3047576
20	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， 2011， 33（8）： 1548-1560. 10.1109/tpami.2010.231
21	LI X L， CUI G S， DONG Y S. Graph regularized non-negative low-rank matrix factorization for image clustering［J］. IEEE Transactions on Cybernetics， 2017， 47（11）： 3840-3853. 10.1109/tcyb.2016.2585355
22	LU Y W， LAI Z H， LI X L， et al. Learning parts-based and global representation for image classification［J］. IEEE Transactions on Circuits and Systems for Video Technology， 2018， 28（12）： 3345-3360. 10.1109/tcsvt.2017.2749980
23	WRIGHT J， PENG Y G， MA Y， et al. Robust principal component analysis： exact recovery of corrupted low-rank matrices via convex optimization［C］// Proceedings of the 22nd International Conference on Neural Information Processing Systems. Red Hook， NY： Curran Associates Inc.， 2009： 2080-2088.
24	LIN Z C， CHEN M M， MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices［EB/OL］. （2013-10-18）［2021-03-10］..
25	JI H， LIU C Q， SHEN Z W， et al. Robust video denoising using low rank matrix completion［C］// Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2010： 1791-1798. 10.1109/cvpr.2010.5539849
26	BAO B K， LIU G C， XU C S， et al. Inductive robust principal component analysis［J］. IEEE Transactions on Image Processing， 2012， 21（8）： 3794-3800. 10.1109/tip.2012.2192742
27	CAI J F， CANDÈS E J， SHEN Z W. A singular value thresholding algorithm for matrix completion［J］. SIAM Journal on Optimization， 2010， 20（4）： 1956-1982. 10.1137/080738970
28	KOUTROUMBAS K， THEODORIDIS S. Pattern Recognition［M］. 4th ed. Orlando： Academic Press， 2009： 335-338. 10.1016/b978-1-59749-272-0.50003-7
29	KUHN H D， TUCKER A W. Nonlinear programming ［C］//Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. Berkeley： University of California Press， 1951： 481-492.
30	LEE D D， SEUNG H S. Algorithms for non-negative matrix factorization［C］// Proceedings of the 22nd International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2000：535-541.
31	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. 10.1016/j.neucom.2019.11.070
32	MAZUMDER R， HASTIE T， TIBSHIRANI R. Spectral regularization algorithms for learning large incomplete matrices［J］. Journal of Machine Learning Research， 2010， 11： 2287-2322.

[1]	Xuebin CHEN, Zhiqiang REN, Hongyang ZHANG. Review on security threats and defense measures in federated learning [J]. Journal of Computer Applications, 2024, 44(6): 1663-1672.
[2]	Weina DONG, Jia LIU, Xiaozhong PAN, Lifeng CHEN, Wenquan SUN. High-capacity robust image steganography scheme based on encoding-decoding network [J]. Journal of Computer Applications, 2024, 44(3): 772-779.
[3]	Jintao RAO, Zhe CUI. Electronic voting scheme based on SM2 threshold blind signature [J]. Journal of Computer Applications, 2024, 44(2): 512-518.
[4]	Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539.
[5]	Han WANG, Yuan WAN, Dong WANG, Yiming DING. Robust weight matrix combination selection method of broad learning system [J]. Journal of Computer Applications, 2024, 44(10): 3032-3038.
[6]	Xuyan ZHAO, Yunhe CUI, Chaohui JIANG, Qing QIAN, Guowei SHEN, Chun GUO, Xianchao LI. CHAIN： edge computing node placement algorithm based on overlapping domination [J]. Journal of Computer Applications, 2023, 43(9): 2812-2818.
[7]	Jian GAO, Zhi LI, Bin FAN, Chuanxian JIANG. Efficient robust zero-watermarking algorithm for 3D medical images based on ray-casting sampling and quaternion orthogonal moment [J]. Journal of Computer Applications, 2023, 43(4): 1191-1197.
[8]	Mengting GE, Minghua WAN. Feature extraction model based on neighbor supervised locally invariant robust principal component analysis [J]. Journal of Computer Applications, 2023, 43(4): 1013-1020.
[9]	Xianbojun FAN, Lijia CHEN, Shen LI, Chenlu WANG, Min WANG, Zan WANG, Mingguo LIU. Robust joint modeling and optimization method for visual manipulators [J]. Journal of Computer Applications, 2023, 43(3): 962-971.
[10]	Mengdi SUN, Zhonggui SUN, Xu KONG, Hongyan HAN. Design of guided adaptive mathematical morphology for multimodal images [J]. Journal of Computer Applications, 2023, 43(2): 560-566.
[11]	Qize REN, Hongjie JIA, Dongyu CHEN. Large-scale subspace clustering algorithm with Local structure learning [J]. Journal of Computer Applications, 2023, 43(12): 3747-3754.
[12]	GAO Gong, YANG Hongyu, LIU Hong. 3D point cloud face recognition based on deep learning [J]. Journal of Computer Applications, 2021, 41(9): 2736-2740.
[13]	LI Xingfeng, HUANG Yuqing, REN Zhenwen, LI Yihong. Robust multi-view clustering algorithm based on adaptive neighborhood [J]. Journal of Computer Applications, 2021, 41(4): 1093-1099.
[14]	WANG Jinkai, JIA Xu. Vein recognition algorithm based on Siamese nonnegative matrix factorization with transferability [J]. Journal of Computer Applications, 2021, 41(3): 898-903.
[15]	Yunpeng GONG, Zhiyong ZENG, Feng YE. Person re-identification method based on grayscale feature enhancement [J]. Journal of Computer Applications, 2021, 41(12): 3590-3595.