自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解算法

何雁雁

（貴州師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，貴陽(yáng) 550025）

0 引言

在文本聚類、圖像處理、模式識(shí)別等領(lǐng)域，往往能遇到非負(fù)高維矩陣。所以，適用于非負(fù)數(shù)據(jù)降維的方法——非負(fù)矩陣分解（NMF）［1］開(kāi)始受到人們的廣泛關(guān)注。隨后，人們將不同的正則項(xiàng)以及約束加入到NMF 模型中構(gòu)成新的模型，并應(yīng)用于數(shù)據(jù)聚類與分類［2］，圖像還原［3］以及盲源信號(hào)分離［4］等領(lǐng)域。Cai 等［5］提出了圖正則化非負(fù)矩陣分解（GNMF），該算法將圖正則項(xiàng)與NMF 算法相結(jié)合，考慮數(shù)據(jù)內(nèi)部的幾何結(jié)構(gòu)信息。圖的構(gòu)造對(duì)GNMF 算法有著至關(guān)重要的影響，因此，文獻(xiàn)［6］提出了多圖正則化非負(fù)矩陣分解算法（MGNMF），該算法通過(guò)優(yōu)化權(quán)重［7］，將多個(gè)圖按照線性組合的方式構(gòu)成一個(gè)多圖正則項(xiàng)加入到NMF 算法中。在自加權(quán)多視圖學(xué)習(xí)（AMGL）［8］的基礎(chǔ)上， Shu 等［9］提出自加權(quán)多圖正則化非負(fù)矩陣分解（PAMGNMF）。在不同的數(shù)據(jù)集上，該算法能夠?qū)Σ煌膱D自動(dòng)加權(quán)，從而更廣泛地應(yīng)用于實(shí)際問(wèn)題中。此外，文獻(xiàn)［10］提出了圖正則化Lp光滑非負(fù)矩陣分解算法（GSNMF），該算法不僅能夠保留數(shù)據(jù)的內(nèi)部幾何結(jié)構(gòu)，而且能夠得到更加光滑且精確的結(jié)果。

為了在近似數(shù)據(jù)內(nèi)部幾何結(jié)構(gòu)的基礎(chǔ)上，得到更加光滑且精確的解，將自動(dòng)加權(quán)多圖正則項(xiàng)以及Lp光滑約束加入到NMF 模型中，本文提出了自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解模型（AMGSNMF）。該模型通過(guò)多個(gè)圖的線性組合構(gòu)成多圖正則項(xiàng)來(lái)近似原始數(shù)據(jù)中的內(nèi)部幾何流形結(jié)構(gòu)，利用Lp光滑約束項(xiàng)的優(yōu)點(diǎn)來(lái)獲得光滑且精確的解。

1 相關(guān)工作

1.1 非負(fù)矩陣分解和圖正則非負(fù)矩陣分解

基于矩陣非負(fù)的約束，NMF 算法［1］是一種用低維非負(fù)矩陣乘積近似高維非負(fù)矩陣的算法。給定非負(fù)矩陣X= [x1,x2, …,xN] ∈RM×N+，其中，X的每一列代表一個(gè)樣本點(diǎn)，NMF 算法的目的是尋找兩個(gè)非負(fù)矩陣U∈RM×K和V∈RN×K，使U和VT的乘積近似于原始矩陣X，表示為如下優(yōu)化問(wèn)題：

其中，‖? ‖F(xiàn)表示矩陣的Frobenius-范數(shù)。Lee等［1］利用乘性更新法提出了以下更新方式：

通過(guò)迭代，獲得優(yōu)化問(wèn)題（1）的局部最優(yōu)解。

然而，NMF 算法并不能夠較好地保留數(shù)據(jù)的內(nèi)部幾何結(jié)構(gòu)，為了解決這一問(wèn)題，Cai 等［5］提出了GNMF算法，其優(yōu)化問(wèn)題如下：

其中：α> 0 是正則化參數(shù)；Tr(?) 表示矩陣的跡；L=D-W是圖拉普拉斯矩陣，W是權(quán)重矩陣，D是對(duì)角矩陣，其對(duì)角元素為。

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

在考慮數(shù)據(jù)集內(nèi)部幾何結(jié)構(gòu)的同時(shí)，GSNMF 算法［10］加入了Lp光滑約束，其優(yōu)化問(wèn)題如下：

1.3 無(wú)參數(shù)的自動(dòng)加權(quán)多圖正則化非負(fù)矩陣分解

文獻(xiàn)［9］利用AMGL 算法［8］中的無(wú)參數(shù)多圖正則項(xiàng)，提出了PAMGNMF 算法，該算法求解如下優(yōu)化問(wèn)題：

其中：α> 0 是正則化參數(shù)；τ= (τ1,τ2, …,τI)，τi是第i個(gè)圖的權(quán)重。

2 自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解

在本節(jié)中，將具體介紹自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解模型，再利用交替更新法求解該模型，提出自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解算法（AMGSNMF）。

2.1 自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解模型

在NMF模型中，加入自動(dòng)加權(quán)多圖正則項(xiàng)，這樣能更精確地近似數(shù)據(jù)內(nèi)部幾何結(jié)構(gòu)。在自動(dòng)加權(quán)多圖正則化非負(fù)矩陣分解的基礎(chǔ)上，對(duì)基矩陣進(jìn)行Lp光滑約束，從而能夠得到一個(gè)更加光滑且精確的分解結(jié)構(gòu)，提高聚類效果。所以，提出了自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解模型：

其中，1 0 和μ> 0 分別是正則化參數(shù)。

2.2 優(yōu)化目標(biāo)函數(shù)

對(duì)于變量U和V而言，優(yōu)化問(wèn)題（5）的目標(biāo)函數(shù)OAMGSNMF是非凸函數(shù)，但是若固定變量U或者V中的一個(gè)，只考慮一個(gè)變量，則它是凸函數(shù)，因此，尋找優(yōu)化問(wèn)題（5）的全局最優(yōu)解是非常困難的，但是可以通過(guò)乘性更新法尋找局部最優(yōu)解。先將優(yōu)化問(wèn)題（5）的目標(biāo)函數(shù)OAMGSNMF轉(zhuǎn)換為如下形式：

2.2.1 優(yōu)化U和V

對(duì)于約束條件uik≥0 和vjk≥0，分別使用拉格朗日乘子φik和?jk，則得到如下拉格朗日函數(shù)：

其中，Ψ =[φik]，Φ =[?jk]。式（7）分別關(guān)于U、V求偏導(dǎo)得：

通過(guò)式（8）和式（9），得出如下關(guān)于uik和vjk的更新公式：

2.2.2 優(yōu)化τ

在每一次迭代更新中，不同圖的權(quán)重τi也需要更新，在AMGSNMF 算法中，設(shè)τi的更新規(guī)則如下：

由更新公式（10）、（11）和（12）可得AMGSNMF算法，詳見(jiàn)算法1。

算法1 自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解

輸入：數(shù)據(jù)矩陣X,正則化參數(shù)α，μ以及p,設(shè)置權(quán)重為，隨機(jī)構(gòu)造非負(fù)矩陣U0和V0

輸出：基矩陣U和系數(shù)矩陣V

1. 構(gòu) 造I個(gè)k鄰 近 圖(W1,W2, …,WI)，并 計(jì)算其對(duì)應(yīng)的拉普拉斯矩陣(L1,L2, …,LI)

2. fori=1, 2, …

3. 根據(jù)式（10）更新Ui

4. 根據(jù)式（11）更新Vi

5. 根據(jù)式（12）更新τi

6. if 滿足停止準(zhǔn)則

7. 得到最終的U和V

8. end if

9. end for

3 數(shù)據(jù)集及實(shí)驗(yàn)評(píng)估

為了評(píng)估AMGSNMF算法的性能，在COIL20和ORL數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

3.1 算法的評(píng)估

利用Frobenius-范數(shù)來(lái)衡量UVT和X逼近程度，將AMGSNMF算法與NMF、GNMF、GSNMF、PAMGNMF、AMGSNMF 算法進(jìn)行比較。并且通過(guò)精確度（ACC）［11］和歸一化互信息（NMI）［11］這兩個(gè)指標(biāo)來(lái)評(píng)價(jià)聚類效果。

3.2 聚類結(jié)果

表1～表4依次給出了算法在COIL20 和ORL 數(shù)據(jù)集上的聚類結(jié)果。為了克服初值對(duì)實(shí)驗(yàn)結(jié)果的影響，選取不同的聚類數(shù)K對(duì)結(jié)果進(jìn)行評(píng)估。對(duì)于給定的K，進(jìn)行10 次重復(fù)的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果的均值和誤差在表中顯示。

表1 在COIL20數(shù)據(jù)集上的聚類精確度

表2 在COIL20數(shù)據(jù)集上的歸一化互信息

表3 在ORL數(shù)據(jù)集上的聚類精確度

表4 在ORL數(shù)據(jù)集上的歸一化互信息

從表1～表4 可以觀察到，AMGSNMF 算法在兩個(gè)數(shù)據(jù)集上的ACC 和NMI 大多數(shù)情況下是最高的，與NMF、GNMF、GSNMF 算法相比，ACC 和NMI 分別至少提高了6.25% 和2.76%, 與PAMGNMF 算法對(duì)比，聚類效果也有一些提升，這說(shuō)明了AMGSNMF 算法能獲得更精確的結(jié)果，從而提高聚類的效果。

3.3 參數(shù)實(shí)驗(yàn)

在AMGSNMF 算法中，有以下幾個(gè)參數(shù)需要進(jìn)行實(shí)驗(yàn)，分別為多圖正則化參數(shù)α,Lp范數(shù)的參數(shù)p以及Lp正則化參數(shù)μ。

首先，圖1表示不同α的取值對(duì)聚類結(jié)果的影響。由圖1 可以看出，AMGSNMF 算法的聚類效果會(huì)隨著α取值的增大而逐漸變好。

圖1 參數(shù)α對(duì)各類算法聚類性能的影響

當(dāng)p從1.1 到1.9 變 化 時(shí)， 在COIL20 以 及ORL數(shù)據(jù)集的不同類別中進(jìn)行實(shí)驗(yàn)，圖2顯示了聚類結(jié)果。可以看出，當(dāng)參數(shù)p選取不同值時(shí)，AMGSNMF算法在大多數(shù)情況下，依舊能夠保持很高的聚類精確度以及歸一化互信息。

圖2 參數(shù)p對(duì)各類算法聚類性能的影響

最后， 針對(duì)μ的變化，在COIL20 和ORL 數(shù)據(jù)集中，分別選取了5 類和30 類進(jìn)行實(shí)驗(yàn)，最終實(shí)驗(yàn)結(jié)果如圖3 所示?？梢钥闯?，當(dāng)μ變化時(shí)，AMGSNMF算法的效果在大多數(shù)情況下，依舊好于其他算法。

圖3 參數(shù)μ對(duì)各類算法聚類性能的影響

4 結(jié)語(yǔ)

本文提出了新的自動(dòng)加權(quán)多圖正則化Lp光滑非負(fù)矩陣分解算法。該算法應(yīng)用自動(dòng)加權(quán)多圖正則項(xiàng)來(lái)逼近數(shù)據(jù)的原始內(nèi)部幾何結(jié)構(gòu)，應(yīng)用Lp光滑約束來(lái)獲得更精確且光滑的解。實(shí)驗(yàn)結(jié)果表明，在聚類效果上，AMGSNMF算法表現(xiàn)得比其他算法都更好。多圖正則項(xiàng)能夠有效地逼近原始數(shù)據(jù)的內(nèi)部幾何結(jié)構(gòu)，但是，如何構(gòu)造多圖正則項(xiàng)是一個(gè)難題，需要下一步繼續(xù)研究。