李勇振,廖湖聲
1.北京工業(yè)大學 信息學部,北京100124
2.北京建筑大學 電氣與信息工程學院,北京100044
隨著信息技術(shù)的飛速發(fā)展以及互聯(lián)網(wǎng)應用的日益豐富,可用數(shù)據(jù)規(guī)模越來越大,數(shù)據(jù)的表現(xiàn)形式也越來越多樣。例如,網(wǎng)頁可以由網(wǎng)頁中出現(xiàn)的圖片、文字以及超級鏈接進行表達,又比如文本可以由詞頻、詞向量等多種描述算子進行刻畫。這種描述相同語義的不同特征表達稱之為多視角數(shù)據(jù)。一般來說,多視角數(shù)據(jù)描述相同的語義又相互補充,表現(xiàn)為互補與一致特性。多視角聚類通過挖掘上述特性獲得了相比于單視角聚類的有效性能提升,并在數(shù)據(jù)挖掘、模式識別、信息檢索等領域產(chǎn)生廣泛的應用[1]。
近些年來,研究者提出了大量的多視角聚類算法并取得了優(yōu)異的聚類性能。一般來說,典型多視角聚類算法包含親和矩陣/圖學習算法[2]、子空間學習算法[3]、協(xié)同訓練算法[4]以及后融合算法[5]。例如,Chaudhuri等人[6]采用典型相關(guān)分析算法實現(xiàn)兩視角數(shù)據(jù)最大相關(guān)性挖掘。Kumar等人[7]基于譜分解技術(shù)提出學習不同視角相似或一致的子空間嵌入,進而實現(xiàn)多視角嵌入學習。Zhao等人[8]引入層次學習思想,提出多視角深度矩陣分解,不同視角數(shù)據(jù)共享一致的深度子空間嵌入。Zhan等人[9]基于標準非負矩陣分解技術(shù)提出自適應的多視角語義分解技術(shù)以學習不同視角一致的子空間表達。
在各種不同類別的多視角聚類算法中,研究者主要致力于互補與一致性的顯式或隱式挖掘與建模。典型采納的技術(shù)如正則化的共同表示建模、多視角統(tǒng)一表達與獨立表達建模等。例如,為了實現(xiàn)多視角數(shù)據(jù)中互補與一致性的顯式挖掘,Yin等人[10]借鑒自然語言建模相關(guān)思想,學習多視角數(shù)據(jù)一致與獨有的子空間嵌入,且上述嵌入之間通過張量操作進行相關(guān)性建模,進而實現(xiàn)互補與一致性的細致刻畫。Liang等人[11]通過引入不同視角構(gòu)建相似度矩陣的相似與不相似約束以映射多視角數(shù)據(jù)之間的一致與互補部分,進而有效挖掘多視角數(shù)據(jù)的特性,實現(xiàn)聚類性能的提升。
總的來說,上述多視角聚類算法可以有效挖掘視角之間的相關(guān)特性,提升整體性能,但是互補與一致性的部分一般通過正則化、線性或者非線性映射等手段實現(xiàn),如Yin等人[10]將多視角表達通過線性映射到各個視角表達,進而在各個視角下建立其對應表達的約束與優(yōu)化。這些方法難以有效區(qū)分互補與一致性部分,即不同視角表達之間哪一部分特征體現(xiàn)了一致特性,哪一部分體現(xiàn)出了互補特性?;诖耍パa與一致性并不能顯式區(qū)分與對應挖掘,也就難以實現(xiàn)互補與一致性的有效挖掘。
針對上述問題,本文提出了一種基于圖卷積神經(jīng)網(wǎng)絡的多視角聚類方法,如圖1所示。通過構(gòu)建不同視角的鄰接圖,多視角數(shù)據(jù)共同子圖可以被提取并基于圖卷積神經(jīng)網(wǎng)絡建模以反映多視角之間的一致性部分?;谙嗤膱D卷積神經(jīng)網(wǎng)絡模型參數(shù),多視角表達通過串接不同視角完整鄰接圖的嵌入實現(xiàn)互補性的有效挖掘。最終通過增加上述多視角表達的相對熵約束,可以實現(xiàn)聚類友好的多視角嵌入學習。本文提出的方法在五個廣泛應用的多視角基準數(shù)據(jù)中取得了相比于主流方法更高的聚類性能。
圖1 基于圖卷積神經(jīng)網(wǎng)絡的多視角聚類框架圖
通過有效挖掘視角之間的互補與一致特性,多視角聚類表現(xiàn)出了相比于使用單一視角更強的聚類性能[12-16]。近些年來,一系列的多視角聚類算法被提出并大致被劃分為以下四類較為主流的算法:親和矩陣/圖學習算法、子空間學習算法、協(xié)同訓練算法以及后融合算法。
親和矩陣/圖學習算法通過學習多視角數(shù)據(jù)的統(tǒng)一相似性度量矩陣并引入譜聚類完成最終的聚類[2]。各種相似性度量技術(shù)以及正則化約束被提出以建模不同視角相似性度量矩陣的關(guān)系。近些年來,啟發(fā)于基于稀疏、低秩等結(jié)構(gòu)約束的子空間分割算法取得的優(yōu)異性能[17],基于結(jié)構(gòu)約束的自表示學習技術(shù)被引入多視角聚類中的相似性度量矩陣構(gòu)建,并通過引入正則化約束有效實現(xiàn)了視角間互補與一致性的建模[2,18-20]并取得了優(yōu)異的多視角聚類性能。
子空間學習算法學習多視角數(shù)據(jù)統(tǒng)一的表達并引入傳統(tǒng)的單視角聚類算法完成最終的聚類。在學習上述統(tǒng)一表達時,典型的技術(shù)包括典型相關(guān)分析[6]、譜分解[7]、矩陣分解[9]、生成模型[20]、深度神經(jīng)網(wǎng)絡[3,21-22]。相似于基于親和矩陣學習的算法,不同視角之間的表達通過正則化約束、線性或非線性映射等方式實現(xiàn)互補與一致性挖掘。例如,Kumar等人[7]通過兩兩視角關(guān)系對的正則項約束實現(xiàn)不同視角譜嵌入的一致性刻畫。Yin等人[10]假設存在隱含的多視角表達可以基于矩陣映射的方式生成視角獨立表達。
協(xié)同訓練算法交替使用不同視角的信息協(xié)助其他視角的聚類。該框架為典型的半監(jiān)督學習算法框架,近些年來被推廣到無監(jiān)督多視角聚類任務中[23]。例如,Kumar等人[4]使用協(xié)同訓練框架進行不同視角拉普拉斯矩陣的協(xié)同構(gòu)造與聚類訓練,該算法被進一步擴展以處理更大規(guī)模的數(shù)據(jù)[24]。后融合算法通過融合不同視角獨立的聚類結(jié)果實現(xiàn)整體多視角聚類[25-26]。為實現(xiàn)融合,一系列對齊技術(shù)被采納,代表性方法如基于概率圖模型[27]以及矩陣優(yōu)化[5]。
考慮到當前的多視角聚類算法在互補與一致性的挖掘上多采用正則項、線性或者非線性映射等手段實現(xiàn),如何實現(xiàn)更有效的多視角相關(guān)信息挖掘仍然是多視角聚類的主要挑戰(zhàn),本文提出了一種基于圖卷積神經(jīng)網(wǎng)絡的多視角聚類算法以建模上述信息。
基于圖卷積神經(jīng)網(wǎng)絡的多視角聚類算法主要包括三個部分。多視角一致性與互補性挖掘?qū)崿F(xiàn)各個視角嵌入表達學習,并且通過一致性與互補性的顯式建模實現(xiàn)該嵌入表達學習的優(yōu)化。多視角表達與優(yōu)化目標建立實現(xiàn)多視角表達的構(gòu)建,同時通過引入相對熵等優(yōu)化目標函數(shù)實現(xiàn)多視角表達的約束以使其與聚類耦合。模型優(yōu)化實現(xiàn)神經(jīng)網(wǎng)絡模型參數(shù)的學習,進而基于學習的模型參數(shù)完成最終的多視角聚類任務。
為實現(xiàn)多視角數(shù)據(jù)間互補與一致特性挖掘、聚類耦合的多視角表達學習以及整體模型優(yōu)化,算法的主要工作流程如下:給定多視角數(shù)據(jù)集,依據(jù)每個視角的特征構(gòu)建當前視角的鄰接矩陣;提取多個視角鄰接矩陣對于同一樣本點的公共子集;基于該公共子集構(gòu)建各個視角的圖卷積神經(jīng)網(wǎng)絡表達并進行一致性約束損失函數(shù)構(gòu)建;基于上述圖卷積神經(jīng)網(wǎng)絡參數(shù)構(gòu)建各個視角針對其完整鄰接矩陣的獨立圖卷積神經(jīng)網(wǎng)絡表達并通過排序損失函數(shù)進行該表達約束;級聯(lián)各個視角獨立圖卷積神經(jīng)網(wǎng)絡表達獲得多視角表達并通過一般聚類算法獲得聚類中心以及所有樣本屬于各個類別的概率;基于該概率值構(gòu)造輔助變量并通過相對熵目標函數(shù)實現(xiàn)上述概率值以及整體網(wǎng)絡的優(yōu)化;最終依據(jù)優(yōu)化獲得的概率值導出多視角數(shù)據(jù)聚類結(jié)果。
假設具有c個類別的多視角數(shù)據(jù)表征為1,2,…,m;i=1,2,…,n},其中m代表視角數(shù)目,n代表樣本數(shù)為樣本i在視角v下的特征向量,維度為dv。為實現(xiàn)不同視角之間一致性與互補性的顯式度量,首先對不同視角進行鄰接圖的構(gòu)建,即Sv,其中Svij代表鄰接圖矩陣中第i行第j列的元素值,為0或者1,表示在視角v下樣本i與j是否相似。Sv的構(gòu)建基于樣本Xv間的歐式距離,即對于每個樣本,選取其k近鄰作為相似樣本,其他樣本為不相似,Sv也稱為相似度圖(具體構(gòu)造細節(jié)見3.2節(jié))。
基于不同視角的Sv,v=1,2,…,m,視角間的一致性部分可以通過相似度圖的公共子集進行刻畫,即Svs。具體來講,對于每一個樣本點,其在不同視角下相同的近鄰點作為構(gòu)建Svs的基礎。Svs在不同視角下一致,屬于不同視角下Sv的子圖。為利用該一致性信息,采用圖卷積神經(jīng)網(wǎng)絡進行不同視角下基于公共子圖的嵌入學習。圖卷積神經(jīng)網(wǎng)絡為近些年來提出的一種圖數(shù)據(jù)特征提取器,可以巧妙地實現(xiàn)圖數(shù)據(jù)中所有節(jié)點的嵌入學習。依據(jù)經(jīng)典的圖卷積神經(jīng)網(wǎng)絡建模方法[28],視角v下所有樣本的嵌入表達傳播公式為:
其中,Hvs(l+1)為視角v下所有樣本的第l+1層嵌入,σ為神經(jīng)網(wǎng)絡非線性激勵函數(shù),即sigmod函數(shù),Av=為單位矩陣,Dv為Av的度矩陣,其計算為為圖卷積神經(jīng)網(wǎng)絡第l層卷積核參數(shù)。通過設置Hvs(1)=Xv,即第一層嵌入為數(shù)據(jù)特征表達,并迭代若干次的上述計算,可以得到各個視角的圖卷積神經(jīng)網(wǎng)絡嵌入Zvs=Hvs(L),L為圖卷積神經(jīng)網(wǎng)絡的層數(shù)。依據(jù)經(jīng)典的圖卷積神經(jīng)網(wǎng)絡[28]進行各個視角下參數(shù)設置:網(wǎng)絡為兩層,隱藏層節(jié)點數(shù)目參考值為128(在64、128、256中擇優(yōu)選擇),激活函數(shù)選擇為ReLU。
不同視角具有一致的Svs,則可對Zvs進行一致性約束的損失函數(shù)構(gòu)建,即:
另一方面,基于上述圖卷積神經(jīng)網(wǎng)絡參數(shù)以及各視角完整的相似度圖Sv,則可以得到各個視角的圖卷積神經(jīng)網(wǎng)絡嵌入Zv,該嵌入可以實現(xiàn)不同視角完整特征表達。為進一步實現(xiàn)不同視角相似性結(jié)構(gòu)對該嵌入表達的約束,引入基于排序的損失函數(shù),即:
基于各個視角在完整相似度圖下的嵌入,為挖掘多視角數(shù)據(jù)之間的互補特性,多視角表達可以建模為不同視角下的嵌入的級聯(lián),即:
基于多視角一致性與互補性建模,zi提供了多視角的完整表達。zi的獲取直接依靠多視角數(shù)據(jù)本身,但是與最終的聚類任務可能存在一定的鴻溝,即多視角表達并非是最優(yōu)的適應聚類任務的表達。為了緩解該問題,提出引入相對熵的目標函數(shù)以提升多視角表達,進而使其更適應于聚類任務而完成最終的聚類。其基本思想為:通過該多視角表達進行聚類置信度的求解并引入輔助目標函數(shù)實現(xiàn)聚類高置信度的提升進而學習得到適用于聚類的多視角表達。
首先基于上述多視角表達采用k均值聚類算法完成多視角數(shù)據(jù)聚類中心的獲取,即vj,j=1,2,…,c,其中c為聚類數(shù)目?;谠摼垲愔行?,樣本i屬于各個類別的概率qij可以表示為:
引入輔助變量pij以增強高置信概率值,即最終,相對熵目標函數(shù)可以構(gòu)建為:
當對L3進行優(yōu)化時,樣本聚類的高置信概率將被增強,進而反向傳播優(yōu)化多視角表達zi,最終完成整個網(wǎng)絡參數(shù)的優(yōu)化。
為獲得優(yōu)異的聚類性能,優(yōu)化目標函數(shù)L3需要提供較為優(yōu)異的初始值,即多視角表達zi以及各視角圖卷積神經(jīng)網(wǎng)絡參數(shù)。為實現(xiàn)此目的,整個模型的優(yōu)化分為兩個部分,即初始值獲取與網(wǎng)絡微調(diào)。初始值獲取通過聯(lián)合優(yōu)化目標函數(shù)L1+L2實現(xiàn),優(yōu)化方法采用標準的誤差反傳算法進行實現(xiàn)。首先構(gòu)造相似三元組數(shù)據(jù)其中遍歷視角v下所有樣本,基于進行采樣,采樣于的非相似樣本。L1可直接進行求導,L2在滿足時無梯度,反之直接計算其梯度。最終目標函數(shù)收斂時,則可獲取圖卷積神經(jīng)網(wǎng)絡的初始值以及多視角表達zi。
基于上述初始值,最終進行目標函數(shù)L3的優(yōu)化,具體來說,基于梯度算法同時優(yōu)化聚類中心vj,j=1,2,…,c以及多視角表達zi:
其中?L3/zi繼續(xù)反傳以實現(xiàn)所有視角圖卷積神經(jīng)網(wǎng)絡參數(shù)的優(yōu)化。
整體的優(yōu)化算法如算法1所述,基本的收斂條件為連續(xù)兩次迭代中少于1%的qij值發(fā)生變化。最終目標函數(shù)收斂時,可以直接基于qij每一行最大值的索引進行樣本聚類中心獲取,即:t(i)即為樣本i的聚類中心。
算法1圖卷積神經(jīng)網(wǎng)絡的多視角聚類優(yōu)化算法
在5個廣泛使用的多視角基準數(shù)據(jù)集上通過對比前沿的多視角聚類算法以驗證所提出的多視角聚類算法性能。同時,將通過可視化等技術(shù)以進一步體現(xiàn)所提出算法的優(yōu)異性。
將采用公認的多視角數(shù)據(jù)基準集進行算法性能的驗證,數(shù)據(jù)基本介紹如下。
Notting-Hill數(shù)據(jù)集,人臉數(shù)據(jù)集,采集自電影Notting Hill。該數(shù)據(jù)集包含5個類別共計4 660張圖像,采用的3個視角特征為經(jīng)典的視角描述子Intensity、LBP以及Gabor特征。
Source數(shù)據(jù)集,新聞數(shù)據(jù)集,采集自BBC、Reuters以及Guardian 3個來源,該數(shù)據(jù)集包含5個類別共計169個樣本,每一種來源作為一個視角描述,特征采用經(jīng)典的詞頻特征。
Cora數(shù)據(jù)集,學術(shù)文章數(shù)據(jù)集,描述神經(jīng)網(wǎng)絡、理論等學術(shù)文章。該數(shù)據(jù)集包含7個類別共計2 708個樣本,采用鏈接特征以及詞頻兩種視角進行實驗。
BBC數(shù)據(jù)集,文本數(shù)據(jù)集,為合成數(shù)據(jù)集。該數(shù)據(jù)集包含5類樣本共計2 012個樣本,視角描述為兩個片段切分的詞頻特征。
CCV數(shù)據(jù)集,視頻數(shù)據(jù)集,采集自YouTube。該數(shù)據(jù)集包含20個類別共計9 317個視頻。時空關(guān)鍵點特征以及尺度不變特征轉(zhuǎn)化兩種描述子作為兩種視角進行實驗。
對比當前主流多視角聚類算法以進行所提出算法性能的驗證。
SingleB:所有單視角譜聚類的最優(yōu)結(jié)果,該算法為基準算法。
CCA[6]:Chaudhuri等人采用CCA算法獲得多視角統(tǒng)一低維表達進而采用k均值完成聚類。
Co-Reg-Pairwise、Co-Reg-Centroid[7]:Kumar等人提出兩種正則化方案以進行視角子空間表達間互補與一致性建模。
MultiDMF[8]:Zhao等人提出深度矩陣分解算法以學習不同視角的層次化表達基矩陣以及視角無關(guān)統(tǒng)一表達矩陣。
MultiTE[10]:Yin等人學習多視角統(tǒng)一表達以及視角獨立表達并采用矩陣映射方式實現(xiàn)多視角互補與一致性挖掘。
MVCF[9]:Zhan等人學習多視角語義分解的統(tǒng)一表達以實現(xiàn)不同視角相關(guān)性的最大化利用。
SGF、DGF[11]:Liang等人顯式挖掘不同視角之間的一致與不一致特性進而實現(xiàn)多視角關(guān)系建模。
GCNMC:本文提出的基于圖卷積神經(jīng)網(wǎng)絡且充分挖掘多視角互補與一致性的多視角聚類算法。
對于上述方法中的Co-Reg-Pairwise、Co-Reg-Centroid、MultiDMF、MVCF、SGF以及DGF,采用開源的代碼并根據(jù)原作者的推薦超參數(shù)獲得聚類結(jié)果。對于CCA,采用LSCCA包進行聚類結(jié)果的獲取。對于MultiTE,基于原文的算法步驟進行復現(xiàn)并采用線性搜索獲得最優(yōu)性能的超參數(shù)。
對于本文方法,Sv的構(gòu)建基于樣本間的距離,具體過程如下:對于該視角下的任意樣本,計算其與該視角下所有其他樣本之間的歐式距離,并將該距離進行由小到大排序,之后選擇前k樣本作為其近鄰,即鄰接矩陣中該樣本對應的上述k個樣本之間相似度為1,其余為0。超參數(shù)k采用經(jīng)驗值獲?。▽嶒炦x用k=20)。具體地,在Ubuntu系統(tǒng)下基于python語言,上述距離計算采用sklearn工具包下的metrics.pairwise.euclidean_distances函數(shù)計算,排序采用numpy下的argsort函數(shù)實現(xiàn)。圖2給出了Notting-Hill數(shù)據(jù)集下各個視角的鄰接圖Sv以及公共鄰接圖Svs,可以看出不同視角具有一致以及獨立的鄰接關(guān)系,體現(xiàn)出多視角的互補與一致特性。
本文的度量準則采用以上所有方法公認的聚類準確率ACC以及歸一化互信息NMI進行評估[10]。其定義如下:
其中,y和o為多視角數(shù)據(jù)的真實類別與聚類預測類別。map()為基于Hungarian算法的置換函數(shù)以對齊上述類別標簽。δ(,)為指示函數(shù),當函數(shù)兩個變量相同時返回值1,否則返回值0。I(;)用于計算兩個變量的互信息,H()用于計算熵。對于ACC以及NMI兩個度量指標,其值越大,則代表聚類性能越好。
所提出算法在各個數(shù)據(jù)集下與當前主流多視角聚類算法的性能對比見表1和表2。通過對比,可以看出,整體上所提出的基于圖卷積神經(jīng)網(wǎng)絡的多視角聚類算法在準確率與歸一化互信息下優(yōu)于其他所有算法。
圖2 Notting-Hill數(shù)據(jù)集不同視角鄰接圖與公共鄰接圖
表1 不同數(shù)據(jù)集上的聚類準確率對比%
表2 不同數(shù)據(jù)集上的聚類歸一化互信息對比 %
相比CCA采用線性映射,本文采用圖卷積神經(jīng)網(wǎng)絡非線性方式進行嵌入學習,因此可以學習得到更好的多視角表達,同時該表達經(jīng)過基于相對熵的目標函數(shù)優(yōu)化可以使得其更適用于聚類任務,因此所提出算法性能超越CCA。
相比于Co-Reg-Pairwise、Co-Reg-Centroid集中在多視角一致性挖掘上,本文所提出的算法可以有效挖掘多視角的互補與一致性,因此更好的多視角表達得以獲得以提升聚類性能。
相比于MultiDMF以及MVCF采用非負矩陣分解技術(shù)進行低維度嵌入學習,所提出的算法在學習嵌入的同時可以有效引入相對熵等優(yōu)化目標以進行嵌入的再學習,實現(xiàn)多視角表達與聚類表達的統(tǒng)一。
相比于MultiTE、SGF與DGF通過學習映射或者相關(guān)正則項約束等方式實現(xiàn)多視角一致性與互補性挖掘,所提出的算法可以更為顯式刻畫視角間的一致與互補性。同時多視角表達的再次優(yōu)化可以進一步提升模型的性能,因此所提出的算法優(yōu)于上述對比算法。
為進一步說明所學習得到的多視角表達優(yōu)于其他相關(guān)算法,采用經(jīng)典的t-SNE可視化方法對不同方法的嵌入進行二維降維與可視化。具體來說采用Python環(huán)境下sklearn工具包中的manifold.TSNE函數(shù)進行降維(降至二維),并采用matplotlib工具包中的pyplot.plot進行繪圖,實驗結(jié)果如圖3所示(不同顏色代表不同的數(shù)據(jù)聚集)。其中T=50為所提出的方法在迭代50次(算法1中步驟4)時的結(jié)果。可以看出,相比于其他方法,所提出的算法使得樣本具有更易區(qū)分的效果,即聚集更明顯且易于劃分,對應多視角表達則更加聚類友好。
目標函數(shù)L3采用基于梯度的優(yōu)化算法,可以保證算法的收斂。為進一步驗證該收斂情況以及多視角表達的優(yōu)化效果,本文可視化隨著迭代次數(shù)多視角表達的t-SNE情況,同時,將隨著迭代次數(shù)增加的聚類性能進行展示,如圖4所示。
圖3 Notting-Hill數(shù)據(jù)集下不同方法t-SNE對比
圖4 Notting-Hill數(shù)據(jù)集下隨著迭代增加t-SNE及聚類性能
在圖4中,給出了T=0、T=5、T=10以及T=50的結(jié)果。通過圖4可以看出隨著迭代次數(shù)的增加,數(shù)據(jù)點的聚集程度在增加,同時不同類別的分類邊界也變得更加容易獲得,可以說明隨著迭代次數(shù)的增加,數(shù)據(jù)的可分性得以改善。反映在多視角聚類性能上,可以看出聚類準確率與歸一化互信息隨著迭代的增加而增加,并逐漸收斂到最好性能并平穩(wěn)。
本文提出基于圖卷積神經(jīng)網(wǎng)絡的多視角聚類算法,借助于相似度圖構(gòu)建以及圖卷積神經(jīng)網(wǎng)絡模型,該算法可以顯式挖掘多視角的互補與一致特性,進而學習多視角表達。同時該多視角表達通過基于相對熵的目標函數(shù)進行再優(yōu)化,使得其為聚類友好表達。在五個公開數(shù)據(jù)集上,所提出的算法相比于主流的多視角聚類算法取得了最優(yōu)的性能。
在多視角互補與一致性建模中,本文通過不同視角鄰接圖交集的方式建模一致性并通過并集的方式建模互補性,該種方式不可避免受到噪聲尤其是圖構(gòu)建中引入噪聲的影響,未來的工作將在該工作基礎上探索更友好的多視角互補與一致性挖掘方法。