基于模糊C-means的多視角聚類算法

楊欣欣，黃少濱

?

基于模糊C-means的多視角聚類算法

楊欣欣，黃少濱

(哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱，150001)

目前多數多視角聚類算法屬于“剛性”劃分算法，不適用于處理具有聚簇重疊結構的數據集，為此，提出一種基于模糊C-means的多視角聚類算法(簡稱FCM-MVC)，該算法利用隸屬度描述對象與類別的關系，能夠更真實地描述具有聚簇重疊結構數據集的聚類結果。FCM-MVC算法同時利用多個視角信息，自動計算每個視角的權重。研究結果表明：FCM-MVC算法能夠有效處理具有聚簇重疊結構的數據集；與已有的3種經典的多視角聚類算法相比，該算法獲得的聚類精度更高。

多視角聚類；模糊C-means；數據挖掘

近年來，在許多實際應用中出現了大量由多種表示方法或多種視角描述的多視角數據(Multi- view)[1?2]。例如，同一則新聞可以由多個新聞機構以不同的描述方式報道，同一則新聞也可以翻譯成多種不同的語言[1?2]。不同的表示方法從不同的視角更全面、更客觀地描述數據集特性。多視角聚類方法充分利用多視角信息，考慮不同視角信息的區別，往往能夠獲得更加準確的數據劃分結果，是近年來備受關注的學習范式。該學習范式主要包含2類算法[3]：集中式和分散式。目前大部分多視角聚類算法為集中式方 法[1?14]。集中式方法同時利用多個數據描述特征空間信息，探測數據中隱藏的模式；分散式算法首先使用單視角算法對每個視角分別進行獨立聚類，然后結合每個視角的聚類結果，得到最終的劃分結果[3]。基于奇異值分解的算法HC-MLSVD[1]，將多視角數據表示為多維張量，利用奇異值方法將其映射到低維空降。

基于譜聚類的方法將多視角數據表示為多個特征空間的視圖，然后尋找多視圖的最小劃分[2?5, 13?14]。基于k-means多視角聚類算法[6, 12]，自動確定視角和特征的權值。Blaschko等[6]提出了一種基于核典型相關分析的雙視角聚類算法，每個視角采用單獨的相似性測量，適用于分析部分只有一種視角描述的數據。Chaudhuri等[8]提出了一種子空間多視角聚類算法，通過典型相關分析將多視角數據映射到低維子空間。Tzortzis等[10]提出基于核的方法，用核矩陣表示每個視角的對象，根據每個視角的信息量自動確定其核矩陣的權重。Long等[3]提出一種分散式多視角聚類模型，該模型通過引入映射函數，使得不同空間的模式具有可比性，從多個視角中學習最佳模式。Bruno等[11]提出一種后期融合方法，重新建立每個視角聚簇之間的關系。這些多視角聚類算法都是“剛性”劃分方法。與剛性聚類方法相比，模糊聚類方法中樣本不再完全屬于或完全不屬于某一類，而是以一定的隸屬度隸屬于每個類，即利用隸屬度描述樣本屬于每個類別的不確定性程度，這樣更能準確地反映現實世界。模糊聚類獲得了廣泛研究，并取得了較好的聚類效果[18?19]。本文作者基于模糊C-means算法提出一種多視角聚類算法FCM-MVC，利用隸屬度描述對象與類別的關系，同時利用多個視角空間中的信息，自動計算每個視角的權重。

1 基于模糊C-means的多視角聚類算法

設具有個視角的多視角數據對象集合為{1，2，…，x}，(i)表示多視角數據在第(1≤≤)個視角空間的特征矩陣，其中第(1≤≤)行向量表示數據對象在第個視角空間中的特征向量，其中n為第個視角的特征維度。FCM-MVC算法的最優化目標函數如下：

s.t

其中：為模糊指數，用于調節隸屬度的模糊程度；為隸屬度矩陣；表示對象隸屬于第個聚簇的隸屬度；，(1≤≤)表示第個聚類中心的向量；，其中w表示視角的權重；表示在第維空間上與之間的歐幾里得距離，如果特征為連續值，則

若特征是離散值，則

運用朗格朗日乘子法，構造約束條件(2)下的目標函數(1)的Lagrange函數為

(5)

求解等式(6)~(10)構成的方程組，得到目標函數(1)在約束條件(2)下取到極小值時需滿足的必要條件為:

其中：

綜上所述，基于模糊C-means的多視聚類算法計算步驟描述如下。

輸出：使目標函數(1)最小化的多視角數據集的隸屬度矩陣。

1) 初始化：隨機產生并歸一化隸屬度矩陣；

2) 重復以下計算過程，直到連續2次迭代目標函數的差值小于或迭代次數達到最大迭代數max；

For each

①根據式(11)計算第個視角空間的聚簇中心(=1，2，…，) 。

②根據(3)或(4)式計算第個視角的第維空間上數據與聚簇中心的距離。

③根據(13)和(14)式計算第個視角空間的權重。

End for

時間復雜度分析：步驟2為循環迭代過程，算法運行時間主要消耗在該步驟。以下主要分析步驟2消耗的時間復雜度。在1次循環中步驟①計算的時間復雜度為()，計算第個視角空間中個聚簇中心的時間復雜度為，計算個視角特征空間的聚簇中心消耗的時間復雜度為。同理分析知步驟②消耗的時間復雜度為。在1次循環中步驟③計算所有視角空間中的消耗的時間復雜度為，計算所有視角空間中的消耗的時間復雜度為，所以在1次循環中，步驟③消耗的時間復雜度為。同理分析知步驟④消耗的時間復雜度是。綜上，FCM-MVC算法消耗的時間復雜度為，其中為所有視角特征維度之和，為算法達到收斂狀態時的迭代次數。

2 實驗分析

2.1 數據集介紹

本實驗使用4個benchmark數據集分析多視角數據內部隱藏的重疊聚簇結構，測試FCM-MVC算法的聚類精度和收斂特性：

3-Sources 數據集是同時由3家新聞社報道的169條新聞組成，包括6個主題。將BBC新聞社報道的新聞作為第1視角，將Guardian和The Reuters新聞社報道的新聞分別作為第2和第3視角[15]。采用Grreene等[15]提出的方法構建多視角數據集Dataset1。

Reuters Multilingual 數據集由5種語言描述的6個主題的文本組成[16]，從每個主題中隨機選取200篇文本，將法語、德語和英語描述的文本作為3個視角。采用Amini等[16]的方法構建多視角數據集Dataset2。

Corel 數據集包含5 000 張圖像，每個圖像包含文字標注信息和圖像分割塊信息[22]。分別從cow，grass和horses 3個類別中選取100 張圖像，將圖像的文字描述信息作為第1視角，將圖像分割組信息作為第2視角，采用文獻[21]中的方法構建多視角數據集Dataset3。

MSRC 數據集包含23個類別圖像[20], 分別從clouds和trees類別中隨機選取400和200張圖像組成數據集dataset4。采用整體視覺特征(GVF)、局部視覺特征(LVF)作為第1和第2視角。采用Shotton等[20]的方法構建多視角數據集Dataset3。

2.2 實驗結果分析

圖1所示為Dataset3數據集和Dataset4數據集中圖像之間相似度可視化示意圖，其中，灰度越深表示相應的圖像之間的相似度越高。從圖1可以發現Dataset3數據集和Dataset4數據集中存在明顯的聚簇結構，并且不同的聚簇之間存在明顯的重疊部分，而基于“剛性”劃分的多視角聚類方法嚴格地將多視角數據對象集合劃分到不同的聚簇中，不同聚簇之間不存在交集，難以表示聚類重疊部分多視角數據對象的聚簇結果。Dataset1數據集和Dataset2數據集具有類似的聚類結構，不再列舉。圖2所示為Dataset4數據集中多視角數據對象屬于第1個聚類的隸屬度值，400~460之間的多視角對象為第1個聚簇和第2個聚簇之間重疊的部分，相應的隸屬度近似于0.5。表1所示為Dataset4中聚簇重疊部分多視角數據對象的隸屬度值示例，這些數據對象既包含cloud又包含tree聚類，難以嚴格地將這些多視角數據對象劃分到cloud聚類或于cloud聚類中，數據對象的隸屬度在0.5左右。由此可見：FCM-MVC算法引入模糊隸屬度概念，利用模糊隸屬度描述數據對象與聚簇之間的隸屬關系，能夠更有效地挖掘和分析聚簇重疊部分數據對象內部隱藏的結構，更客觀地描述現實世界數據對象的聚類結果。

(a) Dataset3 數據集；(b) Dataset4 數據集

圖2 圖像隸屬度值

表1 Dataset4數據集重疊聚簇部分數據隸屬度示例

其次，FCM-MVC算法與目前已有的3種“剛性”劃分多視角聚類算法進行準確率對比，包括基于典型相關性分析的方法KCCA[6]、協同回歸的多視角譜聚類算法Co-reguSC[4]和基于核映射的多視角K-means算法MVKKM[9]。另外，單視角模糊C-means算法的在最優視角上的聚類用Best Single-view表示，將FCM-MVC算法與Best Single-view的聚類效果進行對比分析。利用NMI指標評估聚類效果，NMI越大表明聚類結果越準確。圖3所示為KCCA，Co-reguSC，MVKKM，Best Single-view和FCM-MVC算法聚類結果NMI值比較。結果表明：FCM-MVC算法聚類結果明顯優于目前已有的3種“剛性劃分”多視角聚類算法，這在一定程度上是由于模糊方法利用隸屬度，能夠更客觀、更精確地描述聚簇重疊部分數據對象的聚類結果；另外，FCM-MVC算法的聚類結果明顯優于Best Single-view的聚類結果，主要原因在于FCM-MVC算法能夠充分利用多種視角空間信息，進一步提高聚類精度。

圖3 聚類結果NMI值

最后，圖4所示為FCM-MVC算法在Dataset1和Dataset3數據集上式(1)所示目標函數隨算法迭代運行的變化情況。結果表明：FCM-MVC算法目標函數值逐漸下降，在迭代50次左右逐漸達到收斂狀態。

1—Dataset 1；2—Dataset 3

3 結論

1) 基于模糊C-means算法FCM提出了一種多視角聚類算法FCM-MVC，與已有的多視角聚類算法相比，FCM-MVC算法能夠更有效地描述和挖掘具有重疊聚簇結構的多視角數據的聚類結果，并且能夠有效提高聚類精度。

2) 目前已有的多視角聚類算法需要領域專家預先確定多視角數據的聚類數目，下一步的主要研究工作是考慮如何自動確定多視角數據的聚類數目。

[1] LIU Xinhai, Gl?nzel W, de Moor B. Hybrid clustering of multi-view data via Tucker-2 model and its application[J]. Scientometrics, 2011, 88(3): 819?839.

[2] WANG Xiang, QIAN Buyue, YE Jieping, et al. Multi-objective multi-view spectral clustering via pareto optimization[C]//Proc of the 13th SIAM International Conference on Data Mining. Philadelphia: SIAM, 2013: 234?242.

[3] LONG Bo, YU P S, ZHANG Zhongfei. A general model for multiple view unsupervised learning[C]//Proc of the 8th SIAM International Conference on Data Mining. Philadelphia: SIAM, 2008: 822?833.

[4] Kumar A, Hal Daumé III. A co-training approach for multi-view spectral clustering[C]//Proc of the 28th IEEE International Conference on Machine Learning. NJ: IEEE, 2011: 393?400.

[5] Kumar A, Rai P, Hal Daumé III. Co-regularized multi-view spectral clustering[C]//Proc of the 24th Annual Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2011: 1413?1421.

[6] CHEN Xiaojun, XU Xiaofei, HUANG Joshua, et al. TW-k-means: Automated two-level variable weighting clustering algorithm for multiview data[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(4): 932?944.

[7] Blaschko M B, Lampert C H. Correlational spectral clustering[C]//Proc of the 21st IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2008: 1?8.

[8] Chaudhuri K, Kakade S, Livescu K, et al. Multiview clustering via canonical correlation analysis[C]//Proc of the 26th Annual International Conference on Machine Learning. New York: ACM, 2009: 129?136.

[9] LIU Jialu, WANG Chi, GAO Jing, et al. Multi-view clustering via joint nonnegative matrix factorization[C]//Proc of the 13th SIAM International Conference on Data Mining. Piscataway: IEEE, 2013: 252?260.

[10] Tzortzis G, Likas A. Kernel-based weighted multi-view clustering[C]//Proc of the 12th IEEE international conference on Data Mining. Piscataway: IEEE, 2012: 675?684.

[11] Bruno E, Marchand-maillet S. Multiview clustering: a late fusion approach using latent models[C]//Proc of the 32nd international ACM SIGIR conference on Research and Development in Information Retrieval. New York: ACM, 2009: 736?737.

[12] Eaton E, DesJardins M, Jacob S. Multi-view clustering with constraint propagation for learning with an incomplete mapping between views[C]//Proc of the 19th ACM international conference on Information and knowledge management. New York: ACM, 2010: 389?398.

[13] Eaton E, DesJardins M, Jacob S. Multiview Spectral Embedding [J].IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2010, 40(6): 1438?1446.

[14] ZHOU Dengyong, Burges C J C. Spectral clustering and transductive learning with multiple views[C]//Proc of the 24th International Conference on Machine Learning. New York: ACM, 2007: 1159?1166.

[15] Greene D, Cunningham P. A matrix factorization approach for integrating multiple data views[C]//Proc of European Conference on Machine learning and Principles and Practice of Knowledge Discovery in Databases. Berlin: Springer, 2009: 423?438.

[16] Amini M, Usunier N, Goutte C. Learning from multiple partially observed views: An application to multilingual text categorization[C]//Proc of the 23rd Annual Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2009: 28?36.

[17] Strehl A, Ghosh J. Cluster ensembles-a knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research, 2002, 3(3): 583?617.

[18] Miyamoto S, Mukaidono M. Fuzzy c-means as a regularization and maximum entropy approach[C]//Proc of the 7th International Fuzzy Systems Association Word Congress. Berlin: Springer, 1997: 86?92.

[19] Huang H C, CHUANG Yungyu, CHENChusongMultiple kernel fuzzy clustering[J]. IEEE Transactions on Fuzzy Systems, 2012, 20(1): 120?134.

[20] Shotton J, Winn J, Rother C, et al. Textonboost for image understanding: Multi-class object recognition and segmentation by jointly modeling texture, layout, and context[J]. International Journal of Computer Vision, 2009, 81(1): 2?23.

[21] 杜友田, 李謙, 周亞東, 等. 基于異質信息融合的網絡圖像半監督學習方法[J]. 自動化學報, 2012, 38(12): 1923?1932. DU Youtian, LI Qian, ZHOU Yadong, et al. Web image semi-supervised learning method based on heterogeneous information fusion[J]. Acta Automatica Sinica, 2012, 38(12):1923?1932.

[22] Duygulu P, Barnard K, de Freitas N, et al. Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary[C]//Proceedings of European Conference on Computer Vision. Berlin: Springer, 2002: 97?112.

(編輯 陳愛華)

Multi-view clustering algorithm based on fuzzy C-means

YANG Xinxin, HUANG Shaobin

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Considering that most exiting multi-view clustering algorithms focusing on hard-partition clustering methods, which are not suitable for analyzing dataset with overlapping clusters, a multi-view clustering algorithm based on fuzzy C-means (FCM-MVC) was developed. The membership degree was used to describe the relation between objects and clusters, so FCM-MVC algorithm could more truely describe clustering results of dataset with overlapping clusters. FCM-MVC algorithm simultaneously incorporated fearture information in multi-view space and automatically computes weight of each view. The results show that FCM-MVC can analyze overlapping clusters effectively and the precision of clustering results of FCM-MVCare superior to the three representative algorithms.

multi-view clustering; fuzzy C-means; data mining

10.11817/j.issn.1672-7207.2015.06.021

TP181

A

1672?7207(2015)06?2128?06

2014?08?14；

2014?10?25

國家科技支撐計劃項目(2012BAH08B02)；哈爾濱工程大學中央高校基本科研業務專項資金資助項目(HEUCFZ1212，HEUCF100603)(Project (2012BAH08B02) supported by the National Key Project of Scientific and Technical Supporting Programs; Project (HEUCFZ1212, HEUCF100603) supported by the Fundamental Research Funds of Harbin Engineering University for the Central Universities)

楊欣欣，博士研究生，從事數據挖掘、社會網絡和復雜網絡研究；E-mail：yangxinxin051131@126.com