應(yīng)用稀疏約束的非負(fù)正則矩陣學(xué)習(xí)算法①

魏瑞芳,周棟森

(浙江郵電職業(yè)技術(shù)學(xué)院 教務(wù)處(科研處),紹興 312016)

子空間降維是機(jī)器學(xué)習(xí)和模式識別的一種常用方法,也是數(shù)據(jù)挖掘等領(lǐng)域的研究熱點.Lee和Seung[1]在《Nature》上首次提出非負(fù)矩陣分解(Non-negative Matrix Factorization,NMF)概念,通過添加“矩陣中所有元素均非負(fù)”限制條件,保證分解結(jié)果的可解釋性.隨后,大量改進(jìn)算法被提出并應(yīng)用.文獻(xiàn)[2]在分解原始矩陣時,對基矩陣和系數(shù)矩陣施加稀疏約束,將稀疏編碼思想引入到非負(fù)矩陣分解中,提出的稀疏約束非負(fù)矩陣分解算法(Non-negative Matrix Factorization Sparseness Constraints,NMFSC)具有存儲空間少的優(yōu)點;文獻(xiàn)[3]將增量學(xué)習(xí)與非負(fù)矩陣分解相結(jié)合,提出了增量式非負(fù)矩陣分解算法(Incremental Non-negative Matrix Factorization,INMF),利用上一步的分解結(jié)果參與迭代運算,再新加入訓(xùn)練樣本時不會重新運算從而節(jié)省了運算時間.文獻(xiàn)[4]將稀疏約束和增量學(xué)習(xí)思想引入非負(fù)矩陣分解中,提出的稀疏約束下非負(fù)矩陣分解的增量學(xué)習(xí)算法(Incremental Non-negative Matrix Factorization Sparseness Constraints,INMFSC)在運算時間和稀疏度等指標(biāo)上都有大幅優(yōu)化.上述的標(biāo)準(zhǔn)NMF及其改進(jìn)算法都屬于無監(jiān)督分解方法,沒有考慮樣本的標(biāo)簽信息.文獻(xiàn)[6]將流形學(xué)習(xí)與非負(fù)矩陣分解相結(jié)合,提出的圖正則化非負(fù)矩陣分解(Graph Regularized Nonnegative Matrix Factorization,GNMF)能夠在NMF的低維表示中考慮原始樣本的近鄰結(jié)構(gòu),使得原始樣本的近鄰結(jié)構(gòu)在非負(fù)矩陣分解的低維中得到很好的保留.文獻(xiàn)[7]提出了稀疏約束的圖正則非負(fù)矩陣分解,并給出了迭代公式以及收斂性證明過程.現(xiàn)有研究成果普遍存在非負(fù)矩陣分解數(shù)據(jù)稀疏性降低及訓(xùn)練樣本增多導(dǎo)致運算規(guī)模不斷增大等現(xiàn)象.

針對現(xiàn)有非負(fù)矩陣分解后的數(shù)據(jù)稀疏性較低,訓(xùn)練樣本偏多導(dǎo)致運算規(guī)模持續(xù)增大的普遍現(xiàn)象問題,本文將文獻(xiàn)[7]方法與學(xué)習(xí)算法融合提出基于稀疏約束的非負(fù)正則矩陣學(xué)習(xí)算法(Non-negative Factorization Matrix with Sparseness Constraints,NFM-SC),NFMSC方法不僅能夠有效保持樣本局部結(jié)構(gòu),使得算法具有較高分類準(zhǔn)確率,還能結(jié)合學(xué)習(xí)算法充分利用上一步分解結(jié)果,避免重復(fù)計算從而達(dá)到降低運算時間目標(biāo).

1 非負(fù)矩陣分解

NMF算法具體描述如下[8-10]:對給定的非負(fù)矩陣V,尋找合適的非負(fù)基矩陣和非負(fù)系數(shù)矩陣,使得V≈WH.r代表基向量的個數(shù),當(dāng)r的取值滿足時,原始矩陣V得到了有效的壓縮.可歸結(jié)為最小化下面的歐式空間的描述形式的目標(biāo)函數(shù):

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

當(dāng)給定迭代終止條件后,對隨機(jī)生成的初始非負(fù)矩陣W0和H0,按式(2)和(3)交替迭代更新直到滿足終止條件,可得到最終的W和H[11-13].

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

文獻(xiàn)[7]提出的稀疏約束圖正則非負(fù)矩陣分解方法不僅考慮數(shù)據(jù)幾何結(jié)構(gòu),而且對稀疏矩陣進(jìn)行約束,能夠提取既稀疏又具有很強(qiáng)判別能力的基圖像.本文將文獻(xiàn)[7]與學(xué)習(xí)算法融合提出基于稀疏約束的非負(fù)正則矩陣學(xué)習(xí)算法(Non-negative Factorization Matrix with Sparseness Constraints,NFM-SC),結(jié)合學(xué)習(xí)方法充分利用上一步的分解結(jié)果,避免大量重復(fù)計算過程.

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

設(shè)Wk和Hk分別表示樣本集合Vk的非負(fù)矩陣分解后得到的基矩陣和系數(shù)矩陣,Lk是樣本集合Vk的拉普拉斯矩陣,其中k表示當(dāng)前樣本集合中存在k個樣本.Fk代表Vk經(jīng)過非負(fù)矩陣分解后的目標(biāo)函數(shù),則Fk的表達(dá)式如式(4)所示.

當(dāng)?shù)趉+1個樣本加入后,目標(biāo)函數(shù)則如式(5).

其中,β是非負(fù)參數(shù),Wk+1和Hk+1分別表示樣本集合Vk+1非負(fù)矩陣分解后得到的值,Lk+1是樣本集合Vk+1的拉普拉斯矩陣.

2.2 迭代規(guī)則

當(dāng)新樣本vk+1到來時,系數(shù)矩陣Hk+1的前k列向量近似等于Hk的列向量,即Hk+1=[Hk,hk+1].目標(biāo)函數(shù)Fk+1可以重寫為如式(6)形式.

在得到新的目標(biāo)函數(shù)Fk+1后,利用梯度下降法推導(dǎo)出相應(yīng)的迭代公式.先求出系數(shù)矩陣增量部分hk+1的迭代公式,如式(7).

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

其中,(Lk+1)k+1,:、(Dk+1)k+1,:和(Sk+1)k+1,:分別為Lk+1、Dk+1和Sk+1所對應(yīng)的第k+1行的行向量.

將式(8)和(9)的值代入式(7),得hk+1的迭代公式,如式(10).

同理,得:

ηia是迭代的步長,

將公式(12)和(13)的值代入(10),得Wk+1的迭代公式:

由此,歸納NFM-SC算法步驟如下:

(1)依據(jù)2.1小節(jié)目標(biāo)函數(shù)內(nèi)容,隨機(jī)初始化正則矩陣W和H;

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

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

其中,Hk+1=[Hk,hk+1],hk+1初始化為hk.以上i=1,2,…,n,j=1,2,…,n,a=1,2,…,r,α和β均為非負(fù)常數(shù).

3 實驗分析

實驗環(huán)境:Windows 7,CPU:3.30 GHz,內(nèi)存:8 GB.程序環(huán)境:Matlab R2014b.

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

本實驗采用ORL人臉數(shù)據(jù)庫和COIL20圖像數(shù)據(jù)庫測試NFM-SC算法性能,并與NMF、INMF、GNMF、INMFSC四種算法進(jìn)行比較.ORL人臉數(shù)據(jù)庫中包含40個不同年齡、不同性別和不同種族的面部圖像,每人10種不同姿態(tài),共計400幅灰度圖像.COIL20數(shù)據(jù)庫共有20個類別的物體圖像,每個圖像包括具有不同旋轉(zhuǎn)角度的72個樣本.

在運行本文實驗算法時,在每個類取6個共240個作為訓(xùn)練樣本,正則項參數(shù)λ設(shè)為100,稀疏約束β設(shè)為0.3,迭代次數(shù)為200.在每個類取43個共860個作訓(xùn)練樣本,正則項參數(shù)λ設(shè)為100,稀疏約束β設(shè)為0.4,迭代次數(shù)為200次.

3.2 運行實踐對比

在ORL人臉數(shù)據(jù)庫上,初始訓(xùn)練樣本為240的情況下NMF、INMF、GNMF、INMFSC及NFM-SC五種算法隨新增樣本數(shù)量的增多消耗的時間如表1所示,在COIL20數(shù)據(jù)集上初始訓(xùn)練樣本為860的情況下算法時間消耗如表2所示.

表1 ORL庫新增訓(xùn)練樣本時不同算法對應(yīng)時間消耗(單位:s)

表2 COIL20庫新增訓(xùn)練樣本時不同算法對應(yīng)時間消耗(單位:s)

由表1和表2的結(jié)果可知,與幾種對比算法比較,提出的算法在運算的時間上有明顯優(yōu)勢,而當(dāng)新增訓(xùn)練樣本超過一定數(shù)量時,NFM-SC算法仍能保持相對高的運算效率.

3.3 稀疏度的度量

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

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

以式(14)作為稀疏度度量標(biāo)準(zhǔn),則經(jīng)過NMF、INMF、GNMFSC和本文提出的NFM-SC算法分解后得到的基矩陣W和系數(shù)矩陣H的稀疏度如表3所示.

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

圖1、圖2分別表示在數(shù)據(jù)庫ORL和COIL20上的基圖像.其中,ORL數(shù)據(jù)集的基矩陣特征維數(shù)取36,COIL20數(shù)據(jù)集的基矩陣特征維數(shù)取20.

圖1 COIL20數(shù)據(jù)集的基圖像(r = 20)

由圖1和圖2可以看出,NMF算法的基向量最接近原圖像,容易得到原始樣本的最優(yōu)表示,但是它的稀疏度較差,存儲效率低.同其他的NMF改進(jìn)算法相比,NFM-SC算法能得到更稀疏的基圖像,由此表明算法得到了圖像的最佳局部表示結(jié)果.

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

4 結(jié)論

提出了稀疏約束的非負(fù)正則矩陣學(xué)習(xí)算法,并給出了相應(yīng)的迭代規(guī)則和算法步驟.通過在常用數(shù)據(jù)集上幾種算法的對比實驗,綜合考慮運行時間和稀疏度兩種評價指標(biāo)來衡量所提算法的有效性,實驗表明,提出的算法不僅縮減運行時間,而且使分解后的數(shù)據(jù)更為稀疏,得到局部表達(dá)能力和判別能力更強(qiáng)的基圖像.

1Lee DD,Seung HS.Learning the parts of objects by nonnegative matrix factorization.Nature,1999,401(6755):788-791.[doi:10.1038/44565]

2Hoyer PO.Non-negative matrix factorization with sparseness constraints.The Journal of Machine Learning Research,2004,5:1457-1469.

3Bucak SS,Gunsel B.Incremental subspace learning via nonnegative matrix factorization.Pattern Recognition,2009,42(5):788-797.[doi:10.1016/j.patcog.2008.09.002]

4王萬良,蔡競.稀疏約束下非負(fù)矩陣分解的增量學(xué)習(xí)算法.計算機(jī)科學(xué),2014,41(8):241-244.[doi:10.11896/j.issn.1002-137X.2014.08.051]

5Liu CL.Classifier combination based on confidence transformation.Pattern Recognition,2005,38(1):11-28.[doi:10.1016/j.patcog.2004.05.013]

6Cai D,He XF,Han JW,et al.Graph regularized nonnegative matrix factorization for data representation.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1548-1560.[doi:10.1109/TPAMI.2010.231]

7姜偉,李宏,于震國,等.稀疏約束圖正則非負(fù)矩陣分解.計算機(jī)科學(xué),2013,40(1):218-220,256.

8李樂,章毓晉.非負(fù)矩陣分解算法綜述.電子學(xué)報,2008,36(4):737-743.

9姜小燕.基于非負(fù)矩陣分解的圖像分類算法研究[碩士學(xué)位論文].錦州:遼寧工業(yè)大學(xué),2016.

10汪金濤,曹玉東,王梓寧,等.圖像型垃圾郵件監(jiān)控系統(tǒng)研究與設(shè)計.遼寧工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2016,36(2):78-80,86.

11胡學(xué)考,孫福明,李豪杰.基于稀疏約束的半監(jiān)督非負(fù)矩陣分解算法.計算機(jī)科學(xué),2015,42(7):280-284,304.[doi:10.11896/j.issn.1002-137X.2015.07.060]

12杜世強(qiáng),石玉清,王維蘭,等.基于圖正則化的半監(jiān)督非負(fù)矩陣分解.計算機(jī)工程與應(yīng)用,2012,48(36):194-200.[doi:10.3778/j.issn.1002-8331.1205-0357]

13卜寧,牛樹梓,馬文靜,龍國平.面向相似App推薦的列表式多核相似性學(xué)習(xí)算法.計算機(jī)系統(tǒng)應(yīng)用,2017,26(1):116-121.[doi:10.15888/j.cnki.csa.005502]