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

楊欣欣，黃少濱

?

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

楊欣欣，黃少濱

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱，150001)

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

多視角聚類；模糊C-means；數(shù)據(jù)挖掘

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

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

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

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

s.t

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

若特征是離散值，則

運(yùn)用朗格朗日乘子法，構(gòu)造約束條件(2)下的目標(biāo)函數(shù)(1)的Lagrange函數(shù)為

(5)

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

其中：

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

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

1) 初始化：隨機(jī)產(chǎn)生并歸一化隸屬度矩陣；

2) 重復(fù)以下計(jì)算過程，直到連續(xù)2次迭代目標(biāo)函數(shù)的差值小于或迭代次數(shù)達(dá)到最大迭代數(shù)max；

For each

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

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

③根據(jù)(13)和(14)式計(jì)算第個(gè)視角空間的權(quán)重。

End for

時(shí)間復(fù)雜度分析：步驟2為循環(huán)迭代過程，算法運(yùn)行時(shí)間主要消耗在該步驟。以下主要分析步驟2消耗的時(shí)間復(fù)雜度。在1次循環(huán)中步驟①計(jì)算的時(shí)間復(fù)雜度為()，計(jì)算第個(gè)視角空間中個(gè)聚簇中心的時(shí)間復(fù)雜度為，計(jì)算個(gè)視角特征空間的聚簇中心消耗的時(shí)間復(fù)雜度為。同理分析知步驟②消耗的時(shí)間復(fù)雜度為。在1次循環(huán)中步驟③計(jì)算所有視角空間中的消耗的時(shí)間復(fù)雜度為，計(jì)算所有視角空間中的消耗的時(shí)間復(fù)雜度為，所以在1次循環(huán)中，步驟③消耗的時(shí)間復(fù)雜度為。同理分析知步驟④消耗的時(shí)間復(fù)雜度是。綜上，F(xiàn)CM-MVC算法消耗的時(shí)間復(fù)雜度為，其中為所有視角特征維度之和，為算法達(dá)到收斂狀態(tài)時(shí)的迭代次數(shù)。

2 實(shí)驗(yàn)分析

2.1 數(shù)據(jù)集介紹

本實(shí)驗(yàn)使用4個(gè)benchmark數(shù)據(jù)集分析多視角數(shù)據(jù)內(nèi)部隱藏的重疊聚簇結(jié)構(gòu)，測試FCM-MVC算法的聚類精度和收斂特性：

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

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

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

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

2.2 實(shí)驗(yàn)結(jié)果分析

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

(a) Dataset3 數(shù)據(jù)集；(b) Dataset4 數(shù)據(jù)集

圖2 圖像隸屬度值

表1 Dataset4數(shù)據(jù)集重疊聚簇部分?jǐn)?shù)據(jù)隸屬度示例

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

圖3 聚類結(jié)果NMI值

最后，圖4所示為FCM-MVC算法在Dataset1和Dataset3數(shù)據(jù)集上式(1)所示目標(biāo)函數(shù)隨算法迭代運(yùn)行的變化情況。結(jié)果表明：FCM-MVC算法目標(biāo)函數(shù)值逐漸下降，在迭代50次左右逐漸達(dá)到收斂狀態(tài)。

1—Dataset 1；2—Dataset 3

3 結(jié)論

1) 基于模糊C-means算法FCM提出了一種多視角聚類算法FCM-MVC，與已有的多視角聚類算法相比，F(xiàn)CM-MVC算法能夠更有效地描述和挖掘具有重疊聚簇結(jié)構(gòu)的多視角數(shù)據(jù)的聚類結(jié)果，并且能夠有效提高聚類精度。

2) 目前已有的多視角聚類算法需要領(lǐng)域?qū)＜翌A(yù)先確定多視角數(shù)據(jù)的聚類數(shù)目，下一步的主要研究工作是考慮如何自動確定多視角數(shù)據(jù)的聚類數(shù)目。

[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] 杜友田, 李謙, 周亞東, 等. 基于異質(zhì)信息融合的網(wǎng)絡(luò)圖像半監(jiān)督學(xué)習(xí)方法[J]. 自動化學(xué)報(bào), 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

國家科技支撐計(jì)劃項(xiàng)目(2012BAH08B02)；哈爾濱工程大學(xué)中央高校基本科研業(yè)務(wù)專項(xiàng)資金資助項(xiàng)目(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)

楊欣欣，博士研究生，從事數(shù)據(jù)挖掘、社會網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)研究；E-mail：yangxinxin051131@126.com