張繹凡 ,李婷 ,葛洪偉*

（1.江南大學人工智能與計算機學院，無錫，214122；2.江蘇省模式識別與計算智能工程實驗室(江南大學)，無錫，214122）

聚類是數(shù)據(jù)挖掘和模式識別領域中的一個重要分支，是一種無監(jiān)督的機器學習算法，旨在將數(shù)據(jù)集分成由類似的數(shù)據(jù)對象組成的多個類.過去，傳統(tǒng)的單視圖聚類占主導地位，隨著聚類技術的發(fā)展，單一視圖提供的信息有限，傳統(tǒng)單視圖聚類的研究到了瓶頸階段，因此對同一個數(shù)據(jù)的多角度描述應運而生.多視圖是指從不同角度對同一事物進行描述的視圖集合，例如，圖像可以通過顏色、紋理、形狀等不同特征進行描述，網(wǎng)頁數(shù)據(jù)可以由圖像、文本、超鏈接等進行描述，傳感器信號有時域和頻域上的分解［1］.這些都是多視圖數(shù)據(jù)，它們雖然表現(xiàn)出異質性，但本質上具有潛在相關性和多樣性.

多視圖聚類旨在利用視圖之間互補的特性，分析相互之間的關系，構建完善的約束，最終提升聚類效果.多視圖聚類大致可分為四種：（1）基于協(xié)同訓練的多視圖聚類.受協(xié)同訓練的思想啟發(fā)，Nigam and Ghani［2］將最大似然估計的思想與協(xié)同訓練相結合.Kumar and Rai［3］強制不同的視圖進行共同正則化，最小化不同視圖之間的拉普拉斯矩陣對應的特征向量.（2）基于多核學習的多視圖聚類方法，旨在探索多視圖數(shù)據(jù)的非線性結構.Huang et al［4］提出一種同時執(zhí)行多視圖聚類任務并學習內核空間匯總相似性關系的模型.由于該模型沒有考慮權重分配問題，Liu et al［5］根據(jù)每個視圖的每個內部簇分配的權重提出一種用于多視圖聚類的聚類加權核k均值方法.（3）基于圖學習的多視圖聚類方法，目標是在所有視圖中找到融合圖.Zhan et al［6］提出一種根據(jù)每個視圖的優(yōu)化圖獲得全局圖的多視圖譜聚類.（4）基于子空間學習的多視圖聚類方法.Wang et al［7］為了提高信息互補的實際效果，增強了不同視圖對應的子空間之間的排他性.Zhang et al［8］采取增強信息互補的另一種思路，設計自適應樣本加權策略以及自適應低級多內核學習來加強子空間自表示.這些方法大都直接計算數(shù)據(jù)集中的原始特征，存在噪聲與誤差，不能很好地適應較多視圖的數(shù)據(jù).

針對上述問題，Zhang et al［9］提出潛在嵌入空間的概念，通過間接方法獲取數(shù)據(jù)集中的特征，并利用該潛在嵌入表示進行聚類.Huang et al［10］在Zhang et al［8］的研究基礎上提出共享信息的優(yōu)化，使?jié)撛谇度氡硎靖鼫蚀_.由于現(xiàn)有的二次規(guī)劃求解較復雜，Chen et al［11］將二次規(guī)劃求解法改進為拉格朗日乘子法，進一步提升潛在嵌入多視圖聚類算法的效率.MCLES（Multi‐View Clustering in Latent Embedding Space）［12］在Zhang et al［8］的基礎上結合全局相似性學習以及聚類指標學習進行聚類，取得了較好的效果.但上述方法在潛在嵌入學習過程中僅僅注意了投影矩陣的相關約束，沒有充分利用視圖之間隱藏的多樣性信息，缺少局部信息的約束項，導致潛在嵌入空間存在部分信息無法被合理利用的問題.

為了解決上述問題，提出一種多樣性誘導的潛在嵌入多視圖聚類算法，多樣性指從不同視角學習的子空間表達式具有足夠的獨立性，能夠有效地利用不同視圖之間的互補信息.該方法將希爾伯特施密特獨立準則（Hilbert Schmidt Indepen‐dence Criterion，HSIC）與MCLES 融合在一個框架中，利用HSIC 平衡不同投影矩陣之間的多樣性，提升潛在嵌入學習的結果；同時，對潛在嵌入空間進行全局相似性學習和聚類指標學習，得到一致性親和矩陣對應的譜嵌入矩陣，并通過k‐means 得到最終的聚類結果.在六個公開數(shù)據(jù)集上進行的實驗證明該算法具有一定優(yōu)勢.

1 相關理論

1.1 符號與定義本文中，粗體大寫字母表示矩陣，粗體小寫字母表示向量，小寫字母表示標量.

定義一個具有V個視圖、N個樣本數(shù)據(jù)的多視圖數(shù)據(jù)集X={X1，X2，…，XV}，其中，Di表示第i個視圖的維度.對于矩陣X，Xi表示第i行，Xi，j表示第i行第j列的元素.Tr(X)，XT和‖X‖F(xiàn)分別表示矩陣X的秩、轉置和Frobenius范數(shù).I表示單位矩陣，1 表示元素全為1 的列向量.

1.2 潛在嵌入空間MCLES 中的潛在嵌入空間方法為每個數(shù)據(jù)點推斷一個共享的潛在表示R∈Rd×N，其中，d為潛在嵌入空間的維度，假設所有不同的視圖都起源于一個潛在的表示R.具體地，如圖1 所示，不同視圖可以用它們各自的投影矩陣{P1，…，Pi}進行重構，其中，Pi∈RDi×d，每個視圖的樣本數(shù)據(jù)表示為Xi=Pi Ri，i=1，2，…，V，并具有共享的潛在表示R.潛在嵌入空間方法和子空間自表示方法相比是一種全新的理論方法，能夠較全面地恢復數(shù)據(jù)隱藏的空間結構，對最后的聚類效果有較好的提升.

圖1 潛在嵌入空間示意圖Fig.1 Latent embedding space

MCLES 最終的目標函數(shù)式如下：

2 多樣性誘導的潛在嵌入多視圖聚類

2.1 算法模型根據(jù)式（1）的目標函數(shù)可知，MCLES 在數(shù)據(jù)樣本矩陣和投影矩陣的學習過程中僅僅注意了潛在嵌入學習，缺少局部信息的約束項.多視圖數(shù)據(jù)在不同視圖之間具有差異，即多樣性信息，所以MCLES 忽略了不同視圖之間的多樣性.為了解決這個問題，受Cao et al［14］的啟發(fā)，采用經(jīng)驗的HSIC 約束特定于視圖的投影矩陣.HSIC 具有以下特性：（1）通過將變量映射到一個再生希爾伯特空間來度量變量之間的依賴性，因此可以度量變量之間較復雜的關聯(lián)，適用于非線性相關的情況；（2）在測量變量依賴性時，不需要估計變量的聯(lián)合分布，具有計算優(yōu)勢；（3）經(jīng)驗的HSIC 可以被證明等價于矩陣乘積的跡運算，使方法更易求解且具有良好的收斂性.因此，引入HSIC 可以更好地平衡不同視圖矩陣之間的獨立性和相關性.

給定Z：={(x1，y1)，…，(xn，yn)}?X×Y，Z 為用于產(chǎn)生一系列n個聯(lián)合分布Pxy的獨立觀測數(shù)據(jù).經(jīng)驗HSIC 記作HSIC(Z，F(xiàn)，G)，可以被寫成如下形式：

其中，K，L∈Rn×n是Gram 矩陣且有kij=k(xi，xj)，lij=k(yi，yj)，k(xi，xj)和k(yi，yj)分別是X 和Y上的核函數(shù).hij=δij-1/n將Gram 矩陣中心化，使數(shù)據(jù)在特征空間具有零均值.

利用經(jīng)驗性HSIC 約束可以更真實地反映不同視圖之間的關系，提出多樣性誘導的潛在嵌入多視圖聚類模型（DiMCLES）.目標函數(shù)如下：

2.2 算法優(yōu)化在得到目標函數(shù)后采用交替迭代對目標函數(shù)求解，以下是求解的詳細過程.

固定R，Z，F(xiàn)，求解P，去除無關項，式（3）等價于優(yōu)化以下問題：

直接計算矩陣P較困難，為了有效地解決這個問題，將其劃分為V個子問題：

在計算Pm時，矩陣Pn(n≠m)是固定的.為了方便，采用內積核作為HSIC 的內核，即Km=PmT Pm，因此HSIC 可以寫成：

對式（7）求偏導并令其為零，得到矩陣針對每個視圖的更新式：

固定P，Z，F(xiàn)，求解R，去除無關項，式（3）等價于優(yōu)化以下問題：

使用交替向乘子法（Alternating Direction Method of Multipliers，ADMM），引入輔助變量A1，A2代替R，得到相對應的增廣拉格朗日函數(shù)為：

對A1和A2求偏導并令其為零，得到A1，A2以及Y的更新式：

固定P，R，F(xiàn)，求解Z，去除無關項，式（3）等價于優(yōu)化以下問題：

為方便求解，引入變量M，令M=ZT Z，式（12）可以寫成以下形式：

對式（13）按列展開得到：

式（15）是一個標準的二次規(guī)劃問題，可用現(xiàn)成的二次規(guī)劃包［15］對其進行求解.

固定P，R，Z，求解F，去除無關項，式（3）等價于優(yōu)化以下問題：通過計算矩陣Z的c個最大特征值對應的c個特征向量得到譜嵌入矩陣F的解.

2.3 算法流程和時間復雜度分析算法流程如下所示.

3 實驗設置

3.1 數(shù)據(jù)集介紹在六個廣泛使用的數(shù)據(jù)集上進行相關實驗：3Sourses［11］，Notting‐Hill［11］，Yale［12］，MSRCv1［12］，ORL［12］，BBCSport［12］.數(shù)據(jù)集的具體信息如表1 所示.

表1 實驗使用的數(shù)據(jù)集介紹Table1 Introduction of datasets used in experiments

3Sourses：是多來源的新聞數(shù)據(jù)集，包含來自BBC、衛(wèi)報和路透社的新聞，由來自六個類的169個新聞對象組成.實驗中使用了三個視圖，分別為BBC（視圖1）、衛(wèi)報（視圖2）和路透社（視圖3）.

圖2 DiMCLES，LMSC 和MCLES 在六個基準數(shù)據(jù)集上的收斂曲線Fig.2 Convergence curves of DiMCLES，LMSC and MCLES on six benchmark datasets

圖3 在六個基準數(shù)據(jù)集上根據(jù)ACC對α，β，γ，λ和d 的參數(shù)分析Fig.3 Parameters analysis on α，β，γ，λ and d in terms of ACC on six benchmark datasets

Notting‐Hill：是從電影《Notting‐Hill》中獲得的視頻人臉數(shù)據(jù)集，包含4660 張人臉圖像.每個演員為一個類別，選擇五個主要演員的面孔，隨機采樣每個演員的110 張面部圖像.實驗中使用了三個視圖，分別是強度特征（視圖1）、LBP 特征（視圖2）和Gabor 特征（視圖3）.

Yale：是廣泛使用的人臉圖像數(shù)據(jù)集，由15個不同主題的灰度圖像組成，每個主題由11 張圖像組成，共165 張.圖像的變化包括右光、中心光、左光、是否戴眼鏡、是否快樂、正常、驚訝、眨眼和困倦.實驗中使用了尺寸分別為4096（視圖1）、3304（視圖2）和6750（視圖3）的三個視圖.

MSRCv1：是一個圖像數(shù)據(jù)集，由屬于七個類別的210 個對象組成，分別是飛機、建筑、樹、汽車、牛、臉和自行車.實驗中使用了四個視圖，分別為CM 特征（視圖1）、GIST 特征（視圖2）、LBP特征（視圖3）和GENT 特征（視圖4）.

ORL：是廣泛使用的人臉圖像數(shù)據(jù)集，由屬于40 個不同主題的400 張人臉圖像組成，每個主題包含10 張圖像.每個主題的圖像都在不同的時間、光線、面部表情（是否睜眼、是否微笑）和面部細節(jié)（是否戴眼鏡）下拍攝.實驗中使用了三個視圖，分別為強度特征（視圖1）、LBP 特征（視圖2）和Gabor 特征（視圖3）.

BBCSport：是一個文檔數(shù)據(jù)集，由2004-2005 年五個主題領域的BBC Sport 網(wǎng)站體育新聞的544 個文檔組成，分別是商業(yè)、體育、政治、娛樂、科技.實驗中使用了兩個視圖，其維度分別為3183（視圖1）和3203（視圖2）.

3.2 對比算法介紹將本文提出的方法與10 種多視圖聚類方法進行比較：

SC（Spectral Clustering）：對每個視圖進行單視圖譜聚類，取多個視圖中最好的數(shù)據(jù)，記作SCbest.

ConcatePCA‐SC：是SC 方法的擴展，使用PCA 方法降維所有視圖的特征.

Co‐Reg（Co‐Regularized Spectral Cluster‐ing）：強制所有視圖執(zhí)行共同正則化［2］.

Co‐Training（Co‐Training Multi‐View Clus‐tering）：將最大似然估計與協(xié)同訓練相結合［16］.

Min‐Disagreement（Spectral Clustering with Two Views）：是基于最小化分歧的多視圖譜聚類［17］.

RMSC（Robust Multi‐View Spectral Cluster‐ing）：是使用馬爾可夫鏈進行聚類的魯棒多視圖譜聚類［17］.

LMSC（Latent Multi‐View Subspace Cluster‐ing）：根據(jù)多個視圖的共同潛在結構發(fā)現(xiàn)子空間結構［9］.

MVGL（Graph Learning for Multi‐view Clus‐tering）：根據(jù)每個視圖的優(yōu)化圖獲得全局圖［6］.

MCLES：根據(jù)視圖的潛在結構進行潛在嵌入學習、全局結構學習［12］.

LSRMSC（Latent Shared Representation for Multi‐View Subspace Clustering）：是恢復潛在共享表示的多視圖聚類［10］.

3.3 實驗結果與分析使用精度（Accuracy，ACC）、標準化交互信息（Normalized Mutual In‐formation，NMI）、純度（Purity，PUR）、蘭德指數(shù)（Rand Index，RI）作為聚類指標，指標的數(shù)值越高，表示聚類效果越好.由于算法和最后的k‐means 算法框架存在隨機性問題，因此實驗進行20次，結果取20 次的平均值以及標準差.

表2～7 給出了不同算法在六個公開數(shù)據(jù)集上的聚類實驗結果，表中黑體字表示結果最優(yōu)，括號中的數(shù)字為方差，表7 中的NA 表示該算法不適合該數(shù)據(jù)集對應的聚類指標.

表2 不同算法在3Sources 數(shù)據(jù)集上的聚類表現(xiàn)Table 2 Clustering performance of different algo?rithms on 3Sources

表3 不同算法在Notting?Hill 數(shù)據(jù)集上的聚類表現(xiàn)Table 3 Clustering performance of different algo?rithms on Notting?Hill

表4 不同算法在Yale 數(shù)據(jù)集上的聚類表現(xiàn)Table 4 Clustering performance of different algo?rithms on Yale

表5 不同算法在MSRCv1 數(shù)據(jù)集上的聚類表現(xiàn)Table 5 Clustering performance of different algo?rithms on MSRCv1

表6 不同算法在ORL 數(shù)據(jù)集上的聚類表現(xiàn)Table 6 Clustering performance of different algo?rithms on ORL

表7 不同算法在BBCSport 數(shù)據(jù)集上的聚類表現(xiàn)Table 7 Clustering performance of different algo?rithms on BBCSport

大多數(shù)情況下，DiMCLES 優(yōu)于相關算法或具有一定競爭力，尤其是在3Sources 和Notting‐Hill 上.和MCLES 相比，在3Sources上，Di‐MCLES的ACC提升11.21%，NMI提升5.37%，PUR提升1.42%，RI提升0.43%；在Notting‐Hill上，ACC提升9.95%，NMI提升8.57%，PUR提升7.65%，RI提升3.32%.同時，DiMCLES 在Notting‐Hill，MSRCv1 和BBCSport 上的方差為0，穩(wěn)定性很好，在其余數(shù)據(jù)集上的穩(wěn)定性也不差.但在ORL 上的表現(xiàn)較差，可能是因為ORL 各個視圖之間的差異性較大，算法無法很好地將較大的差異性整合到一致性親和矩陣中.

在多數(shù)真實數(shù)據(jù)集上的實驗結果證明Di‐MCLES 算法優(yōu)于RMSC，LMSC，MCLES，MVGL 等多視圖子空間聚類方法，這是因為DiMCLES 能夠較好地提取多視圖數(shù)據(jù)不同視圖之間的多樣性潛在信息.

3.4 收斂性分析為驗證DiMCLES 的收斂性，圖2 展示了DiMCLES，MCLES 和LMSC（Latent Multi‐View Subspace Clustering）［9］在六個基準數(shù)據(jù)集上的目標函數(shù)圖像.由于LMSC 采用零初始化，因此目標函數(shù)有一段先上升的過程.由圖可見，DiMCLES 在BBCSport 和3Sources 上前10 次迭代急劇下降，在15 次迭代時基本趨于穩(wěn)定；在其余數(shù)據(jù)集上均為前5 次迭代急劇下降再趨于平穩(wěn).和LMSC 相比，DiMCLES 有較好的收斂性和穩(wěn)定性，與MCLES 的收斂性總體相似，在Not‐ting‐Hill 和BBCSport 上略有提升.證明Di‐MCLES 的收斂速度較快，基本能在10 次之內達到收斂，且收斂性較好.

3.5 參數(shù)分析DiMCLES 算法共有五個參數(shù)，在六個基準數(shù)據(jù)集上分析五個參數(shù)對DiMCLES算法精度的影響，實驗結果如圖3 所示.由圖可知，參數(shù)α在[ 0.5，1 ]時，算法的穩(wěn)定性較好.參數(shù)β在[ 0.04，0.08 ]時，算法在除了Notting‐Hill以外的其他數(shù)據(jù)集上均有較好的穩(wěn)定性，這是由于目標函數(shù)在Notting‐Hill 上對非平凡解具有一定敏感性，造成該區(qū)間內的ACC存在20%左右的上下波動.參數(shù)γ在[ 0.001，0.005 ]時，參數(shù)λ在[ 0.2，0.35 ]時，算法的穩(wěn)定性較好.參數(shù)d在[ 40，100 ]時，算法性能趨于平穩(wěn)，但在40 以下波動較大，這是因為潛在嵌入空間維度過小時，算法無法穩(wěn)定地描述原始空間的特征，導致ACC出現(xiàn)較大的波動.

3.6 t?SNE 可視化分析為了更直觀地觀察DiMCLES 的聚類性能，采用t‐SNE（t‐Distribut‐ed Stochastic Neighbor Embedding）將每個視圖的原始特征及一致性親和矩陣映射到二維空間，對得到的降維樣本點進行可視化分析.為了方便觀察，選取聚類數(shù)較少的MSRCv1 和3Sources 進行數(shù)據(jù)可視化分析，實驗結果如圖4 所示，圖中不同顏色表示不同聚類類別.由圖可見，DiMCLES在MSRCv1 上較好地保留了原始數(shù)據(jù)（視圖2 和視圖4）的底層結構，不同顏色的簇內間距比LMSC更緊湊.DiMCLES 在3Sources 上保留了原始數(shù)據(jù)視圖部分的底層結構，和LMSC 相比，在呈現(xiàn)聚類底層結構上有較明顯的提升.因此，DiM‐CLES 算法得到的一致性相似表示比每個視圖的原始特征更能體現(xiàn)良好的聚類結構，進一步證實該算法具有一定優(yōu)勢.

4 結論

本文提出一種多樣性誘導的潛在嵌入多視圖聚類，使用特定于視圖的投影矩陣從多視圖數(shù)據(jù)中恢復潛在嵌入空間，提取各個視圖中的潛在信息，采用經(jīng)驗的希爾伯特施密特獨立準則約束特定于視圖的投影矩陣，保留視圖之間的信息多樣性.在統(tǒng)一的優(yōu)化框架下進行潛在嵌入學習、多樣性學習、全局相似性學習以及聚類指標學習.在真實數(shù)據(jù)集上的收斂性分析、參數(shù)敏感性分析及可視化分析實驗證明了該算法在收斂性、參數(shù)穩(wěn)定性以及保留聚類底層結構上具有一定優(yōu)勢.