陳璐瑤

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

0 引言

在計算機視覺、模式識別、數(shù)據(jù)表示或聚類分析中，低秩矩陣分解是一種非常流行的方法。Lee等人[1]在Nature雜志上發(fā)表了非負矩陣分解（NMF）方法就是一種特殊的低秩矩陣分解的方法，與傳統(tǒng)的算法相比，NMF避免了出現(xiàn)負元素，從而更具有實際物理意義。后來為了利用潛在的流形結(jié)構(gòu)，Cai等人[2]提出了一種圖正則NMF（GNMF）方法，該方法通過構(gòu)造K-最鄰近（KNN）方法來考慮數(shù)據(jù)點幾何結(jié)構(gòu)信息。姜偉等人[3]在圖正則非負矩陣分解的基礎(chǔ)上添加了L1稀疏約束項，得到更加有效和稀疏的系數(shù)矩陣，從而節(jié)省了存儲空間，提高了分解質(zhì)量。但是由于L1損失函數(shù)的結(jié)果更具魯棒性，也就是說對于異常值更加不敏感，而L2的求解更為簡單其解是唯一的。L2相對于L1具有更為平滑的特性，在模型預(yù)測中，往往比L1具有更好的預(yù)測特性。另外，超圖是普通圖的推廣，適用于處理嵌入高維空間的低維子流形的數(shù)據(jù)，超圖考慮到了數(shù)據(jù)內(nèi)部的高維樣本間的關(guān)系，所以要優(yōu)于普通圖。因此，本文在先前工作的基礎(chǔ)上進行改進，現(xiàn)將L2稀疏約束項和超圖正則項引入NMF中，提出新的帶有L2稀疏約束和超圖正則的非負矩陣分解（SHGNMF）方法，來得到更稀疏精確的結(jié)果。并在公開數(shù)據(jù)集上的進行實驗，結(jié)果表明該算法優(yōu)于其他相關(guān)算法。

1 預(yù)備知識

NMF是一種特殊的基于局部特征的矩陣分解方法，它側(cè)重于對元素非負的數(shù)據(jù)進行分析。給定一個非負矩陣V=[ x1,x1,…,xn]∈Rm×n，V的每一列都是一個多維數(shù)據(jù)點。

NMF的目的是找到兩個非負矩陣W∈Rm×r和H∈Rr×n，使以下目標函數(shù)式（1）最小：

為了保持數(shù)據(jù)集的內(nèi)在幾何結(jié)構(gòu)信息，Cai等人[3]在NMF的基礎(chǔ)上提出了以下的目標函數(shù)：

2 SHGNMF算法

在這一部分中，提出了帶有L2稀疏約束和超圖正則的非負矩陣分解算法（SHGNMF），它不僅可以保持數(shù)據(jù)集的內(nèi)在幾何結(jié)構(gòu)信息，而且更加有效和稀疏，提高分解的質(zhì)量，得到更精確的結(jié)果。接下來將給出更新規(guī)則和詳細推導(dǎo)過程。

其中λ，β是大于0的常數(shù)。目標函數(shù)的第二項和第三項分別表示的是超圖正則項和稀疏項。LHyper=Dv-B超圖拉普拉斯矩陣，并且

下面我們采用交替非負最小二乘方法，可得到式（5）的更新規(guī)則。將目標函數(shù)重新寫成：

根據(jù)以上分析，下面給出新算法。

算法1 SHGNMF算法

步驟1 V∈Rm×n，1≤r≤min{m,n，}圖正則化參數(shù)λ>0，稀疏約束參數(shù)β>0，鄰域大小k>0；

步驟2隨機初始化矩陣W和H；

步驟3根據(jù)式（10）、式（11）更新矩陣W和H，直到滿足收斂條件時停止；

步驟4輸出矩陣W∈Rm×r和H∈Rr×n；

步驟5將此算法運用到圖像聚類中，計算聚類性能指標精度（ACC）、歸一化互信息（NMI）。

3 收斂性分析

定理1對于W≥0,H≥0，目標函數(shù)式（5）在更新迭代規(guī)則式（10）和式（11）下是非增的。

為了證明此定理，首先引入輔助函數(shù)[6]的定義：

定義1

若G(x,x')滿足G(x,x')≥F(x)和G(x,x)=F(x)，

則G(x,x')是F(x)的輔助函數(shù)。

引理1若G(x,x')是F(x)的輔助函數(shù)，則F(x)在更新迭代規(guī)則：

下是非增的。

證明：根據(jù)定義1和更新迭代規(guī)則，有：

下面證明當輔助函數(shù)合理構(gòu)造時，H的更新規(guī)則式（11）與式（12）是一致的。定義Fab是目標函數(shù)關(guān)于hab對應(yīng)部分的輔助函數(shù)，對Fab關(guān)于H求偏導(dǎo)數(shù)：

接下來構(gòu)造關(guān)于H合適的輔助函數(shù)，為了證明目標函數(shù)在更新規(guī)則式（11）下是非增長的。

引理2函數(shù)

由于式（15）是Fab的輔助函數(shù)，所以在更新迭代規(guī)則式（20），即式（11）下是非增的。類似地，式（10）同理可證。故而：

4 數(shù)值實驗

為了驗證新算法SHGNMF的有效性，將它與K-means、NMF[1]、GNMF[2]和SGNMF[3]算法進行比較。在ORL和COIL-20數(shù)據(jù)集上進行實驗，并對結(jié)果進行對比。文中的所有實驗均使用MATLAB 2019a軟件進行編程，在處理器型號為Intel Core i5-7500 CPU@3.40GHz 3.41 GHz，系統(tǒng)內(nèi)存為8.00 GB，64位的Win10操作系統(tǒng)環(huán)境下進行的。

4.1 數(shù)據(jù)描述

ORL：ORL數(shù)據(jù)集由40個不同對象的400張112×92的灰度人臉圖像組成。每個人在不同的時間有10個不同的圖像，有不同的燈光、面部表情和面部細節(jié)。在實驗中，ORL中的所有圖像都被調(diào)整為32×32。

COIL-20：COIL-20數(shù)據(jù)集包含對20個物體從不同角度的拍攝，每隔5度拍攝一副圖像，每個物體72張圖像?？偣舶?0個對象的128×128大小的1440張灰度圖像。在實驗中，COIL-20中的所有圖像都被調(diào)整為32×32。

4.2 參數(shù)選擇

對于GNMF、SGNMF和SHGNMF，使用p-最近鄰方法構(gòu)造了圖拉普拉斯和超圖拉普拉斯，其中鄰域大小p設(shè)為1，圖的正則化參數(shù)λ設(shè)為0.5。

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

在實驗中使用的兩個度量標準是精度（ACC）和歸一化互信息（NMI），在文獻[7]中可以找到詳細定義。實施細節(jié)如下：

（1）從數(shù)據(jù)集中隨機選取k個類別。

（2）使用SHGNMF算法進行分解得到對應(yīng)子空間。

（3）使用K-means算法對重構(gòu)表征進行聚類。

（4）計算ACC和NMI兩個聚類指標。

重復(fù)上述步驟20次，記錄其平均值和方差。表1-表4展示出了ORL和COIL-20數(shù)據(jù)集的聚類結(jié)果。

表1 ORL數(shù)據(jù)集聚類精度（ACC）

表4 COIL-20數(shù)據(jù)集歸一化互信息（NMI）

由表可知，SHGNMF對比其他相關(guān)方法，聚類性能明顯提升。其中，聚類精度提升了3.7%～4.5%，歸一化互信息提升了1.1%～1.8%。這也表明所提出的新方法是有效的。

5 結(jié)語

新方法是基于稀疏約束和超圖正則化的非負矩陣分解算法。SHGNMF保留了原始數(shù)據(jù)中的內(nèi)部結(jié)構(gòu)，同時，L2范數(shù)用于稀疏表示為了防止模型過擬合。在公開的真實數(shù)據(jù)集上的實驗結(jié)果表明，SHGNMF得到了更精確的結(jié)果，并獲得了更好的聚類效果。

表2 ORL數(shù)據(jù)集歸一化互信息（NMI）

表3 COIL-20數(shù)據(jù)集聚類精度（ACC）