汪金濤，曹玉東，孫福明

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

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

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

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

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

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

0 引言

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

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

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

1 非負(fù)矩陣分解

(1)

s.t.W≥0,H≥0

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

(2)

(3)

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

2 IGNMFSC算法

2.1 目標(biāo)函數(shù)

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

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

(4)

s.t.W≥0,H≥0

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

(5)

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

(6)

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

2.2 迭代規(guī)則

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

(7)

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

(8)

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

接下來(lái)計(jì)算Fk+1對(duì)hk+1的偏導(dǎo)數(shù)：

(9)

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

ηa=

(10)

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

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

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

(11)

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

(12)

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

(13)

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

(14)

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

3.2 運(yùn)行時(shí)間對(duì)比

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

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

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

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

3.3 稀疏度的度量

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

(15)

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

)

[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] 王萬(wàn)良, 蔡競(jìng). 稀疏約束下非負(fù)矩陣分解的增量學(xué)習(xí)算法[J]. 計(jì)算機(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] 姜偉, 李宏, 于震國(guó),等. 稀疏約束圖正則非負(fù)矩陣分解[J]. 計(jì)算機(jī)科學(xué), 2013, 40(1): 218-256.(JIANGW,LIH,YUZG,etal.Graphregularizednon-negativematrixfactorizationwithsparsenessconstraints[J].ComputerScience, 2013, 40(1): 218-256.)

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

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

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

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

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

[13] 杜世強(qiáng), 石玉清, 王維蘭,等. 基于圖正則化的半監(jiān)督非負(fù)矩陣分解[J]. 計(jì)算機(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。

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

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

1001- 9081(2017)04- 1071- 04

10.11772/j.issn.1001- 9081.2017.04.1071

TP

A