姜凱彬，周世兵，錢雪忠，管嬌嬌

江南大學(xué) 人工智能與計算機(jī)學(xué)院，江蘇 無錫214122

聚類是機(jī)器學(xué)習(xí)中的一個重要課題，旨在發(fā)現(xiàn)數(shù)據(jù)的底層結(jié)構(gòu)。在許多現(xiàn)實(shí)世界的應(yīng)用程序中，數(shù)據(jù)通常是從不同的來源生成的。例如，信號可以從多個傳感器獲得，圖像可以由多個特征描述符描述。所有這些都稱為多視圖數(shù)據(jù)[1]。因?yàn)椴煌晥D可以捕捉不同數(shù)據(jù)視角，存在不同的統(tǒng)計特性，傳統(tǒng)單視圖的聚類方法無法充分反映多視圖聚類結(jié)構(gòu)的本質(zhì)。因此通過集成異構(gòu)和互補(bǔ)的信息的無監(jiān)督多視圖聚類方法開始變得流行。

簡單地將所有特征直接連接成單個視圖，然后對單個視圖數(shù)據(jù)進(jìn)行聚類，可能不會獲得比單獨(dú)使用單個視圖的傳統(tǒng)方法更好的性能。在過去十年中，許多考慮不同視圖多樣性和互補(bǔ)性的先進(jìn)多視圖聚類算法被提出，大致可分為多視圖協(xié)同訓(xùn)練算法[2]、多視圖多核聚類算法[3]、基于圖的多視圖聚類算法[4]、基于子空間的多視圖聚類算法[5]。

在這些方法中，采用多視圖譜聚類可以在任意形狀的數(shù)據(jù)集上聚類并收斂得到全局最優(yōu)解。因此，多視圖譜聚類能更好地探索多視圖數(shù)據(jù)的非線性結(jié)構(gòu)，在實(shí)踐中常優(yōu)于其他多視圖聚類方法。文獻(xiàn)[2]開發(fā)了一種使用線性核來最小化不同譜嵌入之間的不一致并對多個分區(qū)進(jìn)行正則化的方法。但這種方法不能區(qū)分不同視圖的可靠性，容易被噪聲較多的視圖所干擾。為了區(qū)分不同視圖對于聚類結(jié)果的影響，文獻(xiàn)[6]提出了自適應(yīng)加權(quán)的多視圖譜聚類方法。文獻(xiàn)[7]提出一種從多個視圖中學(xué)習(xí)一個具有稀疏結(jié)構(gòu)的一致相似矩陣，然后進(jìn)行單獨(dú)聚類的多視圖譜聚類算法。為了避免額外的聚類步驟帶來的不確定性，文獻(xiàn)[8]提出一種基于非負(fù)矩陣分解的松弛全局相似性矩陣約束的多視圖聚類算法。上述聚類方法成功解決了低維數(shù)據(jù)中的聚類問題。為了處理高維數(shù)據(jù)，文獻(xiàn)[9]提出了兩種無參數(shù)加權(quán)投影聚類方法，可同時進(jìn)行結(jié)構(gòu)圖學(xué)習(xí)和數(shù)據(jù)降維。

雖然這些算法在不同的場景下取得了較好結(jié)果，但仍存在以下問題：（1）以往許多工作都集中在原始數(shù)據(jù)上，而忽略了高維數(shù)據(jù)引入的噪聲和冗余信息。當(dāng)高維數(shù)據(jù)直接用于聚類任務(wù)時，可能會導(dǎo)致重要信息的丟失以及算法性能的下降。（2）現(xiàn)有方法大都預(yù)先構(gòu)造一個共識圖，然后利用該固定的圖執(zhí)行聚類任務(wù)，這種兩步的分離策略可能會造成聚類結(jié)果的次優(yōu)解。（3）通過引入額外的超參數(shù)來解決不同視圖在模型中產(chǎn)生的影響，可能會導(dǎo)致模型復(fù)雜度的提高。

為了解決上述問題，本文提出了一種動態(tài)融合的多視圖投影聚類算法（dynamic-fusion multi-view projection clustering algorithm，DFMPC），將自適應(yīng)降維圖學(xué)習(xí)、無參數(shù)的自權(quán)重圖融合和譜聚類整合在同一框架中，聯(lián)合優(yōu)化投影矩陣、相似性矩陣、共識矩陣以及聚類標(biāo)簽。具體來說，首先將高維數(shù)據(jù)投影到低維子空間，建立不同視圖的相似圖?；诓煌晥D具有相同的底層聚類結(jié)構(gòu)這一假設(shè)，在動態(tài)融合過程中，將共識矩陣與所有相似度矩陣對齊一致，自動學(xué)習(xí)各視圖的權(quán)重并對得到的共識矩陣的拉普拉斯矩陣施加秩約束，直接獲得聚類結(jié)果。與以往引入需要人工調(diào)整的超參數(shù)不同的是，本文引入的啟發(fā)式超參數(shù)會隨著每次優(yōu)化迭代自動調(diào)整。此外，本文設(shè)計了一種有效的交替迭代方法來求解聯(lián)合優(yōu)化問題。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上得到的實(shí)驗(yàn)結(jié)果表明該算法的優(yōu)越性。

1 相關(guān)工作

本章介紹了多視圖聚類方法的基本符號定義，并回顧了傳統(tǒng)多視圖聚類算法的基本形式。

1.1 符號與定義

定義一個具有m個視圖、n個樣本的多視圖數(shù)據(jù)集為X=[X1,X2,…,Xm]∈Rdv×n，其中dv代表第v個視圖的維度。對于一個矩陣Xv來說，和分別表示矩陣第i行第j列元素以及第j列向量。矩陣X的Frobenius 范數(shù)、跡和轉(zhuǎn)置分別表示為||X||F、tr(X)和XT。向量x的第2 范數(shù)為||x||2。此外，I表示單位矩陣，1表示元素全為1的列向量。

1.2 多視圖聚類

2 算法模型

本章在上文介紹的基礎(chǔ)上，提出了本文的算法模型，并給出了模型的優(yōu)化求解算法。

2.1 動態(tài)融合的多視圖投影聚類算法

鑒于子空間學(xué)習(xí)在高維數(shù)據(jù)處理中的優(yōu)越性，本文在前文介紹的式（1）的基礎(chǔ)上，將原始數(shù)據(jù)Xv投影到低維子空間，從具有盡可能少的噪聲和冗余的低維子空間中學(xué)習(xí)相似度矩陣。其對應(yīng)的低維子空間的自適應(yīng)圖學(xué)習(xí)優(yōu)化目標(biāo)如式（3）所示：

在多視圖學(xué)習(xí)中，考慮到每個視圖的相似度圖都是共識圖的擾動，以及為了避免低質(zhì)量視圖的影響，讓共識圖更好地捕捉隱藏在多視圖數(shù)據(jù)中的真實(shí)樣本相似性，本文通過衡量不同視圖的重要性來輸出最終的共識表示，并期望低維子空間中的共識矩陣A可以將所有相似度矩陣S一致對齊。在此基礎(chǔ)上，自權(quán)重融合機(jī)制如式（4）所示：

其中，權(quán)重αv代表不同視圖的重要性，可以采用反向距離加權(quán)方案[6]得到權(quán)重αv，具體公式如下：

此時動態(tài)融合得到的共識矩陣A并不能直接獲得最終聚類結(jié)果，還需要額外的聚類步驟。由文獻(xiàn)[13]可知，A的拉普拉斯矩陣LA的特征值0的重數(shù)r等于A的圖中連通分量數(shù)。為了使動態(tài)融合得到共識矩陣的數(shù)據(jù)點(diǎn)精確聚集成c個簇，即rank(LA)=n-c，希望對共識矩陣A的圖拉普拉斯矩陣施加秩約束，使A達(dá)到理想的效果。但由于LA依賴于目標(biāo)矩陣A并且rank(LA)=n-c也是非線性的，直接引入秩約束會使得優(yōu)化問題難以求解。根據(jù)Ky Fan’s定理[14]，可以得到式（6）：

最后，整合式（3）、式（4）、式（6），得到動態(tài)融合的多視圖投影聚類算法模型的目標(biāo)函數(shù)：

通過這種方式，可以同時研究投影矩陣、相似矩陣、共識矩陣、權(quán)系數(shù)和譜嵌入矩陣，在統(tǒng)一的優(yōu)化框架下聯(lián)合學(xué)習(xí)自適應(yīng)圖、自權(quán)重圖融合和聚類標(biāo)簽。具體來說，(Wv)TXv(Xv)TWv將正交約束應(yīng)用于散射矩陣進(jìn)行低維子空間學(xué)習(xí)，建立不同視圖的相似圖S，緩解了維數(shù)災(zāi)難，保留了數(shù)據(jù)有效信息。融合過程中共識矩陣A自動學(xué)習(xí)各S視圖的權(quán)重，學(xué)習(xí)到的A返回更新各視圖的相似矩陣S。共識矩陣的拉普拉斯矩陣LA上的秩約束也適用于約束共識矩陣中連通分量的個數(shù)（等于所需的簇數(shù)c），直接獲得聚類結(jié)果。

2.2 模型優(yōu)化

2.2.1 固定Wv、A、F，優(yōu)化Sv

關(guān)于初始化相似度矩陣，去掉其他無關(guān)項(xiàng)，每個視圖初始化相似度矩陣優(yōu)化式可以轉(zhuǎn)化為：

由式（9）得到目標(biāo)函數(shù)的拉格朗日函數(shù)：

其中，η和ξ是拉格朗日乘子。根據(jù)KKT（Karush-Kuhn-Tucker）條件[15]，求解得到式（10）中初始化相似度矩陣Sv的最優(yōu)解為：

然而，關(guān)于迭代優(yōu)化過程中的相似度矩陣，去掉其他無關(guān)項(xiàng)，優(yōu)化式可以轉(zhuǎn)化為：

同理，按照求解式（8）的方法求解式（12），從而得到相似度矩陣Sv的最優(yōu)解為：

2.2.2 固定Sv、A、F，優(yōu)化Wv

去掉其他無關(guān)項(xiàng)，關(guān)于Wv優(yōu)化式可以轉(zhuǎn)化為：

2.2.3 固定Sv、Wv、F，優(yōu)化A

去掉其他無關(guān)項(xiàng)，關(guān)于A優(yōu)化式可以轉(zhuǎn)化為：

為了加速計算，文獻(xiàn)[16]中提出的有效迭代算法使A完全稀疏。定義vi是一個向量并且令其第j個元素vij=，A的最優(yōu)解可化簡為：

2.2.4 固定Sv、Wv、A，優(yōu)化F

去掉其他無關(guān)項(xiàng)，關(guān)于F優(yōu)化式可以轉(zhuǎn)化為：

F的最優(yōu)解通過對LA進(jìn)行特征值分解，選擇c個最小非零特征值對應(yīng)的c個特征向量得到。

2.2.5 優(yōu)化αv、β、λ

對于權(quán)重系數(shù)αv的更新，在式（5）中已經(jīng)給出，它依賴于A和Sv。而傳統(tǒng)方法的參數(shù)β、λ值可能從0 到無窮大，很難調(diào)整，因此本文以啟發(fā)式的方法進(jìn)行更新優(yōu)化[17]，避免了選擇參數(shù)的不確定性，能較好地保留數(shù)據(jù)結(jié)構(gòu)信息且可以得到更好的性能。對于參數(shù)β，在不失普遍性的情況下，假設(shè)式（13）中g(shù)i1,gi2,…,gin從小到大排列，若限制si有k個非零項(xiàng)，可以得到sik>0和si,k+1=0。此外，還要對式（13）施加=1 正則化約束。為了得到具有k個非零值的最優(yōu)稀疏si，考慮數(shù)據(jù)的局部性，β可設(shè)置為：

而λ的初始值設(shè)為1，該值在每次迭代中自動調(diào)整。若在迭代過程中A的連通分量數(shù)小于簇的個數(shù)c，則λ變?yōu)閮杀叮环粗?，則λ減少一半。

2.3 時間復(fù)雜度分析

整個算法流程如算法1 所示。在整個優(yōu)化過程中，所提出的DFMPC算法的時間復(fù)雜度主要由三部分組成：相似圖構(gòu)造、圖融合和譜聚類。其對應(yīng)的復(fù)雜度分別為O(mnd+4nd2+d3)、O(n3+mn)以及O(cn2)。其中m代表視圖數(shù)，d代表特征數(shù)，c代表聚類數(shù)。由于n?m并且n?c，DFMPC 算法的時間復(fù)雜度可以表示為O(4nd2+d3+n3)。

算法1DFMPC

輸入：具有m個視圖的多視圖數(shù)據(jù)集{Xv}mv=1，聚類個數(shù)c，初始啟發(fā)式超參數(shù)λ。

輸出：共識矩陣A∈Rn×n及聚類結(jié)果。

3 實(shí)驗(yàn)研究

本文在2 個人工數(shù)據(jù)集、8 個圖像和文檔真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，同時與目前已有的一些先進(jìn)算法進(jìn)行比較，驗(yàn)證本文提出的DFMPC算法的優(yōu)越性。

3.1 人工數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)選取兩組人工數(shù)據(jù)集RandomGaussian數(shù)據(jù)集和TwoMoon 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中兩組人工數(shù)據(jù)集介紹如下：

（1）RandomGaussian數(shù)據(jù)集：兩個視圖都由中心分別為(0,1)和(-1,0)的二維兩高斯分布數(shù)據(jù)組成，每個類有100個樣本點(diǎn)，每個類的協(xié)方差矩陣為

（2）TwoMoon 數(shù)據(jù)集：兩個視圖分別通過添加0.12%的隨機(jī)高斯噪聲疊加彎月的形狀生成，每個類有100個樣本點(diǎn)。

由于頁面空間限制，本文只展示DFMPC在每個人工數(shù)據(jù)集上單個視圖的聚類過程。圖1 顯示了RandomGaussian 數(shù)據(jù)集和TwoMoon 數(shù)據(jù)集的第一個視圖的聚類過程。圖1（b）展示出不同視圖初始的相似矩陣構(gòu)造圖，可以看到兩個類簇是有連接的。圖1（c）展示出不同視圖迭代學(xué)習(xí)后的相似矩陣構(gòu)造圖。可以看出一些有噪聲的相似度邊緣被刪除，而一些可信的相似度邊緣被加強(qiáng)，這表明學(xué)習(xí)得到的共識矩陣可以有效改進(jìn)相似度矩陣。但兩個類簇此時并未完全分離。圖1（d）展示出不同視圖最終學(xué)習(xí)到的共識矩陣構(gòu)造圖。由于本文算法可以利用不同視圖的互補(bǔ)信息，對不同視圖中難以分離的點(diǎn)進(jìn)行更為有效的分離從而得到完全分離的兩個類簇。

圖1 DFMPC在人工數(shù)據(jù)集上的聚類結(jié)果Fig.1 Clustering results of DFMPC on artificial datasets

總的來說，不同視圖的相似矩陣和自加權(quán)得到的共識矩陣的學(xué)習(xí)可以相互加強(qiáng)，彼此促進(jìn)，形成一種動態(tài)融合的增強(qiáng)效果，進(jìn)而得到一個擁有最佳的底層聚類結(jié)構(gòu)的共識矩陣。

3.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

為了全面評估DFMPC 算法對不同的多視圖數(shù)據(jù)集的兼容性和有效性，本節(jié)在表1所示的8個真實(shí)數(shù)據(jù)集上，與7種現(xiàn)有算法進(jìn)行了實(shí)驗(yàn)比較。

表1 數(shù)據(jù)集介紹Table 1 Introduction of datasets

8 個多視圖數(shù)據(jù)集分別是：來源于文獻(xiàn)[6]的Caltech101-7、Caltech101-20，來源于Clément Grimal（http://lig-membres.imag.fr/grimal/data.html）的Newsgroups（NGs）以及來源于文獻(xiàn)[8]的BBCSport、3sources、UCI、MSRCv1和ORL。

用于比較的7 種多視圖譜聚類算法分別是：SC_best、Co-reg（co-regularized）[2]、SwMC（self-weighted multiview clustering）[6]、SwMPC（self-weighted multiview projected clustering）[9]、MCLES（multi-view clustering in latent embedding space）[8]、MSC_IAS（multiview subspace clustering with intactness-aware similarity）[10]和GFSC（multi-graph fusion for multi-view spectral clustering）[18]。其中SC_best方法是將本文算法涉及到的譜聚類算法在多視圖數(shù)據(jù)集的每個單視圖上執(zhí)行，然后選取最佳單個視圖結(jié)果。

對比方法參數(shù)根據(jù)原始論文中的建議進(jìn)行調(diào)整，以產(chǎn)生最佳結(jié)果。在實(shí)驗(yàn)中，算法精度為20次運(yùn)行結(jié)果的平均值和標(biāo)準(zhǔn)差。采用了4 種常用的評價指標(biāo)，即準(zhǔn)確度（accuracy，ACC）、歸一化互信息（normalized mutual information，NMI）、調(diào)整蘭德指數(shù)（adjusted Rand index，ARI）和純度（purity，PUR）。對于這些度量，值越高表示聚類性能越好。表2 至表5報告了8個真實(shí)數(shù)據(jù)集的詳細(xì)聚類結(jié)果，粗體值代表最佳性能，其中→0→0 表示均值和標(biāo)準(zhǔn)差非常接近于0。

表2 不同算法在數(shù)據(jù)集上的ACCTable 2 ACC of different algorithms on datasets 單位：%

在某些情況下，基于單視圖基線的SC_best方法比一些多視圖基線方法稍好，這表明探索多視圖數(shù)據(jù)仍然需要良好的多視圖聚類技術(shù)。相比之下，本文提出的DFMPC 方法表現(xiàn)出更好的性能。這主要是因?yàn)镈FMPC采用了動態(tài)圖融合和自加權(quán)策略，學(xué)習(xí)到了更精確的一致特征表示。

表3 不同算法在數(shù)據(jù)集上的NMITable 3 NMI of different algorithms on datasets 單位：%

表4 不同算法在數(shù)據(jù)集上的ARITable 4 ARI of different algorithms on datasets 單位：%

表5 不同算法在數(shù)據(jù)集上的PURTable 5 PUR of different algorithms on datasets 單位：%

DFMPC 在ACC、NMI、ARI 和PUR 四個指標(biāo)上都明顯優(yōu)于Co-reg經(jīng)典協(xié)同訓(xùn)練多視圖方法。相比之下，DFMPC能更好區(qū)分不同視圖的可靠性。

基于圖的SwMC 方法在3sources 和Caltech101-20 數(shù)據(jù)集的ARI 指標(biāo)分別比DFMPC 高7.21 個百分點(diǎn)和10.6個百分點(diǎn)，但在其他數(shù)據(jù)集中DFMPC表現(xiàn)更好。這表明通過聯(lián)合學(xué)習(xí)單個圖和統(tǒng)一圖，DFMPC可以融合所有視圖學(xué)習(xí)更好的一致特征表示。

多數(shù)真實(shí)數(shù)據(jù)集上的結(jié)果表明，DFMPC 算法優(yōu)于MSC_IAS、SwMPC、MCLES 和GFSC 多視圖子空間聚類方法。這是因?yàn)镈FMPC 對高維數(shù)據(jù)投影降維，并用非參數(shù)自加權(quán)方法提高了聚類效果。

3.3 收斂性分析

為了驗(yàn)證DFMPC 算法的收斂性，圖2 顯示了8個真實(shí)數(shù)據(jù)集的目標(biāo)函數(shù)值的收斂曲線，x軸和y軸分別表示迭代次數(shù)和相應(yīng)的目標(biāo)值。目標(biāo)函數(shù)值與迭代次數(shù)成反比，目標(biāo)函數(shù)值在10 次迭代內(nèi)急劇下降達(dá)到最小值并趨于穩(wěn)定。這表明DFMPC 收斂效率很高。

圖2 DFMPC在8個數(shù)據(jù)集上的收斂曲線Fig.2 Convergence curves of DFMPC on 8 datasets

3.4 魯棒性分析

本節(jié)通過向不同維度真實(shí)數(shù)據(jù)集添加均值為0，方差0到0.5（步長為0.05）不同強(qiáng)度的隨機(jī)噪聲來驗(yàn)證算法的魯棒性。由于頁面空間限制，只展示了4種效果較好的多視圖聚類算法在ORL 數(shù)據(jù)集的魯棒性。如圖3 所示，隨著噪聲的增加，所有算法的性能都會下降，但DFMPC的性能在絕大多數(shù)情況下領(lǐng)先其他算法并且算法性能增益更為顯著。當(dāng)隨機(jī)噪聲方差從0 增到0.5時，DFMPC 與SwMC 的結(jié)果相比，在ACC、NMI、ARI 和PUR 的性能增益從2.00、3.29、1.36、1.50個百分點(diǎn)提高到14.00、4.55、26.50、15.25個百分點(diǎn)。與MCLES算法相比，DFMPC的4個指標(biāo)性能增益從5.50、6.35、6.83、6.00個百分點(diǎn)提高到26.00、16.21、34.78、26.69個百分點(diǎn)。與SwMPC算法相比，DFMPC 的4 個指標(biāo)性能增益從5.05、4.53、4.76、3.70 個百分點(diǎn)提高到17.27、13.22、28.27、18.50個百分點(diǎn)。這些結(jié)果表明，當(dāng)數(shù)據(jù)集含有噪聲時，正交約束應(yīng)用于散射矩陣進(jìn)行低維子空間學(xué)習(xí)的DFMPC 方法能夠抑制噪聲并保持良好的聚類性能，具有良好的魯棒性。

圖3 ORL數(shù)據(jù)集上4種多視圖方法的魯棒性比較Fig.3 Robustness comparison of 4 multi-view algorithms on ORL dataset

3.5 可視化分析

為了更直觀地觀察DFMPC算法的聚類性能，本文采用一種非線性降維的t-分布式隨機(jī)鄰近嵌入（tdistributed stochastic neighbor embedding，t-SNE）算法[19]，將每個視圖的原始特征和由DFMPC 得到的一致相似特征映射到2D空間，使樣本點(diǎn)在2D空間中被可視化。由于頁面空間限制，本文只提供了3sources 和NGs 數(shù)據(jù)集的可視化結(jié)果，具體如圖4 所示，其中不同的顏色表示不同的類別。本文方法可以清楚地揭示底層的聚類結(jié)構(gòu)，即動態(tài)融合得到的一致相似表示比每個視圖的原始特征更能體現(xiàn)良好的聚類結(jié)構(gòu)。這進(jìn)一步證實(shí)了DFMPC算法的有效性。

圖4 t-SNE在3sources和NGs數(shù)據(jù)集上的可視化結(jié)果Fig.4 Visualization results of t-SNE on 3sources and NGs datasets

4 結(jié)束語

本文提出了一種新的動態(tài)融合的多視圖投影聚類算法，在統(tǒng)一的優(yōu)化框架下聯(lián)合學(xué)習(xí)自適應(yīng)圖、無參數(shù)的自權(quán)重圖融合和精確的聚類標(biāo)簽。該算法可以同時研究投影矩陣、相似矩陣、共識矩陣和聚類標(biāo)簽，在低維空間上得到清楚的底層聚類結(jié)構(gòu)。最后，直接從動態(tài)融合得到的最佳共識矩陣得到聚類結(jié)果。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)證明了本文算法的有效性和良好性能。