兩級聯(lián)合融合的多視圖子空間聚類改進算法

劉浩翰 杜嘉欣 李建伏

(中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院 天津 300300)

0 引 言

近年來,隨著互聯(lián)網(wǎng)的廣泛應(yīng)用,人們能夠方便地獲取各種多視圖數(shù)據(jù),如:多種特征的數(shù)據(jù),即可以用形狀、顏色、位置等特征表示圖像數(shù)據(jù);多種模態(tài)的數(shù)據(jù),即可以用文本、圖像、音頻和視頻等模態(tài)表示內(nèi)容數(shù)據(jù);多種關(guān)系的數(shù)據(jù),即可以用參考文獻的引用關(guān)系、作者的合作關(guān)系等關(guān)系表示論文間的關(guān)系數(shù)據(jù)。多視圖數(shù)據(jù)間的互補性可以克服單視圖數(shù)據(jù)的局限性,并擴展其應(yīng)用領(lǐng)域[1]。因此,多視圖聚類受到了廣泛關(guān)注。

目前已經(jīng)提出了多種多視圖聚類算法[2-14],主要可以分為三類。基于矩陣分解的方法[4-5,10-11],旨在尋找一個共同的指標(biāo)矩陣;基于譜聚類的方法[2-3,8],假設(shè)所有視圖共享相同或相似的特征向量矩陣;基于子空間聚類的方法[6,12-14],同時將數(shù)據(jù)劃分為多個子空間進行聚類。由于在許多實際應(yīng)用中,即使給定數(shù)據(jù)是高維的,其內(nèi)在維度通常也很低,這促使尋找底層低維子空間的發(fā)展,所以多視圖子空間聚類最為流行。

多視圖子空間聚類算法利用多視圖信息,分別獲取各個視圖的子空間表示,然后從多個子空間表示中獲得一致的聚類結(jié)果。比較流行的多視圖子空間聚類算法有文獻[6,15-17],其中:文獻[6]使用成對稀疏子空間表示進行多視圖聚類;文獻[15]提出一種使用子空間學(xué)習(xí)完成不完整多視圖聚類任務(wù)的方法;文獻[16]為每個數(shù)據(jù)對象獲得多個稀疏向量作為其表示形式;相較于傳統(tǒng)的采取兩階段策略的聚類方法,即首先提取特征,然后利用多視圖信息學(xué)習(xí)相似度矩陣,文獻[17]提出的多視圖深度子空間聚類網(wǎng)絡(luò)(MvDSCN)更為流行,因為其不僅可以用端到端的方式學(xué)習(xí)自表達矩陣,還把多視圖關(guān)系很好地嵌入特征學(xué)習(xí)階段。

然而MvDSCN算法利用多視圖數(shù)據(jù)的共性信息訓(xùn)練共識網(wǎng)絡(luò),得到一個公共自表達矩陣,進行一次譜聚類直接得到最終的聚類結(jié)果,不僅無法靈活地使用各個視圖的多樣性信息,即沒有充分利用多視圖數(shù)據(jù)的互補信息,而且只考慮了數(shù)據(jù)級的多視圖信息融合,得到公共自表達矩陣后結(jié)果就是固定的,但是某些包含噪聲數(shù)據(jù)的視圖可能會破壞公共自表達矩陣,直接聚類導(dǎo)致聚類性能下降。

針對上述問題,本文提出一種新的多視圖聚類方法,稱為兩級聯(lián)合融合的多視圖子空間聚類改進算法(TJ-MvDSCN)。包括三個方面的改進:(1) 在共識網(wǎng)絡(luò)和多樣網(wǎng)絡(luò)的多個自表達矩陣上分別進行譜聚類得到基本分配,不僅關(guān)注共識網(wǎng)絡(luò)學(xué)習(xí)的多視圖共性信息,還關(guān)注多樣網(wǎng)絡(luò)學(xué)習(xí)的多視圖互補信息;(2) 結(jié)合圖構(gòu)造,使用更新圖的方式進行基本分配的融合,增加了分配級別的多視圖信息融合操作,繼承了集成學(xué)習(xí)的魯棒性,結(jié)合已有的數(shù)據(jù)級融合形成兩級融合結(jié)構(gòu);(3) 增加聚類損失用于進一步指導(dǎo)自表達矩陣的生成和基本分配的更新,基于迭代優(yōu)化策略構(gòu)建了一個可以聯(lián)合學(xué)習(xí)特征表示和聚類分配的多視圖聚類框架。

1 MvDSCN算法

1.1 算法思路

MvDSCN算法的基本思路是通過以端到端的方式學(xué)習(xí)多視圖自表達矩陣。如圖1所示,首先在多樣網(wǎng)絡(luò)和共識網(wǎng)絡(luò)的深度自動編碼器上分別建立子空間[18],然后使用全連接層在子空間中學(xué)習(xí)自表達矩陣,其中多樣網(wǎng)絡(luò)學(xué)習(xí)特定視圖的自表達矩陣,共識網(wǎng)絡(luò)學(xué)習(xí)所有視圖的公共自表達矩陣,最后使用公共自表達矩陣進行一次譜聚類直接得到聚類結(jié)果。MvDSCN使用共識網(wǎng)絡(luò)提取多視圖數(shù)據(jù)的共性信息,在損失函數(shù)中引入希爾伯特·施密特獨立性指標(biāo)提取多視圖數(shù)據(jù)的互補信息。

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

MvDSCN的目標(biāo)函數(shù)包括五個部分,如式(1)所示。

(1)

式(1)中的五項分別代表自編碼器重建損失、自表達損失、自表達正則化損失、統(tǒng)一網(wǎng)絡(luò)損失和多樣性正則化損失。

MvDSCN算法具有把多視圖關(guān)系很好地嵌入特征學(xué)習(xí)階段,用端到端的方式學(xué)習(xí)多視圖自表達矩陣等優(yōu)點。然而該算法同時也存在沒有充分利用多視圖數(shù)據(jù)互補信息、只考慮了數(shù)據(jù)級的多視圖信息融合、噪聲數(shù)據(jù)可能破壞公共自表達矩陣等缺陷。

2 TJ-MvDSCN算法

針對MvDSCN算法的問題,以其作為基礎(chǔ)模型,本文提出一種兩級聯(lián)合融合的多視圖子空間聚類改進算法TJ-MvDSCN,增加了分配級別的多視圖信息融合形成兩級融合結(jié)構(gòu),并且通過增加聚類損失構(gòu)建了一個可以聯(lián)合學(xué)習(xí)特征表示和聚類分配的多視圖聚類框架。

2.1 兩級融合

基于MvDSCN算法的問題,本文結(jié)合圖構(gòu)造,使用更新圖的方式進行基本分配的融合,增加了分配級別的多視圖信息融合。不僅繼承了集成學(xué)習(xí)的魯棒性,而且與數(shù)據(jù)級多視圖信息融合形成一個兩級融合結(jié)構(gòu),提升了多視圖聚類的性能。

初始的數(shù)據(jù)級多視圖信息融合遵循MvDSCN算法的基本結(jié)構(gòu),但在得到自表達矩陣Z1,Z2,…,Zv和Z之后,增加了分配級別的多視圖信息融合,具體步驟如下:

(1) 用Z1,Z2,…,Zv和Z分別進行譜聚類,得到v+1個基本分配。

(2) 用Z提取邊關(guān)系后使用文獻[20]中的networkx計算基準(zhǔn)圖G。

(3) 用基本分配判斷圖G中兩個節(jié)點是否被分到同一個簇。

(4) 若在一個分配中被分到同一個簇,兩節(jié)點的邊權(quán)重加1。

(5) 刪除圖G中邊權(quán)重為0的節(jié)點對。

(6) 判斷是否收斂,若不收斂就隨機恢復(fù)一些刪除的節(jié)點對及其邊。

(7) 迭代更新圖G,直到收斂,得到最終的聚類融合結(jié)果。

2.2 聯(lián)合學(xué)習(xí)

基于MvDSCN算法的問題,本文增加了聚類損失用于進一步指導(dǎo)自表達矩陣的生成和基本分配的更新,基于迭代優(yōu)化策略構(gòu)建一個可以聯(lián)合學(xué)習(xí)特征表示和聚類分配的多視圖聚類框架,提升多視圖聚類的性能。

(2)

式中:C是共識聚類標(biāo)簽矩陣,即共識分配;r是簇數(shù)。

結(jié)合式(1)和式(2),提出TJ-MvDSCN的目標(biāo)函數(shù):

(3)

本文采用梯度下降法來解決式(3)的問題,對于反向傳播的過程,為每個變量計算梯度并進行更新。TJ-MvDSCN集成了特征表示和聚類融合,基于迭代優(yōu)化策略,共識分配用于進一步指導(dǎo)自表達矩陣的生成和基本分配的更新。這種聯(lián)合學(xué)習(xí)策略有助于獲得更優(yōu)的解決方案。

2.3 算法模型

TJ-MvDSCN算法的基本步驟如下:

(1) 輸入各個視圖數(shù)據(jù),使用MvDSCN算法框架學(xué)習(xí)多個初始自表達矩陣。

(2) 分別使用特定視圖的自表達矩陣和公共自表達矩陣構(gòu)建相似度矩陣。

(3) 分別使用多個相似度矩陣進行譜聚類得到多個基本分配。

(4) 進行聚類融合,得到共識分配。

(5) 使用共識分配進一步指導(dǎo)自表達矩陣的生成。

(6) 重復(fù)步驟(2)-步驟(5)直到達到迭代次數(shù)。

TJ-MvDSCN算法的模型結(jié)構(gòu)如圖2所示。

圖2 TJ-MvDSCN算法模型結(jié)構(gòu)

3 實 驗

3.1 實驗設(shè)置

實驗環(huán)境為PyCharm Community Edition 2018.3.5,運行計算機處理器為Intel(R)Core(TM)i5-10210U CPU @ 1.60 GHz, 內(nèi)存為16 GB, 編程語言為Python。在各數(shù)據(jù)集上計算的評價指標(biāo)值是15次實驗后取平均值。

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

本文在三個基本多視圖數(shù)據(jù)集上評估了算法TJ-MvDSCN的多視圖聚類性能。

(1) NGs數(shù)據(jù)集:20個新聞組數(shù)據(jù)集的子集,包含500個新聞組文檔。每個原始文檔都用三種不同的方法進行了預(yù)處理,分別是基于內(nèi)容的評分預(yù)測、已有的其他用戶給出的評分、基于內(nèi)容的其他用戶的評分預(yù)測,并帶有五個主題標(biāo)簽之一,即五個等級的評分。NGs數(shù)據(jù)集來自http://lig-membres.imag.fr/grimal/data.html。

(2) BBC數(shù)據(jù)集:由從BBC新聞網(wǎng)站收集的685個文檔組成。每個文檔都分為四個部分,分別是文章中的4個文本段,并用5個主題標(biāo)簽手動標(biāo)注。BBC數(shù)據(jù)集來自http://mlg.ucd.ie/datasets/segment.html。

(3) WebKB數(shù)據(jù)集:從加州大學(xué)計算機科學(xué)系收集的203個網(wǎng)頁,分為4類。每個網(wǎng)頁均由頁面內(nèi)容、超鏈接的錨文本及其標(biāo)題中的文本描述三個視圖構(gòu)成。WebKB數(shù)據(jù)集來自https://linqs.soe.ucsc.edu/data。

上述三個數(shù)據(jù)集的基本數(shù)據(jù)特征總結(jié)在表1中。

表1 多視圖數(shù)據(jù)集的基本數(shù)據(jù)特征

3.1.2 評價指標(biāo)

本文使用四個常用的評價指標(biāo)來評估聚類質(zhì)量,包括準(zhǔn)確率(ACC)、歸一化互信息(NMI)、F度量和調(diào)整蘭德系數(shù)(AR),可以全面地評估聚類性能。

(1) ACC:被正確聚類的樣本點占總樣本點數(shù)的比率,在[0,1]之間,準(zhǔn)確率越高越好。其計算公式如下:

(4)

式中:li是真實的標(biāo)簽;ci是算法產(chǎn)生的聚類分配;m(ci)是置換映射函數(shù);n是樣本數(shù)。

(2) NMI:計算同一數(shù)據(jù)兩個標(biāo)簽間相似度的歸一化度量。其計算公式如下:

(5)

式中:I(l;c)是l和c的互信息;H表示它們的熵。歸一化到[0,1],0表示沒有相關(guān)性,1是完美的相關(guān)性。

(3) F度量:準(zhǔn)確率和召回率的加權(quán)平均值,其中F度量為1是其最佳值,為0是其最差值。準(zhǔn)確率和召回率對F度量的相對貢獻相等,其計算公式如下:

(6)

(4) AR:調(diào)整的蘭德系數(shù)(RI)。在[0,1]之間,當(dāng)聚類結(jié)果與實際分配完美匹配時,其值為1。其計算公式如下:

(7)

3.1.3 對比方法

本文將TJ-MvDSCN的性能與改進前的多視圖深度子空間聚類算法MvDSCN及其他三種多視圖聚類算法進行了比較。

(1) MultiNMF[5]提出了一種基于非負矩陣分解的多視圖聚類算法,該分解可提供跨多個視圖的兼容聚類解決方案。

(2) MCGL[21]提出了一種基于圖學(xué)習(xí)的多視圖聚類算法來提高圖的質(zhì)量,進而提高多視圖聚類性能。

(3) CoregSC[3]提出了一種譜聚類框架,使用協(xié)同正則化聚類假設(shè)組合了多個數(shù)據(jù)視圖的圖形。

(4) MvDSCN[17]提出了一種新的多視圖深度子空間聚類網(wǎng)絡(luò),通過在深度卷積自動編碼器上建立潛在空間來提高聚類性能。

3.2 實驗結(jié)果

五種多視圖聚類算法在三個數(shù)據(jù)集上的聚類性能分別如表2、表3、表4所示。

表2 五種算法在NGs數(shù)據(jù)集上的聚類性能

表3 五種算法在BBC數(shù)據(jù)集上的聚類性能

表4 五種算法在WebKB數(shù)據(jù)集上的聚類性能

可以得出以下結(jié)果:

(1) 本文提出的TJ-MvDSCN算法明顯優(yōu)于其他算法。除了在WebKB數(shù)據(jù)集上的F度量指標(biāo)稍遜于其他算法,但差距很小,且比改進前的MvDSCN算法高,TJ-MvDSCN在所有數(shù)據(jù)集上均具有最佳性能。結(jié)果表明,TJ-MvDSCN是一種有效的多視圖聚類算法。

(2) 與改進前的MvDSCN算法相比,TJ-MvDSCN在NGs數(shù)據(jù)集上,ACC、NMI、F度量、AR四個指標(biāo)分別提升0.109 9、0.059 0、0.072 9、0.101 1;在BBC數(shù)據(jù)集上,四個指標(biāo)分別提升0.108 2、0.062 7、0.098 7、0.136 2;在WebKB數(shù)據(jù)集上,四個指標(biāo)分別提升0.162 3、0.127 1、0.132 4、0.188 9。

(3) 與改進前的MvDSCN算法相比,TJ-MvDSCN在多個數(shù)據(jù)集上的聚類性能更好。這表明增加分配級別的多視圖信息融合及增加聚類損失提升了多視圖聚類性能。

(4) CoregSC的聚類性能通常比MultiNMF好,而TJ-MvDSCN比兩者均好,原因之一是它們都更加依賴于附加的聚類算法。

(5) MvDSCN的性能通常比其他三種算法好,因為其使用深度自動編碼器把多視圖關(guān)系很好地嵌入特征學(xué)習(xí)階段。

這證明了TJ-MvDSCN算法在多視圖聚類任務(wù)上的有效性,因為TJ-MvDSCN不僅關(guān)注共識網(wǎng)絡(luò)學(xué)習(xí)的多視圖共性信息,還關(guān)注多樣網(wǎng)絡(luò)學(xué)習(xí)的多視圖互補信息;而且增加了分配級別的多視圖信息融合、增加聚類損失用于進一步指導(dǎo)自表達矩陣的生成和基本分配的更新,提升了多視圖聚類性能。

3.3 分配級融合和聚類損失對結(jié)果的影響

為了驗證增加分配級融合和聚類損失兩部分的有效性,進行了進一步的實驗,結(jié)果如圖3所示,其中:MvDSCN是改進前的算法;T-MvDSCN是只增加了分配級融合,沒有增加聚類損失的算法;TJ-MvDSCN是本文算法,既增加了分配級融合,也增加了聚類損失。

(a) (b)

可以看出,在四個評價指標(biāo)上,MvDSCN、T-MvDSCN和TJ-MvDSCN的值均依次呈遞增狀態(tài),即T-MvDSCN明顯優(yōu)于MvDSCN,TJ-MvDSCN明顯優(yōu)于T-MvDSCN。這意味著增加分配級融合和聚類損失兩部分對最終聚類結(jié)果的提升都有貢獻,其中增加分配級融合,繼承了集成學(xué)習(xí)的魯棒性,結(jié)合已有的數(shù)據(jù)級融合形成兩級融合結(jié)構(gòu);增加聚類損失用于進一步指導(dǎo)自表達矩陣的生成和基本分配的更新,構(gòu)建了一個可以聯(lián)合學(xué)習(xí)特征表示和聚類分配的多視圖聚類框架。兩部分共同提升了本文算法TJ-MvDSCN的多視圖聚類性能。

4 結(jié) 語

為提升MvDSCN算法的多視圖聚類性能,本文提出一種兩級聯(lián)合融合的多視圖子空間聚類改進算法TJ-MvDSCN。不僅關(guān)注多視圖共性信息,還關(guān)注多視圖互補信息;增加分配級別的多視圖信息融合,與已有的數(shù)據(jù)級信息融合形成兩級融合結(jié)構(gòu);增加聚類損失,基于迭代優(yōu)化策略構(gòu)建了一個可以聯(lián)合學(xué)習(xí)特征表示和聚類分配的多視圖聚類框架。這提升了自表達矩陣的學(xué)習(xí)能力及多視圖聚類性能。在多個數(shù)據(jù)集上的實驗結(jié)果證明了本文方法的有效性,其聚類性能與現(xiàn)有方法相比有較大的提升。