稀疏約束圖正則非負矩陣分解的增量學(xué)習算法

汪金濤，曹玉東，孫福明

遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001)(*通信作者電子郵箱cyd9229@163.com)

稀疏約束圖正則非負矩陣分解的增量學(xué)習算法

汪金濤，曹玉東*，孫福明

遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001)(*通信作者電子郵箱cyd9229@163.com)

針對非負矩陣分解后數(shù)據(jù)的稀疏性降低、訓(xùn)練樣本增多導(dǎo)致運算規(guī)模不斷增大的現(xiàn)象，提出了一種稀疏約束圖正則非負矩陣分解的增量學(xué)習算法。該方法不僅考慮數(shù)據(jù)的幾何信息，而且對系數(shù)矩陣進行稀疏約束，并將它們與增量學(xué)習相結(jié)合。算法在稀疏約束和圖正則化的條件下利用上一步的分解結(jié)果參與迭代運算，在節(jié)省大量運算時間的同時提高了分解后數(shù)據(jù)的稀疏性。在ORL和PIE人臉數(shù)據(jù)庫上的實驗結(jié)果表明了該算法的有效性。

非負矩陣分解；稀疏約束；圖正則；幾何結(jié)構(gòu)；增量學(xué)習

0 引言

子空間降維是機器學(xué)習和模式識別的一種常用方法，也是數(shù)據(jù)挖掘等領(lǐng)域的研究熱點。1999年，Lee等[1]在《Nature》上首次提出了非負矩陣分解(Non-negative Matrix Factorization, NMF)的概念，通過添加“矩陣中所有元素均非負”的限制條件，保證了分解結(jié)果的可解釋性。隨后，大量改進算法被提出并應(yīng)用。文獻[2]在分解原始矩陣時，對基矩陣和系數(shù)矩陣施加稀疏約束，將稀疏編碼的思想引入到非負矩陣分解中，提出稀疏約束非負矩陣分解算法(NMF with Sparseness Constraints, NMFSC)具有存儲空間少的優(yōu)點;文獻[3]將增量學(xué)習與非負矩陣分解相結(jié)合，提出了增量非負矩陣分解(Incremental NMF, INMF)算法，利用上一步的分解結(jié)果參與迭代運算，當再新加入訓(xùn)練樣本時不會再重新進行運算，從而節(jié)省了運算時間;文獻[4]將稀疏約束和增量學(xué)習思想引入到了非負矩陣分解中，提出了稀疏約束下非負矩陣分解(Incremental NMFSC, INMFSC)的增量學(xué)習算法，在運算時間和稀疏度等指標上都有大幅優(yōu)化。

上述的標準NMF及其改進算法都屬于無監(jiān)督分解方法，沒有考慮樣本的標簽信息。文獻[5]提出一種受限的非負矩陣分解(Constrained NMF, CNMF)算法，它充分考慮已有的類別信息，將樣本的類別信息作為一個硬約束，使已標記樣本類別信息在低維空間中仍保持一致，但該模型沒有考慮到數(shù)據(jù)的幾何結(jié)構(gòu)關(guān)系。文獻[6]將流形學(xué)習與非負矩陣分解相結(jié)合，提出的圖正則化非負矩陣分解(Graph Regularized NMF, GNMF)能夠在NMF的低維表示中考慮原始樣本的近鄰結(jié)構(gòu)，使得原始樣本的近鄰結(jié)構(gòu)在非負矩陣分解的低維中得到很好的保留。

文獻[7]提出的稀疏約束圖正則非負矩陣分解(GNMF with Sparseness Constraints, GNMFSC)算法,不僅考慮了數(shù)據(jù)的幾何信息，并且對系數(shù)矩陣增加稀疏約束，使分解后的圖像具有更高的識別率。本文將增量學(xué)習的思想引入稀疏約束圖正則非負矩陣分解中，提出了稀疏約束圖正則非負矩陣分解的增量學(xué)習(Incremental learning based on GNMFSC, IGNMFSC)算法，不僅有效地保持樣本的局部結(jié)構(gòu)，使算法具有較高的分類準確率，還能結(jié)合增量學(xué)習充分利用上一步的分解結(jié)果，避免重復(fù)計算從而降低運算時間。下面給出算法的迭代規(guī)則，并進行實驗驗證算法的有效性。

1 非負矩陣分解

(1)

s.t.W≥0,H≥0

目標函數(shù)的乘性迭代規(guī)則為：

(2)

(3)

其中：i=1,2,…,m；j=1,2,…,n。當給定迭代終止條件后，對隨機生成的初始非負矩陣W0和H0,按式(2)和(3)交替迭代更新直到滿足終止條件，可得到最終的W和H。

2 IGNMFSC算法

2.1 目標函數(shù)

圖正則非負矩陣分解在矩陣分解過程中要求使降維后的數(shù)據(jù)保持原始數(shù)據(jù)的幾何信息。在分解過程中，GNMF作如下假設(shè)：若點xi和xj在原空間中是近鄰點，那么在新的基下所對應(yīng)的坐標vir和vjr也一定是接近的。

JGNMF=‖V-WHT‖2+λ·Tr(HTLH)

(4)

s.t.W≥0,H≥0

設(shè)Wk和Hk分別表示樣本集合Vk的非負矩陣分解后得到的基矩陣和系數(shù)矩陣，Lk是樣本集合Vk的拉普拉斯矩陣，r是基向量的個數(shù)，λ是正則化參數(shù)，β是稀疏系數(shù)，且β∈(0,1),k表示當前樣本集合中存在k個樣本。Fk代表Vk經(jīng)過非負矩陣分解后的目標函數(shù)，此時，F(xiàn)k的表達式包含非負矩陣分解、圖正則化、稀疏約束三項，如下所示：

(5)

當?shù)趉+1個訓(xùn)練樣本加入后，目標函數(shù)變?yōu)椋?/p>

(6)

其中：Wk+1和Hk+1分別表示樣本集合Vk+1非負矩陣分解后得到的值，Lk+1是樣本集合Vk+1的拉普拉斯矩陣。

2.2 迭代規(guī)則

隨著訓(xùn)練樣本數(shù)量的增多，新訓(xùn)練樣本的表達能力逐漸減小。因此當訓(xùn)練樣本數(shù)量足夠大時，新加入訓(xùn)練樣本對于基矩陣W并不會有太大的影響，其對應(yīng)的系數(shù)向量hk受到的影響也同樣較小。所以當新樣本vk+1到來時，系數(shù)矩陣Hk+1的前k列向量可以近似等于Hk的列向量，即Hk+1=[Hk,hk+1],目標函數(shù)Fk+1可以重寫為如下形式：

(7)

由此可以得到Fk與Fk+1之間的近似關(guān)系，這樣就利用了上一步的分解結(jié)果，當加入了新的訓(xùn)練樣本時，不需要重新迭代運算，從而降低了運算規(guī)模。fk+1表示新樣本加入后損失函數(shù)的增量式，在得到目標函數(shù)的增量表達式Fk+1后，利用梯度下降法推導(dǎo)出相應(yīng)的迭代公式。得出系數(shù)矩陣增量部分hk+1的迭代規(guī)則如下：

(8)

其中:a=1,2,…,r。

接下來計算Fk+1對hk+1的偏導(dǎo)數(shù)：

(9)

為了保證迭代過程中數(shù)據(jù)的非負性，遵循乘性迭代規(guī)則得到梯度下降的迭代步長ηa:

ηa=

(10)

其中：Lk+1是樣本Vk+1的拉普拉斯矩陣，(Lk+1)k+1,:、(Dk+1)k+1,:和(Sk+1)k+1,:分別為Lk+1、Dk+1和Sk+1所對應(yīng)的第k+1行的行向量。

將式(9)和(10)的偏導(dǎo)數(shù)的值和迭代步長代入式(8)的迭代公式中，得到hk+1的最終迭代規(guī)則：

(hk+1)a←(hk+1)a·

(11)

用相同的方法可以求得基矩陣W的更新規(guī)則為：

(12)

為了區(qū)分與系數(shù)矩陣H的迭代步長，設(shè)ηia為上式中基矩陣W的迭代步長，

(13)

同樣地，將式(13)和(14)中的偏導(dǎo)數(shù)值和迭代步長代入基矩陣的迭代公式(12)中，得到Wk+1的迭代規(guī)則：

(14)

由此，歸納IGNMFSC算法步驟如下：

1)隨機初始化正矩陣W和H；

2)對訓(xùn)練樣本集V(包含k個訓(xùn)練樣本)按以下規(guī)則進行迭代，直至滿足收斂條件：

3)當加入新訓(xùn)練樣本vk+1時，按以下迭代規(guī)則更新W和H直至滿足收斂條件，

(hk+1)a←(hk+1)a·

其中：Hk+1=[Hk,hk+1],hk+1初始化為hk。

3 實驗結(jié)果及分析

實驗環(huán)境：Windows7操作系統(tǒng)，CPU為3.30GHz，內(nèi)存8GB，程序環(huán)境為MatlabR2014b。

3.1 數(shù)據(jù)描述及參數(shù)設(shè)置

實驗采用標準人臉庫ORL和PIE人臉庫進行算法的有效性驗證。ORL人臉數(shù)據(jù)庫包含40人面部圖像，每人10種不同的姿態(tài)；在每個類取6個共240個作為訓(xùn)練樣本，迭代次數(shù)設(shè)為200。PIE人臉數(shù)據(jù)庫(PIE_pose子集)含68名志愿者面部姿態(tài)以及表情圖像，共有170種不同的拍攝條件，共11 560幅圖像；在每個類取100個共6 800個作訓(xùn)練樣本，迭代次數(shù)為150。

IGNMFSC算法模型中有兩個關(guān)鍵的折中參數(shù)：正則項參數(shù)λ和稀疏約束β。

為了確定正則項參數(shù)λ,分別在選取的兩個數(shù)據(jù)集上進行實驗。從實驗結(jié)果來分析，IGNMFSC算法在λ在10～500變化時，其值對文章討論的運行時間和稀疏度影響不大，根據(jù)實際經(jīng)驗，在兩個數(shù)據(jù)集取λ=100。同樣，稀疏系數(shù)β的值也通過實驗結(jié)果確定，β∈(0,1),若稀疏系數(shù)β的值太大會使圖像過于稀疏導(dǎo)致不能很好地表示，根據(jù)文獻[12]提供的一種用準確率和歸一化互信息兩個指標決定驗證算法有效性的思想，分別在兩個數(shù)據(jù)集上進行實驗，研究了β值的選取對準確率和歸一化互信息的影響。通過對比實驗，在ORL數(shù)據(jù)集上稀疏約束β設(shè)為0.3，PIE數(shù)據(jù)集上稀疏約束β設(shè)為0.6。

3.2 運行時間對比

在ORL人臉數(shù)據(jù)庫上，初始訓(xùn)練樣本為240時NMF[1]、INMFSC[4]、GNMFSC[7]和本文IGNMFSC算法隨新增樣本數(shù)量的增多而消耗的時間如表1所示；在PIE數(shù)據(jù)集上，初始訓(xùn)練樣本為6 800時算法的時間消耗如表2所示。

表1 ORL庫新增訓(xùn)練樣本時不同算法的時間消耗 s

表2 PIE庫新增訓(xùn)練樣本時不同算法的時間消耗 s

由表1～2可知，與幾種對比算法相比，本文算法在運算時間上有明顯優(yōu)勢，而當新增訓(xùn)練樣本超過一定數(shù)量時，IGNMFSC算法仍能保持相對高的運算效率。

3.3 稀疏度的度量

度量稀疏度的函數(shù)為：

(15)

其中:n是向量x的維度，‖·‖1是向量的1范數(shù)，‖·‖2是向量的2范數(shù)，0≤sparseness(x)≤1。當x僅有一個非零元素時,函數(shù)值為1；當所有元素都不為零且相等時，函數(shù)值為0。

以式(15)作為稀疏度度量標準，則經(jīng)過NMF[1]、INMFSC[4]、GNMFSC[7]和本文IGNMFSC幾種算法分解后得到的基矩陣W和系數(shù)矩陣H的稀疏度如表3所示。

表3 幾種算法得到的因子矩陣稀疏度

圖1～2表示在數(shù)據(jù)庫ORL和PIE上的基圖像。其中，ORL數(shù)據(jù)集的基矩陣特征維數(shù)取36，PIE數(shù)據(jù)集的基矩陣特征維數(shù)取20。由圖1～2可以看出，NMF算法的基向量最接近原圖像，容易得到原始樣本的最優(yōu)表示，但是它的稀疏度較差，存儲效率低。同其他的NMF改進算法相比，IGNMFSC算法能得到更稀疏的基圖像，由此表明算法得到了圖像的最佳的局部表示。

圖1 ORL數(shù)據(jù)集的基圖像(r=36)

圖2 PIE數(shù)據(jù)集的基圖像(r=20)

4 結(jié)語

本文提出了稀疏約束圖正則非負矩陣分解的增量學(xué)習算法，并給出了相應(yīng)的迭代規(guī)則和算法步驟。以O(shè)RL人臉庫和PIE人臉庫的數(shù)據(jù)作為實驗對象進行驗證，結(jié)果顯示本文算法不僅縮短了運行時間，而且使分解后的數(shù)據(jù)更為稀疏，能得到局部表達能力和判別能力更強的基圖像。

)

[1]LEEDD,SEUNGHS.Learningthepartsofobjectsbynon-negativematrixfactorization[J].Nature, 1999, 401(6755): 788-791.

[2]HOYERPO.Non-negativematrixfactorizationwithsparsenessconstraints[J].JournalofMachineLearningResearch, 2004, 5(1): 1457-1469.

[3]SERHATS.BUCAK,BGUNSEL.Incrementalsubspacelearningvianon-negativematrixfactorization[J].PatternRecognition, 2009, 42(5): 788-797.

[4] 王萬良, 蔡競. 稀疏約束下非負矩陣分解的增量學(xué)習算法[J]. 計算機科學(xué), 2014, 41(8): 241-244.(WANGWL,CAIJ.Incrementallearningalgorithmofnon-negativematrixfactorizationwithsparsenessconstraints[J].ComputerScience, 2014, 41(8): 241-244.)

[5]LIUH,WUZ,LIX,etal.Constrainednon-negativematrixfactorizationforimagerepresentation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2012, 34(7): 1299-1311.

[6]CAID,HEX,HANJ,etal.Graphregularizednon-negativematrixfactorizationfordatarepresentation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2011, 33(8): 1548-1560.

[7] 姜偉, 李宏, 于震國,等. 稀疏約束圖正則非負矩陣分解[J]. 計算機科學(xué), 2013, 40(1): 218-256.(JIANGW,LIH,YUZG,etal.Graphregularizednon-negativematrixfactorizationwithsparsenessconstraints[J].ComputerScience, 2013, 40(1): 218-256.)

[8] 李樂, 章毓晉. 非負矩陣分解算法綜述[J]. 電子學(xué)報, 2008, 36(4): 737-743.(LIL,ZHANGYJ.Asurveyonalgorithmsofnon-negativematrixfactorization[J].ActaElectronicaSinica, 2008, 36(4): 737-743.)

[9] 胡麗瑩, 郭躬德, 馬昌鳳. 基于對稱非負矩陣分解的重疊社區(qū)發(fā)現(xiàn)方法[J]. 計算機應(yīng)用, 2015, 35 (10): 2742-2746.(HULY,GUOGD,MACF.Overlappingcommunitydiscoverymethodbasedonsymmetricnonnegativematrixfactorization[J].JournalofComputerApplications, 2015, 35 (10): 2742-2746.)

[10] 姜小燕. 基于基于非負矩陣分解的圖像分類算法研究[D]. 錦州: 遼寧工業(yè)大學(xué), 2016.(JIANGXY.Researchonimageclassificationalgorithmbasedonnon-negativematrixfactorization[D].Jinzhou:LiaoningUniversityofTechnology, 2016.)

[11] 汪金濤, 曹玉東, 王梓寧,等. 圖像型垃圾郵件監(jiān)控系統(tǒng)研究與設(shè)計[J]. 遼寧工業(yè)大學(xué)學(xué)報 (自然科學(xué)版), 2016, 36(2): 78-81.(WANGJT,CAOYD,WANGZN,etal.Researchanddesignofmonitoringsystemonimagespam[J].JournalofLiaoningUniversityofTechnology(NaturalScienceEdition), 2016, 36(2): 78-81.)

[12] 胡學(xué)考, 孫福明, 李豪杰. 基于稀疏約束的半監(jiān)督非負矩陣分解算法[J]. 計算機科學(xué), 2015, 42(7): 280-304.(HUXK,SUNFM.LIHJ.Constrainednonnegativematrixfactorizationwithsparsenessforimagerepresentation[J].ComputerScience, 2015, 42(7): 280-304.)

[13] 杜世強, 石玉清, 王維蘭,等. 基于圖正則化的半監(jiān)督非負矩陣分解[J]. 計算機工程與應(yīng)用, 2012, 48(36): 194-200.(DUSQ,SHIYQ,WANGWL,etal.Graph-regularized-basedsemi-supervisednon-negativematrixfactorization[J].ComputerEngineeringandApplications, 2012, 48(36): 194-200.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61572244),theProgramforLiaoningExcelentTalentsinUniversities(LR2015030).

WANG Jintao, born in 1992, M. S. candidate. His research interests include pattern recognition.

CAO Yudong, born in 1971, Ph. D., associate professor. His research interests include image processing, pattern recognition.

SUN Fuming, born in 1972, Ph. D., professor. His research interests include machine learning, pattern recognition.

Incrementallearningalgorithmbasedongraphregularizednon-negativematrixfactorizationwithsparsenessconstraints

WANGJintao,CAOYudong*,SUNFuming

(SchoolofElectronicsandInformationEngineering,LiaoningUniversityofTechnology,JinzhouLiaoning121001,China)

Focusing on the issues that the sparseness of the data obtained after Non-negative Matrix Factorization (NMF) is reduced and the computing scale increases rapidly with the increasing of training samples, an incremental learning algorithm based on graph regularized non-negative matrix factorization with sparseness constraints was proposed. It not only considered the geometric structure in the data representation, but also introduced sparseness constraints to coefficient matrix and combined them with incremental learning. Using the results of previous factorization involved in iterative computation with sparseness constraints and graph regularization, the cost of the computation was reduced and the sparseness of data after factorization was highly improved. Experiments on both ORL and PIE face recognition databases demonstrate the effectiveness of the proposed method.

Non-negative Matrix Factorization (NMF); sparse constraint; graph regularization; geometry; incremental learning

2016- 08- 09;

2016- 10- 14。

國家自然科學(xué)基金資助項目(61572244); 遼寧省高等學(xué)校優(yōu)秀人才支持計劃項目(LR2015030)。

汪金濤(1992—)，男，安徽合肥人，碩士研究生，主要研究方向：模式識別； 曹玉東(1971—)，男，遼寧鐵嶺人，副教授，博士，主要研究方向：圖像處理、模式識別； 孫福明(1972—)，男，遼寧大連人，教授，博士，CCF會員，主要研究方向：機器學(xué)習、模式識別。

1001- 9081(2017)04- 1071- 04

10.11772/j.issn.1001- 9081.2017.04.1071

TP

A