基于L21范式的多圖正則化非負矩陣分解方法

周長宇 姚明海 李勁松

(渤海大學信息科學與技術學院 遼寧 錦州 121001)

0 引 言

非負矩陣分解(NMF)算法作為一種數據約簡的有效方法，因其非負約束、稀疏的局部表達和良好的可解釋性被廣泛應用于數據挖掘、文本聚類、特征識別和信息檢索等相關領域[1-4]。

非負矩陣分解方法由Lee等[5]在《Nature》上首次提出。主要原理：對于原始數據矩陣X進行分解，尋找適當矩陣A與S，使之乘積近似等于原始矩陣X。由于對A與S的非負限制，原始矩陣X的列向量可近似地看成矩陣A列向量的加權和，S矩陣的元素近似地看成權重系數，則系數矩陣S可以實現原始矩陣的降維，故基矩陣A為原始數據矩陣的局部特征[6]。

諸多學者對其進行了改進并應用于特征提取與分類識別領域：為了保持原始數據的幾何結構信息，文獻[7]首次提出了通過構建近鄰圖來描繪數據矩陣中數據點的內部流形結構的圖正則化非負矩陣分解方法(GNMF)。文獻[8]則利用局部坐標約束，保持樣本局部結構，提出基于局部坐標的圖像正則化NMF圖像表示方法。為了更好地提升算法分解結果的稀疏度，傳遞有效信息，姜偉等[9]提出稀疏約束圖正則化非負矩陣分解方法(SGNMF)。為了增強算法性能，文獻[10]引入了低秩圖約束，提出一種低秩圖正則化非負矩陣分解方法(LGNMF)，提高了對數據局部和全局結構的描述效果。為了對數據進行分層次的特征表達，基于深度學習思想，Trigeorgis等[11]提出一種深度半非負矩陣分解方法(Deep Semi-NMF)。文獻[12]則將圖正則和深度學習思想相結合，提出了一種圖正則化的深度半非負矩陣分解方法(Deep Semi-GNMF)。

基于圖正則思想的方法用單圖對原始數據的內部結構進行約束，一定程度上能夠取得滿足需求的特征向量，但結果未知性大且滿足需求單一；基于深度學習的算法能有效提升精確度，但因訓練模型導致速度稍慢且復雜度高。大多算法在衡量損失函數上采用L2范式，存在算法對噪聲、離群點較敏感導致的分解結果稀疏度和魯棒性較差等問題。為此，本文提出了一種基于L21范式的多圖正則化非負矩陣分解方法(L21-MGNMF)。通過在多個數據庫上的實驗證明，該算法在圖像特征分類或識別效果上優于其他算法。

1 非負矩陣分解

1.1 非負矩陣分解概述

傳統非負矩陣分解(NMF)算法對數據矩陣X∈Rn×m分解得到非負矩陣A∈Rn×r和非負矩陣S∈Rr×m使得：

X≈AS

(1)

重寫式(1)，設xi為矩陣X的第i列，si為矩陣H的第i列，則:

xi≈Asi

(2)

將n維的線性表示xi依據基矩陣A進行分解，可得到一個r維的線性表示si，r為n維的特征降維后的維度，通常情況下，r?n。

一般采用歐氏距離衡量AS到X的逼近程度，目標函數如下：

(3)

(4)

(5)

1.2 圖正則化非負矩陣分解

圖正則化非負矩陣分解(GNMF)算法表示數據點間真實流形結構[13]。圖正則的基本思想是構造數據間鄰接圖，盡可能地刻畫和保持由圖模型反映的真實流形結構，也就是我們希望學習到的低維特征和高維樣本的流形結構相似度更高[14]。

設原始數據點構成的圖為G，則目標函數為：

OGNMF=min‖X-AS‖2+λtr(SLST)

(6)

s.t.A≥0,S≥0

式中：L=D-W，D為對角陣，L為拉普拉斯矩陣；W=[wij]為鄰接矩陣。

迭代更新規則如下：

(7)

(8)

2 基于L21范式的多圖正則化非負矩陣分解

基于L21范式的多圖正則化非負矩陣分解方法，通過融合多個圖從不同角度進行約束，保證了原始數據的更多信息，來最大還原原始數據的真實結構，在構建函數時，采用L21范式作為損失函數，其行稀疏特性能有效提升分解結果的稀疏度和魯棒性。

2.1 模型構建

為了更好地保持原始數據的結構信息，本文采用鄰接圖、權重圖和稀疏圖對原始數據的結構進行約束。原始數據矩陣X∈Rn×m，構成的圖為G。

(9)

鄰接圖可以有效表示原始空間中的近鄰關系，N(xj,σ)表示xi的σ鄰域，即存在鄰接關系的兩個點xi和xj。

(10)

Gs=s.t.‖x-Dα‖p≤ε

(11)

式中：D為矩陣字典；α為數據稀疏表示；ε為存在的誤差項。稀疏約束可以提升分解結果稀疏度，使分解得到的基圖像用盡可能少的特征表示原始圖像，更易獲取蘊含信息。稀疏圖可以表示原始數據的稀疏結構。

2.2 目標函數求解

L21-MGNMF方法目標函數定義如下：

OL21-MGNMF=min‖X-AS‖2,1+

(12)

目標函數中包含3個變量，對于3個變量而言，目標函數是非凸的，因此不能給出變量的顯式解。但對于單個變量而言，目標函數是凸的，因此可以采用迭代求解的方式。固定其中兩個變量，再更新另一個變量。方法求解過程：

固定μ和S，更新A。移除不相關項，有關A的優化問題可以轉化為：

min‖X-AS‖2,1

(13)

s.t.A≥0

可以簡化為：

min‖X-AS‖2,1=tr((X-AS)D(X-AS)T)=tr(XDXT-2ASDXT+ASDSTAT)s.t.A≥0

(14)

式中：D為對角矩陣，其對角元素為Dii=1/‖xi-Asi‖。

對式(14)求解，由拉格朗日定理：引入一個拉格朗日乘子Λ，其拉格朗日函數如下：

l(A,Λ)=tr(XDXT)-2tr(ASDXT)+

tr(ASDSTAT)+λtr(ΛA)

(15)

對式(15)求偏導，并令導數等零，由最優條件ΛijAij=0，可以得:

(-2XDST+2ASDST)Aij=0

(16)

固定μ和A，更新S。移除不相關項，有關S的優化問題可以轉化為：

(17)

s.t.S≥0

同理，由拉格朗日定理求偏導得：

(-2ATXD+2ATASD+αSL)Sij=0

(18)

根據式(16)和式(18)，可以分別得到A和S的更新準則：

(19)

(20)

2.3 算法描述

基于對算法模型的求解，算法1給出L21-MGNMF分類算法的描述。

算法1基于L21范式的多圖正則化非負矩陣分解算法

輸入：初始數據矩陣X，權重μ和平衡因子α。

輸出：ACC，sp(x)。

步驟1對數據矩陣X進行預處理，采用歸一化和高斯金字塔方法。

步驟2初始化非負矩陣A與S，設置最大迭代次數iter、迭代誤差閾值e。

步驟3所有元素進入迭代更新規則式(19)與式(20)，解得基矩陣A與系數矩陣S。

步驟4小于閾值或超出給定迭代次數，則算法終止；否則返回步驟3。迭代結束，得到最優解的非負矩陣A與S。

步驟5進行特征分類及對結果后處理，計算評價指標。

3 實 驗

3.1 實驗數據

實驗采用三個公共數據，數據集信息如表1所示。

表1 數據集信息

COIL20數據集由哥倫比亞大學創建，每個物品(招財貓、杯子、玩具小鴨等)在水平方向旋轉360°，每隔5°拍攝一幅圖像，共計72幅圖像，全庫總共1 440幅圖像。

AR數據集包含50位男性和50位女性，每人26幅共2 600幅圖。所有圖像包含是否睜眼、是否微笑、有無眼鏡等不同面部狀態。

CASIA(1.0)數據集包含756幅圖片來自108只不同的眼睛，每只眼睛有7幅8位灰度圖像，圖像大小為320×480。

3.2 評價指標

采用準確率(Accuracy)和稀疏度(Sparsity)作為評價指標對算法進行評價。計算公式如下：

(21)

式中：N為樣本總數；δ()表示求和函數；map()表示映射函數；將分類結果標簽ri映射到數據的真實標簽si，ACC的值越大說明分類準確率越高。

(22)

式中：n是向量x的維度；0≤sp(x)≤1當只有一個非零元素時，sp(x)=1，取值越小向量x越稠密，反之越稀疏。

3.3 實驗結果與分析

3.3.1參數實驗

算法模型中主要參數有降維后的特征維數r、影響算法的收斂速度的迭代次數iter、影響分解誤差的平衡因子α。在COIL20數據集上進行實驗，相關參數的準確率曲線圖如圖1和圖2所示。

圖1 迭代次數iter-準確率曲線圖

圖2 平衡參數α-準確率曲線圖

由圖1可以看出，算法性能隨著迭代次數的增加先快速提升再逐漸趨于平穩，考慮到運算效率，本文實驗迭代次數取值為2 000。由圖2可以看出，算法的性能隨著平衡因子α的減小而提升，當α=0.01時，算法的性能未能進一步較大提升，所以本文平衡因子取0.01。

3.3.2多圖有效性實驗

本文將提出的L21-MGNMF算法與L21非負矩陣分解算法(L21-NMF)、L21權重圖非負矩陣分解算法(L21-GW-NMF)、L21稀疏圖非負矩陣分解算法(L21-GS-NMF)在COIL20數據集上進行實驗，并對實驗結果進行比較。

圖3 不同算法準確率

可以看出，基于L21范式的無約束算法性能最差，本文提出的多圖約束算法與基于L21范式的單圖約束算法相比較，準確率整體明顯更高，說明了融合多圖對數據的結構約束效果更好，考慮了鄰接結構、權重關系和稀疏性后的效果比僅考慮單個因素的效果更好。

3.3.3對比實驗

通過對比SGNMF、LGNMF、Deep Semi-NMF、Deep Semi-GNMF算法在3個公共數據集上的實驗情況來證明文本算法的可行性和有效性。為保證實驗結果真實有效，本文將10次重復隨機選擇的樣本進行訓練和測試實驗，取平均值作為最終實驗結果，如圖4所示。

(a) COIL20數據集

可以看出，本文算法在3個數據集上的準確率最高，與SGNMF、LGNMF、Deep Semi-NMF算法相比皆有5到10百分點的大幅提升；與Deep Semi-GNMF算法相比有小幅提升，但能更快達到較高分類準確率且趨于穩定。這說明本文提出的L21-MGNMF算法可獲得更好的分類識別效果，性能明顯優于其他算法。

最后對這5種算法進行稀疏度實驗。通過對矩陣分解結果的稀疏度進行對比，選用原始數據X分解后得到的基圖像，基圖像的特征維數取30，用式(22)來計算稀疏度，實驗結果如表2所示。

表2 不同算法在三種數據庫上的稀疏度

可以看出，LGNMF和Deep Semi-NMF算法稀疏度最差，SGNMF 和Deep Semi-GNMF算法的稀疏度有所提升，但本文算法結果超過其他幾種算法，說明L21范式的行稀疏特性對分解結果稀疏度有效提升，即本文方法得到分類結果的基圖像最為稀疏，具有較優的局部表達能力。

綜上所述，本文對提出的算法進行了參數實驗，多圖有效性實驗，并與SGNMF、LGNMF、Deep Semi-NMF、Deep Semi-GNMF算法在3個公共數據集上進行對比實驗。結果證明了融合多圖對數據的結構約束效果更好，分類識別中比其他算法的分類準確率更高，在稀疏性對比實驗中本文算法也具有更好的稀疏度。換言之，本文提出的基于L21范式的多圖正則化非負矩陣分解算法更具優勢。

4 結 語

本文提出一種基于L21范式的多圖正則化非負矩陣分解算法，通過融合多圖對數據結構進行約束解決了單圖正則化算法對原始數據結構約束不完善的情況；采用L21范式作為損失函數解決了大多算法對噪聲、離群點較敏感導致的分解結果稀疏度差等問題。大量的實驗結果表明，本文提出的算法取得良好的分類準確性，分解結果的稀疏度也有顯著提升。本文方法更有利于圖像特征的分類或識別，但如何構建多圖融合模型仍然是一個開放問題。