多視圖聚類算法綜述

何雪梅

摘 要：在大數(shù)據(jù)時(shí)代，數(shù)據(jù)是由不同來源生成的，或者是從不同視圖中觀察得到的，這些數(shù)據(jù)被稱為多視圖數(shù)據(jù)。在數(shù)據(jù)挖掘與分析中，充分發(fā)揮知識(shí)在多視圖數(shù)據(jù)中的作用是非常重要的，因此需要在融合相關(guān)數(shù)據(jù)的同時(shí)，考慮不同視圖的多樣性。近年來，多視圖聚類（MvC）受到越來越多學(xué)者關(guān)注，根據(jù)其涉及的機(jī)制和原則，將多視圖聚類算法分為5類，即協(xié)同訓(xùn)練算法、多核學(xué)習(xí)、多視圖聚類、多視圖子空間聚類與多任務(wù)多視圖聚類。對(duì)多視圖聚類算法進(jìn)行介紹，并重點(diǎn)介紹了協(xié)同訓(xùn)練算法與多核學(xué)習(xí)。

關(guān)鍵詞：數(shù)據(jù)挖掘;聚類分析;多視圖聚類;協(xié)同訓(xùn)練;多核學(xué)習(xí)

DOI：10. 11907/rjdk. 182831

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0079-03

0 引言

在如今信息爆炸的時(shí)代，數(shù)據(jù)量也不斷增加。在眾多數(shù)據(jù)中，如何找出其中的有用信息成為人們關(guān)注的重點(diǎn)。數(shù)據(jù)挖掘技術(shù)作為大數(shù)據(jù)處理及信息挖掘的重要手段，已得到了廣泛應(yīng)用。聚類分析[1]是根據(jù)數(shù)據(jù)對(duì)象間的關(guān)系將集合分割成多個(gè)簇（Cluster）的過程，并將距離近的數(shù)據(jù)對(duì)象劃分到同一個(gè)簇中，將距離遠(yuǎn)的數(shù)據(jù)對(duì)象劃分到不同簇。因此，可以通過相似性對(duì)數(shù)據(jù)進(jìn)行劃分，得到更為準(zhǔn)確的聚類結(jié)果。如果從機(jī)器學(xué)習(xí)層面進(jìn)行解釋，聚類分析是一種無監(jiān)督學(xué)習(xí) （Unsupervised Learning）方法，可以對(duì)標(biāo)簽信息未知的數(shù)據(jù)進(jìn)行聚類等操作，從而提取出有用信息。

隨著如今對(duì)數(shù)據(jù)信息化的要求越來越高，僅從單一視圖描述數(shù)據(jù)已無法得到預(yù)期效果，因此多視圖數(shù)據(jù)（Multi-view Data）聚類問題成為學(xué)者們的研究重點(diǎn)。聚類由一個(gè)視圖組成的數(shù)據(jù)稱為單視圖聚類（Single-view Clustering），而多視圖聚類（Multi-view Clustering）則是用聚類方法處理多視圖數(shù)據(jù)。隨著網(wǎng)絡(luò)信息化的快速發(fā)展，越來越多的多視圖數(shù)據(jù)在實(shí)際中得到應(yīng)用。例如：對(duì)于同一種數(shù)據(jù)，可以根據(jù)該數(shù)據(jù)的不同特征進(jìn)行劃分，每種特征代表一種視圖數(shù)據(jù);對(duì)于網(wǎng)頁大數(shù)據(jù)，可通過文本或網(wǎng)頁鏈接的形式獲取數(shù)據(jù)，從而構(gòu)成兩個(gè)視圖的多視圖數(shù)據(jù)。已有聚類算法通常僅適用于單視圖數(shù)據(jù)，因此本文在傳統(tǒng)算法基礎(chǔ)上進(jìn)行擴(kuò)展，得到多視圖聚類算法，即從多個(gè)視圖出發(fā)，充分利用視圖內(nèi)與視圖間的關(guān)系，不僅分析視圖間的一致性，也分析視圖間的差異性，從而充分運(yùn)用多視圖中的所有有效信息，使聚類結(jié)果更加準(zhǔn)確。

1 多視圖聚類

過去幾十年來，研究者們已提出許多先進(jìn)的聚類算法。雖然這些聚類算法在某種程度上已非常成功，但其中大部分算法僅適用于單視圖數(shù)據(jù)。即使將所有視圖連接成一個(gè)視圖，然后在該單一視圖上采用最先進(jìn)的聚類算法，也無法提高聚類性能，因?yàn)槊總€(gè)視圖都具有其特定的統(tǒng)計(jì)特性，所以該方式在物理上沒有意義。相比之下，多視圖聚類（Multi view Clusteing，MvC）通過考慮不同視圖的多樣性和互補(bǔ)性，可有效處理多視圖數(shù)據(jù)。作為一種先進(jìn)的聚類模式，MvC近年來受到越來越多學(xué)者關(guān)注。

由于多視圖數(shù)據(jù)不同視圖間既具有內(nèi)在聯(lián)系又存在差異，因此充分、合理地利用多視圖數(shù)據(jù)中的信息是提升多視角學(xué)習(xí)性能的關(guān)鍵。為了更好地挖掘出其中的信息，多視圖算法一般需遵循兩個(gè)原則[2]：一致性原則和互補(bǔ)性原則。本文根據(jù)多視圖聚類算法原則將其分為5類，即協(xié)同訓(xùn)練算法、多內(nèi)核學(xué)習(xí)、多視圖圖形聚類、多視圖子空間聚類、多任務(wù)多視圖聚類。

1.1 協(xié)同訓(xùn)練

在多視圖協(xié)商一致的情況下，本文研究了協(xié)同訓(xùn)練算法。該方法旨在最大限度地?cái)U(kuò)展所有觀點(diǎn)的相互協(xié)議，并達(dá)成最廣泛的共識(shí)。協(xié)同訓(xùn)練算法一般過程如圖1所示，根據(jù)該過程對(duì)算法進(jìn)行交替訓(xùn)練，利用先驗(yàn)信息或相互學(xué)習(xí)知識(shí)，使兩種不同視圖的一致性最大化。

在無監(jiān)督學(xué)習(xí)中，Bickel&Scheffer[3]首次利用協(xié)同訓(xùn)練思想研究了MvC，并提出兩種用于文本數(shù)據(jù)的MvC算法。一種是多視圖EM算法，其在視圖之間交替工作，另一種是受協(xié)同訓(xùn)練啟發(fā)的凝聚算法。最后得出結(jié)論，多視圖EM算法顯著優(yōu)于單視圖算法，但凝聚算法會(huì)導(dǎo)致負(fù)面結(jié)果;Tzortzis&Likas[4]提出一種加權(quán)多視圖凸混合模型，該模型通過EM自動(dòng)為視圖分配權(quán)重;Kumar等[5]進(jìn)一步提出用于多視圖譜聚類的共規(guī)則化方法;文獻(xiàn)[6]中提出一種適用于MvC的共正則化概率潛語義分析（PLSA）模型。其核心思想是，一個(gè)視圖主題空間中的樣本相似性應(yīng)與另一個(gè)視圖一致;為了解決視圖之間部分映射（即不完整視圖）的挑戰(zhàn)，文獻(xiàn)[7]、[8]研究了具有成對(duì)約束傳播的CO-EM多視圖約束聚類，即使用CO-EM迭代估計(jì)每個(gè)視圖中的傳播，跨視圖傳遞給定的成對(duì)約束，更新聚類模型，最后學(xué)習(xí)所有視圖的統(tǒng)一聚類結(jié)果。

此外，部分學(xué)者還研究了基于共聚類的MvC。例如，Meng等 [9]提出一種異構(gòu)數(shù)據(jù)協(xié)同聚類方法，其不僅可以將融合從兩個(gè)視圖擴(kuò)展到多個(gè)視圖，還可以對(duì)多個(gè)數(shù)據(jù)源特征進(jìn)行加權(quán)。在矩陣分解的基礎(chǔ)上，Sun等[10]提出一種近端交替線性最小化算法，該算法可以同時(shí)將多個(gè)數(shù)據(jù)矩陣分解為稀疏的行和列向量，并使用二進(jìn)制向量鏈接不同數(shù)據(jù)視圖，其中二進(jìn)制向量可強(qiáng)制保持所有視圖行簇的一致性。

1.2 多核學(xué)習(xí)

最初開發(fā)多核學(xué)習(xí)是為了提高可能的內(nèi)核函數(shù)[11]（例如：線性內(nèi)核、多項(xiàng)式內(nèi)核及高斯內(nèi)核）的搜索空間容量，以實(shí)現(xiàn)良好的泛化性。由于多核學(xué)習(xí)中的內(nèi)核自然對(duì)應(yīng)于不同視圖，因此多核學(xué)習(xí)被廣泛應(yīng)用于處理多視圖數(shù)據(jù)。多核學(xué)習(xí)方法一般過程如圖2所示，其中使用不同的預(yù)定義內(nèi)核處理不同視圖，然后將其進(jìn)行內(nèi)核線性或非線性組合，以便得到一個(gè)統(tǒng)一內(nèi)核。在MvC設(shè)置中，基于多核學(xué)習(xí)的MvC希望能最優(yōu)地組合一組預(yù)定義內(nèi)核，以便提高聚類性能。在該方法中，一個(gè)基本問題是找到一種方法以選擇合適的核函數(shù)，并將這些核采用最優(yōu)方式組合起來。

在單視圖場景中，Zhao等[12]提出一種基于最大邊緣聚類的多核聚類算法，該算法可以同時(shí)找到最大邊緣超平面、最佳聚類和最優(yōu)核;Du等[13]提出一種多核k均值算法，該算法能夠同時(shí)找到最優(yōu)聚類標(biāo)簽、聚類隸屬度和多核最優(yōu)組合。值得強(qiáng)調(diào)的是，上述算法可以在圖4所示框架下處理多視圖數(shù)據(jù)。在多視圖場景中，De Sa等[14]構(gòu)建了一種基于最小分歧算法的自定義核組合方法，其生成了一個(gè)多分圖以誘導(dǎo)內(nèi)核，然后將其用于譜聚類。該方法實(shí)際上可看作核正則相關(guān)分析的變體，是共聚類與譜聚類的推廣。此外，Yu等[15]將經(jīng)典的K均值聚類擴(kuò)展到Hilbert空間，將多視圖數(shù)據(jù)矩陣表示為核矩陣，然后將其自動(dòng)組合后進(jìn)行數(shù)據(jù)融合。

通過考慮視圖間的差異，部分學(xué)者還研究了具有內(nèi)核加權(quán)組合的方法。例如，文獻(xiàn)[16]提出一種系統(tǒng)化的MvC方法，可通過優(yōu)化過程自動(dòng)分配權(quán)重，導(dǎo)出每個(gè)視圖上的核矩陣，其中核矩陣學(xué)習(xí)基于核對(duì)齊，以測量兩個(gè)核矩陣之間的相似度。此外，Liu等[17]展示了一種基于矩陣誘導(dǎo)正則化的加權(quán)多核K-means聚類方法，可以減少冗余核并增強(qiáng)預(yù)定核的多樣性;Zhao等 [18]提出一種基于改進(jìn)變權(quán)高斯核的加權(quán)MvC算法。

然而，在許多應(yīng)用程序中，一些視圖上的數(shù)據(jù)不可用或僅部分可用的情況是十分常見的，從而導(dǎo)致不完整的多視圖數(shù)據(jù)。為解決該問題，Trivedi等[19]提出一種通用方法，允許MvC在完整視圖設(shè)置下適用于該場景，在該場景中只有一個(gè)視圖是完整的，而輔助視圖不完整，并以基于內(nèi)核CCA的MvC為例進(jìn)行說明;De Sa等提出一種基于最小分岐算法，可以計(jì)算具有缺失視圖的樣本關(guān)系;在缺乏完整視圖的環(huán)境中，Shao等[20]提出一個(gè)集體核學(xué)習(xí)算法，以推斷隱藏樣本的相似性。

1.3 多視圖圖聚類

圖形（或網(wǎng)絡(luò)）廣泛用于表示對(duì)象之間的關(guān)系，其中每個(gè)節(jié)點(diǎn)都與數(shù)據(jù)對(duì)象相對(duì)應(yīng)，并且每個(gè)邊描繪一對(duì)對(duì)象之間的關(guān)系。在實(shí)踐中，該關(guān)系通常用相似性或親緣關(guān)系表示，即輸入圖矩陣是由數(shù)據(jù)相似性矩陣生成的。在多視圖場景中，數(shù)據(jù)對(duì)象由多個(gè)圖進(jìn)行捕獲。一個(gè)常見假設(shè)是每個(gè)單獨(dú)的圖可以捕獲數(shù)據(jù)部分信息，而所有圖形都具有相同的基礎(chǔ)數(shù)據(jù)聚類結(jié)構(gòu)。因此，這些圖可以通過合并數(shù)據(jù)對(duì)象之間的關(guān)系以相互增強(qiáng)。多視圖圖聚類的目的是在所有視圖中找到一個(gè)融合圖，然后在融合圖上應(yīng)用圖形切割算法或其它技術(shù)（如譜聚類[21]），產(chǎn)生最終的聚類結(jié)果。

1.4 多視圖子空間聚類

多視圖子空間聚類[22]是對(duì)所有視圖數(shù)據(jù)，從多個(gè)子空間或潛在空間學(xué)習(xí)一種新的、統(tǒng)一的表示，使其在建立聚類模型時(shí)更容易處理高維數(shù)據(jù)。在MvC領(lǐng)域，多視圖子空間聚類已成為一個(gè)熱門話題。多視圖子空間聚類通過以下兩種方式獲得統(tǒng)一的特征表示：①直接從多個(gè)子空間中獲取單一表示;②首先學(xué)習(xí)一個(gè)潛在空間，然后到達(dá)該統(tǒng)一表示。最后，這種統(tǒng)一表示被輸入到現(xiàn)成的聚類模型中，以產(chǎn)生聚類結(jié)果。

1.5 多任務(wù)多視圖聚類

如上文所述，MvC利用不同視圖之間的一致性和互補(bǔ)性以實(shí)現(xiàn)更好的聚類質(zhì)量。多任務(wù)聚類（屬于多任務(wù)學(xué)習(xí)領(lǐng)域[23]）一起執(zhí)行多個(gè)相關(guān)任務(wù)，并利用這些任務(wù)之間的關(guān)系增強(qiáng)單視圖數(shù)據(jù)的聚類性能。通過繼承MvC和多任務(wù)聚類的屬性，多任務(wù)多視圖聚類（Multi-task Multi-View Clustering，M2vC）通過一個(gè)或多個(gè)任務(wù)處理單個(gè)視圖數(shù)據(jù)。M2vC的主要挑戰(zhàn)包括在每個(gè)視圖上找到一種任務(wù)內(nèi)聚類建模方法，以及一種利用多任務(wù)與多視圖關(guān)系的方法，同時(shí)對(duì)任務(wù)間的知識(shí)進(jìn)行相互傳遞。

2 結(jié)語

雖然MvC是在2003年左右提出的，但尚無一個(gè)統(tǒng)一標(biāo)準(zhǔn)決定在所有聚類算法中，哪種算法最優(yōu)，因?yàn)椴煌椒ㄓ衅涓髯缘膬?yōu)缺點(diǎn)。協(xié)同訓(xùn)練算法可通過交換信息以交互式地增強(qiáng)不同視圖聚類。然而，當(dāng)視圖數(shù)量大于3時(shí)，這些數(shù)據(jù)很難進(jìn)行處理;基于核的MvC繼承了內(nèi)核的優(yōu)點(diǎn)，但同時(shí)也帶來了較高的計(jì)算復(fù)雜度;多視圖圖聚類引入譜圖理論，并依賴于構(gòu)造的相似性矩陣;多視圖子空間聚類方法具有直觀的可解釋性與初始化依賴性;多任務(wù)多視圖繼承了多任務(wù)聚類與多視圖聚類的特性，但其仍然處于起步階段。

目前對(duì)MvC的研究已成為熱點(diǎn)，但其仍面臨以下問題和挑戰(zhàn)：①視圖正確性。找到一種判斷視圖是否正確的方法對(duì)于MVC而言是至關(guān)重要的，因此為了確保MvC的有效性，必須在很大程度上解決該問題;②不完整MvC的問題。在現(xiàn)實(shí)生活中，數(shù)據(jù)丟失的情況頻繁發(fā)生，而對(duì)于不完整MvC的研究還不多見，未來將對(duì)不完整MvC作進(jìn)一步研究。

參考文獻(xiàn)：

[1] 曹凱迪. 聚類分析綜述[J]. 智慧健康，2016（10）：50-53.

[2] AGGARWAL C C，REDDY C K. Data clustering ： algorithms and applications[M]. Data Clustering： Algorithms and Applications. Chapman & Hall/CRC， 2013.

[3] BICKEL S，SCHEFFER T. Multi-view clustering[C]. IEEE International Conference on Data Mining，2004.

[4] TZORTZIS G F，LIKAS A C. Multiple view clustering using a weighted combination of exemplar-based mixture models[J]. IEEE Transactions on Neural Networks， 2010， 21（12）：1925-1938.

[5] KUMAR A，RAI P，DAUMé III H. Co-regularized multi-view spectral clustering[C]. Proceedings of the 24th International Conference on Neural Information Processing Systems， 2011.

[6] JIANG Y，LIU J，LI Z，et al. Co-regularized PLSA for multi-view clustering[C]. Asian Conference on Computer Vision， 2012.

[7] EATON E，DESJARDINS M，JACOB S. Multi-view clustering with constraint propagation for learning with an incomplete mapping between views[C]. Toronto：Proceedings of the 19th ACM Conference on Information and Knowledge Management，2010.

[8] EATON E，DESJARDINS M，JACOB S. Multi-view constrained clustering with an incomplete mapping between views[J].? Knowledge and Information Systems，2014，38（1）：231-257.

[9] MENG L，TAN A H，XU D. Semi-supervised heterogeneous fusion for multimedia data co-clustering[J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（9）：2293-2306.

[10] SUN J W，LU J，XU T Y，et al.Multi-view sparse co-clustering via proximal alternating linearized minimization[C]. Proceedings 32nd International Conference Machine Learning， Lille， France， 2015：757-766.

[11] 張佩瑞，楊燕，邢煥來，等. 多核學(xué)習(xí)的多視圖增量聚類模型研究[D]. 成都：西南交通大學(xué)，2017.

[12] ZHAO B，KWOK J T，ZHANG C S. Multiple kernel clustering[C]. Proceedings 2009 SIAM International Conference on Data Mining， 2009：638-649.

[13] DU L， ZHOU P， SHI L，et al. Robust multiple kernel K-means using 2;1-norm[C]. International Conference on Artificial Intelligence，2015：3476-3482.

[14] SA V R， GALLAGHER P W， LEWIS J M，et al. Multi-view kernel construction[J]. Machine Learning，2010，79（1）：47-71.

[15] YU S， TRANCHEVENT L C， LIU X， et al. Optimized data fusion for kernel K-means clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（5）：1031-1039.

[16] LU Y，WANG L，LU J， et al. Multiple kernel clustering based on centered kernel alignment[J]. Pattern Recognition， 2014， 47（11）：3656-3664.

[17] LIU X，DOU Y，YIN J，et al. Multiple kernel k-means clustering with matrix-induced regularization[C]. Thirtieth AAAI Conference on Artificial Intelligence. AAAI Press， 2016.

[18] ZHAO Y，DOU Y，LIU X， et al. A novel multi-view clustering method via low-rank and matrix-induced regularization[J]. Neurocomputing，2016，216：342-350.

[19] TRIVEDI A，RAI P，DAUM'E H，et al. Multiview clustering with incomplete views[C].? Whistler：Proceedings of Workshop on Machine Learning for Social Computing，2010.

[20] SHAO W，SHI X，YU P S.? Clustering on multiple incomplete datasets via collective kernel learning[C]. Proceedings 13th International Conference Data Mining，2013：1181-1186.

[21] 陳新泉，周靈晶，劉耀中. 聚類算法研究綜述[J]. 集成技術(shù)，2017，3（6）：41-49.

[22] YAN Y，WANG H. Multi-view clustering： a survey[J]. Big Data Mining and Analytics， 2018（2）：83-107.

[23] CARUANA R. Multitask learning[J]. Machine Learning，1997， 28（1）：41-75.

（責(zé)任編輯：黃 ?。?/p>