自適應圖正則化的低秩非負矩陣分解算法

余沁茹，盧桂馥，李華

（安徽工程大學 計算機與信息學院,安徽 蕪湖 241009）

聚類是計算機視覺中一項受到廣泛關注且充滿挑戰的任務。近些年來，圖聚類因為相較于其他方法表現出了更好的性能而被廣泛應用于圖像分類、圖像檢索等方面[1-2]。在信息檢索、計算機視覺和模式識別的許多問題中，由于樣本數據的維數很高，使得從樣本直接學習并聚類的的方法是往往不可行的[3]。因此，人們希望找到兩個或多個低維矩陣，使它們的乘積可以很好地近似于原始矩陣，越來越多的矩陣分解技術如LU 分解、QR 分解、矢量量化和奇異值分解（singular value decomposition,SVD）、非負矩陣分解（non-negative matrix factorization,NMF）等由此被提出[4-6]。在面部識別和文檔聚類任務中，NMF 已被證明優于SVD 等其他矩陣分解技術[7]。NMF 的目的是找到兩個非負矩陣，它們的乘積可以很好地近似原始矩陣。由于NMF 更新規則僅允許加法運算，矩陣分解的非負約束使得學習到的成分矩陣成為基于局部的表示，且是學習對象各部分的最佳選擇。為了提高NMF 的性能，學界已提出了許多NMF的拓展算法，例如L2.1范數非負矩陣分解[8]、結構不相干的低秩矩陣分解[9]等。

近年來，有些研究者提出了基于流形學習的算法，例如局部線性嵌入[10]、拉普拉斯特征圖[11]等，這些研究表明，高維數據其本質分布于低維子空間。研究人員發現，在NMF 算法中引入流形學習方法獲得數據的流形結構，有助于提升NMF的性能[12]。Cai 等[13-14]在NMF 的基礎上結合流形學習技術提出了圖非負矩陣分解算法（graph nonnegative matrix factorization,GNMF）。Zhou 等在GNMF 的基礎上為NMF 添加了額外的約束[15]，進一步提出了局部學習正則化NMF（local learning regularized NMF，LLNMF）[16]。Li 等[17]提出圖正則化非負矩陣分解（graph nonnegative low-rank matrix factorization,GNLMF），該方法使得圖正則化時可以獲得原始圖像數據的低秩結構。Du 等[18]提出圖嵌入正則化投影非負矩陣分解方法（graph embedding regularized projection nonnegative matrix factorization for face image feature extraction，GEPNMF），通過引入圖嵌入正則化項，學習的子空間可以保留數據的局部幾何結構，同時提升了算法判別力。Yin 等[19]提出一種拉普拉斯正則化低秩表示及其應用算法（Laplacian regularized low-rank representation and its applications，LLRR），該算法通過對圖形的正則化，既能表示數據的全局低維結構，又能捕獲數據中固有的非線性幾何信息。Wang 等[20]提出一種降維局部約束圖優化算法（locality constrained graph optimization for dimensionality reduction，LC-GODR），該算法將圖優化和投影矩陣學習結合到了一個框架中。由于圖不是預先構造并保持不變的，使得其在降維過程中的圖形可以自適應更新。Meng 等[21]提出的具有稀疏和正交約束的對偶圖正則化非負矩陣分解（dual-graph regularized non-negative matrix factorization with sparse and orthogonal constraints,SODNMF），此方法能同時考慮數據空間和特征空間的流形結構。受到Nie 等[22]的啟發，Huang 等[23]提出了局部自適應結構的正則化非負矩陣分解算法（regularized nonnegative matrix factorization with adaptive local structure learning,NMFAN）。NMFAN 算法使用自適應學習的方法來利用數據局部結構中流形信息，但是，NMFAN 算法并沒有利用數據的有效低秩結構信息。

以上這些算法通過構建拉普拉斯圖來利用數據的局部流形結構信息，其所使用的圖的極大地影響著算法的性能。研究人員往往利用K 近鄰（K nearest neighbor，KNN）來構建圖。然而，一方面，KNN 方法構造的圖有可能會破壞部分原始數據的局部連通性；另一方面，其圖的構造與矩陣分解的結果無關，從而使得相關算法的性能不能達到最優。此外，這些算法往往沒有考慮數據的低秩結構，而數據的有效信息往往隱藏在其低秩結構中。為此，本文提出了一種自適應圖正則化的非負矩陣分解算法（nonnegative low-rank matrix factorization with adaptive graph neighbors，NLMFAN）。一方面，NLMFAN 通過引入低秩約束來獲得原始數據集的潛藏的有效信息，以此提升現有算法性能；另一方面，NLMFAN 將圖的構造和矩陣分解的結果融入一個整體的框架中，自動從數據中學習得到圖中節點的相似性，優化了算法精度。文中同時給出了一種求解NLMFAN 的有效算法，并在多種數據集上進行了實驗驗證本文所提出的算法的有效性。

1 相關工作

1.1 非負矩陣分解（NMF）

NMF 是一種廣泛使用的矩陣分解算法。它試圖將一個非負矩陣分解為兩個階乘矩陣，其乘積是其自身的最佳近似值。給定一個數據矩陣X=[x1x2···xn]∈RM×N的每一列都是樣本矢量，NMF的目的是找到兩個非負矩陣U=[uik]∈RM×K和V=[vik]∈RN×K，使得它們的乘積可以很好地近似于原始矩陣X：

即標準NMF 的目標是搜索兩個非負矩陣U和V以優化以下目標

其中||·||F表示矩陣的F 范數，同時其存在以下更新規則的表示形式：

1.2 圖正則化非負矩陣分解（GNMF）

為了能在NMF 算法中保留其內在結構的同時探索數據的局部幾何結構，近幾年將流形學習與NMF 相結合的算法研究成為熱點。Cai 等[13]通過將圖正則化項融入到標準NMF 算法框架中提出了圖正則化非負矩陣分解(GNMF)，其目標函數如下：

其中，Dap是對角矩陣，Lap=Dap?Sap。

2 自適應低秩非負矩陣分解算法

研究表明，原始圖像數據通常嵌入位于高維歐式空間中的非線性低維流形上，且其有效信息通常隱藏在低秩結構中。另外，在圖正則化相關算法中所使用的圖一般是預先定義的，其圖的構造與算法的其他部分往往互相獨立。因此，這些算法使用的圖并不一定是最優的。為此，在本小節提出一種自適應圖正則化的非負矩陣分解算法NLMFAN，該算法同時兼顧了原始圖像數據的有效低秩結構和自適應圖構造。

2.1 NLMFAN 的算法模型

設輸入的原始數據集為X，先給出本文NLMFAN 算法的求解形式如下：

目標函數的第1 項為在rank(L)≤r,cord(E)≤e條件的約束下通過原始數據集X求其低秩形式L，再對得出的結果使用NMF 分解。其中矩陣X為原始數據集，L代表矩陣的低秩部分，E代表其稀疏部分，U、V由L非負矩陣分解得出。r為L的秩范圍，e為E設置的稀疏范圍，rank（L）表示矩陣L的秩，card（E）表示矩陣E的非零條目數，1表示一個所有元素都為1 的列向量。

目標函數的第2 項為自適應正則項，使用其完成自適應相似矩陣的構造，其中α均為正則化參數。此處我們直接基于數據點間的歐幾里得距離構造鄰域矩陣，并設距離越小則成為最近鄰的可能性越大。原數據集X中的任意一數據點xi，都有所有數據點{x1,x2,···,xn}可以作為近鄰與xi連接，連接的概率為sij。si∈Rn×1表示向量，其第j個元素為sij。在此基礎上，可以得到相似度矩陣構建的求解函數為

上述相似度矩陣求解的問題存在簡化的可能，即我們僅基于歐氏距離求解距離最近的點，并設其與xi的連通概率為1，其他的點概率都為0。此時，對于式（7）中所有的數據點xi，除其之外的所有同數據集的點都存在相同的連通概率即。此時，式（7）可寫作：

結合式（7）和（8）可得目標函數中的第2 項，即自適應正則項為

其中γ是正則化參數。通過求解式（9）獲得的矩陣S∈Rn×n，可被視為相似度矩陣[22]。當我們假設每個點可以被表示為一個向量vi時，則有：

式中：Ls是S的拉普拉斯矩陣，LS=DS?WS；D5∈Rkxh是的對角陣。

目標函數的第3 項是局部圖拉普拉斯約束函數，用其來衡量數據低維表示的平滑度，其中tr(·)表示矩陣的秩。

2.2 NLMFAN 的算法求解

設計了一種有效的更新算法來求解NLMFAN，該算法通過固定其他變量迭代更新一個變量的值來優化目標，此過程重復直到收斂。

2.2.1 固定U、V更新S

觀察式（6），不難發現在固定變量U、V的情況下更新S的最小化，式（6）可等價于解決式（11）：

本文可以對每個i解決式（12），此時式（12）可等價于：

設ζ和η≥0 為拉格朗日乘子，可以寫出式（11）的拉格朗日函數：

根據KKT 條件[23]，滿足sij≥0，最優解可以定義為

結合式（17）和（18），可以得到：

為了獲得具有k個非零值的最優si，可以將γi設置為

為了便于計算，可以將整體γ設置為γ1,γ2,···,γn的均值，即

通過取γi的平均值，所有si的平均非零元素應為k。我們不直接搜索正則化參數γ，而是搜索近鄰數k。因為k是一個整數并且其值是有限的（即0≤k≤n），所以參數搜索會更加容易。

2.2.2 固定S、V更新U

觀察式（6），不難發現在固定變量S、V的情況下更新U的最小化，式（6）可等價于解決下式：

在優先求解L時，求解式（22）可轉換為先求解式（23）再求解U的過程：

將式（23）可拆兩個子問題來解決。當固定L或E時，有：

可見式（24）對于L或E都是凸的，因此可以固定一個變量并更新另一個，直到收斂。通過迭代X?Et?1將奇異值賦給Lt，在X?Lt上進行相同操作得到Et，由此得到兩個子問題的解。

但是，在每次迭代中求X?Et?1的SVD 都很耗時。 本文采用文獻[24]中提出的雙邊隨機投影（bilateral random projection ,BRP）來解決式（24）。

對于給定的矩陣X∈Rmexh，其r個BRPs 如下:

式中：A1∈Rn×r,A2∈Rm×r是隨機矩陣，那么X的秩r逼近為

由此可計算得出L。在此基礎上，對式（28）求解：

可以看出式（28）為式（1）中的標準NMF式。因此，對于等式中的U，我們有式（3）中完全相同的迭代更新規則：

2.2.3 固定S、U更新V

觀察式（6），不難發現在固定變量S、U的情況下更新V的最小化，式（6）可等價于解決下式：

參考2.2.2 節中方法可得一確定L。由此，化式（30）為

為了約束V≥0，令ξ ∈Rn×c表示對應的拉格朗日乘數，則可以將拉格朗日函數定義為

根據KKT 條件[23]滿足ξijvij=0，有：

則式（35）遵從如下迭代規則：

至此，可以給出NLMFAN 的算法求解步驟。

算法1自適應圖正則化的低秩非負矩陣分解算法

2.3 NLMFAN 算法收斂性分析

定理1對于U≥0,V≥0，式(6)中的目標在式(14)、(21)、(36)中的更新規則下不增加，因此收斂。

證明顯然，式(14)可以用第2.2 節中描述的閉式解來解決。因此，我們只需要證明式(21)和式(36)在每次迭代中的更新規則下目標值是不增加的。 此外，因為式(6)中目標的第2 項與U無關，第1 項在計算L時不涉及U值的更新，且計算得出L后的操作符合標準NMF 分解，所以NLMFAN 中的U更新規則與原始NMF 完全相同。 因此，可以使用NMF 收斂的證明方式來證明在等式中更新規則下目標沒有增加。有關詳細信息，可參考文獻[17]。

現在，只需要證明在式(36)中的更新規則下我們的目標不會增加即可，而式(32)中更新規則其實等價于文獻[25]中式(26)、(36)的收斂性證明可參考文獻[25]附錄中證明過程，此處不列出。

3 現實數據集實驗評估

3.1 實驗數據集

為了評估本文提出方法的性能，我們在實際基準數據集進行了實驗。

本文實驗用到的數據集包括CLUTO 數據工具及UCI 機器學習數據集。其中，CLUTO 是一個軟件包，用于對低維和高維數據集進行聚類，并分析各種聚類的特征。CLUTO 的數據工具包中包含的信息檢索、客戶購買交易、網絡、地理信息系統、科學和生物學等數據集非常適于聚類測試。UCI 機器學習數據集是加州大學歐文分校提出的用于機器學習的數據庫，該數據庫目前共有559個數據集，其數目還在不斷增加。UCI 數據集是一個常用的標準測試數據集。

選取CLUTO 數據工具中的4個數據集（Cacmcisi 、Hitech、K1a、K1b）與UCI 機器學習數據集4個數據集（Abalone、Krvs、Wdbc、Vote）進行實驗。表1 給出了各數據集及其特征。

表1 數據集及特征Table1 Description of data sets

3.2 實驗步驟

為了進一步評估所提出方法的性能，將NLMFAN 與一些經典算法和最新算法進行了對比實驗。主成分分析（principal component analysis,PCA）：經典的降維方法[26]。NMF：標準NMF 算法[6]。LLNMF（2009）：使用局部結構學習的NMF算法[16]。GNMF（2011）：圖正則化的NMF[13-14]。NMFAN（2020）：具有局部自適應結構的正則化NMF 算法[25]。

本文實驗條件為Intel(R)Core(TM)i7-1065G7 1.50 GHz CPU，16 GB DDR3 內存，Matlab2019b。在后續的性能評估中，以準確率（accurity,ACC）、標準互信息率（normalized mutual information,NMI）兩個指標作為評價算法性能好壞的標準，在8個基準數據集上測試算法。實驗中所用算法的參數已結合原論文根據需要調節至最優。

在每個數據集上都進行了算法精度與收斂速度測試，并從8個數據集中選取了4個用于測試λ參數對聚類性能的影響。

3.3 CLUTO 數據集實驗

CLUTO 的4個文檔數據集上進行了每組10次實驗。實驗結果均值如表2 所示。

表2 各算法在CLUTO 數據集上聚類結果比較Table2 ACC and NMI of clustering on CLUTO database %

從表2 中可以看出： NMF 相關算法的聚類結果還是優于傳統聚類方法。同時，在NMF 算法中，NLMFAN 算法顯示出了優于其他幾種方法的聚類效果。尤其是與改進前的NMFAN 算法相比，NLMFAN 算法在每個數據集上的精度及平均精度均有所提高。

圖1 展現了在CLUTO 的4個數據集上NLMFAN算法的收斂情況。圖中目標函數值即最小誤差值。可以看出，本文方法在數據集上均可快速收斂，迭代次數均在50 次內。

圖1 NLMFAN 在CLUTO 數據集上的收斂曲線Fig.1 Convergence curves of NLMFAN on CLUTO database

3.4 UCI 數據集實驗

本節使用了與上節相同的幾種算法在UCI的4個文檔數據集上進行了每組十次實驗。實驗結果如表3 所示。

從表3 中可以看出：在UCI 數據集上，NLMFAN算法的聚類效果基本優于其他算法，同時其在Abalone 數據集上的實驗數據較原有的其他算法有5.89%～0.57%的提升。圖2 呈現了在UCI 的4個數據集上NLMFAN 算法的收斂情況。可以看出，NLMFAN 算法在幾個數據集上均有收斂，且速度較快。

圖2 NLMFAN 在UCI 數據集上的收斂曲線Fig.2 Convergence curve of NLMFAN on UCI database

表3 各算法在UCI 數據集上聚類結果比較Table3 ACC and NMI of clustering on UCI database %

3.5 參數選擇實驗

本節對算法中λ參數的選擇進行討論。本文從CLUTO 中選取了Hitech、K1b，從UCI 中選取了Abalone、Krvs，總計4個數據集進行實驗。

從圖3 可以看出：

圖3 各算法中λ 參數對性能的影響Fig.3 Influence ofλparameter on different algorithms

1）除了NMF以外，GNMF、NMFAN、NLMFAN都受到λ值的影響。總體來說，當λ的值取在10 以內時NLMFAN 可以獲得較好的聚類結果，當λ取到10 時可以獲得所有算法平均最優結果。

2）除了在Hitech 數據集上有明顯的波動外，GNMF 在其他數據集上都沒有明顯波動變化，說明其受λ的影響不大。而根據提出GNMF 的文獻[13]中對其的實驗結果表明，GNMF 的結果會在固定λ值時，根據其選取的最近鄰數k值的變化而變化。這是因為GNMF 的精度主要依賴于其通過KNN 方法構建的拉普拉斯圖，且其圖構造與NMF 相互獨立的計算模式使得該特征的表現尤為明顯。而NMFAN 與NLMFAN 依賴的則是自適應選擇最近鄰后生成相似度矩陣的結果，即式（6）中包含基于相似度矩陣S的拉普拉斯矩LS陣 的項，該項即為受到λ影響的圖正則項。

4 結束語

在本文中，提出了一種自適應圖正則化的非負矩陣分解算法（NLMFAN）。

1）提出了一種新的具有低秩特性的自適應鄰域GNMF 模型，同時也設計了一種求解NLMFAN的高效求解算法；

2）NLMFAN 方法可以在低秩約束條件下同時執行局部結構學習和矩陣分解過程，即可以根據分解的結果自適應地學習局部流形結構，并重新構造合適的圖以保留精煉的局部結構；

3）傳統的基于圖的方法通常基于固定的數據圖對數據進行聚類，容易受到預先構造的不準確的圖的影響。NLMFAN 通過引入自適應鄰居（adaptive neighbors，ANs）正則項對迭代中的相似度矩陣進行修正，從而減少分配ANs 對數據點之間相似性帶來的改變。

然而在許多聚類應用中，數據中的噪聲是通過結構或組聚類來分布的，本文算法中并未考慮空間聯系。在未來的工作中，我們將把結構化稀疏性作為約束來提升NLMFAN 的性能。