賀娜，馬盈倉(cāng)

（西安工程大學(xué) 理學(xué)院，西安 710600）

0 概述

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

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

1 模型建立與求解

1.1 模型建立

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

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

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

1.2 模型求解

將多視圖聚類(lèi)模型的目標(biāo)函數(shù)分為4 個(gè)子問(wèn)題，通過(guò)迭代交替優(yōu)化方法進(jìn)行求解。

1）固定V、α、U*，更新U，問(wèn)題式（2）可以改寫(xiě)如下：

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

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

結(jié)合式（6）和式（7）得到：

2）固定U、α、U*，更新V，省略與V無(wú)關(guān)的正則化項(xiàng)：

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

3）固定U、V、U*，更新α，省略與α無(wú)關(guān)的正則化項(xiàng)：

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

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

利用式（14）對(duì)αp求導(dǎo)，使其為0，得到：

問(wèn)題式（13）的KKT 條件表示如下：

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

結(jié)合式（19）與式（20）得到：

4）固定U、V、α，更新U*，省略與U*無(wú)關(guān)的項(xiàng)：

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

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

結(jié)合式（25）和式（26）得到：

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

1.3 算法流程

算法1KMFC 算法

2 理論分析

2.1 冪指數(shù)q

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

由此可見(jiàn)，KMFC 算法將權(quán)重1 賦給Φo最小的視圖，將權(quán)重0 賦給其他視圖。通過(guò)該方法可以保證KMFC 算法在q>1 時(shí)不存在平凡解。

2.2 收斂性分析

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

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

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

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

根據(jù)聚類(lèi)精度（Accuracy，ACC）［30］、標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）［30］、相似性（Jaccard）［31］、純度（Purity）［31］4 個(gè)評(píng)價(jià)指標(biāo)對(duì)KMFC 算法進(jìn)行性能評(píng)價(jià)。

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

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

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

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

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

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

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

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

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

3.2 評(píng)價(jià)指標(biāo)

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

ACC 表示聚類(lèi)精度，定義如下：

其中：n為樣本點(diǎn)的個(gè)數(shù)；τi為第i個(gè)樣本點(diǎn)真實(shí)的類(lèi)標(biāo)簽；ri為學(xué)習(xí)到的第i個(gè)樣本點(diǎn)對(duì)應(yīng)的類(lèi)標(biāo)簽；δ(x,y)定義為一個(gè)函數(shù)，當(dāng)x=y時(shí)δ(x,y)=1，否則為0；map(ri)是一個(gè)映射函數(shù)，它將學(xué)習(xí)到的標(biāo)簽ri與真實(shí)標(biāo)簽τi進(jìn)行匹配。

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

其中：ni表示算法中每一類(lèi)ri(1 ≤i≤c)包含的樣本點(diǎn)的個(gè)數(shù)表示算法中每一類(lèi)τj(1 ≤j≤c)包含的樣本點(diǎn)的個(gè)數(shù)；ni,j表示學(xué)習(xí)到的第i個(gè)樣本點(diǎn)對(duì)應(yīng)的類(lèi)標(biāo)簽ri和真實(shí)的類(lèi)標(biāo)簽τj的交集中所包含的樣本點(diǎn)的個(gè)數(shù)。

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

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

Purity 是正確類(lèi)標(biāo)簽的百分比，定義如下：

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

3.3 實(shí)驗(yàn)設(shè)置

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

在COIL20 和YALE32數(shù)據(jù)集上，KMFC和2種單視圖聚類(lèi)算法FCM、EFCM 的ACC、NMI、Jaccard和Purity 比較結(jié)果如表2、表3 所示，其中括號(hào)中的數(shù)字表示算法排名。從表2、表3 可以看出：在ACC、NMI、Jaccard和Purity4個(gè)評(píng)價(jià)指標(biāo)上，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。上述結(jié)果證明了多視圖學(xué)習(xí)的優(yōu)越性和有效性，并且其有利于提高聚類(lèi)精度。

表2 在COIL20 數(shù)據(jù)集上KMFC 與2 種單視圖聚類(lèi)算法的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 種單視圖聚類(lèi)算法的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ù)集上不同多視圖聚類(lèi)算法的ACC、NMI 和Purity比較結(jié)果如表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 個(gè)數(shù)據(jù)集上的收斂曲線如圖4 所示。可見(jiàn)，KMFC算法的聚類(lèi)性能明顯優(yōu)于對(duì)比算法。

表4 在3-Source 數(shù)據(jù)集上不同多視圖聚類(lèi)算法的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ù)集上不同多視圖聚類(lèi)算法的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ù)集上不同多視圖聚類(lèi)算法的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 結(jié)束語(yǔ)

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