融合KL 信息的多視圖模糊聚類算法

賀娜，馬盈倉

（西安工程大學 理學院，西安 710600）

0 概述

聚類是一種無監(jiān)督的機器學習任務，根據(jù)數(shù)據(jù)自身的距離或相似度將它們劃分為若干組，劃分原則是組內(nèi)距離最小化而組間距離最大化［1-3］。常見的聚類算法主要包括基于層次［4-5］、基于模糊C 均值（Fuzzy C-Means，F(xiàn)CM）［6-7］、基于迭代［8-9］、基于協(xié)作［10-11］，基于分解［12-14］、基于譜聚類集群［15-17］等，其中基于FCM 的聚類算法由于具有較高的聚類準確率且易于處理、空間復雜度低，受到學者們的廣泛關注。但是基于FCM 的聚類算法主要是針對單一視圖數(shù)據(jù)的聚類算法，當其面對多視圖數(shù)據(jù)時只能對各視圖樣本進行獨立的聚類分析以得到每個視圖下的聚類結果，然后使用集成學習機制［18-19］將每個視圖下的聚類結果進行統(tǒng)一，最終獲取全局意義下的聚類結果。然而人為地將多視圖數(shù)據(jù)分解為多個單視圖數(shù)據(jù)進行處理會因不同視圖聚類結果存在明顯差異而影響最終獲取的全局劃分結果。

近些年來，學者們在多視圖聚類算法研究方面取得了較大進展。文獻［20］通過典型相關分析使用數(shù)據(jù)的多個視圖來構建投影。文獻［21］學習了同時為原始問題提供多個視圖的非冗余子空間，并在每個視圖中找到一個聚類方法。文獻［22］提出一種類似將異構圖像特征與圖相結合的多視角光譜聚類算法。文獻［23］引入共正則化譜聚類，采用共正則化框架來解決多視圖聚類問題。文獻［24］提出解決大規(guī)模多視圖數(shù)據(jù)的多視圖K-means 聚類算法。文獻［25］提出同時進行特征選擇和多視圖聚類的結構化稀疏學習方法。文獻［26］分析并研究了基于采樣的主動式初始中心選擇方法對K-means 型多視圖聚類算法的影響。雖然上述算法取得了較好的性能，但其中一些算法忽略了視圖多樣性。文獻［27］通過人為干預或先驗知識實現(xiàn)多視圖加權，但不能保證最終結果與每個視圖的貢獻相一致。文獻［28］提出一種基于FCM 的多視角模糊聚類方法CoFKM，但由于每個視圖被平等對待，因此沒有考慮每個視圖的權重。文獻［29］指出在某些視圖有噪聲或存在干擾的情況下，算法聚類精度可能會降低。受現(xiàn)有研究的啟發(fā)，本文提出一種新的多視圖自加權聚類算法KMFC。該算法通過學習共識隸屬度矩陣進行聚類表示來挖掘多個視圖的潛在共識信息，求解多個隸屬度矩陣和質心矩陣，并利用視圖的特定信息進一步修正共識隸屬度矩陣。

1 模型建立與求解

1.1 模型建立

建立多視圖聚類模型，通過引入Kullback-Leibler（KL）信息使學習的矩陣U*盡可能與每個U(p)一致，從而得到如下目標函數(shù)：

在提高視圖內(nèi)聚類結果時，需要考慮不同視圖間的聚類一致性。若直接將多個視圖拼接在一起，則不利于提高聚類性能。更合理的方法是將這些視圖與合適的權重αp(p=1,2,…,m)進行整合，并增加一個參數(shù)q來保持權重分布的平滑性。如果在式（1）中添加這些參數(shù)，則調(diào)整如下：

由于每個視圖都有各自的屬性信息，因此KMFC 算法可以使視圖內(nèi)信息與公共信息進行較好的擬合，其中視圖內(nèi)信息來自v(p)，不同視圖之間的公共信息來自共識隸屬度矩陣U*。

1.2 模型求解

將多視圖聚類模型的目標函數(shù)分為4 個子問題，通過迭代交替優(yōu)化方法進行求解。

1）固定V、α、U*，更新U，問題式（2）可以改寫如下：

式（3）的拉格朗日函數(shù)表示如下：

其中：η≥0 為約束條件下的拉格朗日乘子。

結合式（6）和式（7）得到：

2）固定U、α、U*，更新V，省略與V無關的正則化項：

使用J表示問題式（9）的目標函數(shù)，得到：

3）固定U、V、U*，更新α，省略與α無關的正則化項：

式（13）的拉格朗日函數(shù)表示如下：

其中：γ，β是拉格朗日乘子。

利用式（14）對αp求導，使其為0，得到：

問題式（13）的KKT 條件表示如下：

結合式（16）～式（18）得到βpαp=0，并將式（15）乘以αp得到：

結合式（19）與式（20）得到：

4）固定U、V、α，更新U*，省略與U*無關的項：

式（22）的拉格朗日函數(shù)表示如下：

其中：ξ≥0 為約束條件下的拉格朗日乘子。

結合式（25）和式（26）得到：

綜上所述，通過問題1 的求解可更新p個視圖的隸屬度矩陣U(p)。通過問題2 的求解更新v(p)可得到p個視圖的聚類中心矩陣。通過問題3 的求解可學習權值αp來協(xié)調(diào)不同的視圖。通過問題4 的求解可學習一個共識隸屬度矩陣U*來表示不同視圖之間的聚類。重復上述過程，直到目標函數(shù)收斂。

1.3 算法流程

算法1KMFC 算法

2 理論分析

2.1 冪指數(shù)q

利用參數(shù)q來調(diào)整權值分布，根據(jù)式（21）可得出存在兩種極端情況：1）當q→∞時，KMFC 算法得到相等的權值，即2）當q→1+時，設Φo為{Φ1,Φ2,…,Φo,…,Φm}中的最小值，將Φo代入式（21）中得到權值：

由此可見，KMFC 算法將權重1 賦給Φo最小的視圖，將權重0 賦給其他視圖。通過該方法可以保證KMFC 算法在q>1 時不存在平凡解。

2.2 收斂性分析

定理1在每次迭代中，問題式（2）的目標函數(shù)值不斷減小，直到算法收斂。

其中：上述目標函數(shù)和約束在αp域中是凸的。這樣問題式（31）就會收斂到全局最優(yōu)解。

顯然，問題式（2）可以分為4 個子問題，每個子問題都是一個凸優(yōu)化問題。因此，上述證明過程驗證了算法1 的收斂性。

3 實驗與結果分析

根據(jù)聚類精度（Accuracy，ACC）［30］、標準化互信息（Normalized Mutual Information，NMI）［30］、相似性（Jaccard）［31］、純度（Purity）［31］4 個評價指標對KMFC 算法進行性能評價。

3.1 數(shù)據(jù)集

在5 個真實數(shù)據(jù)集上評估KMFC 算法的性能：

1）COIL20 數(shù)據(jù)集［32］具有1 440 張標準化圖像，包含20 個對象，每個對象對應72 張圖像。每張圖像可以用30 個等距投影（Isometric，ISO）、19 個線性判別分析（Linear Discriminant Analysis，LDA）和30 個鄰域保持嵌入（Neighborhood Preserving Embedding，NPE）這3 類異構特征來表示。

2）YALE 數(shù)據(jù)集［33］由15 名受試者的165 張圖像組成，每個受試者有11 張圖像，對應不同的面部表情或形態(tài)。每張圖像可以用30 個ISO、14 個LDA 和30 個NPE 這3 類異構特征來表示。

3）3-Sources 數(shù)據(jù)集［34］包含294 篇新聞文章，涵蓋商業(yè)、娛樂、健康、政治、體育和技術6 個方面。第一視圖有3 068 個特征，第二視圖有3 631 個特征，第三視圖有3 560 個特征。

4）NUS-WIDE數(shù)據(jù)集［35］由包含81個對象的269 648張圖像組成。在實驗中選擇貓、牛、狗、麋鹿、鷹、馬、獅子、松鼠、老虎、鯨魚、狼、斑馬12 種動物類別。每張圖像可以用64 種顏色直方圖、144 種顏色相關圖、73 種邊緣方向直方圖、128個小波紋理、225個塊狀顏色矩和500袋基于SIFT 描述的單詞這6 類低級特征來表示。

5）Prokaryotic phyla 數(shù)據(jù)集［36］包含551 個原核生物種類，包括文本數(shù)據(jù)和不同的基因組表達。本文選用的1 個視圖數(shù)據(jù)為由描述原核生物種類的文檔詞袋表示組成的文本數(shù)據(jù)，另外2 個視圖數(shù)據(jù)為2 種基因組表示［17］。與文獻［17］一樣，為降低數(shù)據(jù)集維數(shù)，對3 個視圖分別應用主成分分析（Principal Component Analysis，PCA）并保留解釋90%方差的主成分。

數(shù)據(jù)集統(tǒng)計信息如表1 所示。

表1 數(shù)據(jù)集統(tǒng)計信息Table 1 Dataset statistics

3.2 評價指標

對于ACC、NMI、Jaccard、Purity 這些廣泛使用的指標，值越大表示集群性能越好。

ACC 表示聚類精度，定義如下：

其中：n為樣本點的個數(shù)；τi為第i個樣本點真實的類標簽；ri為學習到的第i個樣本點對應的類標簽；δ(x,y)定義為一個函數(shù)，當x=y時δ(x,y)=1，否則為0；map(ri)是一個映射函數(shù)，它將學習到的標簽ri與真實標簽τi進行匹配。

NMI 表示τi和ri之間的相似程度，定義如下：

其中：ni表示算法中每一類ri(1 ≤i≤c)包含的樣本點的個數(shù)表示算法中每一類τj(1 ≤j≤c)包含的樣本點的個數(shù)；ni,j表示學習到的第i個樣本點對應的類標簽ri和真實的類標簽τj的交集中所包含的樣本點的個數(shù)。

Jaccard 度量有限樣本集N1和N2之間的相似性，定義如下：

其中：TTP是真陽性的數(shù)目；FFP是假陽性的數(shù)目；FFN是假陰性的數(shù)目。

Purity 是正確類標簽的百分比，定義如下：

Purity 的取值范圍為[0,1]，值越靠近1，性能越好。

3.3 實驗設置

首先，比較KMFC 算法與FCM 算法和熵模糊C 均值（Entropy Fuzzy C-Means，EFCM）算法的性能，以證明KMFC 算法體現(xiàn)了多視圖算法的優(yōu)勢。其次，將KMFC 算法與SWMC［37］、MVASM［38］、MVGL［39］3 種算法進行比較，其中比較算法中涉及的參數(shù)調(diào)整參照原文獻進行設置并實驗以顯示最優(yōu)結果。在KMFC 算法中，參數(shù)q控制不同視圖上權值的分配，參數(shù)λ調(diào)節(jié)共識隸屬度矩陣的稀疏性。根據(jù)式（21）在[1,30]內(nèi)以步長為0.01 來調(diào)節(jié)q，在[0,10]內(nèi)以步長0.1 來調(diào)節(jié)λ，在3-Source、NUS-WIDE 和Prokaryotic phyla 數(shù)據(jù)集上設置(q,λ)分別為（1.22，0.9）、（1.30，0.4）和（1.02，0.3）時KMFC 算法的評價指標變化，如圖1～圖3 所示。

圖1 KMFC 算法在3-Source、NUS-WIDE 和Prokaryotic phyla數(shù)據(jù)集上的ACC比較Fig.1 ACC comparation of KMFC algorithm on 3-Source，NUS-WIDE and Prokaryotic phyla datasets

圖2 KMFC 算法在3-Source、NUS-WIDE 和Prokaryotic phyla數(shù)據(jù)集上的NMI比較Fig.2 NMI comparation of KMFC algorithm on 3-Source，NUS-WID and Prokaryotic phyla datasets

圖3 KMFC 算法在3-Source、NUS-WIDE 和Prokaryotic phyla數(shù)據(jù)集上的Purity比較Fig.3 Purity comparation of KMFC on 3-Source，NUS-WID and Prokaryotic phyla datasets

3.4 實驗結果

在COIL20 和YALE32數(shù)據(jù)集上，KMFC和2種單視圖聚類算法FCM、EFCM 的ACC、NMI、Jaccard和Purity 比較結果如表2、表3 所示，其中括號中的數(shù)字表示算法排名。從表2、表3 可以看出：在ACC、NMI、Jaccard和Purity4個評價指標上，KMFC算法在COIL20 數(shù)據(jù)集上相比FCM（2）算法分別提高0.584 9、0.375 5、0.692 4、0.687 4，相比EFCM（2）算法分別提高0.5899、0.383 6、0.702 0、0.698 5；在YALE32 數(shù)據(jù)集上，KMFC 算法相比FCM（2）算法分別提高0.471 6、303 4、617 5、610 8，相比EFCM（2）算法分別提高0.506 7、0.313 4、0.628 4、0.625 3。上述結果證明了多視圖學習的優(yōu)越性和有效性，并且其有利于提高聚類精度。

表2 在COIL20 數(shù)據(jù)集上KMFC 與2 種單視圖聚類算法的ACC、NMI、Jaccard 和Purity 比較Table 2 Comparison of ACC，NMI，Jaccard and Purity between KMFC and two single-view clustering algorithms on COIL20 dataset

表3 在YALE32 數(shù)據(jù)集上KMFC 與2 種單視圖聚類算法的ACC、NMI、Jaccard 和Purity 比較Table 3 Comparison of ACC，NMI，Jaccard and Purity between KMFC and two single-view clustering algorithms on YALE32 dataset

在3-Source、NUS-WIDE 和Prokaryotic phyla 數(shù)據(jù)集上不同多視圖聚類算法的ACC、NMI 和Purity比較結果如表4～表6所示。從表4～表6可以看出：在數(shù)據(jù)集3-Sources 上，KMFC 算法的ACC、NMI、Purity 相比次優(yōu)的MVASM 算法分別提高0.074 6、0.153 4、0.054 8；在數(shù)據(jù)集NUS-WIDE 上，KMFC 算法相比次優(yōu)的MVASM 算法分別提高0.057 4、0.002 4、0.006 7；在數(shù)據(jù)集Prokaryotic phyla 上，KMFC 算法相比次優(yōu)的MVGL算法分別提高0.060 9、0.062 6、0.000 7。KMFC 算法在3 個數(shù)據(jù)集上的收斂曲線如圖4 所示?？梢?，KMFC算法的聚類性能明顯優(yōu)于對比算法。

表4 在3-Source 數(shù)據(jù)集上不同多視圖聚類算法的ACC、NMI 和Purity 比較Table 4 Comparison of ACC，NMI and Purity of different multi-view clustering algorithms on 3-Source dataset

表5 在NUS-WIDE 數(shù)據(jù)集上不同多視圖聚類算法的ACC、NMI 和Purity 比較Table 5 Comparison of ACC，NMI and Purity of different multi-view clustering algorithms on NUS-WIDE dataset

表6 在Prokaryotic phyla 數(shù)據(jù)集上不同多視圖聚類算法的ACC、NMI 和Purity 比較Table 6 Comparison of ACC，NMI and Purity of different multi-view clustering algorithms on Prokaryotic phyla dataset

圖4 在3-Sources、NUS-WIDE、Prokaryotic phyla 數(shù)據(jù)集上KMFC 算法的收斂曲線Fig.4 Convergence curves of KMFC algorithm on 3-Sources，NUS-WIDE，Prokaryotic phyla datasets

4 結束語

本文提出一種新的多視圖加權聚類算法，將每個視圖信息及其權重進行擬合融入標準模糊C 均值聚類算法，再附加一個KL 信息作為模糊正則項，其中KL 信息是一個視圖的隸屬度與其共識隸屬度的比值，因此最小化KL 信息會使每個視圖的隸屬度偏向于共識隸屬度，最終實現(xiàn)對共識隸屬度矩陣的聚類。在多個數(shù)據(jù)集上的實驗結果證明了該算法的有效性。但該算法中的權重需要引入冪指數(shù)q來進行調(diào)節(jié)，其細微變化即可影響算法性能，因此下一步將設計并實現(xiàn)融合KL信息的多視圖完全自加權模糊聚類算法。