李小珍

(安徽國(guó)防科技職業(yè)學(xué)院，安徽 六安 237001)

0 引言

非負(fù)矩陣分解(NMF)是由學(xué)者Lee和Seung首次提出的矩陣分析方法，隨著信息化技術(shù)的快速發(fā)展，矩陣分解在大數(shù)據(jù)處理和模式識(shí)別中發(fā)揮著越來(lái)越重要的作用[1]。傳統(tǒng)的矩陣分解工具，結(jié)果中普遍含有負(fù)數(shù)，這為實(shí)際應(yīng)用帶來(lái)了一定的難度。與此不同的是，非負(fù)矩陣分解的所有結(jié)果均為非負(fù)值，對(duì)象的物理表達(dá)更加自然，具有更加廣闊的應(yīng)用前景。但是傳統(tǒng)非負(fù)矩陣分解方法無(wú)法同時(shí)考慮數(shù)據(jù)樣本特征信息和數(shù)據(jù)固有幾何結(jié)構(gòu)，在一定程度上影響了數(shù)據(jù)的聚類結(jié)果。本文將圖正則化方法和半監(jiān)督學(xué)習(xí)思想深度結(jié)合起來(lái)，提出新的非負(fù)矩陣分解算法。該方法充分考慮樣本的類別信息和數(shù)據(jù)空間的幾何流行結(jié)構(gòu)信息的有效性，并以圖像聚類為例，選擇ORL數(shù)據(jù)集進(jìn)行算法驗(yàn)證[2]。

1 圖像分類與模式識(shí)別

圖像數(shù)據(jù)的維度較高，直接影響了圖像分類的準(zhǔn)確性和運(yùn)算效率，所以圖像分類的第一步就是圖像降維。降維能夠去掉冗余的維數(shù)，將有用的維數(shù)保留下來(lái)，實(shí)現(xiàn)高維數(shù)據(jù)低秩逼近。圖1所示為圖像分類的基本框架，首先通過(guò)圖像降維處理獲得圖的特征值、特征向量，然后將其輸入分類器或者支持向量機(jī)，以此實(shí)現(xiàn)圖像分類。

圖1 圖像分類的框架

2 非負(fù)矩陣分解

2.1 非負(fù)矩陣分解的基本概念

對(duì)非負(fù)矩陣X∈Rm×n來(lái)說(shuō)，矩陣分解的目標(biāo)就是為了得到兩個(gè)非負(fù)矩陣W∈Rm×r和H∈Rr×n，使得X≈WH，其中r=min(m,n)。X≈WH的求解可以近似看做是求最優(yōu)解的問(wèn)題。常用的非負(fù)矩陣分解的目標(biāo)函數(shù)有基于歐式距離和基于K-L散度兩類。

基于歐式距離的目標(biāo)函數(shù)可以表示為：

(1)

基于K-L散度的目標(biāo)函數(shù)可以表示為：

-Xij+(WH)ij)2

(2)

在統(tǒng)計(jì)獨(dú)立性方面，K-L散度具有突出優(yōu)勢(shì)。K-L散度是X和WHT差異的非對(duì)稱性度量。當(dāng)X=WHT，K-L散度函數(shù)最小值為0。如果單獨(dú)分析矩陣W和H，那么上文提到的目標(biāo)函數(shù)為凸函數(shù)；如果同時(shí)考慮矩陣W和H，那么目標(biāo)函數(shù)不是凸函數(shù)。非負(fù)矩陣分解之后的矩陣W和H具有稀疏性，可以有效的降低數(shù)據(jù)冗余。但是，這種方法帶來(lái)的稀疏性不夠明顯，很多情況下無(wú)法滿足應(yīng)用要求，所以需要在目標(biāo)函數(shù)中增加稀疏限制項(xiàng)。非負(fù)矩陣分解算法及其常見(jiàn)的改進(jìn)算法中，矩陣W和H的初始值都是隨機(jī)選擇的，這些隨機(jī)值均為非負(fù)值。如果實(shí)際問(wèn)題相關(guān)信息不明確，那么W和H的初始值無(wú)法確定，只能隨機(jī)選擇。非負(fù)矩陣分解算法類似于約束優(yōu)化問(wèn)題，執(zhí)行問(wèn)題的步驟復(fù)雜繁多，選擇最優(yōu)分解也帶來(lái)了很大的時(shí)間消耗，無(wú)法滿足實(shí)踐應(yīng)用需要[3]。

2.2 迭代規(guī)則及算法收斂性

利用乘性迭代算法更新W，利用交替迭代算法更新H，不僅能夠提升收斂速度，也能夠降低計(jì)算難度。

Lee和Seung[4]提出一種乘法更新算法，將(1)更新為：

(3)

式(2)的更新規(guī)則可以表示為：

(4)

其中1≤i≤m,1≤j≤n,1≤k≤r，轉(zhuǎn)置矩陣表示為T，基矩陣表示為W，其中的列稱為基向量，系數(shù)矩陣表示為H。矩陣W和H的初始值隨機(jī)，在運(yùn)算過(guò)程中不斷更新矩陣W和H的值，直到矩陣的變化足夠小，獲得矩陣分解結(jié)果。為了確保更新過(guò)程中不因?yàn)榉帜笧榱愣鴮?dǎo)致異常，在分母上要添加一個(gè)足夠小的正數(shù)。

歐式距離函數(shù)(1)單調(diào)遞減，如果W和H是函數(shù)的穩(wěn)定點(diǎn)，那么函數(shù)值不再繼續(xù)變化。

K-L散度函數(shù)(2)單調(diào)遞減，如果W和H是函數(shù)的穩(wěn)定點(diǎn)，那么函數(shù)值不再繼續(xù)變化。

在討論非負(fù)矩陣分解算法的收斂性時(shí)，引入了輔助函數(shù)[5]來(lái)分析，并導(dǎo)出迭代規(guī)則。

定義G(k,k′)為F(k)的輔助函數(shù)，并且滿足式：

G(k,kt)≥F(k),G(k,k)=F(k)

(5)

2.3 圖正則非負(fù)矩陣分解算法

采用圖正則化方法的非負(fù)矩陣分解算法，就是在進(jìn)行矩陣分解時(shí)，明確低維度空間樣本數(shù)據(jù)的基本幾何結(jié)構(gòu)。假設(shè)存在兩個(gè)數(shù)據(jù)點(diǎn)，分別表示為xi和xj，它們?cè)谠瓟?shù)據(jù)空間是鄰近的關(guān)系，那么在新的基矩陣下其對(duì)應(yīng)的vi和vj也是鄰近關(guān)系。

假設(shè)G是由原始數(shù)據(jù)點(diǎn)組成的圖，權(quán)重矩陣用Sij來(lái)表示，xi的p個(gè)鄰近數(shù)據(jù)點(diǎn)由Np(xi)表示，那么：

(6)

式(7)為圖正則化非負(fù)矩陣分解算法的最小化目標(biāo)函數(shù)：

(7)

迭代更新規(guī)則表示為：

(8)

3 基于圖正則化和稀疏約束的半監(jiān)督非負(fù)矩陣分解

在特征提取方面，非負(fù)矩陣分解算法只能在數(shù)據(jù)原始空間展開(kāi)，在變形空間無(wú)法實(shí)現(xiàn)。本文提出在非負(fù)矩陣分解算法基礎(chǔ)上，對(duì)基矩陣進(jìn)行稀疏約束，引入拉普拉斯正則化約束，最終有效減少運(yùn)算環(huán)節(jié)和節(jié)約存儲(chǔ)空間，提升非負(fù)矩陣分解的效率。

本文提出的新的最小化目標(biāo)函數(shù)可以表示為：

(9)

上式中，標(biāo)簽約束矩陣可以表示為A，拉普拉斯矩陣表示為L(zhǎng)，正則化參數(shù)表示為λ，稀疏系數(shù)表示為β，β∈(0,1)?！琯‖F(xiàn)表示的是F范數(shù)。按照迭代法和最速下降法的原則，式(9)的迭代規(guī)則可以表示為：

=Tr(XXT)-2Tr(SAZWT)+Tr(WZTATAZWT)

(10)

φ和φ表示的是約束Wik≥0,Zjk≥0對(duì)應(yīng)的拉格朗日乘子，那么可以將拉格朗日函數(shù)表示為：

L1=OF+Tr(φWT)+Tr(φZ(yǔ)T)

(11)

求解W和Z的偏導(dǎo)數(shù)，令它們的值為零，那么：

(12)

利用KKT條件，可以將迭代規(guī)則確定為：

(13)

根據(jù)上述分析，目標(biāo)函數(shù)和Z中任意元素Zij相關(guān)的部分可以表示為Fij，那么：

(14)

此處假設(shè)F′表示的是Z的一階微分，那么Fij的輔助函數(shù)可以表示為：

(15)

證明G(z,z)=Fij，按照輔助函數(shù)的定義，則需要證明G(z,zt)≥Fij(z)。Fij(z)的泰勒展開(kāi)可以表示為：

(16)

相較于輔助函數(shù)，可以將G(z,zt)≥Fij(z)等價(jià)表示為：

≥(AAT)ii(WTW)jj+λ(ATLA)ii

(17)

已知

≥zt(ATA)(WTW)

(18)

且

≥λ(AT(D-U))zt=λ(ATLA)zt

(19)

得證。

4 實(shí)驗(yàn)驗(yàn)證

在Windows10環(huán)境下，利用Matlab R2012b進(jìn)行算法的驗(yàn)證。此次驗(yàn)證基于英國(guó)劍橋Olivetti實(shí)驗(yàn)室提出的人臉圖像數(shù)據(jù)庫(kù)ORL展開(kāi)。所有圖像的尺寸都是92×112。ORL數(shù)據(jù)集共有400張圖片，維度為1024，共40個(gè)類別。

首先從ORL數(shù)據(jù)集的各個(gè)樣本類中選取包含有標(biāo)記信息的樣本，從其中隨機(jī)的選擇K類樣本開(kāi)展聚類分析，本文選定的實(shí)驗(yàn)次數(shù)為20次。

圖2 ORL數(shù)據(jù)庫(kù)的圖像舉例

算法的聚類性能采用聚類準(zhǔn)確率(AC)的指標(biāo)來(lái)分析，即數(shù)據(jù)集中正確分類的樣本的占比。如果樣本的數(shù)據(jù)量為n，ri表示給定的正確樣本類別信息，li表示聚類后的樣本信息。則

(20)

上式中，δ(x,y)表示二值函數(shù)。如果x=y，那么二值函數(shù)值為1；如果x≠y，那么值為0。map(li)表示映射函數(shù)，是li和數(shù)據(jù)集中其他類別的樣本之間的映射關(guān)系。

互信息表示聚類樣本之間存在的相關(guān)性，即MI。假設(shè)存在兩個(gè)聚類樣本集，分別表示為C和C′，則：

MI(C,C′)

(21)

將其歸一化之后，可以表示為：

(22)

此處正則項(xiàng)參數(shù)λ取值為100，稀疏系數(shù)β的取值為0.3。

圖3 ORL數(shù)據(jù)集的收斂曲線及聚類準(zhǔn)確率

圖3所示為利用ORL數(shù)據(jù)集實(shí)驗(yàn)后的收斂曲線，實(shí)驗(yàn)結(jié)果表明利用該方法迭代50次左右就能夠滿足收斂要求。采用幾種不同的非負(fù)矩陣分解算法，對(duì)每個(gè)隨機(jī)的k值運(yùn)行20次后，最終的聚類結(jié)果表明該算法在圖像聚類方面效率良好。

5 結(jié)語(yǔ)

總體來(lái)看，利用本文提出的新的非負(fù)矩陣分解算法，降維之后的圖像聚類效果遠(yuǎn)好于一般的非負(fù)矩陣分解算法，并且穩(wěn)定性能保持在良好的范圍內(nèi)，該算法在圖像分類中有良好的應(yīng)用效果。