特征直連與結(jié)構(gòu)化約束的多視圖子空間聚類*

張翼飛，鄧秀勤，王卓薇

(廣東工業(yè)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,廣東 廣州 510006)

1 引言

多視圖聚類通過數(shù)據(jù)的不同視圖來學(xué)習(xí)數(shù)據(jù)包含的信息和結(jié)構(gòu)，并由此對多視圖數(shù)據(jù)進(jìn)行簇劃分。不同于傳統(tǒng)的單視圖數(shù)據(jù)聚類，多視圖聚類面對的是更加復(fù)雜的數(shù)據(jù)。由于數(shù)據(jù)樣本來源或者特征表達(dá)方式的多樣性，多視圖聚類需要面對的是如何通過多個(gè)視圖來獲取一個(gè)良好的聚類結(jié)果。

綜上所述，由于多視圖聚類算法的不斷發(fā)展，子空間學(xué)習(xí)作為一個(gè)重要的方法已經(jīng)被廣泛應(yīng)用。但是，現(xiàn)有的多視圖聚類卻忽略了原有的特征直連數(shù)據(jù)[15]，即將多視圖數(shù)據(jù)每個(gè)樣本對應(yīng)的特征拼接起來得到的數(shù)據(jù)。盡管傳統(tǒng)的聚類算法在特征直連數(shù)據(jù)上表現(xiàn)不好，但是特征直連數(shù)據(jù)對于聚類結(jié)果仍有一定的促進(jìn)作用。此外，為了學(xué)習(xí)到合適的子空間表示，還需對子空間表示的結(jié)構(gòu)進(jìn)行探究，同時(shí)探尋特征直連數(shù)據(jù)與多個(gè)視圖之間的差異性。因此，本文提出了基于特征直連和結(jié)構(gòu)化約束的多視圖子空間聚類算法FSMC(Feature concatenation and Structured constraints based Multi- view Clustering)。本文主要貢獻(xiàn)可概括為：

(1)將特征直連數(shù)據(jù)加入算法框架，與原有的多視圖共同學(xué)習(xí)，探尋多視圖與特征直連數(shù)據(jù)的關(guān)系；

(2)通過子空間分解重構(gòu)誤差，保證誤差的穩(wěn)定性；

(3)通過正則化約束保證子空間表示的結(jié)構(gòu)稀疏性。

2 相關(guān)工作

2.1 子空間聚類

在數(shù)據(jù)集X1∈Rm×n上共有n個(gè)樣本，每個(gè)樣本有m個(gè)特征，需要一個(gè)合適的子空間V∈Rn×n滿足式(1)：

s.t.diag(V)=0

(1)

其中，‖·‖?為范數(shù)表達(dá)式，?為泛指，其可能取值為1，2,…，當(dāng)?=1時(shí)，式(1)為稀疏約束，當(dāng)?=*時(shí)，式(1)為核范數(shù)，此時(shí)為低秩約束，diag(V)為對角線上元素，diag(V)=0表明其對角元素全為0，該約束是為了防止出現(xiàn)平凡解。為了減少過擬合以及增加學(xué)習(xí)到的子空間的條件(稀疏或低秩)，通常會(huì)在式(1)的基礎(chǔ)上添加約束項(xiàng)，那么式(1)變?yōu)槭?2)[12]：

(2)

其中,‖·‖Ψ為范數(shù)表達(dá)式,Ψ與式(1)中的?同為泛指，當(dāng)Ψ=1時(shí)，式(2)為稀疏約束，當(dāng)Ψ=*時(shí)，式(2)為核范數(shù)，此時(shí)為低秩約束。α為超參數(shù)，用于調(diào)節(jié)范數(shù)大小。

2.2 多視圖子空間聚類

由于子空間聚類算法在多視圖數(shù)據(jù)上的可擴(kuò)展性，可將式(2)擴(kuò)展為多視圖子空間聚類算法。即對于具有v個(gè)視圖的數(shù)據(jù)集X={X1,X2,…,Xv}，有：

(3)

其中,Vi為對應(yīng)視圖Xi下的子空間。在學(xué)習(xí)到每個(gè)視圖下的子空間后，最簡單的辦法是通過求和取平均值來獲得最終的共識(shí)矩陣，即:

(4)

研究人員通過各個(gè)視圖所蕰涵的信息來更加合理地獲得共識(shí)矩陣，則式(3)可改為式(5)[15]：

(5)

其中，S為共識(shí)矩陣，β為超參數(shù)。

式(5)不同于式(3)，其共識(shí)矩陣的獲得是與子空間學(xué)習(xí)一起進(jìn)行的，兩者框架的統(tǒng)一能確保最終的共識(shí)矩陣更加合理。

3 特征直連與結(jié)構(gòu)化約束

本節(jié)提出了一種基于特征直連與結(jié)構(gòu)化約束的多視圖子空間聚類算法FSMC。該算法通過特征直連數(shù)據(jù)與多視圖數(shù)據(jù)的共同學(xué)習(xí)來重構(gòu)誤差，并通過約束使子空間滿足特定的結(jié)構(gòu)，同時(shí)還考慮了多個(gè)視圖子空間與直連視圖之間的關(guān)系。

3.1 特征直連

s.t.E=D-DV

(6)

其中，λ是超參數(shù);E為誤差矩陣;V為其相應(yīng)的子空間表示;‖·‖2,1為矩陣的L2,1范數(shù)，表示對矩陣的行求向量的L2范數(shù)得到一個(gè)向量，然后再對該向量求L1范數(shù)。‖E‖2,1是為了重構(gòu)誤差，使誤差趨于穩(wěn)定，‖V‖2,1為結(jié)構(gòu)化約束，保證子空間的稀疏約束。

3.2 結(jié)構(gòu)化約束

為了穩(wěn)定重構(gòu)誤差和保證子空間的稀疏約束，將式(3)所示的多視圖子空間聚類基本公式修改為式(7)：

s.t.Ei=Xi-XiVi,i=1,2，…,v

(7)

為了將多視圖數(shù)據(jù)與特征直連數(shù)據(jù)聯(lián)系起來，將式(6)與式(7)動(dòng)態(tài)結(jié)合起來得到式(8):

L=αL1+(1-α)L2

(8)

其中,α和1-α是各自的權(quán)重,分別代表多視圖與直連數(shù)據(jù)的重要程度。通過為多視圖數(shù)據(jù)與特征直連數(shù)據(jù)分配權(quán)重可以控制兩者對于最終結(jié)果的影響程度。

在式(8)下，無法得到一個(gè)統(tǒng)一的共識(shí)矩陣，而且從直觀意義上來看，特征直連數(shù)據(jù)與多視圖存在著一定的聯(lián)系，直連數(shù)據(jù)中指定大小的數(shù)據(jù)就可以表示成多視圖中某一個(gè)視圖的特征數(shù)據(jù)。因此，為了測試多視圖各個(gè)子空間與直連數(shù)據(jù)子空間的相似性和差異性，需要通過正則化約束來進(jìn)行學(xué)習(xí)。同時(shí)，為了獲得一個(gè)最終的子空間表示，可以通過多視圖子空間Vi與直連子空間V之和來得到最終的共識(shí)矩陣S。綜上所述，可得公式(9):

s.t.diag(V)=0,diag(Vi)=0,

i=1,2,…,v,Ei=Xi-XiVi,E=D-DV

(9)

其中，γ為超參數(shù);Ei為視圖Xi的誤差矩陣;S為需要學(xué)習(xí)的共識(shí)矩陣;β和γ為超參數(shù);前2項(xiàng)為多視圖與特征直連數(shù)據(jù)的子空間學(xué)習(xí)部分;第3項(xiàng)中的第1部分為多視圖與特征直連數(shù)據(jù)的相關(guān)性和差異性約束，第2部分則是通過多視圖與特征直連數(shù)據(jù)共同學(xué)習(xí)共識(shí)矩陣用作聚類。圖1給出了FSMC算法的大致過程，其中，左邊方框表示特征直連的實(shí)現(xiàn)方式，右邊方框表示多視圖子空間和特征直連子空間之間的差異性和共同性的學(xué)習(xí)，箭頭指向表示其轉(zhuǎn)換過程，如雙向箭頭表示4個(gè)子空間矩陣是相互影響的。

Figure 1 General process of FSMC algorithm

3.3 FSMC算法優(yōu)化

對于式(9)的優(yōu)化，需要引入多個(gè)變量，并采用增廣拉格朗日迭代求解。引入變量Ci和C后式(9)變?yōu)槭?10):

s.t.Ci=Vi,C=V,Ei=Xi-XiVi,

E=D-DV，diag(V)=0,

diag(Vi)=0,i=1,2,…,v

(10)

式(10)的優(yōu)化步驟如下所示(其中，〈A,B〉為矩陣ATB的跡，A和B泛指矩陣)：

步驟1固定除Ei之外的所有變量，更新Ei，此時(shí)式(10)變?yōu)槭?11)：

s.t.Ei=Xi-XiVi,i=1,2,…,v

(11)

由于每個(gè)視圖都是獨(dú)立的，那么式(11)可拆分并轉(zhuǎn)換為式(12)：

(12)

其中,Yi為拉格朗日乘子，是與Xi具有相同行數(shù)和列數(shù)的矩陣;u為參數(shù);Ei的更新公式[19]如式(13)所示:

(13)

其中,Q=Xi-XiV+Yi/u,[Q:,j]表示矩陣Q的第j列元素，[Ei]:,j表示視圖Xi的對應(yīng)矩陣Ei的第j列元素。

步驟2固定除E之外的所有變量，更新E，此時(shí)式(10)變?yōu)槭?14)：

(14)

其中Y是與E具有相同行數(shù)和列數(shù)的矩陣。式(14)的求解方式同式(12)。

步驟3固定除Ci之外的所有變量，更新Ci，此時(shí)式(10)變?yōu)槭?15)：

s.t.Ci=Vi,i=1,2,…,v

(15)

類似于步驟1，式(15)可拆分并轉(zhuǎn)換為式(16)：

(16)

其中，Yv+1是與V具有相同行數(shù)和列數(shù)的矩陣。式(16)的求解方式同步驟1。

步驟4固定除C之外的所有變量，更新C，此時(shí)式(10)變?yōu)槭?17)：

(17)

其中，Y′是與C具有相同行數(shù)和列數(shù)的矩陣。式(17)的求解方法同上。

步驟5固定除Vi之外的所有變量，更新Vi，此時(shí)式(10)變?yōu)槭?18):

(18)

因此，對式(18)求導(dǎo)可得更新式(19)：

Vi=(T1)-1T2

(19)

步驟6固定除V之外的所有變量，更新V，此時(shí)式(10)變?yōu)槭?20):

(20)

對式(20)求導(dǎo)可得更新式(21):

V=(Z1)-1Z2

(21)

步驟7根據(jù)式(22)更新共識(shí)矩陣S：

(22)

步驟8根據(jù)式(23)更新參數(shù)：

Yi=Yi+u(Ei-Xi+XiVi),i=1,2,…,v,

Y=Y+u(E-D+DV),

Yv+1=Yv+1+u(Ci-Vi),i=1,2,…,v,

Y′=Y′+u(C-V),

u=min(ρu,umax)

(23)

其中，ρ是變化幅度的大小，等同于步長；umax為μ可取的最大值。

FSMC算法步驟如算法1所示：

算法1FSMC算法

輸入：多視圖數(shù)據(jù)X={X1,X2,…,Xv},特征直連數(shù)據(jù)D,ρ,umax,期望的誤差ε。

輸出：共識(shí)矩陣S。

步驟：

初始化所需的矩陣Ei,E,Ci,C,Vi,V,S,參數(shù)矩陣Yi,Y,Yv+1,Y′和參數(shù)u；

While迭代次數(shù)<最大迭代次數(shù):

Ifi≤視圖個(gè)數(shù)v:

根據(jù)式(13)更新第i個(gè)視圖的誤差矩陣Ei；

根據(jù)式(16)更新引入的變量Ci；

根據(jù)式(19)更新第i個(gè)視圖的子空間矩陣Vi；

Endif

根據(jù)式(14)更新直連特征的誤差矩陣E；

根據(jù)式(17)更新變量C；

根據(jù)式(21)更新直連特征的子空間矩陣V；

根據(jù)式(22)更新共識(shí)矩陣S；

根據(jù)式(23)更新參數(shù)Yi,Y,Yv+1,Y′和u；

If對應(yīng)的誤差矩陣(‖E-D+DV‖F(xiàn),‖V-C‖F(xiàn))<ε：/*(，)表示其中的元素分別小于ε*/

break;

else

迭代次數(shù)加1;

Endif

Endwhile

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)集及性能指標(biāo)

實(shí)驗(yàn)在新聞數(shù)據(jù)集BBC(BBC news)、人臉數(shù)據(jù)集ORL(ORL face)、手寫數(shù)據(jù)集HW(HandWritten)和新聞組數(shù)據(jù)集NGs(NewsGroup datasets)共4個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行，其中BBC是包含4個(gè)視圖的文本數(shù)據(jù)集，而ORL、HW和NGs都是包含多個(gè)視圖的圖像數(shù)據(jù)集。這4個(gè)數(shù)據(jù)集的簡況如表1所示。

Table 1 Datasets

本文選擇了ACC、NMI和F-score來評(píng)估提出算法的聚類性能。3個(gè)指標(biāo)計(jì)算公式分別如式(24)～式(26)所示：

(24)

(25)

(26)

其中,Precision為精確率；Recall為召回率;τ為平衡兩者權(quán)重的參數(shù)，一般情況下其值為1，表示兩者重要程度一樣。上述3個(gè)指標(biāo)的值都在[0,1]內(nèi)，越接近1表示算法性能越好。

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

為了評(píng)估本文提出的FSMC算法的多視圖聚類性能，本文將FSMC算法與5個(gè)不同時(shí)間段提出的算法進(jìn)行對比實(shí)驗(yàn)，這5個(gè)算法分別是譜聚類SC(Spectrual Clustering)[11](在本文中分別用單個(gè)視圖聚類，即SCi表示在第i個(gè)視圖下的譜聚類算法，值得注意的是在HW數(shù)據(jù)集上選擇了結(jié)果較好的4個(gè)視圖)、基于質(zhì)心的多視圖低秩稀疏子空間MLRSSC (centroid-based Multi-view Low-Rank Sparse Subspace Clustering)算法[12]、用于多視圖聚類的圖學(xué)習(xí)MVGL (Graph Learning for MultiView clustering) 算法[18]、基于圖的多視圖聚類GBS-MV (Graph-Based System for Multi-View clustering)算法[19]和多圖融合的多視圖子空間聚類GFSC (multi-Graph Fusion for multi-view Spectral Clustering) 算法[15]。表2～表5給出了這6種算法在4個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)中每個(gè)算法運(yùn)行10次，然后取平均值和標(biāo)準(zhǔn)差作為最終的性能指標(biāo)值。對于權(quán)重參數(shù)，考慮到復(fù)雜性，假設(shè)其多視圖數(shù)據(jù)與特征聯(lián)合數(shù)據(jù)的權(quán)重占比是一樣的，即暫且認(rèn)為其對于最終聚類結(jié)果的影響同等重要，因此將權(quán)重參數(shù)α設(shè)為0.5，而權(quán)重參數(shù)對于聚類結(jié)果的影響可以參照圖2，該圖給出了當(dāng)其余參數(shù)固定時(shí)，α參數(shù)對BBC數(shù)據(jù)集聚類結(jié)果的影響。

Table 2 Comparison results of different algorithms on BBC dataset

Table 3 Comparison results of different algorithms on ORL dataset

Table 4 Comparison results of different algorithms on HW dataset

Table 5 Comparison results of different algorithms on NGs dataset

Figure 2 Effect of parameter α on BBC dataset

由表2～表5可以看出，本文提出的算法FSMC在ACC、NMI和F-score指標(biāo)上都有明顯的改善，也就是說FSMC能在4個(gè)數(shù)據(jù)集上實(shí)現(xiàn)更好的聚類結(jié)果。從表2中的數(shù)據(jù)可以看出，對于BBC文本數(shù)據(jù)集，F(xiàn)SMC算法在聚類指標(biāo)ACC、NMI和F-score上有了顯著的提高。從表2還可以看到，譜聚類作用于單個(gè)視圖的性能并不好，而FSMC相比5個(gè)對比算法中最優(yōu)的MLRSSC算法在ACC、NMI和F-score指標(biāo)上分別提高了14.47%，5.96%和17.6%。從表3可以看出，雖然FSMC算法在ACC和F-score上相比于最優(yōu)的算法有所下降，但是也明顯優(yōu)于其他對比算法，而且ACC相比于最優(yōu)的算法(GBS-MV)也提高了1.7%。而表4的實(shí)驗(yàn)結(jié)果顯示FSMC在ACC上優(yōu)于5個(gè)對比算法，且有顯著的提升，但是其余2個(gè)指標(biāo)相比MVGL與GBS-MV來說是略有降低的。表5的實(shí)驗(yàn)結(jié)果則顯示在NGs數(shù)據(jù)集上，F(xiàn)SMC在3個(gè)評(píng)價(jià)指標(biāo)上接近1，說明聚類結(jié)果只有少量的錯(cuò)誤，能達(dá)到一個(gè)接近完美的準(zhǔn)確度，ACC、NMI和F-score相比于最優(yōu)的對比算法GBS-MV來說分別提高了1%，3%，1.97%，明顯優(yōu)于最新的多視圖算法GFSC。GBS-MV算法利用加權(quán)構(gòu)造融合鄰接矩陣得到統(tǒng)一的圖矩陣可以有效地保持?jǐn)?shù)據(jù)的流形結(jié)構(gòu)，但是忽略了特征直連數(shù)據(jù)的相關(guān)信息；而GFSC算法則是在子空間表示的基礎(chǔ)上增加圖結(jié)構(gòu)關(guān)系的選擇，同樣沒有考慮到特征直連數(shù)據(jù)，因此兩者在一定程度上都忽略了可用來聚類的部分信息。FSMC則是在子空間學(xué)習(xí)的基礎(chǔ)上考慮到特征直連數(shù)據(jù)對最終結(jié)果的影響，將特征直連數(shù)據(jù)加入到多視圖子空間學(xué)習(xí)的框架中，豐富了可用的聚類信息，有效地提升了聚類性能。

式(9)存在超參數(shù)，因此需要選擇合適的參數(shù)來調(diào)節(jié)公式，以便得到更優(yōu)的聚類結(jié)果。圖3給出了參數(shù)α和β對BBC數(shù)據(jù)集的聚類結(jié)果的影響程度。由于涉及到3個(gè)超參數(shù)，因此需要固定其中一個(gè)超參數(shù)γ，然后再搜尋合適的α和β。圖3給出了在γ固定為100時(shí)，不同的α和β對于ACC指標(biāo)的影響。如圖3所示，α=10,β=100時(shí)，對BBC數(shù)據(jù)集進(jìn)行聚類得到的準(zhǔn)確率為0.86；而在α=1,β=0.1時(shí)得到的準(zhǔn)確率就會(huì)降低，所以選擇合適的超參數(shù)也是十分重要的。圖4給出了FSMC算法在BBC數(shù)據(jù)集上的迭代過程。從圖4可以看出，F(xiàn)SMC算法在迭代了13次左右就趨于穩(wěn)定，換句話說，該算法能實(shí)現(xiàn)快速收斂。

Figure 3 Impact of α and β on ACC indicator when γ=100

Figure 4 Convergence of FSMC on BBC dataset

5 結(jié)束語

本文在多視圖子空間聚類算法的基礎(chǔ)上提出了基于特征直連和重構(gòu)誤差的多視圖聚類算法。與現(xiàn)有的算法不同，F(xiàn)SMC在原有的視圖中增加了一個(gè)特別的視圖數(shù)據(jù)——特征直連數(shù)據(jù)，讓算法學(xué)習(xí)的信息更加豐富。同時(shí)通過重構(gòu)誤差矩陣使誤差穩(wěn)定，在保證表示矩陣結(jié)構(gòu)稀疏的同時(shí)學(xué)習(xí)到特征直連視圖與其余視圖的差異性，最終通過共同學(xué)習(xí)得到最終的表示矩陣。本文在4個(gè)真實(shí)數(shù)據(jù)集上評(píng)估了算法的聚類效果，驗(yàn)證了算法的有效性。但是，F(xiàn)SMC算法只考慮多視圖與特征直連視圖之間的權(quán)重，沒有考慮到多視圖之間的權(quán)重，而且沒有探尋特征直連數(shù)據(jù)的子空間結(jié)構(gòu)，后續(xù)工作可以考慮在這2個(gè)方面改進(jìn)。