基于核典型相關(guān)分析的多視圖譜聚類算法

王春杰，石延新，何進(jìn)榮，王文發(fā)

(延安大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 延安 716000)

隨著信息量的不斷增加，數(shù)據(jù)結(jié)構(gòu)的越來越復(fù)雜。隨著數(shù)據(jù)采集技術(shù)的發(fā)展，大量的數(shù)據(jù)以各種形式呈現(xiàn)，形成了多視圖數(shù)據(jù)[1-2]，例如，一個(gè)物體可以用各種形式來描述，它的形狀、顏色或紋理。多視圖數(shù)據(jù)比單視圖數(shù)據(jù)具有更多的特征信息，每個(gè)視圖中的特征信息趨于互補(bǔ)[3]，這使得多視圖數(shù)據(jù)的研究比單視圖數(shù)據(jù)更有意義[4]。直接學(xué)習(xí)多視圖數(shù)據(jù)不僅浪費(fèi)大量的時(shí)間和成本，而且會導(dǎo)致維災(zāi)難，因此多視圖數(shù)據(jù)學(xué)習(xí)面臨著更嚴(yán)峻的挑戰(zhàn)[5]。

典型相關(guān)分析[6](Canonical Correlations Analysis，CCA)是一種將兩個(gè)多維變量之間的線性關(guān)系關(guān)聯(lián)起來的方法，可以看作是尋找兩組變量的基向量的問題，使得變量在這些基向量上的投影之間的相關(guān)性相互最大化。在很多問題里，兩個(gè)變量之間的關(guān)系是不能簡單用線性相關(guān)來表示的。為了提高特征選擇的靈活性，核方法利用把低維數(shù)據(jù)映射到高維特征空間能很好的處理了一些非線性數(shù)據(jù)，成為了一種很好替代方法。近年來，核方法在處理數(shù)據(jù)方面取得了很大的進(jìn)展。越來越多的學(xué)者對基于核的方法感興趣，潘榮華等[7]從模型識別的角度提出了基于核的局部保持CCA的算法。Lai等[8]提出了針對于人工神經(jīng)網(wǎng)絡(luò)有關(guān)核的幾個(gè)非線性典型相關(guān)的擴(kuò)展，文獻(xiàn)[9-10]也相繼提出了有關(guān)核CCA的方法。Fyfe等[11]推導(dǎo)出一種基于內(nèi)核CCA新方法，同時(shí)還利用非線性核的低階典型相關(guān)性，揭示了時(shí)變混合矩陣的性質(zhì)。Bach等[12]隨后在再生核Hilbert空間中，不僅證明了其對比函數(shù)與互信息有關(guān)，還基于核方法的最新發(fā)展證明了這些準(zhǔn)則及其導(dǎo)數(shù)可以有效地計(jì)算。Hofmann等[13]通過數(shù)據(jù)域定義的函數(shù)再生核希爾伯特空間中描述學(xué)習(xí)和估計(jì)問題，論述了使用正定核函數(shù)的機(jī)器學(xué)習(xí)方法。Nielsen[14]簡要介紹了基于多集CCA的方法，并將這個(gè)方法作為經(jīng)驗(yàn)正交函數(shù)技術(shù)的多元擴(kuò)展。此外，Chen等[15]針對大多數(shù)工業(yè)過程是非線性的采用了核典型相關(guān)分析(KCCA)，獲得了更精確的狀態(tài)監(jiān)測效果。最近，Mitsuhiro等[16]則提出了一種將KCCA的擴(kuò)展與統(tǒng)計(jì)匹配相結(jié)合的數(shù)據(jù)組合方法?？梢怨烙?jì)公共低維空間的正則變量，保持協(xié)變量和結(jié)果變量之間的關(guān)系。Hui等[17]提出了一種基于特征分解的魯棒方法，用于多視圖圖像分類。他們引入特征因式分解矩陣來度量維數(shù)中各特征向量與投影向量之間的近似值，由于圖像從多個(gè)視圖獲取的，還提出了一種基于多投影向量的多因子分解矩陣的方法，權(quán)衡了投影中每個(gè)特征的重要程度，得到了更好的多視圖圖像的特征表示。

基于以上研究的啟發(fā)，本文提出了一種基于核典型相關(guān)分析的多視圖譜聚類(Multi-view Spectral Clustering algorithm based on Kernel Canonical Correlation Analysis,以下簡稱KCCAMvSC)算法模型。首先簡要介紹了兩個(gè)相關(guān)的經(jīng)典算法思想；然后對KCCAMvSC算法模型進(jìn)行了詳細(xì)的介紹，并介紹了實(shí)驗(yàn)的設(shè)計(jì)方案以及對實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證和分析；最后對本文進(jìn)行了總結(jié)和展望。

1 相關(guān)工作

主要介紹2個(gè)經(jīng)典的多視圖聚類算法，即多視圖K-Means和多視圖譜聚類。

1.1 多視圖K-Means(MK)

K-Means的核心思想：根據(jù)樣本集之間的距離大小將樣本集分為K個(gè)簇，現(xiàn)假設(shè)把數(shù)據(jù)集里的簇分為(C1，C2，…Ck)，則目標(biāo)函數(shù)為

(1)

E是平方誤差，μi是簇Ci的均值向量。通過矩陣G∈Rd×n來替換，其目標(biāo)函數(shù)為

(2)

G是聚類指導(dǎo)矩陣，F(xiàn)是中心矩陣。通過(2)式將K-Means擴(kuò)展應(yīng)用到多視圖數(shù)據(jù)集中，則多視圖K-Means的目標(biāo)函數(shù)如(3)式所示

(3)

1.2 多視圖譜聚類(MSC)

令{x1(v),x2(v)，…，xn(v)}表示視圖v，視圖v的相似度矩陣和度矩陣分別用K(v)和D(v)表示，則視圖v的拉普拉斯矩陣L(v)為

L(v)=D(v)-1/2K(v)D(v)-1/2。

(4)

用SVD來優(yōu)化(4)式得到(5)式

U(v)TU(v)=I，

(5)

tr是矩陣的跡。文獻(xiàn)[18]給出(6)式作為雙視圖聚類結(jié)果是否一致的度量，

D(U(v),U(w))=

(6)

U(v)的相似矩陣用KU(v)表示，先對(6)式進(jìn)行歸一化，選擇線性核作為相似性的度量，則

KU(v)=U(v)×U(v)T。

(7)

λtr(U(v)U(v)TU(w)U(w)T，

使得U(v)TU(v)=I，U(w)TU(w)=I。

(8)

迭代最大化(8)式，當(dāng)給定U(w)時(shí)，則(8)式可以轉(zhuǎn)化成(9)式

使得L(v)+λU(w)U(w)T。

(9)

(9)式是自適應(yīng)的，結(jié)合拉普拉斯算子與內(nèi)核函數(shù)得到最大值。選用適當(dāng)?shù)某跏蓟撕蚽保證算法收斂，隨選取最具有信息性的視圖，從該視圖開始進(jìn)行迭代，通過計(jì)算迭代之間的目標(biāo)差值來判斷算法是否收斂，當(dāng)?shù)陀谀骋粋€(gè)設(shè)定好的閾值時(shí)停止迭代。將兩個(gè)視圖擴(kuò)展到m個(gè)視圖時(shí)目標(biāo)函數(shù)為

使得U(v)TU(v)=I,?1≤v≤V。

(10)

選擇相同的λ對全部需要共則化的進(jìn)行平衡。當(dāng)給定多視圖U(v)時(shí)，目標(biāo)函數(shù)如下所示

使得L(w)+λU(v)U(v)T。

(11)

2 基于核典型相關(guān)分析的多視圖譜聚類算法(KCCAMvSC)

2.1 基本思想

本文提出的KCCAMvSC，即將數(shù)據(jù)通過引用核經(jīng)過一個(gè)變換把最初的樣本投影到一個(gè)高維的特征空間里面，接著在這個(gè)特征空間中可實(shí)現(xiàn)不同視圖間一致性信息的有效提取，然后在此特征空間中最小化不同視圖之間蘊(yùn)含信息的一致性，應(yīng)用協(xié)同訓(xùn)練的思想對每個(gè)視圖上進(jìn)行譜聚類，最終得到所有視圖上的結(jié)果趨于一致。KCCAMvSC示意圖如圖1所示。

圖1 KCCAMvSC示意圖

2.2 數(shù)學(xué)原理

2.2.1 核典型相關(guān)分析

KCCA就是依靠核的理論，經(jīng)過一個(gè)變換把最初的樣本投影到一個(gè)高維的特征空間，隨即在這個(gè)特征空間里面在繼續(xù)進(jìn)行CCA，通過這樣一種方法，間接的完成了最開始空間的非CCA。但是和其他核的方法不相同的地方是：KCCA存在兩個(gè)變換，這兩個(gè)變換各自分別作用在兩組變量上。KCCA的推導(dǎo)簡要的描述如下：

L(wX,wY,λX,λY)=E[(u-E(u))(v-E(v))]-

2.2.2 算法描述

KCCAMvSC算法

輸入：多視圖數(shù)據(jù)集。

輸出：分配給k個(gè)集群。

① 數(shù)據(jù)應(yīng)用核典型相關(guān)分析初始化；

② 在核典型相關(guān)空間上應(yīng)用協(xié)同訓(xùn)練；

③ 初始化：L(v)；

⑦ 構(gòu)成矩陣V；

⑧ 如果V的第j行通過k均值算法可以分配給簇c，就將j分配給簇c；

⑨ 結(jié)束。

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

3.1 核函數(shù)

3.1.1 核函數(shù)定義

核函數(shù)定義：如果函數(shù)f(x)可以看作是個(gè)無窮向量，那么對于具有兩個(gè)自變量的函數(shù)K(x,y)，就可以把它看作一個(gè)無限矩陣。如果對任意的函數(shù)

f都滿足K(x,y)=K(y,x)且

??f(x)K(x,y)f(y)dxdy≥0，

那么K(x,y)是正定的對稱矩陣，這時(shí)的K(x,y)就是一個(gè)核函數(shù)。與特征向量和矩陣特征值類似，這時(shí)存在一個(gè)特征值λ和特征函數(shù)Ψ(x)，使得?K(x,y)Ψ(x)dx=λΨ(y)。對于兩個(gè)不同特征值λ1,λ2對應(yīng)的特征函數(shù)Ψ1(x)，Ψ2(x)，證明如下

?λ1(x,y)Ψ1(x)Ψ2(x)dx=

??K(y,x)Ψ1(y)dyΨ2(x)dx=

??K(x,y)Ψ2(x)dxΨ1(y)dy=

?λ2Ψ2(y)Ψ1(y)dy=

?λ2Ψ2(x)Ψ1(x)dx，

<Ψ1,Ψ2>=?Ψ1(x)Ψ2(x)dx=0，又因?yàn)樘卣骱瘮?shù)是正交的，所以Ψ表示函數(shù)本身。

3.1.2 核函數(shù)的種類

核函數(shù)的種類很多，在這里只簡單的介紹實(shí)驗(yàn)中所用到的9種核函數(shù)。

1)線性核(Linear Kernel)是最簡單的核函數(shù)，數(shù)學(xué)公式：k(x,y)=xty。

2)多項(xiàng)式核(Polynomial Kernel)是一種非標(biāo)準(zhǔn)核函數(shù)，數(shù)學(xué)公式：k(x,y)=(axty+c)d。

3)高斯核(Gaussian Kerne)函數(shù)對噪音有著較好的抗干擾能力，數(shù)學(xué)公式：

7)多元二次核(Multiquadric Kernel)是非正定核函數(shù)，數(shù)學(xué)公式：k(x,y)=(||x-y||2+c2)0.5。

8)對數(shù)核(Log Kernel)一般用在圖像分割上，數(shù)學(xué)公式：k(x,y)=-log(1+||x-y||d)。

3.2 數(shù)據(jù)集的描述

為了評估KCCAMvSC算法模型，選用不同性質(zhì)的數(shù)據(jù)集來分別對模型進(jìn)行實(shí)驗(yàn)和對比分析。這些數(shù)據(jù)集包括文本數(shù)據(jù)集和圖像數(shù)據(jù)集，分別是手寫體數(shù)字(HW)數(shù)據(jù)集、4所大學(xué)的網(wǎng)頁(WebKB)數(shù)據(jù)集、劍橋微軟研究院(MSRCV1)數(shù)據(jù)集、英國廣播體育專題(BBCSport)數(shù)據(jù)集、3個(gè)在線新聞文章構(gòu)成(3-Sources)數(shù)據(jù)集、人臉數(shù)據(jù)庫(ORL)數(shù)據(jù)集。如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集的描述

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

為了驗(yàn)證KCCAMvSC模型的有效性，首先給出不同算法在不同多視圖數(shù)據(jù)集上的聚類評估值，對比研究了多個(gè)代表性的經(jīng)典算法，即：K-Means、K-Means級聯(lián)(CK)、多視圖K-Means(MK)、單視圖譜聚類(SC)、SC級聯(lián)(CSC)、多視圖譜聚類(MSC)。定義了10個(gè)不同的參數(shù)，每個(gè)參數(shù)運(yùn)行3次，選擇參數(shù)最優(yōu)的20次結(jié)果的平均值作為最終值。從3種不同的數(shù)據(jù)預(yù)處理方法對數(shù)據(jù)進(jìn)行預(yù)處理，采用0～100之間的參數(shù)對數(shù)據(jù)進(jìn)行降維，接著選取出效果最佳的維數(shù)，然后取20次運(yùn)行結(jié)果的平均值作為最終的算法效果評估值，最后和其他算法的最高值做對比。統(tǒng)計(jì)了各種算法在6個(gè)數(shù)據(jù)集上的歸一化互信息(NMI)，NMI給出了所獲得的聚類與聚類熵歸一化的真實(shí)聚類之間的相互信息。NMI范圍在0～1之間，如果得到的值越高，就表示與真實(shí)聚類更接近。同時(shí)還采用了蘭德指數(shù)(RI)、純度(P)、精度(ACC)值作為聚類質(zhì)量評估度量，取值都介于0和1之間，值越高聚類精度越好。聚類評估值對比表2～5分別表示每個(gè)聚類算法在6個(gè)數(shù)據(jù)集上的聚類評價(jià)指標(biāo)的值。

表2 不同聚類算法在多視圖數(shù)據(jù)集上的NMI值(Rate/%)

表3 不同聚類算法在多視圖數(shù)據(jù)集上的RI值(Rate/%)

表4 不同聚類算法在多視圖數(shù)據(jù)集上的P值(Rate/%)

表5 不同聚類算法在多視圖數(shù)據(jù)集上的ACC值(Rate/%)

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

表2～5分別表示了不同算法在不同數(shù)據(jù)集上的聚類評價(jià)指標(biāo)值，實(shí)驗(yàn)選用KCCAMvSC的20次運(yùn)行結(jié)果的平均值作為KCCAMvSC最終的有效評估值，與K-Means、CK、MK、SC、CSC、MSC的20次運(yùn)行結(jié)果的最大值作對比。

由表2～5可以看出：KCCAMvSC相比MK、MSC，在HW數(shù)據(jù)集、WebKB數(shù)據(jù)集、MSRCV1數(shù)據(jù)集、BBCSport數(shù)據(jù)集、3-Sources數(shù)據(jù)集、ORL數(shù)據(jù)集上的性能都有所提高。具體來說，KCCAMvSC的NMI、P指標(biāo)值在6個(gè)多視圖數(shù)據(jù)集上都明顯的超過了MK、MSC。RI、ACC指標(biāo)值除了在MSRCV1數(shù)據(jù)集表現(xiàn)為次優(yōu)以外，在其余5個(gè)數(shù)據(jù)集上也取得了最優(yōu)。對于KCCAMvSC在MSRCV1數(shù)據(jù)集上表現(xiàn)次優(yōu)，分析可能存在的原因，雖然已經(jīng)對MSRCV1數(shù)據(jù)集的視圖從多個(gè)方面描述，但是有可能因?yàn)橐晥D之間的信息互補(bǔ)性相對較弱、各個(gè)視圖在局部樣本上對簇結(jié)構(gòu)差異性的刻畫能力不明顯所導(dǎo)致。

4 結(jié)論

本文提出并討論了KCCAMvSC算法模型。目的是尋求從多個(gè)表示中找到一致的解決方法，利用每個(gè)表示中的信息來提高經(jīng)典聚類系統(tǒng)的性能。依次介紹了MK、MSC，給出了KCCAMvSC算法模型。實(shí)驗(yàn)不僅對比了3個(gè)算法在多視圖數(shù)據(jù)集上的聚類效果，同時(shí)還對比了K-Means、CK、SC、CSC，實(shí)驗(yàn)數(shù)據(jù)充分證明了KCCAMvSC算法模型的優(yōu)勢。雖然KCCAMvSC算法模型的整體優(yōu)勢很明顯，但是在MSRCV1數(shù)據(jù)集上的優(yōu)勢卻很小，其中的緣由需要在以后的工作中更加深入研究和探討。