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

周長宇 姚明海 李勁松

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

0 引 言

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

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

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

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

1 非負(fù)矩陣分解

1.1 非負(fù)矩陣分解概述

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

X≈AS

(1)

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

xi≈Asi

(2)

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

一般采用歐氏距離衡量AS到X的逼近程度，目標(biāo)函數(shù)如下：

(3)

(4)

(5)

1.2 圖正則化非負(fù)矩陣分解

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

設(shè)原始數(shù)據(jù)點構(gòu)成的圖為G，則目標(biāo)函數(shù)為：

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

(6)

s.t.A≥0,S≥0

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

迭代更新規(guī)則如下：

(7)

(8)

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

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

2.1 模型構(gòu)建

為了更好地保持原始數(shù)據(jù)的結(jié)構(gòu)信息，本文采用鄰接圖、權(quán)重圖和稀疏圖對原始數(shù)據(jù)的結(jié)構(gòu)進行約束。原始數(shù)據(jù)矩陣X∈Rn×m，構(gòu)成的圖為G。

(9)

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

(10)

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

(11)

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

2.2 目標(biāo)函數(shù)求解

L21-MGNMF方法目標(biāo)函數(shù)定義如下：

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

(12)

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

固定μ和S，更新A。移除不相關(guān)項，有關(guān)A的優(yōu)化問題可以轉(zhuǎn)化為：

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)求解，由拉格朗日定理：引入一個拉格朗日乘子Λ，其拉格朗日函數(shù)如下：

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

tr(ASDSTAT)+λtr(ΛA)

(15)

對式(15)求偏導(dǎo)，并令導(dǎo)數(shù)等零，由最優(yōu)條件ΛijAij=0，可以得:

(-2XDST+2ASDST)Aij=0

(16)

固定μ和A，更新S。移除不相關(guān)項，有關(guān)S的優(yōu)化問題可以轉(zhuǎn)化為：

(17)

s.t.S≥0

同理，由拉格朗日定理求偏導(dǎo)得：

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

(18)

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

(19)

(20)

2.3 算法描述

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

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

輸入：初始數(shù)據(jù)矩陣X，權(quán)重μ和平衡因子α。

輸出：ACC，sp(x)。

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

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

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

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

步驟5進行特征分類及對結(jié)果后處理，計算評價指標(biāo)。

3 實 驗

3.1 實驗數(shù)據(jù)

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

表1 數(shù)據(jù)集信息

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

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

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

3.2 評價指標(biāo)

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

(21)

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

(22)

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

3.3 實驗結(jié)果與分析

3.3.1參數(shù)實驗

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

圖1 迭代次數(shù)iter-準(zhǔn)確率曲線圖

圖2 平衡參數(shù)α-準(zhǔn)確率曲線圖

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

3.3.2多圖有效性實驗

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

圖3 不同算法準(zhǔn)確率

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

3.3.3對比實驗

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

(a) COIL20數(shù)據(jù)集

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

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

表2 不同算法在三種數(shù)據(jù)庫上的稀疏度

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

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

4 結(jié) 語

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