L2稀疏超圖正則非負矩陣分解的圖像聚類算法

陳璐瑤

（貴州師范大學數學科學學院，貴陽550025）

0 引言

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

1 預備知識

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

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

為了保持數據集的內在幾何結構信息，Cai等人[3]在NMF的基礎上提出了以下的目標函數：

2 SHGNMF算法

在這一部分中，提出了帶有L2稀疏約束和超圖正則的非負矩陣分解算法（SHGNMF），它不僅可以保持數據集的內在幾何結構信息，而且更加有效和稀疏，提高分解的質量，得到更精確的結果。接下來將給出更新規則和詳細推導過程。

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

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

根據以上分析，下面給出新算法。

算法1 SHGNMF算法

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

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

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

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

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

3 收斂性分析

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

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

定義1

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

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

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

下是非增的。

證明：根據定義1和更新迭代規則，有：

下面證明當輔助函數合理構造時，H的更新規則式（11）與式（12）是一致的。定義Fab是目標函數關于hab對應部分的輔助函數，對Fab關于H求偏導數：

接下來構造關于H合適的輔助函數，為了證明目標函數在更新規則式（11）下是非增長的。

引理2函數

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

4 數值實驗

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

4.1 數據描述

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

COIL-20：COIL-20數據集包含對20個物體從不同角度的拍攝，每隔5度拍攝一副圖像，每個物體72張圖像。總共包含20個對象的128×128大小的1440張灰度圖像。在實驗中，COIL-20中的所有圖像都被調整為32×32。

4.2 參數選擇

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

4.3 實驗結果與分析

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

（1）從數據集中隨機選取k個類別。

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

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

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

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

表1 ORL數據集聚類精度（ACC）

表4 COIL-20數據集歸一化互信息（NMI）

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

5 結語

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

表2 ORL數據集歸一化互信息（NMI）

表3 COIL-20數據集聚類精度（ACC）