多視角模糊雙加權可能性聚類算法

蔣亦樟，朱麗，劉麗，王士同

聚類分析作為一種常見的無監督學習數據預處理方法，在數據挖掘、文件恢復、圖像分割及模式分類等領域有著廣泛的應用基礎。隨著現代技術發展的不斷更新，傳統的聚類模式已不再適應新的學習場景，如多視角學習場景[1-5]、遷移學習場景[6-9]、多任務學習場景[10-11]及子空間學習場景[12]等。本文將主要關注多視角學習場景，進而針對傳統聚類模型如何在多視角學習場景下更好地學習優化及應用展開探討。

對于傳統聚類方法，主要有以FCM(fuzzy c-means)算法[13-16]為代表的劃分型聚類算法, 還有以AP(affinity propagation)算法[17-18]為代表的圖論型聚類算法等。相對于其他聚類模型，基于劃分的聚類算法模型結構簡單，優化過程亦不復雜，經常被用于實際應用。但在以FCM算法為族群的各種基于劃分的算法中，如MEC(maximum entropy clustering, MEC)算法[19-20]及 PCM(possibilistic c-means)算法[21-22]等，經實驗驗證PCM算法較之其他算法具備更好的噪聲及孤立點魯棒性，因此本文將以經典PCM算法模型為理論基礎開展其在多視角學習場景下的模型優化及應用問題的研究。

目前針對多視角聚類問題，已有一些代表性的工作[2-5]被提出，如：1)基于概率論方法的多視角協同聚類Co-EM(collaborative expectation maximization)算法[2]；2)基于FCM算法模型的Co-FC(collaborative fuzzy clustering)算法[3]；3)針對 Co-FC算法改進的Co-FKM(collaborative fuzzy kmeans)算法[4]；4) Tzortzis等[5]基于核聚類方法提出的兩種多視角聚類算法MVKKM(multi-view kernel k-means)和MVSpec(multi-view spectral clustering)。盡管上述方法已使得一些傳統聚類算法獲得了多視角聚類的能力，但各方法在視角權重和視角內特征權重優化問題上的考量還是欠缺的，如基于協同學習思想提出的Co-EM、Co-FC及Co-FKM算法均未考慮視角權重和視角內特征權重優化問題，而MVKKM和MVSpec算法僅管采用了視角權重優化方法但在視角內特征權重優化問題上又未涉及。此外，上述大部分的算法是以FCM算法為基礎提出的，魯棒性較一般。為此，必須在多視角聚類領域提出一種新的具備較強魯棒性及多視角聚類能力且兼顧視角權重及視角內特征權重優化問題的新聚類算法。為達此目的，本文擬針對傳統PCM算法開展多視角聚類方面的模型優化工作，本文工作的創新主要涵蓋以下幾點：

1)針對傳統可能性(PCM)算法無法解決多視角聚類場景的問題，提出了多視角PCM算法；

2)多視角PCM算法各視角之間的視角權重是一致的，這與客觀事實不符。針對各視角之間視角權重應該不同的問題，引入視角間模糊加權機制；

3)多視角PCM算法各視角內的屬性權重默認是一致的，這也與客觀事實不符。針對各視角內的屬性權重應該不同的問題，引入視角內屬性模糊加權機制。

1 相關工作

為了更好地說明本文所提之算法，首先本小節將對傳統的PCM算法進行回顧，其次說明傳統PCM算法在面對多視角聚類任務時所存在的問題，最后引出具備最佳視角及最優特征劃分能力的多視角模糊雙加權可能性聚類算法(MV-FDW- PCM)的迫切性。

1.1 傳統PCM算法

傳統PCM算法于1996年被提出[1]。當時模糊C均值聚類FCM算法[2]是模糊聚類算法中最流行的聚類算法之一。隨著FCM算法使用的推廣，一些專家學者發現FCM算法中對隸屬度的限制條件增大了噪聲、例外點對聚類結果的影響。為了消除FCM算法中隸屬度之和為1的限制，R.Krishnapuram等提出了PCM算法。該算法的優勢在于去除了隸屬度之和為1的限制條件，從而降低了噪聲對聚類精度的影響。PCM算法的目標函數式為

式中：m是模糊系數，參數αi的計算公式為

求解目標函數式(1)得到隸屬度和聚類中心表達式為

1.2 PCM算法處理多視角聚類任務

隨著多視角應用場景不斷出現，傳統聚類算法的單視角學習模式的局限性導致其在處理多視角聚類問題時性能往往無法令人滿意。如傳統PCM算法在處理多視角聚類任務時，其聚類原理如下：

將多視角數據中每一個視角數據獨立出來，作為多個不相干的樣本進行獨立聚類分析。具體實施時是將各視角的樣本直接使用傳統PCM算法聚類以分別獲取各視角的劃分結果，K為視角數。最后，對多個劃分結果進行整合(如使用加權平均等策略)，最終得到一個劃分，進而根據該劃分確定樣本所歸屬的類別。傳統PCM算法處理多視角數據的原理圖如圖1。

根據上述分析及圖1所示的原理圖可以看出，傳統PCM算法在對多視角數據進行聚類任務時，存在以下問題：1)將各視角數據完全獨立開來進行單獨聚類，未考慮各視角間數據的關聯性信息；2)對各視角聚類結果進行融合時，未考慮不同視角數據對聚類結果的差異化影響，即結果的融合策略采用平均策略不符合客觀事實。綜上，傳統PCM算法受限于陳舊的聚類模式在處理多視角聚類任務時顯得不再有效。

圖1 傳統PCM算法聚類多視角數據原理圖Fig. 1 The principle diagram of traditional PCM algorithm clustering multi-view data

2 多視角模糊雙加權可能性聚類算法

針對傳統PCM算法在處理多視角數據聚類任務時效果不理想的問題，本節首先提出了多視角PCM算法。考慮到實際的多視角聚類問題各視角的聚類特性應有差異(如圖1所示)，因而所設計的多視角聚類算法對于各視角的權重應根據實際情況進行優化獲取，為此本節提出了視角間模糊加權機制。又由子空間聚類的原理可知各視角內屬性的權重也應存在一定的差異性，于是本節又提出了視角內屬性模糊加權機制。最后，基于上述兩個機制，提出了具備最佳視角及最優特征劃分能力的多視角模糊雙加權可能性聚類算法。

2.1 多視角聚類問題描述

對于一個多視角聚類問題(如圖2所示)，其描述了一個3維(X維、Y維及Z維)的多視角模擬數據，若任意選擇兩維進行投影，可將一個3維數據變成2維且可視化程度更高的樣本(如圖2 (b)～(d))，同理對于4維以上的數據亦可如此。在投影后，可以清晰地發現由X維和Y維組成的X-Y視角具備較之其他兩視角更好的可分性，其類別結構清晰且類與類之間劃分亦較為清晰。因此，對于任意一個多視角聚類問題，各視角的權重應通過優化學習得到而并非強制的一致對待。此外，根據子空間聚類理論[12]可知樣本特征的權重對于不同的聚類問題應是有差異的，這種特征權重的差異性反應到多視角聚類問題中將進一步延伸為視角內部各特征的權重也應是有所差異的，即同樣以X-Y視角為例，若將X-Y視角的樣本向X軸投影，那么“+”類將與“*”類嚴重重疊而不易區分，但若向Y軸投影則得到的3類的區分度(可分性)更佳。由此可知，在多視角聚類過程中，各視角下樣本特征的權重與視角權重一樣也需要得到優化，采用最佳的特征權重關系將進一步使得聚類結果得到顯著提升。

圖2 問題描述Fig. 2 Problem description

本文所用的符號說明如表1所示。

表1 符號說明Table 1 The explanation of some notations

2.2 多視角PCM算法

為了讓PCM算法能夠更好地適應多視角聚類任務，本文首先提出了多視角PCM算法。該算法的目標函數式如下：

式(5)為視角隸屬度融合項，θ為視角隸屬度融合項的平衡系數。根據式(4)、(5)得到每個視角最終的隸屬度矩陣。最終的劃分結果用融合函數計算為

2.3 視角間模糊加權機制

多視角PCM算法雖然改變了傳統PCM算法的單視角聚類模型，使其能夠解決多視角聚類任務，但該算法仍未考慮視角間的權重大小應當存在差異化的情況。因為現實生產生活中，多視角數據的每一個視角的數據存在聚類特性不相同的情況，即有些視角數據的聚類特性較好，有些視角數據的聚類特性較差。如果在聚類的過程中，無差別地將所有視角數據的權重默許一致，這種計算策略顯然是不科學的。考慮到以上因素，本節提出了一種可行的視角間模糊加權機制。即賦予每一個視角一個合理的權重且所有視角權重之和為1。該機制的示意圖如圖3所示。

圖3 視角間加權機制示意圖Fig. 3 The schematic diagram of weighting mechanism between perspectives

視角間加權的表達式為

2.4 視角內屬性模糊加權機制

考慮到各視角內各個屬性權重默認相同的情況與客觀現實不符，本文又提出了視角內屬性加權機制。賦予聚類質量高的屬性高的權重，聚類質量較差的屬性低的權重。具體表達式為

式(9)為視角隸屬度融合項，θ為視角隸屬度融合項的平衡系數。

2.5 多視角模糊雙加權可能性聚類算法

在多視角PCM基礎上，通過引入視角間模糊加權以及視角內屬性模糊加權兩種機制，本文提出了具備最佳視角及最優特征劃分能力的多視角模糊雙加權可能性聚類MV-FDW-PCM算法。該算法的原理如圖4所示。

圖4 MV- FDW -PCM算法聚類多視角數據Fig. 4 The MV- FDW -PCM algorithm clustering multi-view data

算法的目標函數式為

由于式(10)采用了屬性加權機制以及多視角隸屬度融合機制，所以的新優化項定義如下：

利用拉格朗日最小化目標函數式(10)，得到聚類中心、隸屬度、視角權重以及屬性權重的計算式為

最終的劃分結果用式(16)融合函數進行計算：

MV-FDW-PCM算法步驟如下：

1)給定聚類數C，樣本總數N，視角總數K，聚類精度 ε，最大迭代次數 T，模糊系數 m1，m2，m3，初始化隸屬度矩陣U和聚類中心V；

2)根據式(12)更新聚類中心；

3)根據式(13)更新隸屬度；

4)根據式(14)更新視角間權重系數；

5)根據式(15)更新視角內屬性權重系數；

7)算法收斂后，輸出各視角的隸屬度矩陣uij,k；

8)利用式(16)計算出最終的劃分結果。

3 實驗與分析

3.1 實驗環境及實驗參數設置

為了驗證本文所提MV-FDW-PCM算法的性能，本文在以下幾個數據集上進行了實驗分析，實驗數據集分別是： UCI標準數據集、Brodatz紋理圖像[23]以及一組關于我實驗室老師的真實人臉圖像的實際應用效果展示。實驗采用的對比算法主要有：經典的適用于單視角聚類環境的可能性C均值聚類算法PCM(Possibilistic c-means)、具備多視角模糊聚類性能的協同模糊K均值算法CoFKM[4](Collaborative fuzzy K-means)、具備聚類任務組合能力的K均值算法CombKM[24](Combine K-means)、具有多視角聚類算法代表性的多視角譜聚類算法MVSpec[5](Multi-view spectral clustering)。所有實驗運行平臺的配置如下：酷睿i3 3.6 GHz CPU，3.42G RAM，32位Windows 7操作系統，MATLAB R2012b編程環境。

本文算法的評價指標如表2所示。

表2 評價指標Table 2 The evaluation index

表中兩種評價指標分別為歸一化互信息(normalized mutual information，NMI)和芮氏指標(rand index，RI)，這兩種指標為常用的評價聚類結果評價指標[5,12]，其取值范圍均在[0, 1]，指標數值越大(越接近1)，代表該算法的性能表現越好。

實驗中相關參數設置如下：本文MV-FDWPCM 算法中參數 m1，m2，m3均在{1.1, 1.3, 1.5, 1.7,1.9, 2.5}中尋優取得，參數θ設為1。MVSpec算法中指數 p 通過從{1, 1.1, ···, 1.9, 2, 3, ···, 6, 7}中進行網絡搜索來設置最優值。實驗結果均為算法運行20次的平均值與均方差, 因此實驗結果部分對應的NMI-mean、NMI-std、RI-mean、RI-std分別為 NMI和RI指標在20次運行后所得結果的均值和方差。

3.2 UCI標準數據實驗

本文使用了UCI數據集中經典的4種多視角表達的數據集，分別是手寫數據集(MF)、圖像分割數據集(IS)、污水處理數據集(WTP)及互聯網廣告數據集(IADS)，表3中簡要介紹了各數據集的基本信息。此外，各算法在這4種UCI數據集上的實驗結果如表4所示。

表3 UCI數據集介紹Table 3 Description of UCI data sets

表4 UCI數據集上的實驗結果對比Table 4 The performance of clustering algorithm

從實驗結果可以觀察出如下結論：

1) 通過觀察各算法在MF數據集上的聚類結果，可以明顯地看出CoFKM算法及本文所提的MVFDW-PCM算法有著較大的性能優勢。但是由于MF數據集本身所含的各視角樣本的可分性均是比較均衡一致的，因此本文算法的視角加權的優勢并不明顯，其所得性能與CoFKM算法基本接近。

2) 當進一步觀察本文算法在IS及WTP這兩個多視角數據集上的聚類性能，本文所提的MVFDW-PCM算法在IS數據集上性能優勢較為明顯，這是由于IS這類圖像分割數據集不同視角間的特征差異明顯、可分性也有一定的區分，這使得本文算法的屬性加權機制和視角加權機制產生了一些積極的聚類效果，提高了聚類性能。而對于WTP這一水污染數據集，本文算法的性能與其他4種方法相比基本處于相同的性能水平，導致這一現象的原因主要是水污染數據集樣本數較少各類之間的數據分布區分并不顯著，此外該數據所含的類別較多，這對于采用歐式距離的算法而言是一種挑戰，對于此類數據集，我們將在今后考慮使用其他的距離公式來替換歐氏距離改善聚類性能。

3) 觀察IADS數據可發現具備多視角聚類能力的算法較之單視角的聚類算法如經典的PCM算法有著明顯的聚類優勢，但本文所提的MV-FDWPCM算法的聚類性能卻略差于基于譜聚類聚類原理的MVSpec算法。究其原因在于如IADS等廣告類數據一般數據分布呈現非團狀數據特征，而PCM、CombKM、CoFKM及MV-FDW-PCM均是基于c-means框架提出的方法，其對團狀數據有效，對于非團狀數據特別是凸型數據則顯得無能為力。為了改善此類算法在非團狀數據集上的聚類性能，一種有效的途徑也是更換距離公式，今后我們也將在這部分研究內容上進行深入的探討。

3.3 Brodatz紋理圖像實驗

除了驗證本文算法在UCI標準數據集上的聚類性能，本小節還在圖像分割實驗中驗證了本文算法的性能。本文在著名的Brodatz紋理圖庫中(http://www.ux.uis.no/～tranden/brodatz.html)選擇了7種具有常見的具備代表性的紋理圖片組成了圖5。兩種不同的紋理組合圖像的目標分割數均為7。對比算法不變，各算法對該紋理圖的分割結果如圖6所示。具體的聚類性能對比如表5所示。

根據圖6各算法在兩種不同的紋理組合圖像上的實驗結果可以觀察出，本文算法MV-FDWPCM所得的分割結果與理想分割結果圖的效果最為接近。觀察圖6(a)、6(b)、6(f)及6(g)的實驗結果，我們可以肉眼評價出單視角聚類算法的性能明顯劣于3種多視角聚類算法，其分割結果的圖像質量較差。而對于3種多視角聚類算法，本文方法由于其具備多視角加權和多視角屬性加權機制，特別是多視角屬性加權機制，該機制能夠增大圖像中重要屬性的權重進而提高分割結果的質量使得本文算法獲得了優于其他兩種多視角聚類算法的更佳分割效果。綜合圖6與表5的結果，我們可以得出結論，本文提出的MV-FDW-PCM算法在圖像分割實驗中較其他算法具有更好的聚類性能。

圖5 紋理圖像Fig. 5 Texture image

圖6 各算法分割結果對比Fig. 6 Comparison of image segmentation results

表5 各算法的聚類性能對比Table 5 Comparison of clustering performance of each algorithm

3.4 真實人臉圖像實驗

在本節的實驗中，我們針對一幅真人的證件照片圖7(a)為例，以最基本的RGB通道分別獲得3個視角樣本如圖7(b)、(c)所示，而后使用本文所提的MV-FDW-PCM算法與其他的4種相關算法做了進一步的性能比對分析。由于真人照片無法標定像素的真實標記，因此NMI指標和RI指標在該實驗部分將無法使用，僅能夠通過圖8給出的分割結果從肉眼上進行評估。

從圖8的分割結果可以明顯地看出，3種具備多視角聚類能力的Co-FKM算法、MVSpec算法及本文所提的MV-FDW-PCM算法較之傳統的單視角PCM算法及CombKM算法在分割性能上有著明顯的優勢。進而，對3種多視角聚類算法的結果進行分析，本文所提的MV-FDW-PCM算法在臉部及皮膚分割方面較之其他兩種方法有著一定的分割優勢，這也從側面反映了兩種加權策略(視角加權和屬性加權)在聚類過程中起到了一定的作用, 改善了聚類結果。

圖7 真實人臉圖像Fig. 7 Real face image

3.5 算法運行性能分析

根據表6的實驗結果可知，本文所提方法的運行效率在所對比的5種方法中排名在后兩位。因本文算法包含了4個參數(聚類中心、隸屬度、視角內屬性權重及視角權重)需要迭代優化，較之傳統的PCM算法的2優化參數(類中心及隸屬度)、組合K均值算法CombKM的2優化參數(類中心及隸屬度)及多視角協同算法CoFKM的2優化參數(類中心及隸屬度)均有著高出近1倍的優化迭代需求，而對于多視角譜聚類算法MVSpec，由于該算法基于譜聚類聚類原理和MV-FDW-PCM算法的C均值聚類原理有較大差別，兩者的運行性能不具可比較性。綜上，本文算法雖擁有較之其他相關算法更佳的聚類性能，但在運行效率上較之其他算法顯得并不高效。為此，今后我們將進一步地探討如何在更少的優化參數下保持當前聚類性能的多視角可能性聚類算法。

圖8 各算法在真實人臉圖像上的分割結果Fig. 8 The segmentation results of the algorithm on the real face image

表6 各算法的運行性能對比Table 6 Comparison of the running time of each algorithm

4 結束語

為解決傳統可能性聚類算法無法滿足多視角學習場景聚類的實際問題，并進一步考慮到現有多視角聚類算法尚未重視的視角間權重及視角內特征權重優化問題，本文致力于提出一種新的具備最佳視角及最優特征劃分能力的多視角模糊雙加權可能性聚類算法(MV-FDW-PCM)。該算法基于傳統的PCM算法，給出詳細的多視角聚類學習框架，使得PCM算法具備多視角聚類能力，進而通過引入視角間模糊加權機制及視角內屬性模糊加權機制以解決視角權重及視角內特征權重優化問題。本文在UCI中的標準多視角數據集、紋理圖像分割實驗以及真實人臉圖像中，均進行了實驗驗證。實驗結果表明，本文所提的MV-FDW-PCM算法在面對多視角聚類問題時較其他對比聚類算法具備更佳的聚類效果。

[1]JIANG Y Z, DENG Z H, CHUNG F L, et al. Realizing twoview TSK fuzzy classification system by using collaborative learning[J]. IEEE transactions on systems, man, and cybernetics: systems, 2017, 47(1): 145–160.

[2]YAMANISHI Y, VERT J P, KANEHISA M. Protein network inference from multiple genomic data: a supervised approach[J]. Bioinformatics, 2004, 20(1): 363–370.

[3]PEDRYCZ W. Collaborative fuzzy clustering[J]. Pattern recognition letter, 2002, 23(14): 1675–1686.

[4]CLEUZIOU G, EXBRAYAT M, MARTIN L, et al.CoFKM: a centralized method for multiple-view clustering[C]//Proc of the 9th IEEE International Conference on Data Mining (ICDM 2009). Miami, USA, 2009: 752–757.

[5]TZORTZIS G F, LIKEAS A C. Kernel-based weighted multi-view clustering[C]//IEEE 12th International Conference on Data Mining. Brussels, Belgium, 2012: 675–684.

[6]DENG Z H, JIANG Y Z, ISHIBUCHI H, et al. Enhanced knowledge-leverage-based tsk fuzzy system modeling for inductive transfer learning[J]. ACM transactions on intelligent systems and technology, 2016, 8(1): 1–21.

[7]QIAN P J, JIANG Y Z, DENG Z H, et al. Cluster prototypes and fuzzy memberships jointly leveraged cross-domain maximum entropy clustering[J]. IEEE transaction on cybernetics, 2016, 46(1): 181–193.

[8]DENG Z H, JIANG Y Z, CHUNG F L, et al. Transfer prototype-based fuzzy clustering[J]. IEEE transactions on fuzzy systems, 2016, 24(5): 1210–1232.

[9]PAN S J, YANG Q. A survey on transfer learning[J]. IEEE transactions on knowledge and data engineering, 2010,22(10): 1345–1359.

[10]JIANG Y Z, CHUNG F L, ISHIBUCHI H, et al. Multitask TSK fuzzy system modeling by mining intertask common hidden structure[J]. IEEE transactions on cybernetics,2015, 45(3): 548–561.

[11]CARUANA R. Multitask learning[J]. Machine learning,1997, 28(1): 41–75.

[12]DENG Z H, CHOI K S, JIANG Y Z, et al. A survey on soft subspace clustering[J]. Information sciences, 2016, 348:84–106.

[13]HALL LO, GOLDGOF DB. Convergence of the singlepass and online fuzzy C-means algorithms[J]. IEEE transactions on fuzzy systems, 2011, 19(4): 792–794.

[14]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York, USA: Plenum Press,1981: 65–79.

[15]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972–976.

[16]曾令偉, 伍振興, 杜文才. 基于改進自監督學習群體智能(ISLCI)的高性能聚類算法[J]. 重慶郵電大學學報: 自然科學版, 2016, 28(1): 131–137.ZENG Lingwei, WU Zhengxin, DU Wencai. Improved selfsupervised learning collection intelligence based high performance data clustering aproach[J]. Journal of Chongqing university of posts and telecommunications:natural science edition, 2016, 28(1): 131–137.

[17]程旸, 王士同. 基于局部保留投影的多可選聚類發掘算法[J]. 智能系統學報, 2016, 11(5): 600–607.CHENG Yang, WANG Shitong. A multiple alternative clusterings mining algorithm using locality preserving projections[J]. CAAI transactions on intelligent systems, 2016,11(5): 600–607.

[18]杭文龍, 蔣亦樟, 劉解放, 等. 遷移近鄰傳播聚類算法[J].軟件學報, 2016, 27(11): 2796–2813.HANG Wenlong, JIANG Yizhang, LIU Jiefang, et al.Transfer affinity propagation clustering algorithm[J].Journal of software, 2016, 27(11): 2796–2813.

[19]鄧趙紅, 王士同, 吳錫生, 等. 魯棒的極大熵聚類算法RMEC及其例外點標識[J]. 中國工程科學, 2004, 6(9):38–45.DENG Zhaohong, WANG Shitong, WU Xisheng, et al.Robust maximum entropy clustering algorithm rmec and its outlier labeling[J]. Engineering science, 2004, 6(9): 38–45.

[20]KARAYIANNIS N B. MECA: maximum entropy clustering algorithm[C]//Proc of the 3rd IEEE Conf. on Fuzzy Systems. Orlando: IEEE Press, 1994: 630–635.

[21]KRISHNAPURAM R, KELLER J. A possibilistic ap-proach to clustering[J]. IEEE transactions on fuzzy systems, 1993, 1(2): 98–110.

[22]KRISHNAPURAM R, KELLER J M. The possiblistic means algorithms: Insights and recommendation[J]. IEEE transactions on fuzzy systems, 1996, 4(3): 385–393.

[23]TRYGVE R, BRODATZ T. Texture classification[EB/OL]. [2007-08-01]. http://www.ux.uis.no/tranden/brodatz.html.

[24]GU Q Q, ZHOU J. Learning the shared subspace for multitask clustering and transductive transfer classification[C]//Proc Int Conf Data Mining (ICDM). Miami, USA,2009: 59–168.