余沁茹，盧桂馥，李華

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

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

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

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

1 相關(guān)工作

1.1 非負(fù)矩陣分解（NMF）

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

即標(biāo)準(zhǔn)NMF 的目標(biāo)是搜索兩個非負(fù)矩陣U和V以優(yōu)化以下目標(biāo)

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

1.2 圖正則化非負(fù)矩陣分解（GNMF）

為了能在NMF 算法中保留其內(nèi)在結(jié)構(gòu)的同時探索數(shù)據(jù)的局部幾何結(jié)構(gòu)，近幾年將流形學(xué)習(xí)與NMF 相結(jié)合的算法研究成為熱點。Cai 等[13]通過將圖正則化項融入到標(biāo)準(zhǔn)NMF 算法框架中提出了圖正則化非負(fù)矩陣分解(GNMF)，其目標(biāo)函數(shù)如下：

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

2 自適應(yīng)低秩非負(fù)矩陣分解算法

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

2.1 NLMFAN 的算法模型

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

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

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

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

結(jié)合式（7）和（8）可得目標(biāo)函數(shù)中的第2 項，即自適應(yīng)正則項為

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

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

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

2.2 NLMFAN 的算法求解

設(shè)計了一種有效的更新算法來求解NLMFAN，該算法通過固定其他變量迭代更新一個變量的值來優(yōu)化目標(biāo)，此過程重復(fù)直到收斂。

2.2.1 固定U、V更新S

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

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

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

根據(jù)KKT 條件[23]，滿足sij≥0，最優(yōu)解可以定義為

結(jié)合式（17）和（18），可以得到：

為了獲得具有k個非零值的最優(yōu)si，可以將γi設(shè)置為

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

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

2.2.2 固定S、V更新U

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

在優(yōu)先求解L時，求解式（22）可轉(zhuǎn)換為先求解式（23）再求解U的過程：

將式（23）可拆兩個子問題來解決。當(dāng)固定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。在此基礎(chǔ)上，對式（28）求解：

可以看出式（28）為式（1）中的標(biāo)準(zhǔn)NMF式。因此，對于等式中的U，我們有式（3）中完全相同的迭代更新規(guī)則：

2.2.3 固定S、U更新V

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

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

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

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

則式（35）遵從如下迭代規(guī)則：

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

算法1自適應(yīng)圖正則化的低秩非負(fù)矩陣分解算法

2.3 NLMFAN 算法收斂性分析

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

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

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

3 現(xiàn)實數(shù)據(jù)集實驗評估

3.1 實驗數(shù)據(jù)集

為了評估本文提出方法的性能，我們在實際基準(zhǔn)數(shù)據(jù)集進行了實驗。

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

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

表1 數(shù)據(jù)集及特征Table1 Description of data sets

3.2 實驗步驟

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

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

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

3.3 CLUTO 數(shù)據(jù)集實驗

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

表2 各算法在CLUTO 數(shù)據(jù)集上聚類結(jié)果比較Table2 ACC and NMI of clustering on CLUTO database %

從表2 中可以看出： NMF 相關(guān)算法的聚類結(jié)果還是優(yōu)于傳統(tǒng)聚類方法。同時，在NMF 算法中，NLMFAN 算法顯示出了優(yōu)于其他幾種方法的聚類效果。尤其是與改進前的NMFAN 算法相比，NLMFAN 算法在每個數(shù)據(jù)集上的精度及平均精度均有所提高。

圖1 展現(xiàn)了在CLUTO 的4個數(shù)據(jù)集上NLMFAN算法的收斂情況。圖中目標(biāo)函數(shù)值即最小誤差值。可以看出，本文方法在數(shù)據(jù)集上均可快速收斂，迭代次數(shù)均在50 次內(nèi)。

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

3.4 UCI 數(shù)據(jù)集實驗

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

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

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

表3 各算法在UCI 數(shù)據(jù)集上聚類結(jié)果比較Table3 ACC and NMI of clustering on UCI database %

3.5 參數(shù)選擇實驗

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

從圖3 可以看出：

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

1）除了NMF以外，GNMF、NMFAN、NLMFAN都受到λ值的影響。總體來說，當(dāng)λ的值取在10 以內(nèi)時NLMFAN 可以獲得較好的聚類結(jié)果，當(dāng)λ取到10 時可以獲得所有算法平均最優(yōu)結(jié)果。

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

4 結(jié)束語

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

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

2）NLMFAN 方法可以在低秩約束條件下同時執(zhí)行局部結(jié)構(gòu)學(xué)習(xí)和矩陣分解過程，即可以根據(jù)分解的結(jié)果自適應(yīng)地學(xué)習(xí)局部流形結(jié)構(gòu)，并重新構(gòu)造合適的圖以保留精煉的局部結(jié)構(gòu)；

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

然而在許多聚類應(yīng)用中，數(shù)據(jù)中的噪聲是通過結(jié)構(gòu)或組聚類來分布的，本文算法中并未考慮空間聯(lián)系。在未來的工作中，我們將把結(jié)構(gòu)化稀疏性作為約束來提升NLMFAN 的性能。