一致性引導的自適應加權(quán)多視圖聚類

于 曉 劉 慧 林毓秀 張彩明

1(山東財經(jīng)大學計算機科學與技術(shù)學院 濟南 250014) 2(山東省數(shù)字媒體技術(shù)重點實驗室(山東財經(jīng)大學) 濟南 250014) 3(山東大學軟件學院 濟南 250014)

聚類是數(shù)據(jù)挖掘中的一項重要任務，將相似的點劃分到同一簇中，相異點劃分到不同簇中.聚類在信息檢索[1]、醫(yī)療診斷[2]、社交網(wǎng)絡分析[3]、圖像分割[4]等領域都發(fā)揮著重要作用.傳統(tǒng)的單視圖聚類算法已遇到瓶頸，在過去的幾年中，多視圖聚類成為前沿研究.

多視圖聚類利用多視圖數(shù)據(jù)中的信息來進行聚類.多視圖數(shù)據(jù)從多個角度來描述同一事物，隨著技術(shù)的進步，近年來這類數(shù)據(jù)日益增多.例如，可以同時使用多個設備對同一事物進行拍攝，得到的多個圖像屬于多視圖數(shù)據(jù).再者，同一張圖像可以使用不同的特征來表示，多種特征形成的數(shù)據(jù)即為多視圖數(shù)據(jù).通過使用多視圖數(shù)據(jù)，多視圖聚類能夠利用不同視圖之間的互補信息，從而可能提高聚類的效果.

迄今為止，研究人員已提出大量的多視圖聚類算法，大致包括基于多核學習的算法[5-7]、基于矩陣分解的算法[8]、基于圖學習的算法[9-10]、基于譜聚類的算法等.其中，基于譜聚類的多視圖聚類算法也可稱為多視圖譜聚類算法，該類算法將譜聚類的思想應用到了多視圖數(shù)據(jù)的聚類中，通?？梢苑譃?類:第1類是為所有視圖的數(shù)據(jù)生成一個一致的相似度矩陣，然后利用譜聚類算法得到聚類結(jié)果.有些算法[11-13]直接從原始數(shù)據(jù)中為所有視圖學習統(tǒng)一的相似度矩陣，還有一些算法利用核函數(shù)[14]或k近鄰圖[15-16]等方式先為每個視圖構(gòu)造相應的初始相似度矩陣，然后從中學習一致性相似度矩陣.第2類是為各個視圖的數(shù)據(jù)生成相應的相似度矩陣，再利用各視圖的相似度矩陣生成一致的拉普拉斯矩陣[17]，從拉普拉斯矩陣中生成劃分矩陣，使用k均值聚類算法得到聚類結(jié)果.第3類是為每個視圖構(gòu)造好相似度矩陣后，直接利用譜聚類的思想，為所有視圖學習統(tǒng)一的劃分矩陣[18]，然后使用k均值算法進行聚類.第4類是基于協(xié)同訓練的思想[19]，利用視圖間的互補信息進行聚類.盡管該領域已有大量研究成果，但仍然存在不少挑戰(zhàn).首先，原始數(shù)據(jù)通常包含冗余信息和噪聲，很多算法忽略了這一問題.其次，在聚類過程中，每個視圖扮演的角色是不同的，不少算法將各個視圖同等對待.為了解決這些問題，本文提出了一種基于Markov鏈的多視圖譜聚類算法——一致性引導的自適應加權(quán)多視圖聚類(consensus guided auto-weighted multi-view clustering, CAMC)，主要思想如圖1所示.由圖1可知，該算法首先為原始數(shù)據(jù)的各個視圖構(gòu)建轉(zhuǎn)移概率矩陣，然后為所有視圖學習一致性轉(zhuǎn)移概率矩陣，最后執(zhí)行譜聚類算法.目標是為各視圖學習不同權(quán)重，并得到所有視圖的一致性鄰接矩陣.

Fig. 1 The framework of CAMC圖1 CAMC的整體框架

本文的主要貢獻有3個方面:

1) 為每個視圖構(gòu)造一個轉(zhuǎn)移概率矩陣，以減小原始數(shù)據(jù)中的冗余信息和噪聲對聚類性能的影響.

2) 以自適應加權(quán)的方式獲得一致性轉(zhuǎn)移概率矩陣，并對一致性轉(zhuǎn)移概率矩陣的拉普拉斯矩陣進行秩約束，以確保拉普拉斯圖中連通分量的數(shù)目與聚類的數(shù)目完全相等.

3) 在人造數(shù)據(jù)集上證明了CAMC是有效的；在7個真實數(shù)據(jù)集上的大量實驗表明，CAMC算法在聚類性能方面優(yōu)于其他單視圖和多視圖聚類基準算法.

1 相關工作

為了更加方便地介紹后面的內(nèi)容，本文在表1中對文中的符號進行了說明.由于本文提出的算法屬于基于Markov鏈的譜聚類算法，故在本節(jié)對該類算法的相關工作進行介紹.

Table 1 The Meaning of Notations表1 符號及含義

目前，已有研究[20-21]在聚類和Markov鏈之間建立了聯(lián)系.給定n個數(shù)據(jù)點的單視圖數(shù)據(jù)矩陣X∈d×n，X的相似度矩陣用S表示.計算S的一種常見方式是其中，i,j∈(1,n)，xi,xj分別表示第i、第j個向量，σ是標準差.之后構(gòu)建圖G=(V,EG,S)，其中V是頂點集，EG是邊集，S用來表示邊的權(quán)值.轉(zhuǎn)移概率矩陣定義為P=D-1S，其中D為對角矩陣，從Markov鏈的角度來看，pij是從節(jié)點Nodei一步到達節(jié)點Nodej的隨機行走概率，圖G存在平穩(wěn)分布π，其中譜聚類就是對圖G進行劃分，使Markov隨機行走盡量在同一簇內(nèi)進行.關于基于Markov鏈聚類的詳細信息，請參考文獻[20-21].

在基于Markov鏈的多視圖聚類研究方面，Xia等人[22]提出了魯棒多視圖譜聚類法(robust multi-view spectral clustering, RMSC).RMSC通過低秩和稀疏分解從所有視圖的數(shù)據(jù)中恢復了潛在的轉(zhuǎn)移概率矩陣，并將其作為相似度矩陣，使用譜聚類得到最終的結(jié)果.RMSC的目標函數(shù)為:

(1)

其中，P(v)表示第v個視圖構(gòu)造的轉(zhuǎn)移概率矩陣，P*是學到的轉(zhuǎn)移概率矩陣，E(v)是第v個視圖中學到的轉(zhuǎn)移概率矩陣和構(gòu)造矩陣之間的誤差.

Wu等人[23]提出了多視圖譜聚類的本質(zhì)張量學習法(essential tensor learning for multi-view spectral clustering, ETLMSC).ETLMSC將各個視圖得到的轉(zhuǎn)移概率矩陣疊成張量，對張量施加核范數(shù)的約束，確保張量的低秩性質(zhì)，并對張量進行旋轉(zhuǎn)來探索不同視圖之間的關系.ETLMSC的目標函數(shù)為:

(2)

盡管這些方法取得了不錯的結(jié)果，但仍有很多方面需要改進.從式(1)中可以得知，RMSC將各視圖平等對待，忽視了視圖所起作用的多樣性.ETLMSC使用張量來探索各視圖之間的關系，但是當計算最終的相似度矩陣時，直接將張量切片進行平均，忽略了各視圖之間的差異.由于我們提出的算法CAMC更為接近RMSC，故在實驗部分使用RMSC與CAMC進行對比.

2 一致性引導的自適應加權(quán)多視圖聚類

2.1 算法思想

基于Markov鏈的譜聚類算法很關鍵的一個環(huán)節(jié)是獲得最終轉(zhuǎn)移概率矩陣.本文使用文獻[24]中的算法為每個視圖學習相應的轉(zhuǎn)移概率矩陣，在RMSC的啟發(fā)下，利用核范數(shù)確保學到的一致性轉(zhuǎn)移概率矩陣P*是低秩的.該方案的表達式為:

(3)

其中,i,j∈(1,n).但是，這種方式忽略了各視圖之間的差異性，故為每個視圖分配了權(quán)重，即

(4)

其中，w(v)是第v個視圖的權(quán)值.

受到自動分配權(quán)值策略[9,25]的啟發(fā)，本文提出了一種自適應加權(quán)的策略來學習一致性的轉(zhuǎn)移概率矩陣.令w(v)為

(5)

則式(4)等價于

(6)

式(6)所學到的轉(zhuǎn)移概率矩陣中相連部分的數(shù)量是不確定的.假設簇的數(shù)量是c，為了使P*恰好有c個相連部分，對P*的拉普拉斯矩陣的秩進行約束.目標函數(shù)表達式設計為:

(7)

其中，LP*表示P*的拉普拉斯矩陣.

(8)

如圖1所示，CAMC先為原始數(shù)據(jù)的各個視圖構(gòu)建轉(zhuǎn)移概率矩陣；然后，利用式(8)為全部視圖學習一致性轉(zhuǎn)移概率矩陣；最后，將其作為輸入執(zhí)行譜聚類算法，得到聚類結(jié)果.所學的一致性轉(zhuǎn)移概率矩陣如圖2所示，同一簇內(nèi)的點之間存在轉(zhuǎn)移概率，不同簇之間轉(zhuǎn)移概率值為0，一致性轉(zhuǎn)移概率矩陣的秩等于簇的數(shù)目.

Fig. 2 An example of the consensus transition probability matrix P*圖2 對一致性轉(zhuǎn)移概率矩陣P*的示例

2.2 優(yōu) 化

CAMC的目標函數(shù)為式(8)，其等價于

(9)

其中，w(v)的值見式(5).

為了求解式(9)，本文采用交替方向乘子法(alternating direction method of multiplier, ADMM)[27]設計優(yōu)化策略.將矩陣變量Q作為輔助變量來替代核范數(shù)中的P*.式(9)可轉(zhuǎn)化為:

(10)

式(10)的求解可以轉(zhuǎn)換為求解5個子問題.

1) 求解w(v)，將其他變量固定，w(v)的值見式(5).

2) 求解P*，固定其他變量，關于P*的目標函數(shù)變?yōu)?/p>

(11)

其中，Y是拉格朗日乘子，μ是懲罰項參數(shù).對于不同的i，該問題是獨立的，故而有

(12)

(13)

式(13)可以通過投影算法[28]求解.

3) 求解F，固定w(v)，Q,P*時,F的值可以通過求解問題得出:

(14)

找出LP*的c個最小特征值，對應特征向量為F的解.

4) 求解Q，當w(v),P*,F固定不變時，式(9)變?yōu)?/p>

(15)

式(15)等價于

(16)

式(16)可通過奇異值閾值法[29]進行求解.

5) 更新乘子Y和懲罰項參數(shù)μ:

(17)

上述5個子問題是求解目標函數(shù)式(9)的核心內(nèi)容.CAMC的算法流程如算法1所示:

算法1.CAMC.

輸入:多視圖數(shù)據(jù)集X，超參λ1和λ2;

輸出:聚類結(jié)果.

② 為每個視圖構(gòu)建轉(zhuǎn)移概率矩陣；

③ whileiter

④iter=iter+1;

⑤ forvfrom 1 tomdo

⑥ 根據(jù)式(5)更新w(v);

⑦ end for

⑧ 根據(jù)式(13)更新P*;

⑨ 根據(jù)式(14)更新F;

⑩ 根據(jù)式(16)更新Q;

2.3 算法復雜度和收斂性

算法CAMC的求解涉及5個子問題.求解w的復雜度為O(mn)；求解P*時使用了矩陣的加法，復雜度為O(n2)；求解F時涉及了特征向量分解，復雜度為O(n3)；求解Q時使用了奇異值分解，復雜度為O(n3)；更新乘子Y的復雜度為O(n2)，所以整個算法的復雜度為O(n3+n2).

根據(jù)文獻[10]，式(14)是凸函數(shù)，由于F范數(shù)和核范數(shù)均是凸函數(shù)，根據(jù)文獻[30]，式(9)是凸的.

本文提出的優(yōu)化算法在每次迭代時，需要求解式(10)(13)(14)(16)(17).根據(jù)已有文獻[10,25]，這幾個問題都是凸的，這確保了算法1能夠收斂到問題的最優(yōu)解.

3 實 驗

為了對算法進行評估，在人造數(shù)據(jù)集和真實數(shù)據(jù)集兩大類數(shù)據(jù)集上進行了實驗，采用了7個常用的聚類指標：標準化互信息(normalized mutual information,NMI)、準確率(accuracy,ACC)、F分數(shù)(F)、調(diào)整后的蘭德指數(shù)(adjusted rand index,ARI)、精度(precision,P)、召回率(recall,R)、純度(Purity).這些指標的定義參見文獻[31]，它們的值越高，聚類效果越好.

3.1 人造數(shù)據(jù)集實驗分析

在文獻[32]提供的人造數(shù)據(jù)集雙月(Two-Moon)上進行了實驗.如圖3(a),3(b)所示，該數(shù)據(jù)集包含了2個視圖，每個視圖里的點都是2個月亮的形狀，對應著2個簇，每個簇中有100個點，每個視圖中都加上了0.12%的高斯噪聲.CAMC在此數(shù)據(jù)集上聚類得到的標簽和數(shù)據(jù)集中的標簽是完全一致的.為了直觀地對結(jié)果進行說明，進行了可視化展示.選取了距離較近但屬于2個不同簇的40個點，在一致性轉(zhuǎn)移概率矩陣中提取出來了相應的部分，對這40個點在2個視圖中使用學到的一致性轉(zhuǎn)移概率矩陣進行可視化，結(jié)果如圖3(c),3(d)所示.盡管這些點距離較近，在聚類時容易出錯，但CAMC能將它們分開，這表明了基于Markov鏈的方法是有效的.另外，該復雜圖形中存在噪聲，CAMC能有效將點分開證實了間接學習相似度矩陣和使用低秩正則化能夠減弱噪聲對聚類的影響.此外，圖4展示了為各視圖構(gòu)造的轉(zhuǎn)移概率矩陣和學習到的一致性轉(zhuǎn)移概率矩陣，明顯可以看出，學習到的一致性轉(zhuǎn)移概率矩陣具有更好的塊結(jié)構(gòu)，更適合聚類.基于自動加權(quán)機制進行聚類，能夠更有效地利用不同視圖之間的互補信息，因而能提升聚類性能.

Fig. 3 Two-Moon dataset analysis圖3 Two-Moon數(shù)據(jù)集分析

Fig. 4 The transition probability matrix visualization圖4 轉(zhuǎn)移概率矩陣的可視化

3.2 真實數(shù)據(jù)集簡介

本文選取了7個真實數(shù)據(jù)集進行實驗.數(shù)據(jù)集包括：英國廣播公司體育新聞數(shù)據(jù)集(BBCSport)[33]、三新聞源文本數(shù)據(jù)集(3Sources)[34]、微軟逐像素標記的圖像數(shù)據(jù)集v1(MSRC)[35]、Citeseer科學出版物引用網(wǎng)絡文本數(shù)據(jù)集(Citeseer)[36]、Mfeat手寫體識別數(shù)據(jù)集(Mfeat)[37]、新聞組數(shù)據(jù)集(NGs)[38]、100種植物葉子數(shù)據(jù)集(100leaves)[39].這些數(shù)據(jù)集的詳細信息如表2所示.

Table 2 Statistic Information of Datasets表2 數(shù)據(jù)集的相關信息

3.3 參數(shù)敏感性分析和算法收斂性驗證

CAMC中有2個超參λ1和λ2，用來平衡目標函數(shù)中3項之間的關系.這2個超參的值域為{0.000 1,0.01,0.1,1,10,100,1 000}.在3Sources和Mfeat數(shù)據(jù)集上，使用了網(wǎng)格化調(diào)參法對CAMC進行參數(shù)敏感性實驗，記錄聚類結(jié)果的準確率值和標準化互信息值，結(jié)果如圖5所示.

Fig. 5 Parameter sensitivity analysis on different datasets圖5 在不同數(shù)據(jù)集上的參數(shù)敏感性分析

Fig. 6 Convergence analysis on different datasets圖6 在不同數(shù)據(jù)集上的算法收斂性分析

從圖5中可以看出，當λ1>100時對結(jié)果較為敏感，當λ1<100時性能較為穩(wěn)定；參數(shù)λ2的變化對性能影響不大，但當λ2<1時聚類效果要更好一些.總的來說，CAMC的性能是比較穩(wěn)定的.

Fig. 7 The t-SNE visualization on NGs dataset圖7 在NGs數(shù)據(jù)集上的t-SNE可視化

3.4 性能可視化

為了進一步說明CAMC性能上的優(yōu)勢，在NGs數(shù)據(jù)集上，對每個視圖的原始數(shù)據(jù)和最終學習到的一致性轉(zhuǎn)移概率矩陣都通過t分布隨機鄰居嵌入(t-SNE)[40]進行可視化表示，如圖7所示.使用各種顏色區(qū)分不同的簇.相同顏色的點越近、不同顏色的點越遠表示簇的可分離性越好.從圖7中可以看出，學習到的一致性轉(zhuǎn)移概率矩陣的聚類效果明顯優(yōu)于原始數(shù)據(jù).主要原因在于CAMC能夠利用不同視圖之間的互補信息，為不同視圖學習最優(yōu)的權(quán)重.

3.5 對比算法

為了驗證CAMC的有效性，本文將CAMC與8種基準算法進行了比較.其中譜聚類(SC)[41]、低秩表示子空間聚類(LRR)[42]是單視圖聚類算法，基于共同正則化的聚類(CoReg)[43]、魯棒多視圖譜聚類(RMSC)[22]是經(jīng)典多視圖聚類算法，基于圖學習的多視圖聚類(MVGL,2017Transactions)[10]、基于圖的自加權(quán)多視圖聚類(SWMC,2017IJCAI)[44]、自適應加權(quán)法(AWP,2018KDD)[45]、稀疏多視圖譜聚類(SMVSC,2020Nerocomputing)[15]是最新多視圖聚類算法.對于每一種算法，都根據(jù)該算法所在的文獻在所有的數(shù)據(jù)集上調(diào)參.

3.6 真實數(shù)據(jù)集的實驗分析

本文選取了7個真實數(shù)據(jù)集來驗證CAMC的性能.在每個數(shù)據(jù)集上，先找出結(jié)果最好的參數(shù)，然后使用該參數(shù)的值重復進行30次實驗，記錄平均值和均值.結(jié)果如表3～9所示，每個數(shù)據(jù)集上每個評價指標中最好的2個結(jié)果加粗顯示.

Table 3 Clustering Results (Mean±Standard Deviation) on the BBCSport Dataset表3 在BBCSport數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

Table 4 Clustering Results (Mean±Standard Deviation) on the 3Sources Dataset表4 在3Sources數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

Table 5 Clustering Results (Mean±Standard Deviation) on the MSRC Dataset表5 在MSRC數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

Table 6 Clustering Results (Mean±Standard Deviation) on the Citeseer Dataset表6 在Citeseer數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

Table 7 Clustering Results (Mean±Standard Deviation) on the Mfeat Dataset表7 在Mfeat數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

Table 8 Clustering Results (Mean±Standard Deviation) on the NGs Dataset表8 在NGs數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

Table 9 Clustering Results (Mean±Standard Deviation) on the 100leaves Dataset表9 在100leaves數(shù)據(jù)集上的聚類結(jié)果(平均值±標準差)

由表3～9可知，在這9種算法中CAMC結(jié)果最好，它在BBCSport,3Sources,Citeseer,NGs,100leaves數(shù)據(jù)集上的評價指標結(jié)果基本上都是最優(yōu)的.特別是在BBCSport數(shù)據(jù)集上，在NMI,ACC,F,ARI,P等評價指標上，CAMC分別以10.9%,7.7%,11.5%,15.2%,13.4%的優(yōu)勢拉開了與第2名之間的距離.

從結(jié)果中，本文有4方面的思考:

1) 總的來說，多視圖算法的聚類性能要優(yōu)于單視圖算法.和單視圖算法相比，多視圖算法能夠利用來自不同視圖的多種互補信息，從而提高聚類的能力.

2) CAMC在多種類型的圖像和文本數(shù)據(jù)集上均表現(xiàn)優(yōu)異，這說明CAMC對各類型的數(shù)據(jù)集具有魯棒性.

3) CAMC的聚類性能遠優(yōu)于RMSC.這2種方法都是基于Markov鏈的多視圖譜聚類算法，RMSC將各個視圖同等對待，而CAMC則考慮了不同視圖之間的差異，為各個視圖學習最優(yōu)的權(quán)值，這表明為每個視圖學習相應的權(quán)值能提高聚類的準確性.

4) 在對比算法中，SWMC和AWP均考慮了不同視圖的差異性，但它們和CAMC仍然存在差距，這表明了基于Markov鏈聚類算法的有效性.

4 結(jié) 論

本文提出了一種基于Markov鏈的多視圖譜聚類算法，利用了多個視圖之間的互補信息，并考慮了各視圖在聚類中發(fā)揮的不同作用，為各視圖學到最優(yōu)權(quán)值.此外，該算法對一致性轉(zhuǎn)移概率矩陣的拉普拉斯矩陣進行了秩約束，以確保拉普拉斯圖中連通分量的數(shù)目與聚類的數(shù)目完全相等.基于ADMM，提出了一種優(yōu)化策略來對目標函數(shù)進行求解.在人造數(shù)據(jù)集和真實數(shù)據(jù)集上進行了大量實驗，結(jié)果表明了CAMC是有效的.將來，我們會基于錨點等策略將CAMC擴展到大規(guī)模數(shù)據(jù)集上.

作者貢獻聲明：于曉負責研究方案設計和實驗實現(xiàn), 以及論文設計、撰寫和修改; 劉慧設計研究方案，指導并參與論文修訂; 林毓秀負責數(shù)據(jù)的整理和校對; 張彩明參與論文修訂.