劉瑞秀，高艷麗，鄧趙紅+，王士同

1.江南大學 數字媒體學院，江蘇 無錫 214122

2.江南計算技術研究所，江蘇 無錫 214083

1 引言

聚類是一種基于相似性信息，將對象或數據樣本劃分為若干組或類的方法。聚類是一種無監(jiān)督學習技術，它作為一種重要的數據處理方法，在數據挖掘、圖像處理、模式識別等領域有著廣泛的應用。傳統(tǒng)的聚類分析方法主要有K-means[1-3]、FCM（fuzzy C-means）[4-6]、MEC（maximum entropy clustering algorithm）[7-8]、PCM（possibilistic C-means algorithm）[9-10]、譜聚類[11-12]等。這些方法具有計算簡單、速度快等特點，并且有著廣泛的應用領域。但是，隨著現(xiàn)代技術的發(fā)展，所采集數據的大小、屬性等越來越復雜。許多數據集都可以用不同的屬性集描述，即多視角數據。例如一個文檔可以被翻譯成英語、漢語兩種語言；一個網頁可以用兩個視角描述，一個是網頁上出現(xiàn)的文本，另一個是指向該網頁的超鏈接上的文本。不同的視角之間通常提供兼容和互補的信息。由于傳統(tǒng)的聚類分析方法只使用數據樣本的一個特征集或一個視角，其在處理多視角數據集時，不能充分利用視角與視角間的關聯(lián)性。因此，如何從多視角數據中整合信息，以獲得更好的聚類性能已成為機器學習中的一個重要的課題。

近年來，為了提高多視角聚類算法的性能，已經開發(fā)了許多多視角聚類方法。文獻[13]基于期望最大化提出了協(xié)同聚類算法Co-EM（collaborative expectationmaximization algorithm）算法；同樣基于協(xié)同的思想，文獻[14]提出了一種雙視角譜聚類的算法。文獻[15]提出了多視角譜聚類算法，這些都是早期基于協(xié)同思想的多視角聚類算法。基于經典的K-means算法，文獻[16]提出了雙層變量自動加權聚類算法TW-Kmeans。通過在經典的模糊C-均值（FCM）中引入協(xié)同的思想，文獻[17]提出了一種協(xié)同聚類算法Co-FC（collaborative fuzzy clustering）算法。文獻[18]基于FCM算法提出多視角模糊聚類算法Co-FKM（collaborative fuzzyK-means），該算法通過在目標函數中引入一個懲罰項，減少了不同視角之間劃分的不一致性。文獻[19]以經典的FCM 算法為框架，提出了多視角模糊聚類Co-FCM算法，然后為了識別每個視角的重要性程度，文獻[19]基于香農熵又提出了其增強版本多視角加權協(xié)同模糊聚類算法WV-Co-FCM。文獻[20]在經典的FCM 算法中引入了最小最大優(yōu)化項，提出了多視角模糊聚類算法MinimaxFCM。

另一方面，一些文獻提出通過不同的方法將多視角數據從不同的特征空間轉換到一個共同的低維特征空間。這個低維空間的數據就是嵌入在多視角數據的隱性信息。例如文獻[21]提出了一種基于聯(lián)合非負矩陣分解的多視角聚類算法，該算法首先通過聯(lián)合非負矩陣分解方法將從每個視角學習的系數矩陣規(guī)范化成一個共同的一致性矩陣，然后直接應用K-means或其他聚類算法對一致性矩陣聚類。文獻[22]基于核典范相關分析提出了相關譜聚類算法，該算法首先將多視角數據從多個特征空間映射到一個共同的低維子空間，然后應用K-means等聚類算法對低維空間的數據進行聚類。文獻[23]基于無向潛在的空間馬爾可夫網絡，通過提出一個通用的大邊緣學習框架來發(fā)現(xiàn)由多個視角共享的預測潛在子空間表示。

盡管上述文獻提出的多視角聚類方法為解決多視角聚類問題提出了可行的方案，并且也都取得了很好的聚類性能，但是有兩個主要的缺點。第一，一些多視角聚類算法[16-19]主要運用多視角數據集的原始特征聚類，而沒有深入挖掘各視角間存在的隱性信息，這些隱性信息往往對聚類效果起重要的作用。第二，一些多視角聚類算法[21-23]試圖發(fā)現(xiàn)嵌入在多視角數據中的隱性信息并基于隱性信息進行聚類，但此類算法會不同程度地丟失原始特征的信息。這是由于原始的各視角數據更多地反映了個性化信息，僅用隱性信息會過多地偏重于共性信息，而對個性化信息沒能有效使用。多視角學習的關鍵是如何綜合利用各視角間個性化信息和共性信息。在多視角聚類中，如何將個性化信息和共性信息有效融合起來，是一個具有挑戰(zhàn)性的課題。

針對上述挑戰(zhàn)，本文提出了融合稀疏隱視角信息學習的多視角聚類算法。該算法首先通過求解一個多視角稀疏隱信息學習模型得到多視角數據共享的稀疏表示系數矩陣，即隱性信息。該隱性信息在一定程度上描述了不同數據點之間的共性信息，并且具有稀疏性。然后，采用協(xié)同學習的方式同時對原始特征集和隱性信息聚類，同時引入香農熵策略自適應地調整不同原視角的權重。將上述策略應用到經典的FCM 聚類框架，得到融合稀疏隱視角信息學習的多視角聚類算法。

2 相關工作

2.1 多視角聚類

傳統(tǒng)的單視角聚類算法處理多視角數據的框架如圖1所示。在處理多視角數據時，傳統(tǒng)的聚類方法通常獨立地考慮每個視角，并將每個視角視為獨立的聚類任務，分別對每個視角進行聚類獲得每個視角下的劃分矩陣，然后使用簡單加權或集成學習機制[24-25]獲得全局的劃分矩陣。這種方式雖然為單視角算法處理多視角數據提供了一種可行的方法，但是簡單地進行加權整合沒有考慮到視角與視角間的關聯(lián)性，這在一定程度上會造成聚類效果不佳。與此不同的是，多視角聚類充分利用來自不同視角的信息，通過運用不同視角之間的相關性和協(xié)作來訓練模型?，F(xiàn)有的多視角聚類算法大致可以分為三類。第一類算法在聚類過程中實現(xiàn)視角間的協(xié)同學習[16-20]。第二類算法試圖發(fā)現(xiàn)嵌入在多視角數據中共同低維子空間的表示，然后再用某種單視角聚類算法對這個數據進行聚類[21-23]。第三類就是后期融合[26-27]，也就是分別處理每個視角的數據，最終的聚類結果來自每個單獨的視角聚類結果的整合。例如文獻[26]通過引入映射函數，使得來自不同視角的集群具有可比性，同時從多個視角的多個集群中學習最佳的集群；文獻[27]基于在單個數據集上計算不同的相似矩陣，并且聚合形成組合相似度矩陣，然后將其用于獲得最終聚類結果。

Fig.1 Classical framework of single view clustering algorithms for multi-view data圖1 經典的單視角聚類算法處理多視角的框架

2.2 稀疏表示

近年來，稀疏表示[28-29]（sparse representation，SR）在模式識別、圖像處理等研究領域受到了廣泛的關注和研究，其目的就是在給定的字典中，用盡可能少的原子的線性組合來表示數據，由此獲取數據樣本之間的聯(lián)系。最簡單的稀疏表示模型是：

其中，||c||0是l0范數，用來計算c中非零元素的個數；y∈Rd是數據樣本，D∈Rd×K是字典矩陣，x∈RK是系數向量。由于式（1）是NP難問題，因此通常用l1范數來代替l0范數。字典的選取是至關重要的，許多稀疏表示模型都用數據集本身作為字典，即稀疏自表示。許多算法都采用數據集本身作為字典，例如文獻[28]使用數據集本身作為字典，提出了一種稀疏子空間聚類算法（sparse subspace clustering，SSC）；文獻[29]提出了一種低秩表示的子空間聚類方法（low rank representation，LRR）。通過SSC、LRR 等算法得到的稀疏表示系數矩陣能很好地反映數據集的潛在的群結構信息，并且具有稀疏性，從中能夠很好地發(fā)現(xiàn)數據樣本間的關系。這促使把稀疏表示方法應用到多視角聚類中。

3 融合稀疏隱視角信息學習的多視角聚類

3.1 多視角稀疏隱信息抽取

給定一個多視角數據集X={X(1)X(2),…,X(K)}，共K個視角，第k個視角的樣本集用矩陣表示為，1 ≤k≤K。其中N表示樣本個數，dk表示第k個視角的特征數。通過解決如下優(yōu)化問題得到多視角數據的稀疏隱視角信息：

其中，Z∈RN×N是多視角數據共享的稀疏表示系數矩陣，即隱視角。||.||F是Frobenius范數，||.||1是l1范數，diag(Z) 是隱視角Z的對角線元素，并且約束條件diag(Z)=0可避免平凡解，即避免每個樣本用自身表示。

在式（2）中，每一項的描述如下：

（2）第二項||Z||1是l1正則化項，該項的目的是使隱視角盡可能地稀疏。

（3）第三項是流形正則化項，該項是為了維持每個視角中的原始特征的流形結構。對于第k個視角，如果兩個數據點在原始的特征空間中彼此接近，那么在隱視角中，這兩個數據點也應該是彼此接近。第k個視角的相似度矩陣為S(k)，讓，則有：

其中，L(k)=D(k)-S(k)是圖拉普拉斯矩陣。

（4）λ和η是正則化參數，分別平衡相應項的影響。

為了求解式（2），首先引入一個輔助變量C，則式（2）被轉換為：

采用交替方向乘子法（alternating direction method of multipliers，ADMM）[30]求解式（4）。由此可獲得式（4）的增廣拉格朗日形式為：

（1）固定Z和Q，優(yōu)化C。

其中，cj、zj、qj和分別是C、Z、Q和的第j列，j=1,2,…,N?？梢允褂梦墨I[31-32]中的策略求解式（7），式（7）有閉式解。由此可得C的更新規(guī)則如下：

（2）固定C和Q，優(yōu)化Z。

對上式Z求偏導數并使其導數為0，可得：

因此可以通過求解下式得到Z的更新公式：

（3）固定Z和C，更新乘子Q。

乘子Q可以簡單地按照以下規(guī)則更新：

因此，通過ADMM方法求解式（4）的完整的算法描述如算法1所示。

算法1ADMM方法求解式（4）

輸入：給定一個多視角數據集X={X(1),X(2),…,X(K)}，共K個視角，第k個視角的樣本集為1 ≤k≤K，參數λ、η。

1.初始化Q=0，Z=C=0，ρ=1.1，迭代閾值ε=10-6；

2.根據式（8）更新C；

3.通過求解式（12）更新隱視角Z；

4.根據式（13）更新Q；

5.更新μ=μρ；

6.如果||Z-C||∞＜ε，則算法停止迭代循環(huán)，否則返回步驟2；

輸出：稀疏隱視角Z。

3.2 融合稀疏隱視角信息學習的多視角聚類算法

給定一個多視角數據集X={X(1),X(2),…,X(K)}，共K個視角，第k個視角的樣本集為通過算法1，可以獲得多視角數據共享的稀疏隱視角數據。該隱視角數據在一定程度上反映了多視角數據的全局結構信息，并且具有稀疏性。因此，基于原始的特征集和隱視角數據，本文提出了一種新的多視角聚類算法，即融合稀疏隱視角信息學習的多視角聚類算法，其目標函數為：

其中，Z=[z1,z2,…,zN]∈RN×N是隱視角數據；U是C×N的模糊劃分矩陣；V={V(1)，V(2)，…，V(K)}是K個原視角的聚類中心的集合，是第k個原視角的聚類中心矩陣，表示第k個原視角的聚類i的類中心；是隱視角的聚類中心矩陣，表示隱視角的聚類i的類中心；向量w=[w1,w2,…,wK]是原視角劃分權重的集合，wk是分配給第k個原視角的權重；模糊指數m＞1；α是正則化參數。

為了自適應調整各原視角的權重，式（14）引入了香農熵正則化項。讓，且wk≥0，將各原視角權重看作概率分布，則其香農熵表示為。最小化負香農熵趨向于使得各個視角具有相等的重要性。β是正則化參數，用來控制香農熵正則化項的影響。

對于式（14），這里給出如下的進一步說明：一方面，如果聚類目標函數僅考慮在聚類數據上各視角的聚類緊度，即文中式（14）的第一項，則最小化該項則趨向于讓類內緊度最小的視角占有很大重要性，而其他視角的作用完全被忽略；一方面，最大化各視角權重對應的香農熵，即最小化負香農熵趨向于使得各個視角具有相等的重要性，這在沒有任何先驗信息作指導時是合理的。上述兩種情況都走上了極端，因此通過引入正則化參數β來平衡兩項的作用是一種較好的處理方式，通過調節(jié)參數，可得到最佳的聚類效果。

3.3 目標函數的優(yōu)化

通過迭代求解如下4個子問題最小化式（14）：

問題1固定和，并解決子問題

問題2固定并解決子問題

問題3固定并解決子問題

問題4固定并解決子問題

（1）問題1的解決方案由定理1給出。

定理1當最小化時的必要條件為：

證明利用給定的模糊劃分矩陣、隱視角的類中心矩陣和權重向量，對目標函數求偏導，并令，可得：

由此定理1得證。 □

（2）問題2的解決方案由定理2給出。

定理2當最小化時的必要條件為：

證明利用給定的模糊劃分矩陣、原視角的類中心矩陣和權重向量，對目標函數求偏導，并令，可得：

由此定理2得證。 □

（3）問題3的解決方案由定理3給出。

定理3當最小化時的必要條件為：

證明對于目標函數（14），由于有一個約束條件,uij∈[0,1],1 ≤j≤N，則可以建立如下的拉格朗日函數：

上式分別對uij、γ1求導，并使得導數為0，得到：

進而得到：

由此定理3得證。 □

（4）問題4的解決方案由定理4給出。

定理4當最小化時的必要條件為：

證明對于目標函數（14），由于有一個約束條件則可以建立如下的拉格朗日函數：

上式分別對wk、γ2求導，并使得導數為0，得到：

進而得到：

由此定理4得證。 □

3.4 算法描述

根據3.3節(jié)推導的參數學習規(guī)則，下面給出所提算法的具體過程，如算法2所示。

算法2融合稀疏隱視角信息學習的多視角聚類算法

輸入：多視角數據集X={X(1),X(2),…,X(K)}，共K個視角，第k個視角的樣本集為參數α、β，模糊指數m，迭代閾值ε，當前迭代次數t，聚類數目n。

1.由算法1得到隱視角數據Z；

2.初始化隨機產生歸一化的隸屬度uij，隨機產生歸一化的原視角權重wk；

5.根據式（19）更新uij；

6.根據式（24）更新各原視角的權重wk；

7.如果||Jt+1-Jt||＜ε，則算法停止迭代循環(huán)，否則返回步驟3。

輸出：模糊劃分矩陣U，原視角聚類中心點隱視角聚類中心點，各原視角權重wk。

4 實驗研究

4.1 數據集

為了驗證本文所提算法的聚類有效性，本文選擇了5個多視角數據集進行實驗，這些數據集分別是Multiple Features 數據集、Image Segmentation 數 據集、Dermatology數據集、3-Sources數據集[33]和WebKB數據集。這些數據集的信息統(tǒng)計如表1所示。

Table1 Statistics of multi-view datasets表1 多視角數據集統(tǒng)計

（1）Multiple Features 數據集來自于UCI 數據集庫。數據集由2 000個樣本組成，其中視角1是傅里葉系數視角，該視角描述字符形狀的傅里葉系數，視角2是Zernike矩視角，描述字符形狀的Zernike矩。

（2）Image Segmentation 數據集來自于UCI 數據集庫，由2 310個樣本組成，包含兩個視角，分別是形狀視角和RGB視角。

（3）Dermatology數據集來自于UCI數據集庫，由366個樣本組成，其中視角1是組織病理學視角，視角2是臨床視角。

（4）3-Sources數據集是從3個在線新聞來源收集的，選擇所有3個來源報道的169個新聞故事，這些故事被手工分成6類，每個來源看作一個故事的視角。

（5）WebKB數據集由4個大學的網頁組成，每個網頁由3個視角組成：網頁上的文本、指向它的超鏈接上的錨文本以及標題中的文本。選擇其中1個大學的網頁作為本文實驗的數據集。

4.2 實驗設置

為了驗證本文所提算法的聚類性能，本文選擇了5個聚類算法作對比。通過比較5個多視角數據集在本文所提算法和對比算法上的實驗結果來驗證本文所提算法的聚類性能。實驗中采用的對比算法有基于多任務的組合K-means 算法（CombKM）[34]、基于樣本與特征空間協(xié)同聚類的Co-clustering 算法[35]、多視角模糊聚類算法Co-FKM[18]、多視角雙層變量自動加權聚類算法TW-K-means[16]、基于聯(lián)合非負矩陣分解的多視角聚類算法MultiNMF[21]。

本文采用歸一化互信息（normalized mutual information，NMI）36-37]、芮氏指標（rand index，RI）[37-38]、精度（Precision）[39]3種評價指標評估各聚類算法的聚類性能。3種評價指標的取值范圍均為[0，1]，取值越高，表示算法的聚類性能越好。

（1）歸一化互信息（NMI）

（2）芮氏指標（RI）

（3）精度（Precision）

其中，ni,j表示類i中的樣本被分到第j個聚類的數據樣本量；ni表示類i所包含的數據樣本量；nj表示第j個聚類所包含的數據樣本量；f00表示數據點具有不同的類標簽并且屬于不同類的配對點數目；f11則表示數據點具有相同的類標簽并且屬于同一類的配對點數目；N表示整個數據樣本的總量大小。

在本文實驗部分，采用網格搜索策略確定每個算法的最優(yōu)參數，采用的尋優(yōu)范圍具體見表2。實驗結果均由相關算法在最優(yōu)參數下運行10次得到的均值及方差所組成。

4.3 實驗分析

表3至表7分別顯示了在5個多視角數據集上，本文所提算法和其他5個對比算法在3個評價指標上的實驗結果。為了直觀地比較各個算法的聚類性能，圖2、圖3和圖4分別繪制了在所有數據集上每種算法的平均NMI、RI和Precision的值。

通過觀察表3至表7的實驗結果，可以得到如下的結論。

和其他聚類算法相比，本文算法在5個多視角數據集上的聚類結果都是最高的。

本文所提算法明顯優(yōu)于多任務的組合K-means算法CombKM。從多視角數據集在CombKM算法上的聚類結果可以看出，簡單地將多視角數據樣本進行融合并不能取得較好的聚類性能。

通過觀察5個數據集在多視角聚類算法TW-Kmeans、Co-FKM上的結果可以看出，本文所提算法體現(xiàn)了一定的聚類優(yōu)勢。原始的多視角數據更多地反映了各視角間個性化信息。TW-K-means和Co-FKM算法在聚類過程中均只利用原始的特征集進行聚類，而忽略了共性信息對聚類效果的影響。但是，本文所提算法通過引入隱性信息使得共性信息得到有效的利用，實現(xiàn)了個性化信息和共性信息的協(xié)同學習，這在一定程度上提高了算法的聚類性能。

MultiNMF 算法采用非負矩陣分解策略進一步挖掘了多視角數據之間的隱性信息，提高了算法的聚類性能。但是，MultiNMF 算法僅利用隱性信息會過多地偏重于共性信息，而未能有效利用個性化信息。與MultiNMF算法不同，本文所提算法不僅挖掘多視角數據的隱性信息，而且在聚類過程實現(xiàn)了隱性信息和原始特征集的協(xié)同學習，大大提高了算法的聚類性能。

通過觀察圖2、圖3和圖4，可以直觀地看出本文算法優(yōu)于其他算法。多視角聚類算法Multi-NMF、Co-FKM和TW-K-means也都取得了良好的聚類性能。

Table 2 Parameter setting of algorithms表2 算法參數設置

Table 3 Performance of algorithms on Multiple Features dataset表3 各算法在Multiple Features數據集上的性能

Table 4 Performance of algorithms on Image Segmentation dataset表4 各算法在Image Segmentation數據集上的性能

Table 5 Performance of algorithms on Dermatology dataset表5 各算法在Dermatology數據集上的性能

Table 6 Performance of algorithms on 3-Sources dataset表6 各算法在3-Sources數據集上的性能

Table 7 Performance of algorithms on WebKB dataset表7 各算法在WebKB數據集上的性能

Fig.2 Mean NMI of each algorithm on all datasets圖2 所有數據集上每種算法的平均NMI

Fig.4 Mean Precision of each algorithm on all datasets圖4 所有數據集上每種算法的平均Precision

綜上所述，在對多視角數據進行聚類時，本文所提算法的聚類性能優(yōu)于其他聚類算法。

4.4 隱性信息的影響及分析

多視角學習的關鍵是如何綜合利用各視角間個性化信息和共性信息，原始的各視角數據更多地反映了個性化信息，隱性信息的引入使得共性信息也得到了較充分的應用。這也是本文所提算法依據的核心思想。

為了驗證將隱性信息引入到本文算法中的優(yōu)勢，本節(jié)對隱性信息對多視角聚類性能的影響進行了實驗分析。分別在有隱性信息和無隱性信息情況下，對本文算法的聚類結果進行了比較。由于空間限制，只給出NMI指標值，具體結果見表8，另外兩個評價指標與NMI有類似的結果。通過觀察表8的聚類結果可以看出，隱性信息的引入有助于提高大多數數據集的聚類性能。

Table 8 Performance of algorithm with and without hidden information表8 有無隱性信息的算法性能

4.5 參數分析

正則化參數β控制香農熵正則化項的影響，為了驗證該參數對本文算法性能的影響，本節(jié)針對正則化參數β進行實驗。在實驗中，將參數m和α固定，并逐漸改變參數β的值，其中β的取值范圍為{2-6,2-5,…,25,26}。由于文章篇幅限制，只顯示在Multiple Features 和Image Segmentation 兩個多視角數據集上的實驗結果。圖5和圖6分別繪制了基于NMI、RI和Precision的聚類性能，其中橫坐標表示{2-6,2-5,…,25,26}從左至右的順序序號。從圖5和圖6中可以看出，在2-6到26范圍內，當選擇一個合適的β值，可得到最好的聚類結果。

Fig.5 Performance curve with varying β on Multiple Features圖5 Multiple Features上算法性能隨β 變化的曲線

Fig.6 Performance curve with varying β on Image Segmentation圖6 Image Segmentation上算法性能隨β 變化的曲線

5 結束語

本文提出了一種新的多視角聚類算法，即融合稀疏隱視角信息學習的多視角聚類算法。為了從多視角數據中學習更有效的稀疏隱視角信息，本文首先提出了一種多視角稀疏隱信息學習模型，然后在聚類過程中實現(xiàn)原始特征集與稀疏隱視角信息的協(xié)同學習。實驗研究表明，在UCI數據集和真實的多視角數據集上，所提算法在處理多視角聚類問題時相比其他聚類算法有更好的聚類性能。

雖然本文所提算法在處理多視角數據時已經取得較好的效果，但是還有很大的改進空間，比如針對高維多視角數據，引入軟子空間聚類策略[36，40]來實現(xiàn)顯隱信息的協(xié)同學習有望取得更好的聚類效果。此外，在實際應用中如何確定最優(yōu)的參數，也是將來研究的重點。