L1范數(shù)約束正交子空間非負(fù)矩陣分解①

韓 東,蓋 杉

(南昌航空大學(xué) 信息工程學(xué)院,南昌 330063)

1 引言

非負(fù)矩陣分解(Non-negative Matrix Factorization,NMF)[1]算法因其收斂速度快以及分解后的稀疏分量能夠清晰直觀地描述原始數(shù)據(jù)等特點(diǎn),在計(jì)算機(jī)視覺,文本聚類,模式識(shí)別等領(lǐng)域受到了廣泛關(guān)注.NMF本質(zhì)上是一種基于部分的矩陣分解方法,能夠以非負(fù)形式表示原始數(shù)據(jù)的局部特征.

NMF將原始非負(fù)矩陣X分解為兩個(gè)非負(fù)矩陣WH的乘積.分解后的矩陣僅包含非負(fù)元素,并且基向量W具有一定的數(shù)據(jù)局部表示能力,這使得NMF在諸多領(lǐng)域得到廣泛運(yùn)用.在文獻(xiàn)[2]中,Park等通過人眼過濾和最小化基于NMF的重構(gòu)圖像錯(cuò)誤率來進(jìn)行人眼檢測(cè).考慮到數(shù)據(jù)集合的內(nèi)部幾何結(jié)構(gòu),文獻(xiàn)[3]通過最近鄰圖來刻畫數(shù)據(jù)集中相鄰數(shù)據(jù)點(diǎn)的關(guān)系,提出了圖正則化非負(fù)矩陣分解.為了充分利用判別信息,同時(shí)考慮到數(shù)據(jù)中的幾何結(jié)構(gòu),文獻(xiàn)[4]提出了K近鄰非負(fù)矩陣分解(NMF-K-NN).在此基礎(chǔ)上,Jun Ye等使用模糊集來處理模式識(shí)別中的不確定因素,提出了模糊K近鄰非負(fù)矩陣分解(NMF-FK-NN)方法[5].Zhang等[6]通過最小化約束梯度距離,提出保持拓?fù)湫苑秦?fù)矩陣分解(TPNMF),該方法能夠保持臉部空間的局部?jī)?nèi)在拓?fù)浣Y(jié)構(gòu).在研究聚類問題的過程中,Yang等指出[7],正交性的約束能在很大程度上優(yōu)化聚類效果,其本質(zhì)是施加正交性約束后的NMF結(jié)果更加稀疏,從而使原始數(shù)據(jù)的基之間區(qū)別性增強(qiáng),進(jìn)而提升聚類效果.Li等[8]提出基于正交子空間的非負(fù)矩陣分解(Non-negative Matrix Factorization on Orthogonal Subspace,NMFOS),將對(duì)W(或 H )的正交性約束作為NMF目標(biāo)函數(shù)中的一部分直接進(jìn)行優(yōu)化,減少因施加正交性約束而帶來的巨大計(jì)算量,同時(shí)還能在一定程度上提升基矩陣 W(系數(shù)矩陣 H )的稀疏性.

基于正交子空間的非負(fù)矩陣分解雖然能在一定程度上提升分解矩陣的稀疏性,但是它導(dǎo)致的稀疏程度是難以控制的.本文為了在分解過程中進(jìn)一步提升分解矩陣的稀疏性,在分解過程中引入了L1范數(shù)約束,將L1范數(shù)約束轉(zhuǎn)換成目標(biāo)函數(shù)的正則部分進(jìn)行求解,提出了L1范數(shù)約束正交子空間非負(fù)矩陣分解(Nonnegative Matrix Factorization on Orthogonal Subspace with L1 norm constrains,NMFOS-L1).本文方法不僅能提升聚類效果,同時(shí)還提升了分解結(jié)果的稀疏表達(dá)能力,具有實(shí)用價(jià)值.

2 非負(fù)矩陣分解

給定非負(fù)矩陣X=[x1,x2,···,xn]∈Rm+×n,NMF將原始矩陣分解為兩個(gè)非負(fù)低秩矩陣 W 和 H,即:

其中,r＜＜min{m,n}.NMF常采用歐氏距離衡量 W H對(duì)X的逼近程度,目標(biāo)函數(shù)如下:

式中,‖·‖F(xiàn)為Frobenius范數(shù),矩陣 W 的每一列稱作基向量,矩陣 H 每一列為系數(shù)向量,將基向量進(jìn)行線性組合來表示原始數(shù)據(jù)矩陣.Lee和Seung[9]給出如下乘性迭代規(guī)則:

式中,?為矩陣元素的乘積運(yùn)算符號(hào),交替進(jìn)行式(3)和式(4),可以求得式(2)的系數(shù)矩陣和基矩陣.

3 基于正交子空間的非負(fù)矩陣分解

NMFOS將分解所得矩陣的正交性約束通過拉格朗日乘子引入到矩陣分解的目標(biāo)函數(shù)中進(jìn)行優(yōu)化,從而使分解結(jié)果的正交性不必通過正交性約束完成,減少計(jì)算量.NMFOS的目標(biāo)函數(shù)如下:對(duì)矩陣W加入正交性約束,目標(biāo)函數(shù)為:

對(duì)矩陣 H 加入正交性約束,目標(biāo)函數(shù)為:

其中,λ ≥0為正則參數(shù),I是全1矩陣.對(duì)于式(5)和式(6),Li等[8]給出了如下的乘性迭代規(guī)則:

4 L1范數(shù)約束正交子空間非負(fù)矩陣分解

NMF算法的分解結(jié)果在一定程度上呈現(xiàn)稀疏性,但是稀疏程度難以控制.Hoyer于2004年提出稀疏性非負(fù)矩陣分解[10],在目標(biāo)函數(shù)上添加L1正則化的稀疏約束.如果對(duì)NMFOS加上正則化的稀疏約束,那么就可以得到更加稀疏的分解矩陣,從而提高分解質(zhì)量.

通過引入稀疏約束條件到NMFOS的目標(biāo)函數(shù),將稀疏約束正交子空間非負(fù)矩陣分解歸結(jié)為下列優(yōu)化問題:對(duì)矩陣 W 而言,目標(biāo)函數(shù)為:

對(duì)矩陣 H 而言,目標(biāo)函數(shù)為:

式中,λ,α,β均為大于0的常數(shù).利用最速下降法和乘子迭代法,推導(dǎo)出上式的乘性迭代規(guī)則;首先新的目標(biāo)函數(shù)可表示為:

5 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證NMFOS-L1算法有效性,本文在手寫體數(shù)字光學(xué)識(shí)別數(shù)據(jù)集(Optical Recognition of Handwriting Digits)[11]、ORL 人臉數(shù)據(jù)庫[12]和Yale人臉數(shù)據(jù)庫[13]進(jìn)行了聚類的對(duì)比實(shí)驗(yàn).同時(shí),為了驗(yàn)證本文算法所得到的基矩陣的稀疏性,在ORL和Yale人臉數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn),比較了幾種不同算法的稀疏表達(dá)能力.

手寫體數(shù)字光學(xué)識(shí)別數(shù)據(jù)集:該數(shù)據(jù)集從UCI數(shù)據(jù)庫中選取0,2,4,6幾個(gè)數(shù)字,構(gòu)成2237個(gè)樣本,每個(gè)樣本有62特征,分為4個(gè)類.ORL人臉數(shù)據(jù)庫[12]是由40個(gè)人,每人10幅圖像構(gòu)成.每幅圖像為256個(gè)灰度級(jí),分辨率為1 1 2×92.該庫的人臉圖像表情變化,面部細(xì)節(jié),以及拍攝角度變化較大.圖1為ORL人臉庫同一個(gè)人的10張圖像.

圖1 ORL人臉數(shù)據(jù)庫

Yale人臉庫[13]包含15個(gè)人每人11幅共165幅人臉圖像,這些照片在不同的光照條件和角度下拍攝,人臉表情也有較大變化.每幅圖像均為1 0 0×100像素.圖2為Yale同一個(gè)人的10張圖像.

圖2 Yale人臉數(shù)據(jù)庫

5.1 聚類實(shí)驗(yàn)

在聚類問題中,常見的評(píng)測(cè)指標(biāo)是純度和F值.本文在已知類標(biāo)簽情況下,將不同算法的聚類結(jié)果進(jìn)行對(duì)比,利用純度來評(píng)價(jià)不同算法產(chǎn)生的分類效果.純度:所有簇的純凈度的均值.范圍為[0,1],數(shù)值越大,純凈度越高,效果越好.定義式為:

式中,q為總的類數(shù),nlk是簇k中標(biāo)記為類l的個(gè)數(shù).聚類熵:度量各簇中所有類的分布情況.取值范圍為[0,1],取值越小,聚類效果越好.定義如下:

在本節(jié)實(shí)驗(yàn)中設(shè)定P=q,在每個(gè)數(shù)據(jù)庫獨(dú)立地重復(fù)實(shí)驗(yàn)200次,并設(shè)定迭代次數(shù)的最大值為2000.在實(shí)驗(yàn)時(shí),選取參數(shù) λ=5,β=1.實(shí)驗(yàn)結(jié)果如表1所示.

表1 三種數(shù)據(jù)庫上的聚類純度(均值±方差)

表2 三種數(shù)據(jù)庫上的聚類熵(均值±方差)

5.2 稀疏性對(duì)比實(shí)驗(yàn)

本節(jié)我們?cè)贠RL和Yale人臉數(shù)據(jù)庫上進(jìn)行人臉特征提取,對(duì)比了NMF、ONMF、NMFOS、和本文NMFOS-L1幾種算法的局部表達(dá)能力.圖3給出了秩為25時(shí),不同算法得到的基矩陣圖像.

由圖3可以看出,在這兩個(gè)數(shù)據(jù)庫上對(duì)比這4種算法的基圖像稀疏度,NMF稀疏度最低,NMFOSL1的基圖像最為稀疏,換言之,該算法具有最優(yōu)的局部表達(dá)能力.

圖3 ORL和Yale數(shù)據(jù)庫不同算法人臉特征提取結(jié)果對(duì)比

Hoyer在文獻(xiàn)[9]中給出了度量向量稀疏度的函數(shù):

實(shí)驗(yàn)最后,我們對(duì)矩陣分解結(jié)果的稀疏性進(jìn)行對(duì)比.從表3和表4中我們可以看到,本文算法所得的基矩陣和稀疏矩陣更加稀疏,本文算法的稀疏表達(dá)能力優(yōu)于對(duì)比的幾種算法.

表3 ORL數(shù)據(jù)庫上不同算法的稀疏性

表4 Yale數(shù)據(jù)庫上不同算法的稀疏性

6 結(jié)束語

針對(duì)正交子空間非負(fù)矩陣分解相對(duì)稀疏或局部化描述原數(shù)據(jù)時(shí)導(dǎo)致的稀疏能力和程度比較弱的問題,本文將稀疏約束引入正交子空間非負(fù)矩陣分解的目標(biāo)函數(shù)中,提出稀疏約束正交子空間非負(fù)矩陣分解.同時(shí)給出了迭代公式.實(shí)驗(yàn)證明該算法具有更好的聚類效果以及稀疏表達(dá)能力,在人臉特征提取領(lǐng)域具有應(yīng)用潛力.進(jìn)一步提升正交子空間非負(fù)矩陣分解算法效率,以及將本文方法推廣應(yīng)用到計(jì)算機(jī)視覺中都是我們進(jìn)一步要研究的內(nèi)容.