稀疏限制的增量式魯棒非負矩陣分解及其應(yīng)用

楊亮東 楊志霞

摘 要：針對魯棒非負矩陣分解（RNMF）的運算規(guī)模隨訓(xùn)練樣本數(shù)量逐漸增多而不斷增大的問題，提出一種稀疏限制的增量式魯棒非負矩陣分解算法。首先，對初始數(shù)據(jù)進行魯棒非負矩陣分解;然后，將其分解結(jié)果參與到后續(xù)迭代運算;最后，在對系數(shù)矩陣增加稀疏限制的情況下與增量式學(xué)習(xí)相結(jié)合，使目標(biāo)函數(shù)值在迭代求解時下降地更快。該算法在節(jié)省運算時間的同時提高了分解后數(shù)據(jù)的稀疏度。在數(shù)值實驗中，將所提算法與魯棒非負矩陣分解算法、稀疏限制的魯棒非負矩陣分解（RNMFSC）算法進行了比較。在ORL和YALE人臉數(shù)據(jù)庫上的實驗結(jié)果表明，所提算法在運算時間和分解后數(shù)據(jù)的稀疏度等方面均優(yōu)于其他兩個算法，并且還具有較好的聚類效果，尤其在YALE人臉數(shù)據(jù)庫上當(dāng)聚類類別數(shù)為3時該算法的聚類準(zhǔn)確率達到了91.67%。

關(guān)鍵詞：增量式學(xué)習(xí);非負矩陣分解;稀疏限制;聚類;人臉識別

中圖分類號：TP181

文獻標(biāo)志碼：A

Abstract： Aiming at the problem that the operation scale of Robust Nonnegative Matrix Factorization （RNMF） increases with the number of training samples， an incremental robust nonnegative matrix factorization algorithm with sparseness constraints was proposed. Firstly， robust nonnegative matrix factorization was performed on initial data. Then， the factorized result participated in the subsequent iterative operation. Finally， with sparseness constraints， the coefficient matrix was combined with incremental learning， which made the objective function value fall faster in the iterative solution. The cost of computation was reduced and the sparseness of data after factorization was improved. In the numerical experiments， the proposed algorithm was compared with RNMF algorithm and RNMF with Sparseness Constraints （RNMFSC） algorithm. The experimental results on ORL and YALE face databases show that the proposed algorithm is superior to the other two algorithms in terms of operation time and sparseness of factorized data， and has better clustering effect， especially in YALE face database， when the clustering number is 3， the clustering accuracy of the proposed algorithm reaches 91.67%.

英文關(guān)鍵詞Key words： incremental learning; Nonnegative Matrix Factorization （NMF）; sparseness constraint; clustering; face recognition

0 引言

圖像處理已經(jīng)廣泛應(yīng)用于生活中各個行業(yè)，涉及機器學(xué)習(xí)、模式識別、數(shù)據(jù)挖掘等領(lǐng)域，也與人類大腦的認知原理緊密相關(guān)，受到了國內(nèi)外學(xué)者的廣泛關(guān)注。在處理圖像過程中子空間降維是一種最為常見的方法， 主要思路是將高維空間的原始數(shù)據(jù)（包括向量數(shù)據(jù)、矩陣數(shù)據(jù)、張量數(shù)據(jù)）映射到低維子空間進行處理，有效避免了維度災(zāi)難[1]所帶來的困難。為了處理矩陣中的數(shù)據(jù)信息以達到降維的目的，通常將矩陣進行分解， 典型的矩陣分解方法主要包括：主成分分析[2]、線性判別分析[3]、獨立分量分析[4]、奇異值分解[5]等。通常這些方法是在一定的限制下對原始數(shù)據(jù)矩陣進行線性變換或分解，從而實現(xiàn)了對原始矩陣降維，但是這些方法的共同點是在求解時有可能會出現(xiàn)負值。 然而在許多應(yīng)用中，負值是與客觀現(xiàn)實相矛盾的，不具有可解釋性。

因此，非負矩陣分解（Nonnegative Matrix Factorization， NMF）[6]這種新的矩陣分解方法被提出，它最早由Lee等[7-8] 于1999年在《Nature》雜志上發(fā)表的。它不同于上述典型的矩陣分解算法，其獨特之處是通過添加非負限制，不但保證了分解結(jié)果的可解釋性，還使分解后的數(shù)據(jù)具有局部表達的特性。后來一些學(xué)者在此基礎(chǔ)上又提出了一些非負矩陣分解的改進算法，并將它們成功地應(yīng)用到人臉識別、數(shù)據(jù)挖掘等領(lǐng)域：文獻[9]中提出了增量式非負矩陣分解（Incremental NMF， INMF）算法;進一步文獻[10]中提出了圖正則（稀疏）增量式非負矩陣分解算法等。這些改進算法有一個共同點是損失函數(shù)都是F范數(shù)或KL散度，而文獻[11]中在2011年提出了一種基于L2，1范數(shù)的非負矩陣分解——魯棒非負矩陣分解（Robust Nonnegative Matrix Factorization， RNMF）算法，該算法自提出后立即得到了學(xué)術(shù)界的廣泛關(guān)注，并取得了大量的研究成果。為了達到特定的實驗效果，有些學(xué)者在基本的魯棒非負矩陣分解算法框架中又添加各種限制，如稀疏性、流形、正交性、判別性等，提出了若干種改進的算法，并將其應(yīng)用于各個領(lǐng)域，取得了良好的實驗效果：文獻[12-13]中考慮到原始數(shù)據(jù)中蘊含著幾何結(jié)構(gòu)，從而將流行學(xué)習(xí)與魯棒非負矩陣分解相結(jié)合，提出了圖正則的魯棒非負矩陣分解（Graph Regularized RNMF， GRNMF）算法，該算法在分解過程中保留了數(shù)據(jù)集攜帶的局部幾何信息，使得在低維能很好地表示原始樣本近鄰結(jié)構(gòu);? 文獻[14-15]中提出了稀疏限制的魯棒非負矩陣分解（RNMF with Sparseness Constraints， RNMFSC）算法，對系數(shù)矩陣進行了稀疏限制，使分解后人臉圖像有更高的識別率。

針對魯棒非負矩陣分解的運算時間和分解后數(shù)據(jù)的稀疏程度來說，隨著樣本個數(shù)的實時增加，直接利用魯棒非負矩陣分解時會出現(xiàn)運算規(guī)模不斷增大的現(xiàn)象。本文就將魯棒非負矩陣分解算法（RNMF）與增量式學(xué)習(xí)結(jié)合在一起，并在此基礎(chǔ)上增加了L2，1范數(shù)的稀疏限制，從而提出了稀疏限制的增量式魯棒非負矩陣分解（Incremental Robust Nonnegative Matrix Factorization with Sparseness Constraints， IRNMFSC）算法。該算法不僅有效地提高了分解后數(shù)據(jù)的稀疏度，得到圖像的最佳局部表示，而且結(jié)合增量式學(xué)習(xí)充分利用上一步對初始數(shù)據(jù)的分解結(jié)果，避免重復(fù)計算從而降低運算時間，提升算法迭代優(yōu)化求解時的收斂速度，使得此算法具有較好的聚類準(zhǔn)確率。最后在多個數(shù)據(jù)庫上的仿真結(jié)果表明，本文IRNMFSC算法均優(yōu)于RNMF算法和RNMFSC算法。

4 結(jié)語

本文提出了稀疏限制的增量式魯棒非負矩陣分解（IRNMFSC），并給出了相應(yīng)的迭代法則和算法步驟，該算法隨著新增樣本個數(shù)的增加依然保持較好的收斂速度。通過對YALE人臉數(shù)據(jù)和ORL人臉數(shù)據(jù)進行數(shù)值實驗，結(jié)果顯示本文算法在迭代過程中收斂速度更快，尋優(yōu)效果更好，不僅縮短了運算時間，而且使分解后的數(shù)據(jù)更為稀疏，能得到局部表達能力更強的基圖像和比較高的聚類準(zhǔn)確率。但是，算法中依然存在著不足，如迭代初值和稀疏參數(shù)的選取等，目前依然沒有一個統(tǒng)一的標(biāo)準(zhǔn)，這些問題都將成為今后要研究的重點。

參考文獻 （References）

[1] PARDALOS P M. Approximate Dynamic Programming： Solving the Curses of Dimensionality[M]. New York： Wiley， 2009： 39-50.

[2] 史衛(wèi)亞，郭躍飛，薛向陽.一種解決大規(guī)模數(shù)據(jù)集問題的核主成分分析算法[J]. 軟件學(xué)報， 2009， 8（20）： 2153-2159. （SHI W Y， GUO Y F， XUE X Y. A kernel principal component analysis algorithm for solving large scale data sets problem[J]. Journal of Software， 2009， 8（20）： 2153-2159.）

[3] 張燕平，竇蓉蓉，趙姝，等. 基于集成學(xué)習(xí)的規(guī)范化LDA人臉識別[J].計算機工程， 2010， 36（14）：144-146.（ZHANG Y P， DOU R R， ZHAO S， et al. Regularized linear discriminant analysis for face recognition based on ensemble learning[J]. Computer Engineering， 2010， 36（14）：144-146.）

[4] KOLDOVSKY Z， TICHAVSKY P. Efficient variant of algorithm fastica for independent component analysis attaining the cramerRAO lower bound[C]// Proceedings of the 2005 IEEE/SP Workshop on Statistical Signal Processing. Piscataway， NJ： IEEE， 2005：1090-1095.

[5] GOLUB G H， REINSCH C. Singular Value Decomposition and Least Squares Solutions[M]. Berlin： Springer， 1971： 403-420.

[6] PAATERO P， TAPPER U. Positive matrix factorization： a nonnegative factor model with optimal utilization of error estimates of data values[J]. Environmental Surveying， 1994， 5（2）：111-126.

[7] LEE D D， SEUNG H S. Learning the parts of objects with nonnegative matrix factorization[J]. Nature， 1999， 401（6755）：788-791.

[8] LEE D D. Algorithms for nonnegative matrix factorization[J]. Advances in Neural Information Processing Systems， 2001， 13（6）：556-562.

[9] BUCAK S S， GUNSEL B. Incremental subspace learning via nonnegative matrix factorization[J]. Pattern Recognition， 2009， 42（5）：788-797.

[10] YU Z Z， LIU Y H， LI B， et al. Incremental graph regulated nonnegative matrix factorization for face recognition[J]. Journal of Applied Mathematics， 2014， 2014（1）： Article ID 928051.

[11] KONG D， HUANG H. Robust nonnegative matrix factorization using L21norm[C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011：673-682.

[12] HUANG S， WANG H， LI T， et al. Robust graph regularized nonnegative matrix factorization for clustering[J]. ACM Transactions on Knowledge Discovery from Data， 2017， 11（3）： Article No. 33.

[13] DAI L Y， FENG C M， LIU J X， et al. Robust nonnegative matrix factorization via joint graph laplacian and discriminative information for identifying differentially expressed genes[J]. Complexity， 2017， 2017（40）： Article ID 4216797.

[14] YANG S， HOU C， ZHANG C， et al. Robust nonnegative matrix factorization via joint sparse and graph regularization[C]// Proceedings of the 2013 International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2014：541-559.

[15] DU S， SHI Y， WANG W. L（3/2） sparsity constrained graph nonnegative matrix factorization for image representation[C]// Proceedings of the 26th Chinese Control and Decision Conference. Piscataway， NJ： IEEE， 2014：2962-2965.

[16] CAI D， HE X， WU X， et al. Nonnegative matrix factorization on manifold[C]// Proceedings of the 8th IEEE International Conference on Data Mining. Piscataway， NJ： IEEE， 2008： 63-72.

[17] XU W， LIU X， GONG Y. Document clustering based on nonnegative matrix factorization[C]// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2003：267-273.

[18] 汪金濤， 曹玉東， 孫福明. 稀疏約束圖正則非負矩陣分解的增量學(xué)習(xí)算法[J]. 計算機應(yīng)用， 2017，37（4）： 1071-1074.（WANG J T， CAO Y D， SUN F M. Incremental learning algorithm based on graph regularized nonnegative matrix factorization with sparseness constraints[J]. Journal of Computer Applications， 2017， 37（4）： 1071-1074.）