基于多樣性的一致譜嵌入學(xué)習(xí)

耿 莉, 王長鵬

(長安大學(xué) 理學(xué)院, 西安 710064)

0 引 言

近年來, 隨著多視圖數(shù)據(jù)的大量增長, 多視圖聚類[1]在各領(lǐng)域應(yīng)用廣泛, 如醫(yī)學(xué)診斷[2]、 生物數(shù)據(jù)分析、 信息檢索、 軌跡線分析[3]、 異常檢測[4]等. 因此, 如何充分利用多視圖數(shù)據(jù)的互補性和兼容性成為數(shù)據(jù)挖掘、 計算機視覺和機器學(xué)習(xí)領(lǐng)域一個重要課題. 在建立多視圖聚類模型[5]過程中, 應(yīng)遵循使類間差異盡可能大、 類內(nèi)差異盡可能小的原則, 在考慮數(shù)據(jù)質(zhì)量的基礎(chǔ)上, 較全面地利用多視圖數(shù)據(jù)的各特征.

目前, 多視圖聚類算法中基于圖學(xué)習(xí)的多視圖聚類方法[6-11]受到廣泛關(guān)注. 在多數(shù)情況下, 基于圖的方法能取得令人滿意的性能. 其基本思想是： 對給定數(shù)據(jù)樣本進行特征提取得到每個視圖相應(yīng)的數(shù)據(jù)矩陣, 通過一些相似性度量方法構(gòu)造圖矩陣, 然后建立模型以獲得高質(zhì)量用于聚類的融合圖矩陣. Nie等[12]將圖的構(gòu)建與譜聚類作為兩個分離的過程進行建模, 但未取得令人滿意的性能； 文獻[13]進一步提出了將兩個過程整合到統(tǒng)一框架的模型； Wang等[14]提出了一種更簡潔、 高效的方法, 該方法先自加權(quán)每個圖矩陣, 可獲得更好的融合圖矩陣, 然后對融合矩陣加入Laplace秩約束控制融合圖的連通分量, 在融合圖上直接得到聚類結(jié)果, 并考慮了不同的圖度量對聚類性能的影響； Zhan等[15]利用Hadamard積將不同視圖直接融合, 保持其內(nèi)在結(jié)構(gòu), 學(xué)習(xí)到的全局圖也盡可能接近得到的Hadamard積, 最后直接由全局圖本身得到聚類結(jié)果； Zhan等[16]利用定義的代價函數(shù)最小化不同視圖的差異, 通過考慮視圖的兼容性獲得具有Laplace秩約束的一致圖； Liang等[17]通過增加對于視圖不一致部分的關(guān)注, 更全面地捕獲視圖特有的信息； Huang等[18]將自加權(quán)學(xué)習(xí)融合圖的過程與多樣性度量整合到統(tǒng)一框架中, 得到具有確定分量的融合圖, 直接獲得標簽分布； Wu等[19]設(shè)計了一個無參數(shù)的模型, 該模型同時關(guān)注兩個不同的方面, 即不同視圖的重要性不同和同一視圖不同特征的重要性不同. 上述方法提升了聚類性能, 但計算復(fù)雜度較高. Shi等[20]提出了結(jié)合矩陣分解相關(guān)知識的方法, 降低了模型的計算復(fù)雜度, 但其未充分考慮每個視圖特有的屬性, 而且忽略了不同視圖的重要性不同, 未分配每個視圖合適的權(quán)重.

現(xiàn)有的多視圖聚類算法仍存在以下問題亟待解決：

1) 現(xiàn)有的多數(shù)方法只考慮了視圖之間的一致性, 忽略了視圖的不一致部分, 會對聚類結(jié)果產(chǎn)生影響；

2) 許多方法需要后續(xù)的處理才能得到聚類結(jié)果, 而這些步驟會導(dǎo)致信息損失；

3) 各過程獨立進行, 導(dǎo)致次優(yōu)的聚類性能.

為解決上述問題, 本文提出一種基于離散化的一致譜嵌入學(xué)習(xí)(diversity consensus spectral embedding, DCSE)聚類算法, 通過自加權(quán)策略學(xué)習(xí)不同視圖的權(quán)重, 并將視圖多樣性整合到一致圖學(xué)習(xí)過程中, 同時學(xué)習(xí)一致的譜嵌入, 以便獲得聚類指標矩陣. 為求解該優(yōu)化問題, 本文采用交替迭代優(yōu)化方案, 并在4個真實數(shù)據(jù)集上驗證本文算法的有效性. DCSE算法流程如圖1所示.

圖1 DCSE算法流程Fig.1 Flow chart of DCSE algorithm

1 預(yù)備知識

1.1 圖學(xué)習(xí)

近年來, 各種相似性度量準則被廣泛應(yīng)用于多視圖問題中, 如二進制相似、 余弦相似、 高斯核相似及文獻[21]提出的相似性度量準則. 對于給定的多視圖數(shù)據(jù)Xv∈dv×n(其中dv為第v個視圖的維數(shù),n為樣本數(shù)), 可同時基于多視圖的一致性與不一致性建模：

(1)

其中:v表示視圖的數(shù)量;W(i)為第i個視圖的相似性矩陣,αi為其對應(yīng)的縮放系數(shù), 為使縮放結(jié)果唯一, 本文限制α中分量和為1, 用簡單的加法思想可得W(i)=A(i)+E(i),A(i)為多視圖的一致部分,E(i)=W(i)-A(i)為各視圖的不一致部分；S為一致相似矩陣;B=(bij)∈v×v的對角線元素為β, 非對角線元素為γ.

1.2 譜聚類

給定一個集合的數(shù)據(jù)點X=(x1,x2,…,xn)∈d,W=(wij)∈n×n表示數(shù)據(jù)點之間的相似性, 則譜聚類的目標函數(shù)可表示為

(3)

1.3 聚類指標矩陣學(xué)習(xí)

離散的多圖學(xué)習(xí)可同時進行譜嵌入與聚類指標矩陣的學(xué)習(xí)[22], 從而更精確地逼近最優(yōu)離散解, 其目標函數(shù)為

(4)

其中:F為一致譜嵌入;Y∈n×c為聚類指標矩陣, 即每行只有一個元素為1, 其余元素均為0,n和c分別為樣本數(shù)和聚類數(shù)量.該目標函數(shù)將譜嵌入學(xué)習(xí)與聚類指標矩陣學(xué)習(xí)兩個分開的過程整合到統(tǒng)一框架中, 取得了較好的結(jié)果.

2 DCSE算法

2.1 算法模型

本文將一致圖學(xué)習(xí)、 一致譜嵌入與聚類指標矩陣的學(xué)習(xí)過程整合到統(tǒng)一框架, 可得目標函數(shù)為

(5)

其中:wi為第i個視圖的權(quán)重;Ai=Ci+Ei,Ai為構(gòu)造的相似性矩陣,Ci為各視圖的一致部分,Ei=Ai-Ci為視圖之間的不一致部分, 即每個視圖特有的屬性;B=(bij)∈v×v的對角線元素為β, 非對角線元素為α;λ和σ為平衡參數(shù).第一項與最后一項可獲得更高效的一致圖S, 第二項與第三項用于學(xué)習(xí)一致譜嵌入F和聚類指標矩陣Y, 各過程相互促進, 共同提升聚類性能.

2.2 優(yōu) 化

由式(5)可知, 目標函數(shù)主要有4個變量需要求解, 若同時考慮4個變量, 則式(5)是非凸問題, 但當求解一個變量固定其余變量時, 則問題變?yōu)橥箖?yōu)化問題.因此, 本文采用交替迭代策略對目標函數(shù)進行優(yōu)化.

2.2.1 更新Ci

當只考慮變量Ci時, 式(5)可轉(zhuǎn)化為

(6)

對式(6)關(guān)于Ci求偏導(dǎo), 并令導(dǎo)數(shù)為0, 可得下列v個矩陣方程：

(7)

P=B(wwT)+diag(w),

(8)

其中diag(w)表示對角矩陣, 第i個對角元素為wi.

(9)

即

(10)

其中P?表示P的偽逆矩陣.最后, 可通過vec(Ci)得到Ci.同時, 為滿足約束條件Ai≥Ci≥0(i=1,2,…,v), 可進一步得Ci的解為

Ci=max{Ci,0},Ci=min{Ai,Ci}.

(11)

2.2.2 更新S

固定Ci,F,Y時, 只考慮變量S, 則式(5)為

(12)

將式(12)寫成元素的形式為

(13)

式(13)對每個r獨立, 因此有

(14)

(15)

(16)

其具體求解過程同文獻[14].

2.2.3 更新F

固定式(5)中其余變量, 只考慮一致譜嵌入F, 可得

(17)

將式(17)改寫成如下形式：

(18)

證明： 式(18)的Lagrange函數(shù)為

(19)

其中Lagrange乘子φ是對稱矩陣.將式(19)關(guān)于F求偏導(dǎo)并令導(dǎo)數(shù)為0, 可得

(20)

即

(21)

通過緊奇異值分解得

(22)

因此, 有

(Fφ)T(Fφ)=(UΣVT)T(UΣVT),

(23)

即

φTφ=VΣ2VT.

(24)

因為φ為對稱矩陣, 所以

φT=φ,φTφ=φ2,

從而

φ=VΣVT.

(25)

將式(25)代入式(22)可得

F(VΣVT)=UΣVT,

(26)

即

F=UVT.

(27)

2.2.4 更新Y

當Ci,S,F固定時, 式(5)為

(28)

由跡相關(guān)性質(zhì)可知tr(FTY)=tr(YFT), 從而有

(29)

因為Y∈Ind, 所以Y的每行有且僅有一個元素為1, 其余元素為0, 而且每行元素獨立, 于是可逐行更新Y：

(30)

算法1求解問題(5).

輸入：A1,A2,…,Av, 參數(shù)σ, 聚類數(shù)c;

輸出： 聚類指標矩陣Y;

循環(huán):

1) 由式(10)和式(11)更新Ci;

2) 通過求解式(16)更新S;

4) 由隨機初始化得正交矩陣F, 由文獻[23]得參數(shù)γ, 迭代更新F;

5) 由式(30)更新Y.

直至收斂.

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

本文采用迭代方法對式(5)進行求解, 將式(5)分解為多個子問題進行計算, 其各子問題的時間復(fù)雜度如下： 式(10)和式(11)用于更新Ci, 其時間復(fù)雜度為O(v2n2)； 式(16)用于更新一致圖S, 其時間復(fù)雜度為O(cn)； 式(27)用于更新F, 其時間復(fù)雜度為O(t1nc2), 其中t1表示更新F時的迭代數(shù)量； 式(30)用于更新Y, 其時間復(fù)雜度為O(cn)； 更新wi的時間復(fù)雜度為O(vn2).假設(shè)整個算法的迭代數(shù)量為t2, 則該算法的時間復(fù)雜度為O(t2(v2n2+cn+t1nc2+vn2)).

3 實驗與分析

為充分評估模型的有效性, 本文在4個廣泛使用的數(shù)據(jù)集上進行實驗, 并將聚類結(jié)果與現(xiàn)有方法進行比較.

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

本文選取4個數(shù)據(jù)集ORL,Yale,MSRCV1和Cal-7, 各數(shù)據(jù)集的信息列于表1. 數(shù)據(jù)集ORL包含40個人的400張不同圖像, 每張圖像在不同條件下獲得. 3個視圖的特征維數(shù)分別為d1=4 096,d2=3 304,d3=6 750. 數(shù)據(jù)集Yale從15個個體中提取165個樣本, 每張圖像通過不同的燈光、 面部表情和姿勢獲取, 共3個視圖的數(shù)據(jù). 數(shù)據(jù)集MSRCV1從8個類別中提取7個類別, 分別為樹、 建筑、 飛機、 牛、 人臉、 汽車和自行車, 共210個樣本. 廣泛使用的Caltech101是包含101個類別的數(shù)據(jù)集, 而數(shù)據(jù)集Cal-7是由其中7個類別的1 474個樣本所構(gòu)成的數(shù)據(jù)集.

表1 數(shù)據(jù)集信息

3.2 評價指標

為驗證本文模型的有效性, 采用5個廣泛使用的指標精度(accuracy, ACC)、 歸一化互信息(normalized mutual information, NMI)、 純度(Purity)、F-score、 調(diào)整蘭德系數(shù)(adjusted Rand index, ARI)評估其聚類性能, 指標數(shù)值越大, 聚類性能越好.

ACC表示為

(31)

其中n表示屬于c類樣本點個數(shù),ri表示第i個樣本的真實標簽,si表示對應(yīng)學(xué)習(xí)到的標簽,δ(·,·)表示Dirac函數(shù), map(·)表示最優(yōu)的映射函數(shù).NMI表示為

(32)

其中I(ri,si)表示ri和si的互信息,H(·)表示信息熵.Purity表示為

(33)

其表示正確聚類的樣本占總樣本的百分數(shù).F-score表示為

(34)

其綜合考慮準確率(Precision)和召回率(Recall)的調(diào)和值, 其中

ARI表示為

(35)

3.3 對比方法

將本文算法與現(xiàn)有的多視圖聚類算法進行比較, 按原算法進行參數(shù)設(shè)置, 對比方法如下：

1) 經(jīng)典的譜聚類算法(spectral clustering, SC), 本文在每個視圖上實施該方法, SC1表示在第一個視圖上運行該算法, 其余依次表示在對應(yīng)視圖上運行該算法；

2) 基于多圖融合的多視圖聚類算法(multi-graph fusion for multi-view spectral clustering, GFSC)同時考慮圖融合與結(jié)構(gòu), 在進行譜聚類步驟后執(zhí)行K-means以獲得最終的標簽;

3) 基于圖學(xué)習(xí)的多視圖聚類模型(graph learning for multiview clustering, MVGL)從不同的單視圖學(xué)習(xí)一個全局圖, 最后學(xué)習(xí)到的全局圖包含確定的連通分量, 避免了通過后續(xù)步驟得到聚類指標矩陣;

4) 自適應(yīng)加權(quán)普魯克方法(adaptively weighted Procrustes, AWP), 該方法對視圖的聚類能力進行加權(quán), 形成一個加權(quán)的普魯克平均問題；

5) 多視圖一致圖聚類算法(multiview consensus graph clustering, MCGC)學(xué)習(xí)一致圖, 最小化不同視圖之間的分歧, 并加入Laplace秩的約束；

6) 自加權(quán)多視圖聚類(self-weighted multiview clustering, SwMC), 該方法自動學(xué)習(xí)權(quán)重, 避免了引入額外的參數(shù), 并加入Laplace秩的約束獲得聚類標簽.

3.4 實驗結(jié)果

本文DCSE算法與其他對比算法在4個真實數(shù)據(jù)集上的比較結(jié)果分別列于表2和表3. 為避免K-means初始化步驟導(dǎo)致的隨機性, 本文運行DCSE算法20次取平均結(jié)果.

表2 不同算法在數(shù)據(jù)集ORL和Yale上的聚類性能比較

由表2和表3可見：

1) 不同視圖具有不同的聚類性能, 因此在多視圖聚類過程中需分配給不同視圖不同的權(quán)重, 而本文采用的自加權(quán)策略可較好地解決該問題；

2) DCSE算法在數(shù)據(jù)集ORL和MSRCV1上取得了最好的聚類性能, 并在數(shù)據(jù)集MSRCV1上與性能第二好的MCGC算法相比, 分別在ACC和NMI上約提高3%, 在Purity上約提高5%, 因此聚類過程中同時考慮視圖多樣性與學(xué)習(xí)標簽矩陣非常必要;

3) 在數(shù)據(jù)集Yale上, 雖然DCSE算法沒有在每個指標上都取得最好的聚類性能, 但其度量指標值與最好的算法相比差距很小；

4) 在數(shù)據(jù)集Cal-7上, DCSE算法在3個指標上都取得了最大值, 這也驗證了本文算法的優(yōu)越性, 而執(zhí)行譜聚類算法時第5個視圖在Purity指標上數(shù)值較大, 因此多視圖聚類時需分配較大權(quán)重, 本文算法可處理此問題.

表3 不同算法在數(shù)據(jù)集MSRCV1和Cal-7上的聚類性能比較

綜上, 本文模型在考慮視圖多樣性的同時自動學(xué)習(xí)權(quán)重, 使學(xué)習(xí)到的一致圖具有更優(yōu)性能, 且避免了后續(xù)過程獨立進行導(dǎo)致的信息損失, 在4個數(shù)據(jù)集上性能都較好.

3.5 參數(shù)分析

本文算法共涉及α,β,λ,σ4個參數(shù), 為學(xué)習(xí)到具有較好聚類結(jié)構(gòu)的一致圖, 需調(diào)整參數(shù)λ使圖的聯(lián)通分量數(shù)等于聚類數(shù)量c, 因此在迭代過程中, 若連通分量數(shù)大于c, 則將λ調(diào)整為λ/2, 若連通分量數(shù)小于c, 則將λ調(diào)整為2λ.對于參數(shù)σ, 根據(jù)經(jīng)驗設(shè)為0.1.對于參數(shù)α和β, 均在[10-5,105]內(nèi)取值, 并以數(shù)據(jù)集Cal-7和ORL為例驗證參數(shù)的敏感性. 圖2為在數(shù)據(jù)集Cal-7和ORL上參數(shù)α和β的敏感性分析. 由圖2可見, DCSE算法性能較穩(wěn)定, 表明本文算法對參數(shù)α和β具有魯棒性.

圖2 在數(shù)據(jù)集Cal-7和ORL上參數(shù)α和β的敏感性分析Fig.2 Sensitivity analysis of parameters α and β on Cal-7 and ORL data sets

3.6 收斂性分析

(36)

然后, 通過求解式(12)得變量S(t+1), 則有

(37)

結(jié)合式(17)可知

(38)

最后, 通過式(30)更新Y(t+1), 有

(39)

因此, 本文目標函數(shù)收斂.

綜上所述, 本文提出了一種DCSE多視圖聚類模型, 與已有模型不同[24-25], 該模型同時進行一致圖學(xué)習(xí)、 一致譜嵌入學(xué)習(xí)與聚類指標矩陣的學(xué)習(xí), 在學(xué)習(xí)一致圖過程中綜合了視圖多樣性的信息, 得到了高質(zhì)量的一致圖.上述3個學(xué)習(xí)過程同時進行, 也可有效地避免步驟分開導(dǎo)致的信息損失.由于模型中加入了標簽離散化過程, 因此不需任何后續(xù)步驟便可得到聚類結(jié)果.此外, 本文還提供了有效求解的優(yōu)化算法, 并在4個數(shù)據(jù)集上驗證了本文算法的有效性.