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

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

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山西 太原 030024)

0 引 言

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

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

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

論文的創(chuàng)新點(diǎn)包括:(1)設(shè)計(jì)了一種改進(jìn)的非負(fù)矩陣分解方法,提高單視圖矩陣分解的魯棒性和稀疏性;(2)提出了一種自適應(yīng)單視圖融合方法,改進(jìn)了各單視圖之間融合的效果;(3)結(jié)合上述方法,提出了一種基于非負(fù)矩陣分解的均方殘差多視圖聚類方法;(4)采用標(biāo)準(zhǔn)數(shù)據(jù)集和古建筑圖像,驗(yàn)證了算法的有效性。

1 相關(guān)工作

隨著信息技術(shù)的飛速發(fā)展,數(shù)據(jù)的規(guī)模出現(xiàn)海量、多源、異構(gòu)、高維等特點(diǎn)。針對上述數(shù)據(jù),傳統(tǒng)的單視圖聚類存在聚類效率低、聚類效果差等問題,而多視圖聚類方法可從不同角度分析數(shù)據(jù),進(jìn)而提高聚類效果,因此,受到了研究者的廣泛關(guān)注。

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

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

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

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

2 基礎(chǔ)知識

2.1 非負(fù)矩陣分解

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

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

X≈UV

s.t.U≥0,V≥0

(1)

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

s.t.U≥0,V≥0

(2)

其中,*表示點(diǎn)積。

2.2 流形正則化

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

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

(3)

2.3 希爾伯特-施密特獨(dú)立性準(zhǔn)則

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

定義4(HSIC的一般形式):給定n個(gè)樣本點(diǎn)和不同視圖V(s),V(w),則視圖V(s)和視圖V(w)的關(guān)聯(lián)性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)是兩個(gè)內(nèi)積矩陣。

3 文中算法

3.1 問題定義

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

3.2 算法步驟

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

圖1 算法流程

3.2.1 系數(shù)矩陣的改進(jìn)

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

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

定義5(改進(jìn)的非負(fù)矩陣誤差O1):

O1=‖Ex‖21+‖Eu‖*

(5)

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

由于改進(jìn)的非負(fù)矩陣分解沒有考慮視圖內(nèi)部數(shù)據(jù)間結(jié)構(gòu)特征的完整性,低維潛在表示存在難以解釋的問題,進(jìn)而導(dǎo)致視圖內(nèi)部聯(lián)系不緊密、結(jié)構(gòu)不一致。為保證每個(gè)視圖內(nèi)部的局部幾何結(jié)構(gòu),針對上述問題,利用流形正則化以保持矩陣內(nèi)部結(jié)構(gòu)的不變性。為了進(jìn)一步加強(qiáng)不同視圖之間的相互學(xué)習(xí)和雙向融合,添加了HSIC模塊,以便于在模型優(yōu)化過程中實(shí)現(xiàn)視圖之間的互連、相互學(xué)習(xí)和信息集成。

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

定義6(更新系數(shù)矩陣V(s)的目標(biāo)函數(shù)):

(6)

式中有三個(gè)正則化參數(shù),其中λ1用來測量稀疏表示的重要性,(α(s))γ和λs分別是平滑項(xiàng)和反向回歸項(xiàng)的權(quán)衡相關(guān)性。更新V(s)需固定變量U(s),Ex(s),Eu(s),(α(s))γ,則式6的優(yōu)化問題轉(zhuǎn)化為:

(7)

其中,λ和μ是拉格朗日參數(shù)。將式7中關(guān)于V(s)的導(dǎo)數(shù)設(shè)為0。根據(jù)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)利用譜聚類算法得到各單視圖下的聚類結(jié)果C(s)。接著利用雙聚類的概念,計(jì)算具有高相似性分?jǐn)?shù)即均方殘差得分的子集。通過向重復(fù)簇所在矩陣中添加非重復(fù)簇的方式,判斷添加后相似性是否提高。

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

(9)

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

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

4.1 環(huán)境設(shè)置

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

4.2 數(shù)據(jù)集

為了驗(yàn)證算法的效率,以5個(gè)標(biāo)準(zhǔn)的多視圖數(shù)據(jù)集和古建筑數(shù)據(jù)集為對象進(jìn)行驗(yàn)證。

4.2.1 標(biāo)準(zhǔn)數(shù)據(jù)集

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

(2)3-Sources數(shù)據(jù)集:涵蓋BBC、路透社和《衛(wèi)報(bào)》報(bào)道3個(gè)在線新聞來源,包含416例病例。

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

(4)Yale數(shù)據(jù)集:由15個(gè)受試者的165張?jiān)枷袼貓D像組成。

(5)BBCSport 數(shù)據(jù)集:來自BBC體育網(wǎng)站的體育新聞文章的集合,包含282個(gè)報(bào)告的3個(gè)視圖的數(shù)據(jù)集。

4.2.2 古建筑數(shù)據(jù)集

古建筑數(shù)據(jù)集采用中科院金光寺數(shù)據(jù)集中的金光寺主建筑圖片進(jìn)行實(shí)驗(yàn),如圖2所示。

圖2 金光寺圖片

對上述兩幅古建筑圖像進(jìn)行多視圖數(shù)據(jù)集的構(gòu)建,首先對每幅圖像選取11 320個(gè)特征點(diǎn),其次提取特征點(diǎn)的位置、顏色、紋理、輪廓、領(lǐng)域和SIFT特征,即可構(gòu)建一個(gè)高維海量的多視圖數(shù)據(jù)集。

4.3 評估指標(biāo)

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

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 標(biāo)準(zhǔn)數(shù)據(jù)集下的結(jié)果

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

表1 ORL數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表2 MSRCV1數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表3 Yale數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表4 3-Sources數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

表5 BBCSport數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

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

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

4.4.2 古建筑數(shù)據(jù)集下的結(jié)果

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

圖3 聚類數(shù)為6時(shí)金光寺聚類結(jié)果圖

圖4 聚類數(shù)為8時(shí)金光寺聚類結(jié)果圖

從圖3和圖4可以看出,簇?cái)?shù)為6,8時(shí),MSRNMF對非負(fù)矩陣分解的目標(biāo)函數(shù)添加L21范數(shù)和核范數(shù),剔除了圖像噪聲,提高了古建筑多視圖聚類的魯棒性;結(jié)合MSR融合各單視圖聚類結(jié)果,進(jìn)一步平衡了各單視圖的重要性,最終得到一個(gè)較好的聚類結(jié)果。

5 結(jié)束語

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