L1范數約束正交子空間非負矩陣分解①

韓 東,蓋 杉

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

1 引言

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

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

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

2 非負矩陣分解

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

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

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

式中,?為矩陣元素的乘積運算符號,交替進行式(3)和式(4),可以求得式(2)的系數矩陣和基矩陣.

3 基于正交子空間的非負矩陣分解

NMFOS將分解所得矩陣的正交性約束通過拉格朗日乘子引入到矩陣分解的目標函數中進行優化,從而使分解結果的正交性不必通過正交性約束完成,減少計算量.NMFOS的目標函數如下:對矩陣W加入正交性約束,目標函數為:

對矩陣 H 加入正交性約束,目標函數為:

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

4 L1范數約束正交子空間非負矩陣分解

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

通過引入稀疏約束條件到NMFOS的目標函數,將稀疏約束正交子空間非負矩陣分解歸結為下列優化問題:對矩陣 W 而言,目標函數為:

對矩陣 H 而言,目標函數為:

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

5 實驗與結果分析

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

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

圖1 ORL人臉數據庫

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

圖2 Yale人臉數據庫

5.1 聚類實驗

在聚類問題中,常見的評測指標是純度和F值.本文在已知類標簽情況下,將不同算法的聚類結果進行對比,利用純度來評價不同算法產生的分類效果.純度:所有簇的純凈度的均值.范圍為[0,1],數值越大,純凈度越高,效果越好.定義式為:

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

在本節實驗中設定P=q,在每個數據庫獨立地重復實驗200次,并設定迭代次數的最大值為2000.在實驗時,選取參數 λ=5,β=1.實驗結果如表1所示.

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

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

5.2 稀疏性對比實驗

本節我們在ORL和Yale人臉數據庫上進行人臉特征提取,對比了NMF、ONMF、NMFOS、和本文NMFOS-L1幾種算法的局部表達能力.圖3給出了秩為25時,不同算法得到的基矩陣圖像.

由圖3可以看出,在這兩個數據庫上對比這4種算法的基圖像稀疏度,NMF稀疏度最低,NMFOSL1的基圖像最為稀疏,換言之,該算法具有最優的局部表達能力.

圖3 ORL和Yale數據庫不同算法人臉特征提取結果對比

Hoyer在文獻[9]中給出了度量向量稀疏度的函數:

實驗最后,我們對矩陣分解結果的稀疏性進行對比.從表3和表4中我們可以看到,本文算法所得的基矩陣和稀疏矩陣更加稀疏,本文算法的稀疏表達能力優于對比的幾種算法.

表3 ORL數據庫上不同算法的稀疏性

表4 Yale數據庫上不同算法的稀疏性

6 結束語

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