曹佳偉，錢鵬江

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫214122

1 引言

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

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

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

2 相關(guān)工作

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

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

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

3 流形學(xué)習(xí)與成對約束聯(lián)合正則化非負(fù)矩陣分解聚類方法

3.1 目標(biāo)函數(shù)

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

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

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

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

然后，根據(jù)譜聚類的思想[4]可以將目標(biāo)函數(shù)簡化為如下形式：

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

進(jìn)一步將式（4）重寫為如下：

其中，λ=λ1且β=。

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

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

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

由此定理1得證。 □

因?yàn)長和Z都是對稱的，基于上述理論有：

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

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

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

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

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

3.2 算法優(yōu)化

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

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

（1）更新E

固定F、H和G，目標(biāo)函數(shù)變?yōu)椋?/p>

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

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

并且X*的第i列為：

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

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

其中，yi是Y的列。

（2）更新F

固定E、H和G，目標(biāo)函數(shù)變?yōu)椋?/p>

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

若不加入正交約束，則目標(biāo)函數(shù)變?yōu)椋?/p>

令上式關(guān)于F的一階導(dǎo)數(shù)為0，則F的最優(yōu)解可由下式得到：

于是，可以得到：

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

（3）更新H

固定F、E和G，目標(biāo)函數(shù)變?yōu)椋?/p>

展開式（25）并舍棄與H無關(guān)的項(xiàng)得：

化簡式（26）得：

可得H的解為：

（4）更新G

固定F、E和H，目標(biāo)函數(shù)變?yōu)椋?/p>

和上一部分優(yōu)化H的過程相似，令：

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

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

則G的最優(yōu)解為：

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

（5）更新μ、Σ和Λ

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

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

NMF-JRMLPC算法步驟如下：

輸入：數(shù)據(jù)矩陣X，類別數(shù)k、μ、λ、τ，部分有標(biāo)記樣本信息。

輸出：簇隸屬度矩陣G。

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

（2）根據(jù)式（17）和式（18）計(jì)算E。

（3）根據(jù)式（20）和式（21）計(jì)算F。

（4）根據(jù)式（28）和式（29）計(jì)算H。

（5）根據(jù)式（31）和式（34）計(jì)算G。

（6）根據(jù)式（35）、式（36）和式（37）分別計(jì)算Λ、Σ和μ。

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

3.3 算法收斂性分析

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

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

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

Table 1 Description of datasets表1 數(shù)據(jù)集描述

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

Fig.1 Original AT&T face image data圖1 原始的AT&T人臉圖像數(shù)據(jù)

4.1 參數(shù)設(shè)置

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

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

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

4.2 在實(shí)驗(yàn)數(shù)據(jù)集上的聚類結(jié)果分析

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

Table 2 Clustering results of 6 algorithms表2 6種算法聚類結(jié)果

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

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

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

4.3 權(quán)衡系數(shù)τ 的影響分析

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

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

5 結(jié)束語

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