流形學習與成對約束聯合正則化非負矩陣分解*

曹佳偉，錢鵬江

江南大學 數字媒體學院，江蘇 無錫214122

1 引言

聚類是機器學習和數據挖掘領域中最基本的研究課題之一，它的目標是將數據點劃分成不同的組份，并且相同組份中的樣本之間具有很高的相似度。迄今為止，大量的聚類算法已經被提出，例如K均值聚類（K-means clustering）[1]、層次聚類（hierarchical clustering）[2-3]、譜聚類（spectral clustering）[4-5]、多視角聚類（multi-view clustering）[6-7]等。

最近，非負矩陣分解（nonnegative matrix factorization，NMF）[8]作為一種具有良好性能的松弛技術，其在聚類任務中已經得到了廣泛的應用。現有的NMF算法大多是無監督的[9-15]，即它不使用數據標簽或成對約束等監督信息。在許多實際問題中，很難獲得數據集的全局監督信息，但局部監督信息相對容易獲得，而有限的監督信息有助于提高機器學習算法的識別能力[16-18]。因此，將NMF擴展為一種半監督的算法將具有很大的實際應用價值。同時，利用流形學習方法來挖掘未標記數據中所蘊含的大量可用信息也是一種有效手段來提高算法模型的性能[13-15，18-19]。圖正則化非負矩陣分解（graph regularized NMF，GNMF）[14]既考慮了原始實例空間中數據點的線性關系，也考慮了它們之間的非線性關系，因此它比普通的NMF具有更強的鑒別性。值得注意的是，標準的NMF 采用了相對于噪聲和離群值不穩定的最小二乘誤差函數，導致一些噪聲特征或誤差較大的離群值將主導目標函數。因此，需要一個更健壯的NMF 來解決噪聲或異常值的問題。魯棒的流形非負矩陣分解（robust manifold NMF，RMNMF）[15]使用了一種基于結構化稀疏范數的魯棒公式，使其對數據中的噪聲和離群值不敏感。

為了拓展關于半監督非負矩陣分解方法的研究，本文提出了一種流形學習與成對約束聯合正則化非負矩陣分解聚類方法（nonnegative matrix factorizationbased clustering using joint regularization of manifold learning and pairwise constraints，NMF-JRMLPC），將成對約束引入到流形正則化框架中，從而能夠高效地利用已知的監督信息；同時使用基于l2,1范數的損失函數來提升模型的魯棒性。與Frobenius 范數相比，l2,1范數同時保持了每個數據向量的特征旋轉不變性和最小化數據向量中的離群值影響，使得本文的目標函數比原始函數更為魯棒。

2 相關工作

首先簡單回顧一下非負矩陣分解[8]。給定一個輸入數據矩陣X=[x1,x2,…,xn]∈?p×n，其中p是數據維度，n是樣本數量。NMF 的目標是將矩陣X分解為兩個非負矩陣F∈?p×k和G∈?n×k的乘積，使得它們的乘積是原始矩陣的一個很好的近似。為了得到兩個非負的低秩矩陣，可以優化以下目標函數：

矩陣F的每一列可以被看作是一個位于新的表示空間中的基向量，而矩陣G中的每一行包含了一組F中列向量的線性組合系數。利用矩陣F的列向量與矩陣G的第i個行向量的線性組合來近似矩陣X的第i個列向量。實際上，矩陣G的第i個行向量是原始高維數據xi的低維表示，且新的表示空間的維度k遠遠小于原始空間的維度p。于是，高維向量就被低維坐標空間中的低維向量所表示。通過這個步驟可以去除原始數據中大量的冗余信息，從而提取出原始數據中的底層結構。與其他降維方法如主成分分析（principal component analysis，PCA）相比，NMF 分解后的矩陣因子不允許包含負值項，且只允許基向量在新的表示空間中的非負組合，這就是為什么NMF可以被視為一種基于部分的表示方法。

當使用NMF 進行聚類時，可以將k值設為數據的簇個數。具體來說，假設數據集由k個簇組成，則每個數據點可以屬于這k個簇中的一個或多個。因此，NMF也可以看作是一種軟聚類方法，即每個樣本點的簇隸屬度可以由G相應的行向量確定。更具體地說，檢查G的每一行，如果k=，就將樣本點xi分配給簇k。因此得到的矩陣G是數據的簇隸屬度矩陣，從而也就得到了數據集的劃分。

3 流形學習與成對約束聯合正則化非負矩陣分解聚類方法

3.1 目標函數

給定數據矩陣X=[x1,x2,…,xn]∈?p×n，令G=[g1;g2;…;gn]∈?n×k是簇隸屬度矩陣，其中n為樣本個數，k為簇的個數。由于在許多現實問題中存在一小部分可用先驗知識，例如樣本之間的must-link 和cannot-link成對約束。于是，假設MS和CS分別表示必須關聯集（must-link set）和不可能關聯集（cannotlink set），它們來自給定的成對約束信息。用|?|表示MS 或CS 中的條目數量。于是，結合流形學習方法與成對約束監督信息，得到如下目標函數：

其中，邊權值Wij表示樣本之間的相似性；圖拉普拉斯矩陣定義為L=D-W，D是對角度矩陣，且Dii=表示MS 中的任意條目，并且c、d是X中各自數據的索引值；同樣的，表示CS中的任意條目，p和q是相應的數據索引值，c,d,p,q∈[1,n]。λ1和λ2是用來控制NMF 目標函數中三個部分比例的正則化系數。

事實上，任意兩個樣本xc和的類標簽應該相同，因此xc和xd的理想的聚類結果分別為gc和gd中最大元素的索引值。于是，通過最小化||gc-gd||2得到這樣一個條件。同樣的，對于任意兩個樣本xp和的類標簽應該不同，這就等價于最小化-||gp-gq||2，即。鑒于MS 和CS 之間的潛在數量級差距，這里采用了和的平均值。

顯然，式（2）的形式不利于對問題的解決。這里定義一個矩陣Qn×n：

然后，根據譜聚類的思想[4]可以將目標函數簡化為如下形式：

其中，Z=H-Q，Hii=∑jQij。并且，這里的Q、H和Z的角色分別類似于上述的W、D和L。

進一步將式（4）重寫為如下：

其中，λ=λ1且β=。

在式（5）中，參數β權衡了成對約束對圖拉普拉斯的總體影響。但是，觀察到參數β的數值范圍常常難以估計，尤其是在tr(GTLG)和tr(GTZG)數量級不同時候。于是，需要如下定理來解決此問題。

定理1假設M是n×n維的對稱矩陣，G是n×k維的嵌入矩陣，對于tr(GTMG)的范圍先前是不確定的，通過使用轉換M′=，可得0≤tr(GTM′G)≤1。其中λmin_M和λmax_M分別為M的最小和最大特征值，I為單位陣。

證明根據比例割（ratio cut）[4，20]、瑞利熵（Rayleigh quotient）[21-22]和極大極小值理論（min-max theorem）[23]可得如下不等式：

由此定理1得證。 □

因為L和Z都是對稱的，基于上述理論有：

其中，λmin_L和λmax_L分別是L的最小和最大特征值，λmin_Z和λmax_Z分別是Z的最小和最大特征值，因此tr(GTL′G)和tr(GTZ′G)有相同的值域。

至此，就能夠得到如下流形與成對約束聯合正則化NMF框架：

不同于tr(GTLG)與tr(GTZG)，tr(GTL′G)與tr(GTZ′G)的數量級是一致的。因此，使用一個簡單的權衡系數τ∈[0,1)在任何數據場景中自適應地控制它們各自的影響。

最后，為了提升算法的魯棒性，將損失函數中的Frobenius 范數替換為l2,1范數，就得到了NMFJRMLPC算法的目標函數：

這里增加了一個額外的正交約束GTG=I，并且松弛了F的非負約束。其中，加入正交約束的主要目的有兩個：第一個目的是為了保證解的唯一性。假設F*和G*是式（11）的解，那么對于任意給定的常數c＞1，無論F*和G*是局部最優解還是全局最優解，將cF*和G*/c代入目標函數中會使第一項中得到的值不變，而第二項中會得到較低的值。為了解決這個問題，文獻[14]在算法收斂后通過標準化F的列來作為補救措施。因此，有必要通過引入正交約束來避免這樣一個特別的步驟。第二個目的是降低算法的計算成本，稍后將對此進行詳細說明。另外，松弛F的非負約束能夠讓算法處理具有混合符號的輸入數據矩陣[15]。

3.2 算法優化

注意，上述目標函數中存在F和G兩個變量。使用增廣拉格朗日乘子法（augmented Lagrangian multiplier，ALM）來對本文的算法進行優化。在此，首先引入兩個輔助變量E=X-FGT和H=G，并且令S=(1-τ)L′+τZ′。然后重寫目標函數：

這里的μ、Λ和Σ都為ALM 框架中的參數；μ是決定不可行性懲罰的規范化系數；Λ和Σ都是用來懲罰目標變量和輔助變量之間的差距；并且μ是標量，Λ和Σ是兩個n×k維的矩陣。下面通過迭代優化的方法來更新每一個變量。

（1）更新E

固定F、H和G，目標函數變為：

這里需要定理2來解決式（13），這個定理也在文獻[24]中作為命題1 被提出。由于篇幅問題，不再對其進行詳細的證明。

定理2給定一個矩陣W=[w1,w2,…,wn]∈?m×n和一個正標量λ，則X*是式（14）的最優解。

并且X*的第i列為：

因此，式（13）可以寫成如下形式：

于是，根據定理2可以得到式（13）的解為：

其中，yi是Y的列。

（2）更新F

固定E、H和G，目標函數變為：

由于GTG=I，得到F的解為：

若不加入正交約束，則目標函數變為：

令上式關于F的一階導數為0，則F的最優解可由下式得到：

于是，可以得到：

這就意味著除了保證解的唯一性外，有必要對G施加正交約束，否則求解F就需要對大尺寸矩陣進行求逆運算。顯然，加入正交約束能夠大大降低計算成本。這是加入正交約束的第二個目的。

（3）更新H

固定F、E和G，目標函數變為：

展開式（25）并舍棄與H無關的項得：

化簡式（26）得：

可得H的解為：

（4）更新G

固定F、E和H，目標函數變為：

和上一部分優化H的過程相似，令：

可將式（30）寫為如下形式：

顯然，式（32）等價于如下式子：

則G的最優解為：

其中，U和V是對N進行奇異值分解之后的左右奇異向量組成的矩陣。詳細證明過程可見文獻[25]中的理論1。

（5）更新μ、Σ和Λ

更新完F、E、H和G四個變量之后，還需要對ALM框架中的參數進行更新：

其中，ρ＞1是用來控制收斂速度的。ρ越大，收斂所需的迭代次數就越少，但與此同時會降低算法的精度。

NMF-JRMLPC算法步驟如下：

輸入：數據矩陣X，類別數k、μ、λ、τ，部分有標記樣本信息。

輸出：簇隸屬度矩陣G。

（1）初始化F和G，并根據式（8）和式（9）分別計算L′和Z′。

（2）根據式（17）和式（18）計算E。

（3）根據式（20）和式（21）計算F。

（4）根據式（28）和式（29）計算H。

（5）根據式（31）和式（34）計算G。

（6）根據式（35）、式（36）和式（37）分別計算Λ、Σ和μ。

重復步驟（2）至（5），直到算法收斂。

3.3 算法收斂性分析

在上一部分對本文方法進行了總結。注意到：隨著迭代次數的增加，μ以指數級開始增長；同時，式（12）中的目標函數逐漸地收斂為式（11）中的原始目標函數。這是因為當μ變為無窮大時，為了保持目標函數值是有限的，則式（12）中的第三項和第四項必須為0。因此，只要給定充足的迭代次數，就能夠保證本文算法的收斂性。并且，本文算法的收斂依賴于ALM 框架的收斂。在文獻[26]中，已經證明和討論了ALM框架的收斂性。還有需要注意的一點是，由于式（12）是非凸的，通過對式（12）的迭代優化得到的解不是全局最優解，而是一個局部最優解。但是，由于標準正交約束，它也是一個唯一解。該解漸近收斂于式（11）對應的解，因此式（11）的解也是局部唯一解。

4 實驗結果分析

本章在5 個圖像數據集和3 個UCI 數據集上，將本文的NMF-JRMLPC 算法和K-means、PCA、NMF、GNMF 和RMNMF 進行比較，從而評價本文算法的性能。表1總結了實驗中用到的數據集的參數信息。

Table 1 Description of datasets表1 數據集描述

選取AT&T人臉數據集中第5到第8個文件夾中的圖像數據，其中各類樣本數量為10 張并統一尺寸為28×23，如圖1所示。之后，在這些人臉圖像中隨機加入7×7 的遮擋區域來模擬真實世界的噪聲數據，如圖2所示。將本文的基于l2,1范數的NMF聚類模型與傳統的基于l2范數的NMF聚類模型應用于這些有遮擋圖像中，并比較聚類結果。為了進一步驗證本文算法模型對有噪聲干擾圖像的識別效果，在這些人臉圖像中隨機加入椒鹽噪聲，加噪之后的圖像數據如圖3所示。

Fig.1 Original AT&T face image data圖1 原始的AT&T人臉圖像數據

4.1 參數設置

Fig.2 Occluded AT&T face image data圖2 有遮擋的AT&T人臉圖像數據

Fig.3 AT&T face image data with salt&pepper noise圖3 加入椒鹽噪聲的AT&T人臉圖像數據

對于圖正則化的矩陣分解算法（即GNMF、RMNMF），使用0-1 權重的數據圖，并且根據原文獻設置近鄰數尋優區間在{1,2,…,10}之間，正則化參數的尋優區間在{0.1,1,…,1 000}之間。由于K-means算法、PCA 算法和NMF 算法沒有任何參數可以進行選擇，因此只需給定聚類的簇個數即可。對于NMFJRMLPC 算法，初始化Γ,Σ∈0n×p，μ=0.001，ρ=1.05。然后設置正則化參數的尋優區間在{0.001,0.01,0.1,1,10,100}之間，近鄰數尋優區間在{1,2,…,10}之間。對于所有的數據集，都隨機采樣10%的樣本點來構造成對約束矩陣。最后，在每個數據集上運行所有算法20次，并記錄結果進行比較。

4.2 在實驗數據集上的聚類結果分析

使用歸一化互信息（normalized mutual information，NMI）[27]和芮氏指標（Rand index）[28]作為聚類結果的評價指標。兩種評價指標的取值范圍均為[0，1]，值越大表明算法的聚類性能越好。6 種算法在本文的實驗數據集上的聚類結果對比如表2所示。從表2中可以看出，本文算法的聚類性能在多數數據集中都優于其他5 個對比算法。這就意味著本文算法結合有效利用成對約束信息和充分學習樣本結構信息這兩方面的正確性和有效性。特別需要注意的是，AR和PIE這兩個數據集中的圖像中都包含著大量遮擋區域和不同光照引起的干擾，而從結果中可以看出：本文的NMF-JRMLPC 算法相對其他算法都表現出了較大的性能優勢。這就證明了基于l2,1范數的目標函數對噪聲和干擾所具有的魯棒性。此外，表3中對有遮擋圖像的聚類結果更進一步地說明了這一點。

Table 2 Clustering results of 6 algorithms表2 6種算法聚類結果

圖4展示了NMF-JRMLPC算法在加入椒鹽噪聲的AT&T圖像數據上的聚類結果。如圖4可見，本文算法將所有圖像分成的4 個簇中都包含著相同類別的圖像。因此，進一步證明了本文的算法不易受噪聲數據的干擾。

Table 3 Clustering results on occluded images表3 在遮擋圖像上的聚類結果

Fig.4 Clustering results of NMF-JRMLPC on noise image圖4 NMF-JRMLPC算法在噪聲圖像上的聚類結果

4.3 權衡系數τ 的影響分析

本節研究了成對約束項與流行正則化項的權衡系數對聚類精度的影響。如前所述，本文算法通過使用一個在固定區間[ 0,1) 內變的權衡因子τ來控制成對約束對圖拉普拉斯的影響程度。圖5 展示了當固定其他參數時，τ從0.1到0.9之間的變化對聚類結果產生的影響。從圖5 中可以看出：AR、AT&T、PIE和Heart 數據集對權衡系數τ存在著一定的魯棒性，它們的聚類結果隨著權衡系數的變化表現得較為穩定；而在JAFFE、Yale、Dermatology 和Balance 數據集中，聚類精度隨著權衡系數的變化而不斷波動，這就體現了成對約束對圖拉普拉斯矩陣的調節作用。因為很難得到對數據流形的無偏估計，并且從給定的數據標簽轉換而來的成對約束通常具有較高的置信度，于是這種類型的調節就起到了一種校正的作用。通過這種靈活的參數調整，能夠進一步提升半監督學習模型的性能。

Fig.5 Clustering results with varyingτ values圖5 不同τ 值的聚類結果

5 結束語

本文通過樣本中包含的少量成對約束信息來構造成對約束矩陣，并結合流形學習的知識，提出了流形學習與成對約束聯合正則化非負矩陣分解聚類方法（NMF-JRMLPC）。本文的目的是通過有效利用實際應用中存在的有限監督信息和充分探索樣本中的結構信息來提升NMF算法的聚類準確性；同時，使用基于l2,1范數的損失函數來減少數據中噪聲的影響程度并保持數據向量的特征旋轉不變性。另外，本文提出的流形與成對約束聯合正則化框架不只是流形與成對約束正則化的簡單組合，它還利用了成對約束對圖拉普拉斯的隱式調節，從而能夠促進對真實數據流形的無偏差近似。