多視圖聚類算法綜述

何雪梅

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

關鍵詞：數據挖掘;聚類分析;多視圖聚類;協同訓練;多核學習

DOI：10. 11907/rjdk. 182831

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）004-0079-03

0 引言

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

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

1 多視圖聚類

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

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

1.1 協同訓練

在多視圖協商一致的情況下，本文研究了協同訓練算法。該方法旨在最大限度地擴展所有觀點的相互協議，并達成最廣泛的共識。協同訓練算法一般過程如圖1所示，根據該過程對算法進行交替訓練，利用先驗信息或相互學習知識，使兩種不同視圖的一致性最大化。

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

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

1.2 多核學習

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

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

通過考慮視圖間的差異，部分學者還研究了具有內核加權組合的方法。例如，文獻[16]提出一種系統化的MvC方法，可通過優化過程自動分配權重，導出每個視圖上的核矩陣，其中核矩陣學習基于核對齊，以測量兩個核矩陣之間的相似度。此外，Liu等[17]展示了一種基于矩陣誘導正則化的加權多核K-means聚類方法，可以減少冗余核并增強預定核的多樣性;Zhao等 [18]提出一種基于改進變權高斯核的加權MvC算法。

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

1.3 多視圖圖聚類

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

1.4 多視圖子空間聚類

多視圖子空間聚類[22]是對所有視圖數據，從多個子空間或潛在空間學習一種新的、統一的表示，使其在建立聚類模型時更容易處理高維數據。在MvC領域，多視圖子空間聚類已成為一個熱門話題。多視圖子空間聚類通過以下兩種方式獲得統一的特征表示：①直接從多個子空間中獲取單一表示;②首先學習一個潛在空間，然后到達該統一表示。最后，這種統一表示被輸入到現成的聚類模型中，以產生聚類結果。

1.5 多任務多視圖聚類

如上文所述，MvC利用不同視圖之間的一致性和互補性以實現更好的聚類質量。多任務聚類（屬于多任務學習領域[23]）一起執行多個相關任務，并利用這些任務之間的關系增強單視圖數據的聚類性能。通過繼承MvC和多任務聚類的屬性，多任務多視圖聚類（Multi-task Multi-View Clustering，M2vC）通過一個或多個任務處理單個視圖數據。M2vC的主要挑戰包括在每個視圖上找到一種任務內聚類建模方法，以及一種利用多任務與多視圖關系的方法，同時對任務間的知識進行相互傳遞。

2 結語

雖然MvC是在2003年左右提出的，但尚無一個統一標準決定在所有聚類算法中，哪種算法最優，因為不同方法有其各自的優缺點。協同訓練算法可通過交換信息以交互式地增強不同視圖聚類。然而，當視圖數量大于3時，這些數據很難進行處理;基于核的MvC繼承了內核的優點，但同時也帶來了較高的計算復雜度;多視圖圖聚類引入譜圖理論，并依賴于構造的相似性矩陣;多視圖子空間聚類方法具有直觀的可解釋性與初始化依賴性;多任務多視圖繼承了多任務聚類與多視圖聚類的特性，但其仍然處于起步階段。

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

參考文獻：

[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] 張佩瑞，楊燕，邢煥來，等. 多核學習的多視圖增量聚類模型研究[D]. 成都：西南交通大學，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]. 集成技術，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.

（責任編輯：黃 ?。?/p>