特征直連與結構化約束的多視圖子空間聚類*

張翼飛，鄧秀勤，王卓薇

(廣東工業大學數學與統計學院,廣東 廣州 510006)

1 引言

多視圖聚類通過數據的不同視圖來學習數據包含的信息和結構，并由此對多視圖數據進行簇劃分。不同于傳統的單視圖數據聚類，多視圖聚類面對的是更加復雜的數據。由于數據樣本來源或者特征表達方式的多樣性，多視圖聚類需要面對的是如何通過多個視圖來獲取一個良好的聚類結果。

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

(1)將特征直連數據加入算法框架，與原有的多視圖共同學習，探尋多視圖與特征直連數據的關系；

(2)通過子空間分解重構誤差，保證誤差的穩定性；

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

2 相關工作

2.1 子空間聚類

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

s.t.diag(V)=0

(1)

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

(2)

其中,‖·‖Ψ為范數表達式,Ψ與式(1)中的?同為泛指，當Ψ=1時，式(2)為稀疏約束，當Ψ=*時，式(2)為核范數，此時為低秩約束。α為超參數，用于調節范數大小。

2.2 多視圖子空間聚類

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

(3)

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

(4)

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

(5)

其中，S為共識矩陣，β為超參數。

式(5)不同于式(3)，其共識矩陣的獲得是與子空間學習一起進行的，兩者框架的統一能確保最終的共識矩陣更加合理。

3 特征直連與結構化約束

本節提出了一種基于特征直連與結構化約束的多視圖子空間聚類算法FSMC。該算法通過特征直連數據與多視圖數據的共同學習來重構誤差，并通過約束使子空間滿足特定的結構，同時還考慮了多個視圖子空間與直連視圖之間的關系。

3.1 特征直連

s.t.E=D-DV

(6)

其中，λ是超參數;E為誤差矩陣;V為其相應的子空間表示;‖·‖2,1為矩陣的L2,1范數，表示對矩陣的行求向量的L2范數得到一個向量，然后再對該向量求L1范數。‖E‖2,1是為了重構誤差，使誤差趨于穩定，‖V‖2,1為結構化約束，保證子空間的稀疏約束。

3.2 結構化約束

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

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

(7)

為了將多視圖數據與特征直連數據聯系起來，將式(6)與式(7)動態結合起來得到式(8):

L=αL1+(1-α)L2

(8)

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

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

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

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

(9)

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

Figure 1 General process of FSMC algorithm

3.3 FSMC算法優化

對于式(9)的優化，需要引入多個變量，并采用增廣拉格朗日迭代求解。引入變量Ci和C后式(9)變為式(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)的優化步驟如下所示(其中，〈A,B〉為矩陣ATB的跡，A和B泛指矩陣)：

步驟1固定除Ei之外的所有變量，更新Ei，此時式(10)變為式(11)：

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

(11)

由于每個視圖都是獨立的，那么式(11)可拆分并轉換為式(12)：

(12)

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

(13)

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

步驟2固定除E之外的所有變量，更新E，此時式(10)變為式(14)：

(14)

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

步驟3固定除Ci之外的所有變量，更新Ci，此時式(10)變為式(15)：

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

(15)

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

(16)

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

步驟4固定除C之外的所有變量，更新C，此時式(10)變為式(17)：

(17)

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

步驟5固定除Vi之外的所有變量，更新Vi，此時式(10)變為式(18):

(18)

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

Vi=(T1)-1T2

(19)

步驟6固定除V之外的所有變量，更新V，此時式(10)變為式(20):

(20)

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

V=(Z1)-1Z2

(21)

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

(22)

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

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算法

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

輸出：共識矩陣S。

步驟：

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

While迭代次數<最大迭代次數:

Ifi≤視圖個數v:

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

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

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

Endif

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

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

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

根據式(22)更新共識矩陣S；

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

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

break;

else

迭代次數加1;

Endif

Endwhile

4 實驗

4.1 數據集及性能指標

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

Table 1 Datasets

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

(24)

(25)

(26)

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

4.2 實驗結果與分析

為了評估本文提出的FSMC算法的多視圖聚類性能，本文將FSMC算法與5個不同時間段提出的算法進行對比實驗，這5個算法分別是譜聚類SC(Spectrual Clustering)[11](在本文中分別用單個視圖聚類，即SCi表示在第i個視圖下的譜聚類算法，值得注意的是在HW數據集上選擇了結果較好的4個視圖)、基于質心的多視圖低秩稀疏子空間MLRSSC (centroid-based Multi-view Low-Rank Sparse Subspace Clustering)算法[12]、用于多視圖聚類的圖學習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個數據集上的實驗結果。

實驗中每個算法運行10次，然后取平均值和標準差作為最終的性能指標值。對于權重參數，考慮到復雜性，假設其多視圖數據與特征聯合數據的權重占比是一樣的，即暫且認為其對于最終聚類結果的影響同等重要，因此將權重參數α設為0.5，而權重參數對于聚類結果的影響可以參照圖2，該圖給出了當其余參數固定時，α參數對BBC數據集聚類結果的影響。

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

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

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

Figure 4 Convergence of FSMC on BBC dataset

5 結束語

本文在多視圖子空間聚類算法的基礎上提出了基于特征直連和重構誤差的多視圖聚類算法。與現有的算法不同，FSMC在原有的視圖中增加了一個特別的視圖數據——特征直連數據，讓算法學習的信息更加豐富。同時通過重構誤差矩陣使誤差穩定，在保證表示矩陣結構稀疏的同時學習到特征直連視圖與其余視圖的差異性，最終通過共同學習得到最終的表示矩陣。本文在4個真實數據集上評估了算法的聚類效果，驗證了算法的有效性。但是，FSMC算法只考慮多視圖與特征直連視圖之間的權重，沒有考慮到多視圖之間的權重，而且沒有探尋特征直連數據的子空間結構，后續工作可以考慮在這2個方面改進。