基于非負矩陣分解的均方殘差多視圖聚類算法

郝敬琪,胡立華,張素蘭,張繼福

(太原科技大學 計算機科學與技術學院,山西 太原 030024)

0 引 言

聚類分析作為機器學習的主要研究分支,是一種廣泛使用的無監督學習技術。在沒有使用任何先驗知識的條件下,按照對象間的相似程度,將不同的對象劃分為不同的簇,確保每個簇內的對象盡可能相似,而不同簇間的對象盡可能相異。目前,聚類分析已廣泛應用在科學數據分析[1]、商業[2]、生物學[3]、醫療診斷[4]、文本挖掘[5]等領域。

多視圖聚類(Multi-View Clustering,MVC)主要包括基于k-means的方法[6]、基于圖的方法[7]以及基于子空間的方法[8]等。相較單視圖聚類,多視圖聚類方法充分考慮到數據的多樣性和多面性,能夠處理異常值和噪聲,從而獲得更好的聚類性能,因此成為聚類分析中的研究熱點。然而,針對高維、海量的數據,現有的多視圖聚類方法中仍然存在以下問題:(1)多視圖數據集維度過高時,現有的多視圖聚類方法很難發現隱藏信息;(2)大多數多視圖方法融合過程僅考慮各單視圖內部的局部特征,無法平衡每個視圖的重要性。

針對上述問題,結合非負矩陣分解和均方差殘差思想,提出了一種基于非負矩陣分解的均方殘差多視圖聚類方法。該方法首先采用非負矩陣分解思想,在相關誤差矩陣中加入魯棒低秩約束,使系數矩陣的內部結構信息和誤差矩陣中一些有用的判別信息得到充分的挖掘,并解決維度過高無法發現隱藏信息的問題;其次利用均方殘差對每個視圖結構進行自適應融合,使不同視圖的結構在算法更新過程中得到融合和改變,從而平衡各單視圖之間的重要性。

論文的創新點包括:(1)設計了一種改進的非負矩陣分解方法,提高單視圖矩陣分解的魯棒性和稀疏性;(2)提出了一種自適應單視圖融合方法,改進了各單視圖之間融合的效果;(3)結合上述方法,提出了一種基于非負矩陣分解的均方殘差多視圖聚類方法;(4)采用標準數據集和古建筑圖像,驗證了算法的有效性。

1 相關工作

隨著信息技術的飛速發展,數據的規模出現海量、多源、異構、高維等特點。針對上述數據,傳統的單視圖聚類存在聚類效率低、聚類效果差等問題,而多視圖聚類方法可從不同角度分析數據,進而提高聚類效果,因此,受到了研究者的廣泛關注。

目前,多視圖聚類算法可分為三類:基于k-means的方法、基于圖的方法以及基于子空間的方法。

(1)基于k-means的方法:該方法首先對多視圖數據的各單視圖采用k-means聚類生成單視圖聚類結果,然后對各單視圖的聚類結果進行融合,最后得到最終聚類結果。典型方法有:2004年Bickel等人[9]提出了擴展的k-means的方法,處理具有兩個條件獨立視圖的情況。但是該方法只能處理兩個視圖的情況,無法處理三個或更多視圖的情況。為了解決三個或更多視圖聚類的問題,2016年Rai等人[10]將部分視圖聚類(PVC)算法擴展到k部分視圖場景。其次擴展了k部分視圖算法,包括將視圖拉普拉斯正則化。使得該算法能夠利用每個視圖中數據分布的內在幾何結構。2018年Zhang等人[11]提出了一種基于k-means的兩級加權融合多視圖聚類方法,有效解決了三個及以上視圖的情況,但沒有考慮各單視圖的結構和不同視圖的融合。

(2)基于圖的方法:該方法的核心思想是將多視圖聚類問題轉化為圖分割問題[12]并進行譜聚類操作。但是,該類算法也存在一些問題,圖譜聚類的最終結果完全依賴于構造的相似矩陣,然而不同的構造方法會影響聚類結果,因此構造理想的相似矩陣成為研究熱點[13]。近年來,許多學者對譜聚類算法中相似矩陣的構造方法做了進一步研究與改進。典型方法有:2000年Shi等人[7]通過高斯核函數構造相似矩陣。2001年Ng等人[14]提出NJW算法,通過高斯核函數構造相似矩陣,并采用全連接構造方法。2010年Zhang等人[15]利用兩個樣本點之間的局部密度求相似矩陣。2016年Nie等人[16]通過局部連通性為每個數據點分配自適應和最優鄰居來學習相似矩陣。2018年Xie等人[17]采用樣本點與樣本點的近鄰點之間的歐氏距離作為局部標準差構造相似矩陣。2018年Zhan等人[18]聯合優化圖矩陣,充分利用視圖之間的數據相關性進行多視圖聚類,并且可以處理任意數據集,即使它們包含負值。2020年Liang等人[19]構造每個視圖的鄰接圖來保持每個視圖的幾何信息,并推導出相應的基于交替迭代規則的乘法更新算法。然而這些文獻中構造的相似矩陣都是固定的,不能很好地挖掘和利用數據結構。

(3)基于子空間的方法:該方法試圖揭示多視圖共享的公共潛在子空間,子空間多視圖方法利用矩陣分解來設計。利用各種矩陣分解方法,可尋找出隱藏在原始數據中的低維結構,便解決了“維度魔咒”的問題。典型方法有:2016年Zhou等人[20]提出稀疏多視圖矩陣分解算法,旨在根據方差的視圖特異性對特性進行優先級排序。2017年Zhao等人[21]提出了一種通過圖正則化半非負矩陣分解的深度多視圖聚類算法,關鍵是通過半非負矩陣分解構建深層結構,以尋求具有一致知識的公共特征表示,從而促進聚類。2020年Chen等人[22]提出了一個統一的框架,聯合了學習潛在嵌入表示、相似信息和聚類指標矩陣。然而,上述方法應用到高維海量多視圖數據中,存在以下問題:利用非負矩陣分解的子空間聚類算法進行降維時,不僅會丟失數據的隱藏信息,而且降維維度的不確定性也導致了后序算法的不穩定性;并且大部分多視圖聚類算法沒有平衡每個視圖的重要性,僅僅考慮了各個視圖內部的局部特征,沒有考慮到視圖之間的聯系。

2 基礎知識

2.1 非負矩陣分解

給定矩陣X∈Rm×n,m為對象特征個數,n為對象數量,將其非負矩陣分解[23]為基矩陣U∈Rm×k和系數矩陣V∈Rk×n,k為分解維度,具體定義如下:

定義1(非負矩陣分解):給定一個矩陣X,其非負矩陣分解過程可描述為:

X≈UV

s.t.U≥0,V≥0

(1)

定義2(非負矩陣的誤差Ex):Ex為給定矩陣X與基矩陣系數矩陣乘積UV之間的誤差,Ex的計算公式如下:

s.t.U≥0,V≥0

(2)

其中,*表示點積。

2.2 流形正則化

流形正則化[24]是由Tenenbaum等人于2000年提出的一種方法,具體定義如下:

定義3(流形正則化O2):設Vi和Vj表示系數矩陣的第i列和第j列。利用F-范數計算列之間的偏差,以測量多視圖中的低維表示的平滑度。流行正則化過程定義為:

(3)

2.3 希爾伯特-施密特獨立性準則

希爾伯特-施密特獨立性準則(Hilbert-Schmidt Independence Criterion,HSIC)[25]是一種基于核的獨立性度量方法,具體定義如下:

定義4(HSIC的一般形式):給定n個樣本點和不同視圖V(s),V(w),則視圖V(s)和視圖V(w)的關聯性HSIC被定義為:

HSIC(Z,V(s),V(w))=

(n-1)2tr(K(s)HK(w)H)

(4)

其中,Z:={(x1,y1),(x2,y2),…,(xn,yn)}∈V(s)×V(w),hij=δij-1/n是中心矩陣,δij為n階單位陣,K(s)和K(w)是兩個內積矩陣。

3 文中算法

3.1 問題定義

基于圖正則化概念分解的多視圖聚類方法采用非負矩陣分解方法實現數據從高維到低維的映射表示,利用視圖之間的數據相關性進行多視圖聚類,從多視圖數據中學習親和圖,以解決視圖之間的相關性問題,同時避免利用單個圖構造親和圖。然而針對高維海量數據,該算法具有以下問題:(1)非負矩陣分解將矩陣X分解為基矩陣U和系數矩陣V的乘積,但是,此過程是近似分解,導致數據缺失從而增加矩陣分解的誤差;(2)使用低維系數矩陣V代替高維矩陣X進行多視圖聚類時,視圖內部潛在信息存在難以解釋的問題,使得低維數據不能完全映射高維數據;(3)現有的多視圖聚類算法不能充分挖掘視圖之間的差異性和互補性,導致了聚類結果不準確。

3.2 算法步驟

針對上述問題,提出了基于非負矩陣分解和均方殘差的多視圖聚類方法(MSRNMF)。首先,對多視圖數據中各單視圖矩陣進行改進后的非負矩陣分解,得到各單視圖的系數矩陣;其次,為了保持多視圖內部結構和視圖之間的聯系,使用流形正則化和HSIC以自適應的方式獲得潛在表示,得到改進后的系數矩陣;然后,對多視圖下各單視圖進行譜聚類;最后,依據各單視圖聚類結果,再結合均方殘差的思想對聚類結果進行融合,得到最終多視圖下聚類結果。算法流程如圖1所示。

圖1 算法流程

3.2.1 系數矩陣的改進

根據非負矩陣分解的特點,矩陣X(s)可以分解為U(s)和V(s)。非負矩陣分解是一種近似分解,為了減少分解過程中的誤差,很多算法常使用定義2最小化誤差矩陣。然而,Ex忽視了數據間的稀疏性和魯棒性,增加了矩陣的誤差。

針對上述問題,在誤差Ex中使用L21范數代替F-范數,以提高分解的稀疏性和魯棒性。為了充分利用數據的內在信息,添加了給定矩陣X和基矩陣U之間的誤差,即誤差矩陣Eu,并對其使用核范數。結合上述改進思想,提出了一種改進的非負矩陣誤差。具體的:

定義5(改進的非負矩陣誤差O1):

O1=‖Ex‖21+‖Eu‖*

(5)

s.t.Ex=X-UV,Eu=X-U,U≥0,V≥0

由于改進的非負矩陣分解沒有考慮視圖內部數據間結構特征的完整性,低維潛在表示存在難以解釋的問題,進而導致視圖內部聯系不緊密、結構不一致。為保證每個視圖內部的局部幾何結構,針對上述問題,利用流形正則化以保持矩陣內部結構的不變性。為了進一步加強不同視圖之間的相互學習和雙向融合,添加了HSIC模塊,以便于在模型優化過程中實現視圖之間的互連、相互學習和信息集成。

綜合改進的非負矩陣分解、流行正則化和HSIC三部分知識,更新系數矩陣V(s)的目標函數可由以下公式給出。

定義6(更新系數矩陣V(s)的目標函數):

(6)

式中有三個正則化參數,其中λ1用來測量稀疏表示的重要性,(α(s))γ和λs分別是平滑項和反向回歸項的權衡相關性。更新V(s)需固定變量U(s),Ex(s),Eu(s),(α(s))γ,則式6的優化問題轉化為:

(7)

其中,λ和μ是拉格朗日參數。將式7中關于V(s)的導數設為0。根據Karush-Kuhn-Tucker條件,可以寫成:

F1V(s)+V(s)F2=F3

F1=μ(U(s))TU(s)+λ,F2=α(s)L(s)+λs

(8)

3.2.2 多視圖聚類融合

對V(s)利用譜聚類算法得到各單視圖下的聚類結果C(s)。接著利用雙聚類的概念,計算具有高相似性分數即均方殘差得分的子集。通過向重復簇所在矩陣中添加非重復簇的方式,判斷添加后相似性是否提高。

定義7(均方殘差得分):對于矩陣C(s),假設X為一組行集,Y為一組列集,cij為矩陣C(s)第i行j列下的數據值,I∈X和J∈Y是行列的子集,子矩陣(I,J)具有均方殘差得分H(I,J):

(9)

計算各單視圖的聚類結果C(s)中重復簇的均方殘差得分H(I,J)并取均值,將其定義為XH。接著考慮是否將非重復簇添加到重復簇所在的矩陣中,計算添加后的均方殘差得分H(I,J)并取均值,將其定義為YH。若XH-YH<θ,則將此簇添加入重復簇中,如此迭代,則可得到最終結果。在后續實驗中得出θ=0.02效果最佳。

4 實驗結果與分析

4.1 環境設置

古建筑多視圖數據集構造方面采用Ubantu 18.04.6 LTS操作系統,intel Core i7-7800X處理器 (CPU@3.50 GHz×12),32 GB內存,選擇Python語言進行實驗。多視圖聚類算法采用Windows11操作系統,AMD處理器(CPU@3.25 GHz×8), 16 GB內存,選擇Matlab語言進行實驗。

4.2 數據集

為了驗證算法的效率,以5個標準的多視圖數據集和古建筑數據集為對象進行驗證。

4.2.1 標準數據集

(1)ORL數據集:包括40個不同主題的10個不同灰度人臉圖像。

(2)3-Sources數據集:涵蓋BBC、路透社和《衛報》報道3個在線新聞來源,包含416例病例。

(3)MSRCv1數據集:由7類210幅場景識別圖像組成。

(4)Yale數據集:由15個受試者的165張原始像素圖像組成。

(5)BBCSport 數據集:來自BBC體育網站的體育新聞文章的集合,包含282個報告的3個視圖的數據集。

4.2.2 古建筑數據集

古建筑數據集采用中科院金光寺數據集中的金光寺主建筑圖片進行實驗,如圖2所示。

圖2 金光寺圖片

對上述兩幅古建筑圖像進行多視圖數據集的構建,首先對每幅圖像選取11 320個特征點,其次提取特征點的位置、顏色、紋理、輪廓、領域和SIFT特征,即可構建一個高維海量的多視圖數據集。

4.3 評估指標

對于定量性能評估,使用以下7個眾所周知的評估標準。它們分別是聚類準確度(ACC):用于衡量聚類算法得到的聚類結果的準確率,取值范圍為0到1;歸一化信息(NMI):用于衡量兩個聚類簇中所包含的數據點之間的相似性,取值范圍為0到1;純度(purity):反映聚類結果中所有樣本中被正確聚類的樣本比例,取值范圍為0到1;精度(precision):表示預測為正確的數據中,真實值為正確的比例,取值范圍為0到1;召回率(recall):表示在所有的真實值為正確的數據中,預測正確的比例,取值范圍為0到1;F-score:將精度和召回率結合起來綜合評價分類或聚類結果的指標,取值范圍為0到1;調和蘭德指數(ARI):用于衡量聚類算法的聚類結果與真實類別之間的相似度的一種常用外部評價指標,取值范圍為-1到1。

4.4 實驗結果

4.4.1 標準數據集下的結果

將MSRNMF與部分多視圖聚類方法(GPMVNMF)[10]、多視圖聚類的自適應結構概念分解方法(MVCF)[18]、圖正則化部分共享非負矩陣分解方法(GPSNMF)[19]、基于深度矩陣分解的多視圖聚類方法(DMF)[21]、潛在嵌入空間中的多視圖聚類方法(MCLES)[22]進行比較,結果如表1～表5所示。

表1 ORL數據集實驗結果

表2 MSRCV1數據集實驗結果

表3 Yale數據集實驗結果

表4 3-Sources數據集實驗結果

表5 BBCSport數據集實驗結果

(1)針對圖像數據集ORL,MSRCv1和Yale,MSRNMF相較于MVCF,GPSNMF,GPMVC和MCLES在ACC與NMI兩個聚類指標上得到了顯著改進,較最優算法至少提升了0.1左右,MSRNMF與MCLES在ACC與NMI兩個聚類指標上相差不大;在purity,ARI,F-score,precision和recall上,MSRNMF不都是最優算法,但是相較GPMVNMF得到了明顯改進,至少提升了0.2。

(2)針對文本數據集3-Sources和BBCSport,MSRNMF相較于MVCF,GPSNMF,GPMVC,DMF和MCLES,在ACC上至少提升了0.2;相較于GPSNMF和MVCF,在NMI上得到了顯著改進,至少提升了0.1;在purity,ARI,F-score,precision和recall上,MSRNMF較最優算法最多相差0.2,MSRNMF較GPMVNMF得到了明顯改進,提升了0.3以上。

4.4.2 古建筑數據集下的結果

以金光寺為對象,聚類數選擇6和8,MSRNMF的結果如圖3和圖4所示。

圖3 聚類數為6時金光寺聚類結果圖

圖4 聚類數為8時金光寺聚類結果圖

從圖3和圖4可以看出,簇數為6,8時,MSRNMF對非負矩陣分解的目標函數添加L21范數和核范數,剔除了圖像噪聲,提高了古建筑多視圖聚類的魯棒性;結合MSR融合各單視圖聚類結果,進一步平衡了各單視圖的重要性,最終得到一個較好的聚類結果。

5 結束語

針對海量高維數據,現有多視圖聚類方法很難發現數據的隱藏信息,無法平衡每個視圖的重要性。針對上述問題,提出了一種基于非負矩陣分解和均方殘差的子空間多視圖譜聚類算法(MSRNMF)。該方法設計了一種改進的非負矩陣分解誤差,提高了矩陣分解的魯棒性和稀疏性;引入流形正則化和希爾伯特-施密特獨立性準則,加強了視圖內部和視圖之間信息的聯系和融合。以標準數據集和古建筑數據集為對象,MSRNMF與MVCF,GPSNMF,GPMVC,DMF和MCLES相比,在ACC與NMI兩個聚類指標上得到了顯著提升,MSRNMF產生了顯著改進的結果。