基于多視角自適應圖正則的非負矩陣分解聚類

林虹燕, 杜元花, 周 楠, 田永強

(1.成都信息工程大學應用數學學院,四川 成都 610225;2. 成都大學電子信息與電氣工程學院,四川 成都 610106;3.華為科技有限公司,云南 昆明 650011)

0 引言

多視角學習在近年成為機器學習的熱門話題之一,在圖像處理、衛星通信、模式識別等領域有廣泛應用。 多視角學習能夠整合多視角數據的互補性和異構性,并將其重構為一個共識表達,在越來越多的領域受到歡迎。

隨著多視角數據在實際應用中的日益增多,提出了多種多視角聚類方法[1-4]。 Nie 等[5]通過探索拉普拉斯秩約束圖來構建多視角聚類,可近似地為每個具有不同置信度的視角構建共識親和圖。 Zhan 等[6]提出一種多視圖一致性聚類方法,通過學習一致性圖,直接獲得聚類標簽,并且無需進行任何后處理。 Wen等[7]提出一種簡單有效的不完備多視角聚類框架,該框架同時考慮了這些不完備多視角觀測的局部幾何信息并具備不平衡的判別能力。 Luo 等[8]提出一種多視角雙聚類方法,該方法在統一的框架中同時探索共識表達和雙聚類結構。 Liu 等[9]提出一種基于潛在表示空間近鄰學習的新型多視角聚類方法。 其中,多視角非負矩陣分解通過對多個視角數據進行矩陣分解達到原數據矩陣的低秩逼近,從而可以發現每個視角的內在結構表達成一個基,并將互補信息融合成一個低維空間的共識表達。 上述大多數方法只重視原始空間數據的一致性,忽略了各個視角的獨特性,得不到滿意的數據表達。 同時,低維空間的數據表達跟聚類結果也有很強的聯系,共識表達可以展現數據的內在結構,另一個矩陣則為低維空間的系數表達矩陣。 因此,在數據表達的同時可以對數據進行聚類。 最后,通過對拉普拉斯圖進行秩約(constraint Laplacian rank,CLR)[10]來構造多視角圖,該多視角圖能很好地學習到數據內在結構。 受到該思想的啟發,本文提出一種多視角自適應圖非負矩陣分解(multi-view adaptive graph nonnegative matrix factorization, MAGNMF)的聚類方法。該方將多個視角共識圖嵌入框架[11]與非負矩陣分解特征學習相結合,不僅考慮了多視角數據的全局重構信息,也考慮了多視角的局部結構信息,以此達到數據表達和聚類的效果。 本文主要貢獻如下:

(1)提出了一種結合非負矩陣分解、CLR 和圖嵌入的多視角特征學習聚類方法,使低維表達既能保持高維數據的內在局部結構信息,也能提取出多個視角的全局重構信息;

(2)提出了一個基于快速塊坐標更新(block coordinate update, BCU)[12]迭代更新算法來求解所提出的優化模型;

(3)通過在4 個真實數據集上進行大量驗證,結果表明本文所提出的多視角數據表達聚類方法MAGNMF 在多數情況下優于現有的方法。

1 相關工作

1.1 符號

本文用到的符號如表1 所示。

表1 符號

1.2 拉普拉斯秩約束算法

現有的多視角聚類方法多基于多圖聚類,如協同訓練[13],多視角譜聚類[14]等。 這些方法都是在固定輸入的數據圖上進行聚類,如果輸入的圖質量較差,則聚類結果也較差,其次需要進行后處理才能完成聚類。拉普拉斯秩約束定理通過限制拉普拉斯矩陣秩的個數(n-k)來約束數據的相似圖的連通分量個數(k),給定親和矩陣A,尋找相似矩陣S。 通過數據的原始親和矩陣A,可以學習到相似矩陣S以及相應的拉普拉斯矩陣L=D-(ST+S)/2,它的秩為n-k,其中對角矩陣D的第i個元素為Σj(sij+sji)/2。 在這個限制之下,學習到的S是有合適排列的塊對角矩陣,這樣就可以直接將數據點劃分到k簇。 其模型表示為

1.3 圖正則化的非負矩陣分解算法

現實中的數據基本都是高維的,非負矩陣分解(nonnegative matrix factorization, NMF)[15]是將高維空間的數據矩陣近似表達成兩個低維矩陣,U是基矩陣,F是低維表達矩陣。X是數據矩陣,其中X每一列表示一個樣本點,每一行表示一個特征。

為了尋找一個高質量的近似,可以將NMF 的目標函數變成以下優化問題:

這樣NMF 就可以學到局部表達。 為更好地學習數據空間的內部幾何和判別結構,同時維持高維數據在低維空間的流型結構,避免過擬合,加入了圖正則項。 于是,圖正則化的非負矩陣分解[16]模型表示如下:

其中U≥0,F≥0 表示矩陣U與F中所有元素都是非負的,正則項參數λ≥0,用于控制低維表達對于高維數據局部結構的保持性,L=D-(ST+S)/2 為圖拉普拉斯矩陣,其中S為數據矩陣的相似矩陣。 將圖正則項與原始非負矩陣分解結合被稱為圖正則化非的負矩陣分解。

2 自適應圖正則的非負矩陣分解

本文提出一種新的多視角自適應圖非負矩陣分解模型。 根據拉普拉斯秩約束需要找到共識的拉普拉斯約束圖,該圖可以近似地作為每個視角的相似度圖的質心。 圖非負矩陣分解將數據從嵌入的高維環境空間中的低維流形中采樣,得到在低維空間的表達。 本文模型還加入了懲罰項以防止平凡解的出現。

給定一個多視角數據集X= [X(1),X(2),…,X(m)],本文模型目標是找到共識相似矩陣S,共識低維表達矩陣F和每個視角的基矩陣U(v)。 因此,目標函數被表示成:

這里,λ>0 是CLR 和圖正則項的平衡系數。 限制S、F、U(v)為非負矩陣,且S與F的每一行和為1,有效地避免了平凡解和減小計算復雜度。 最后,將K-means算法[17]應用到共低維表達矩陣,得到聚類結果。

3 求解算法

3.1 加速BCU 迭代方法

本文采用加速BCU 策略來推導模型(5)的求解算法。 在每次迭代中,更新目標函數的一個變量,將其他兩個變量固定在其最近更新的值。 具體來說,每個變量通過迭代地執行以下的表達式來進行更新。

其中和分別是?Sf(·)和?Ff(·)的利普希茨(Lipchitz)常數,并且插值點

這里,?[0,1)分別為插值點和的權重,文獻[18-19]認為,通過該插值的辦法可以明顯提高BCU的求解效率。

3.2 更新S

消除式(5)中與S無關的項,式(6)可以被重新表示為

式(13)按照列可以分解為n個相互獨立的子問題:

如此,這個問題就變成了單純形上的投影。 根據文獻[20]中的方法可以將式(14)很好地求解,其求解方法如下。

算法1 單純形上的投影:s=Proj-Sim(c)

第1 步 按上升順序排列c形如c(1)≤…≤c(p),令i=p-1;

第4 步 將c的投影s=(c-)+投到Δp上。

3.3 更新F

與S子問題求解方法類似,令D=?Ff(Sk+1,,(U(v))k)且L2=,于是式(7)可以表示成

消除式(5)中與F無關的項,式(7)可以被重新表示為

最后,式(7)等價于:

式(17)也可以通過算法1 來求解。

3.4 更新U(v)

由于式(8)具有閉形式解,且在每個視角中都是獨立的,因此可以將這個問題的每個視角分開處理。先求出關于U(v)式子的梯度,去除目標函數式(5)中與U(v)無關的項,得到:

(i)令f1=‖X(v)-U(v)FT‖2F

=Tr((X(v)-U(v)FT)T(X(v)-U(v)FT))

=Tr((X(v))TX(v)-(X(v))TU(v)FT

F(U(v))TX(v)+F(U(v))TU(v)FT)

=Tr((X(v))TX(v)-2 (X(v))TU(v)FT+

F(U(v))TU(v)FT)

那么可以得到

結合(i)和(ii)得到

令梯度為零,于是得到

得到

因此U(v)的封閉解為

3.5 參數設置

算法共有5 個參數:輸入平滑參數λ?[10-3,103],以及前文提到的更新變量S和F以更新相應的利普希茨(Lipchitz)常數和和權重和。

3.5.1 推導

去除目標函數式(5)中與S無關的項,得到

其中fi是F的第i行。

(iii)令fv=‖S-A(v)‖2F=Tr((S-A(v))T(S-A(v)))

=Tr(STS-2STA(v)+(A(v))TA(v))

(iv)令Hij=‖fi-fj‖22,hi、si分別是H和S的第i行。

則任何和有

因此,Lipschitz 常數為

定義

3.5.2 推導

去除目標函數式(5)中與F無關的項,得到:

(v)令:f1=‖X(v)-U(v)FT‖2F

=Tr((X(v)-U(v)FT)T(X(v)-U(v)FT))

=Tr((X(v))TX(v)-(X(v))TU(v)FT

F(U(v))TX(v)+F(U(v))TU(v)FT)

=Tr((X(v))TX(v)-2 (X(v))TU(v)FT+

F(U(v))TU(v)FT)

那么可以得到

結合(v)和(vi)得到

則任何和有

因此,Lipschitz 常數為

定義

3.5.3 推導權重及

根據文獻[12]提到的辦法,定義插值權重如下:

這里δw<1,= (τt-1-1)/τt且

結合3.1 ～3.5,整體求解模型式(5)的算法如下:

算法2 多視角自適應圖非負矩陣分解(MAGNMF)

輸入:親和矩陣A={A(1),A(2),…,A(m)}?Rn×n,多視角非負矩陣

X={X(1),X(2),…,X(m)}?Rd×n,參數λ

輸出:共識相似矩陣S?Rn×n、每個視角的基矩陣

U(v)={U(1),U(2),…,U(m)}?Rd×c以及共識系數矩陣F?Rn×c;

步驟1 通過式(17) ～(20)計算、、和;

步驟2 令=Sk+(Sk-Sk-1);

步驟3 令=Fk+(Fk-Fk-1);

步驟4 利用算法1 求解式(11)更新Sk+1;

步驟5 利用算法1 求解式(13)更新Fk+1;

步驟6 通過式(16)更新(U(v))k+1;

步驟7 如果f(Sk+1,Fk+1,(U(v))k+1)≤f(Sk,Fk,(U(v))k),令=Sk,=Fk回到步驟(4);

步驟8 令k←k+1;

步驟9 重復步驟(1) ～(8)直至收斂。

3.6 收斂性分析

定理1算法2 的迭代更新策略可使式(5)中的目標函數值單調遞減,并收斂到最小值點。

為簡單起見,假設=0、=0,即不進行外推。=0、=0 的情況較復雜,但可以按文獻[12]類似地處理。

根據式(5),令

s.t.S≥0,si1n=1,F≥0,fi1n=1,U≥0 于是φ(S,F,U(v))≥0,因此函數目標值下界為0。 根據算法2 的更新策略,由文獻[15]可得:

同理可得:

于是

目標值的單調遞減。 又由于目標函數存在下界,于是算法2 的更新策略收斂到一個極小值點。

通過算法2 的更新規則,可使目標函數單調遞減并收斂到一個極小值點,完成證明。

圖1 展示了MAGNMF 算法在ORL 數據集上,不同迭代次數下的目標函數值。 由圖1 可知,隨著迭代次數的增加,目標函數值呈單調遞減趨勢,并最終達到收斂。

圖1 收斂曲線

4 實驗

將MAGNMF 算法與目前先進的算法在聚類效果上進行比較。 為保證算法比較的公平性,對于需要k近鄰構建親和矩陣的算法,統一將近鄰數k設置為5,運行算法得到的低維表達之后,再使用K-means 算法進行聚類得到聚類結果,其中K-means 算法直接得到結果。 全部的算法都在MATLAB R2018b 上進行。

4.1 數據集

實驗用到4 個數據集,其中包含1 個文本數據集和3 個圖像數據集。

BBC:該數據來源于BBC 新聞網頁,由685 個文件構成,每個文檔被分成4 個部分(4 個視角),包含5個類別的主題標簽。

COIL20:該數據集的圖片含有20 個類別,共有1440 張,這些圖片為32×32 的灰度照片并從3 個不同的角度描述了樣本。

Digit:該數據集由2000 張手寫數字圖片(0 ～9)組成,視角1 是76 個傅里葉系數,視角2 是240 像素的像素特征。

ORL:該數據集共400 張人臉圖片,由40 個不同人的人臉圖片構成,每個人有10 張圖片,每張圖片由4 個不同的特征描述。

4 個數據集的主要信息如表2 所示,其中di表示第i個視角數據的維度。

表2 數據集的主要信息統計

4.2 對比方法

選取8 種聚類算法來對比本文所提出的多視角聚類算法,各聚類算法如下。

K 均值聚類(K-means):通過迭代更新,將數據點分給相應的聚類中心。

共正則譜聚類(coregSC)[21]:在譜聚類框架下,通過共同規范聚類假設,使所有視角一致,最終得到聚類結果。

非負矩陣分解(NMF):通過基矩陣和系數矩陣近似表達原數據,得到低維空間的表達。

基于非負矩陣分解的多視角聚類(multiview nonnegative matrix factorization, MultiNMF)[21]:跨多個視角的NMF。

基于圖正則項的多視角聚類(graph nonnegative matrix factorization, GMNMF)[22]:通過有局部圖正則項的多視角NMF 進行特征提取,考慮了數據之間內部視圖的相關性。

自加權多視圖學習(auto-weighted multiple graph learning,AMGL)[23]:模型沒有額外的參數,能夠自動學習每個視圖的最優權值。

多圖自加權多視角聚類(self-weighted multiview clustering,SwMC)[24]:通過融合不同的權重圖來構造相似圖,然后利用相似圖構造一個具有明確塊對角結構的拉普拉斯圖。

基于一致相似度矩陣的圖非負矩陣分解(similarity graph nonnegative matrix factorization, SGNMF)[25]:通過多圖自加權多視角聚類學習相似度矩陣,來構造拉普拉斯圖正則項,最后將該正則項加入原始的非負矩陣分解模型中。

4.3 評價指標

采用精確度(ACC)[26]和歸一化互信息(NMI)[26]兩種指標來度量聚類性能。 指標數值越大,聚類性能越好,4 個真實數據集和ORL 數據集的不同視角組合的ACC 和NMI 如表3 ～5 所示,其中加粗的數值為最高數值,加下劃線的數值為次高數值。

表3 4 個數據集的ACC 實驗結果

4.4 多視角聚類實驗

將本文所提出的MAGNMF 算法和其他8 種對比算法在4 個真實數據集下的聚類效果(ACC、NMI)總結在表3 和表4。 通過觀察和對比實驗結果,得到如下結論:

表4 4 個數據集的NMI 實驗結果

K-means 和NMF 表現的效果不是很好,SwMC、MultiNMF、GMNMF、coregSC、AMGL 以及SCGNMF 等算法的效果不相上下,本文的MAGNMF 算法效果在大多數情況下優于所比較的其他算法。

在BBC、COIL20 和ORL 等數據集上,MAGNMF 算法對比其他算法效果有較大提升。 特別是在BBC 數據集上,對比排第二的算法,MAGNMF 在ACC 度量下提高了16.04%,在NMI 度量下提高了31.73%。 在ORL 數據集中,對比排第二的算法,MAGNMF 在ACC度量下提高了8.37%,在NMI 度量下提高了2.93%。

在Digit 數據集的實驗中,MAGNMF 方法在ACC度量下取得了第二好的聚類結果,僅與最好的方法差1.45%,在NMI 度量下取得了最高的聚類結果,優于第二好的結果1.32%。

從實驗結果來看,本文的算法效果相對于其他的算法在聚類上有一定的優越性,說明拉普拉斯秩約束的共識相似度矩陣學習和圖正則化的非負矩陣的結合,使MAGNMF 方法可以讓原始空間的數據在低維空間中更好地保持原始數據的全局重構信息與局部結構信息,使低維表達更具有判別性,從而提升樣本的聚類精度。

4.5 多視角聚類有效性驗證

為驗證本文所提出的MAGNMF 算法在多視角聚類問題的有效性,在ORL 數據集的不同視角組合上進行實驗,表5 展示了不同視角組合下,采用MAGNMF算法在ACC 和NMI 度量下的聚類結果。 實驗結果表明,完整的多視角數據集比單視角或者不完整視角數據集的聚類性能更好。

表5 ORL 數據集各視角在本方法的實驗結果

4.6 參數敏感性分析

算法中的λ是拉普拉斯秩算法和圖正則項的參數,它是促進所有視角一致性和權衡這兩部分的平滑度。 為使實驗具有公平性,將對比算法中所有實驗計算親和矩陣的近鄰值設置為K=5。 參數λ在集合{0.001,0.05,0.01,0.5,1,5,10,50,100,500,1000}中變動。 圖2 和圖3 中的4 條折線分別表示了4 個數據集在不同λ數值時對應ACC 和NMI 度量下的聚類結果。 由此可知,在4 個數據集上,聚類結果對于參數λ的變化并不敏感。

5 結束語

提出了一種新的基于多視角圖自適應非負矩陣分解(MAGNMF)方法來處理多視角數據的聚類問題。該方法的優點包括3 個方面:(1)利用CLR 和圖嵌入的結合,同時考慮了所有數據的一致性和每個視角之間的互補性,達到數據表達和聚類的效果;(2)該方法有且僅有一個參數需要調優;(3)一個有效的BCU 迭代更新算法被提出。 通過4 個現實數據集的實驗,結果表明,本文所提出的MAGNMF 方法在大部分情況下都優于目前的方法。