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

陳璐瑤

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

0 引言

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

1 預(yù)備知識(shí)

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

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

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

2 SHGNMF算法

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

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

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

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

算法1 SHGNMF算法

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

步驟2隨機(jī)初始化矩陣W和H；

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

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

步驟5將此算法運(yùn)用到圖像聚類中，計(jì)算聚類性能指標(biāo)精度（ACC）、歸一化互信息（NMI）。

3 收斂性分析

定理1對(duì)于W≥0,H≥0，目標(biāo)函數(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ī)則，有：

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

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

引理2函數(shù)

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

4 數(shù)值實(shí)驗(yàn)

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

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

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

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

4.2 參數(shù)選擇

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

4.3 實(shí)驗(yàn)結(jié)果與分析

在實(shí)驗(yàn)中使用的兩個(gè)度量標(biāo)準(zhǔn)是精度（ACC）和歸一化互信息（NMI），在文獻(xiàn)[7]中可以找到詳細(xì)定義。實(shí)施細(xì)節(jié)如下：

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

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

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

（4）計(jì)算ACC和NMI兩個(gè)聚類指標(biāo)。

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

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

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

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

5 結(jié)語(yǔ)

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

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

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