徐浩琦，侯建，袁華強(qiáng)

（東莞理工學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，廣東東莞 523000）

現(xiàn)實(shí)中樣本的特征多是來自不同的視圖。多視圖聚類就是利用不同視圖的特征進(jìn)行聚類[1]。多視圖數(shù)據(jù)融合策略一般可以分為三種，分別是一致性策略、互補(bǔ)性策略和兼容性策略。一致性策略算法一般會(huì)最大化不同視圖之間的相關(guān)性，然后從中提取出視圖間的共享成分進(jìn)行分析[2]。互補(bǔ)策略主要是顯示保留多視圖數(shù)據(jù)中視圖間的共享成分和每個(gè)單視圖的特有信息成分[3]。而兼容性策略主要是自適應(yīng)地兼容共享信息和特有信息[4]。

文獻(xiàn)[5]提出將跨視圖圖擴(kuò)散用于多視圖聚類統(tǒng)一圖的學(xué)習(xí)，但是該算法沒有考慮不同視圖之間重要性的差異。文獻(xiàn)[6]提出了一種基于子空間融合的多視圖聚類算法，但是該算法需要對(duì)不同視圖的權(quán)重進(jìn)行單獨(dú)優(yōu)化。該文提出了一種基于譜聚類的自加權(quán)多視圖聚類算法。該算法可以自動(dòng)為視圖添加權(quán)重，同時(shí)利用秩約束來控制全局圖的連通分量，使連通分量個(gè)數(shù)與簇的個(gè)數(shù)相同，以直接從圖結(jié)構(gòu)中獲得聚類結(jié)果。

1 相關(guān)工作

譜聚類是一種被廣泛使用的聚類算法。其中譜聚類的歸一化割（NCUT）算法更是在諸多領(lǐng)域取得了較好的效果。但是，譜聚類算法的效果高度依賴于相似度矩陣的質(zhì)量。如果可以直接構(gòu)建出具有k個(gè)連通分量的相似度圖，那么就可以直接從圖的本身獲得聚類結(jié)果，通過這一方式來為每個(gè)單一視圖進(jìn)行聚類。對(duì)于數(shù)據(jù)集X={X(1),X(2),…,X(nv)}，其中X(i)代表第i個(gè)視圖的原始數(shù)據(jù)。根據(jù)文獻(xiàn)[7]，將歸一化拉普拉斯矩陣L的前k個(gè)最小特征值對(duì)應(yīng)的特征向量組成的矩陣H視為原始數(shù)據(jù)X的低維嵌入，可以通過以下目標(biāo)函數(shù)得出圖的相似度距陣W：

其中，W受約束條件W1=1 的約束。這一約束可以將得到的拉普拉斯矩陣控制為歸一化拉普拉斯矩陣，即L=I-W。隨著該目標(biāo)函數(shù)不斷優(yōu)化，最終使得L的前k個(gè)最小特征值的和為0。通過該目標(biāo)函數(shù)得出的W具有理想的鄰居分配，并且其連通分量個(gè)數(shù)與簇的個(gè)數(shù)相同。

這里引入一個(gè)定理，以進(jìn)行接下來的論述：

定理1：圖G的拉普拉斯矩陣L的0 特征值的重?cái)?shù)等于圖G連通分量個(gè)數(shù)[8]。

由定理1 可以得出，可以通過控制圖的拉普拉斯矩陣的0 特征值重?cái)?shù)，來控制圖的連通分量個(gè)數(shù)。不失一般性，將L的特征按照從小到大排列，由于拉普拉斯矩陣的最小特征值為0，如果前k個(gè)最小特征值之和為0，則有L的秩rank(L)=n-k，根據(jù)定理1 進(jìn)一步可得，圖的連通分量個(gè)數(shù)為k。由此可以得到約束條件：=0 。該約束條件可以控制圖的連通分量個(gè)數(shù)始終為k，保證了最終的聚類結(jié)果可以從圖的結(jié)構(gòu)中直接得出。

目標(biāo)函數(shù)（1）的優(yōu)化結(jié)果可以通過優(yōu)化兩個(gè)子問題交替求解，直到L的前k個(gè)最小特征值之和為0。第一個(gè)子問題是求解方程特征值分解問題。第二個(gè)子問題則是單純形空間上的歐幾里得投影問題[9]。

2 多視圖聚類算法

2.1 自動(dòng)加權(quán)算法

當(dāng)面對(duì)多視圖數(shù)據(jù)時(shí)，不同的視圖可能具有不同的重要性。因此，需要給不同的視圖增加權(quán)重。一些算法選擇使用拉格朗日乘數(shù)法，通過最大梯度對(duì)權(quán)重進(jìn)行優(yōu)化，但是這種方法需要給權(quán)重添加一個(gè)超參數(shù)。過多的參數(shù)將會(huì)給算法帶來很大的不確定性，調(diào)整參數(shù)的過程也將會(huì)產(chǎn)生很大的計(jì)算開支。鑒于上述原因，選擇使用自加權(quán)[10-11]的方式對(duì)每個(gè)視圖進(jìn)行加權(quán)。構(gòu)造了如下形式的目標(biāo)函數(shù)：

其中，W(v)=假設(shè)H(v)可以由式（2）進(jìn)行計(jì)算，那么H(v)就可以用來更新之前的W(v)。可以使用循環(huán)迭代的方式對(duì)上式進(jìn)行優(yōu)化。

2.2 全局圖的構(gòu)造

多視圖聚類需要將不同視圖中的信息匯集到一起，學(xué)習(xí)得到一個(gè)全局圖。為了使得到的全局圖能充分包含各個(gè)單視圖的信息，需要在學(xué)習(xí)過程中將全局圖與各個(gè)單視圖之間的差距控制到最小。為此，需要構(gòu)造出一個(gè)更能體現(xiàn)每個(gè)單視圖特征的矩陣。

首先，對(duì)每個(gè)單視圖的特征矩陣進(jìn)行處理，使其可以更好地表達(dá)每個(gè)視圖的結(jié)構(gòu)信息。為此，使用譜聚類的歸一化割算法，得到每個(gè)視圖的低維嵌入矩陣H。這樣的處理能夠使圖中的各個(gè)樣本點(diǎn)分配到最佳鄰居的結(jié)構(gòu)。再利用自加權(quán)的方式，為每個(gè)視圖添加各自的權(quán)重。這樣就可以協(xié)同所有視圖共同取得最小的歸一化割，以此來學(xué)習(xí)到合適的嵌入矩陣。

為了使嵌入矩陣可以更好地體現(xiàn)原視圖的圖結(jié)構(gòu)，采用線性核函數(shù)k(xi,xj)=來計(jì)算每個(gè)視圖在經(jīng)過NCUT 之后的相似度矩陣HHT。理想狀態(tài)下，HHT為對(duì)角矩陣?？梢岳眠@些不同的視圖得到一個(gè)全局圖矩陣S。該全局圖可以通過最小化S與不同視圖的對(duì)角矩陣H(v)(H(v))T之間的差值mv得到：

選擇線性核來度量相似性的主要原因[12]在于，拉普拉斯譜聚類中使用的相似性度量已經(jīng)考慮了數(shù)據(jù)中存在的非線性結(jié)構(gòu)，并且嵌入矩陣H(·)是實(shí)值的聚類指標(biāo)矩陣，因此可以認(rèn)為該結(jié)構(gòu)服從線性相似性。

該算法有以下要點(diǎn)。首先，算法初始化過程中，每個(gè)視圖的相似度圖可以通過式（1）得到。其次，利用W得到每個(gè)視圖的嵌入矩陣H。同時(shí)，可以利用rank(LS)=n-k的約束，使最終學(xué)習(xí)到的全局圖S恰好有k個(gè)連通分量，每個(gè)連通分量恰好可以作為一個(gè)簇。最后，通過最小化全局圖與每個(gè)視圖的H(v)(H(v))T矩陣之間的距離，可以得到更優(yōu)的全局圖S。目標(biāo)函數(shù)如下：

其中，LS是S的歸一化拉普拉斯矩陣。整體算法思路如圖1 所示。

圖1 算法思路

2.3 算法優(yōu)化

目標(biāo)問題可以分為兩個(gè)子問題，分別固定其中一個(gè)目標(biāo)變量，更新另一個(gè)目標(biāo)變量，交替循環(huán)迭代求解。

2.3.1 更新H(v)

第一個(gè)子問題中，將變量S固定視為常數(shù)，更新變量H(v)。此時(shí)，目標(biāo)函數(shù)變?yōu)椋?/p>

同時(shí)考慮約束條件(H(v))TH(v)=I，原問題可以等價(jià)為：

該方程的解即為[W(v)(W(v)-I)+2S]的前k個(gè)最大的特征值對(duì)應(yīng)的特征向量組成的矩陣。

2.3.2 更新S

第二個(gè)子問題中，將變量H(v)固定視為常數(shù)，更新變量S，此時(shí)，目標(biāo)函數(shù)變?yōu)椋?/p>

約束條件rank(LS)=n-k可以用minTr(HTLSH)來實(shí)現(xiàn)。令Q=則式（7）可以等價(jià)為：

其中，γ是權(quán)衡參數(shù)。

式（8）中的變量在不同的列之間是相互獨(dú)立的，則上述問題可以表示為：

其中，sj表示S的第j列。為了方便表示，令上述問題可以等價(jià)為一個(gè)在單純形空間上的拉格朗日投影問題。根據(jù)Karush-Kuhn-Tucker(KKT)條件[13]，可以驗(yàn)證最優(yōu)解為：

在式（1）和式（8）中出現(xiàn)的權(quán)衡參數(shù)α和γ是用來實(shí)現(xiàn)約束條件rank(L)=n-k的。它們將會(huì)在算法優(yōu)化過程中自動(dòng)求解。它們的初始值將會(huì)設(shè)置為1，并且在迭代期間會(huì)根據(jù)不斷優(yōu)化，直到

2.4 算法步驟

算法整體流程如下所示：

輸入：原始數(shù)據(jù)X={X(1),X(2),…,}，視圖數(shù)nv，簇個(gè)數(shù)k；

輸出：恰有k個(gè)連通分量的全局圖S；

初始化：初始的相似度矩陣W和嵌入矩陣H0由式（1）計(jì)算得到，初始全局圖矩陣S0由得到。此處的H0由拉普拉斯矩陣LS的前k個(gè)最小特征值對(duì)應(yīng)的特征向量組成。

步驟1：對(duì)于數(shù)據(jù)的每一個(gè)視圖v∈{1,2,…,nv}，通過式（6）求得當(dāng)前具有最佳鄰居分配的H(v)；

步驟2：對(duì)每一個(gè)樣本j∈{1,2,…,n}，通過式（10）更新sj；

步驟3：利用LS的前k個(gè)最小的特征值對(duì)應(yīng)的特征向量組成H；

步驟4：重復(fù)步驟2-3，直到S恰有k個(gè)連通分量；

步驟5：重復(fù)步驟1-4，直到算法收斂。

算法流程如圖2 所示。

圖2 算法流程圖

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

將該文算法在一些數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)測(cè)試，以驗(yàn)證算法的有效性。首先引入了兩個(gè)在多視圖聚類算法實(shí)驗(yàn)中廣泛使用的數(shù)據(jù)集。然后將該算法與另外幾種常用于比較的多視圖聚類算法進(jìn)行對(duì)比，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行討論。

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

COIL-20 數(shù)據(jù)集由20 個(gè)類別的1 440 幅圖像組成，每個(gè)類別有72 幅圖像。每個(gè)樣本由4 個(gè)不同的特征表示，這些特征組成了4 個(gè)視圖。

Mfeat數(shù)據(jù)集來自UCI機(jī)器學(xué)習(xí)資源庫(kù)。該數(shù)據(jù)集由2 000 個(gè)樣本(從0 到9 的每個(gè)類種各包含200 個(gè)樣本)組成。其使用了6 個(gè)不同的特征組成了相應(yīng)的視圖，包括76 個(gè)字符形狀傅里葉系數(shù)、216 個(gè)輪廓系數(shù)、64 個(gè)Karhuen-Love 系數(shù)、240 個(gè)2×3 窗口的像素平均值、47 個(gè)Zernike 矩和6 個(gè)形態(tài)特征。

3.2 實(shí)驗(yàn)結(jié)果與比較

將提出的算法與另外3 種多視圖聚類算法進(jìn)行了比較。這些算法分別是譜聚類的親和度聚合算法[14]（AASC）、穩(wěn)健的多視圖譜聚類算法[15]（RMSC），以及多視圖共識(shí)圖聚類算法[16]（MCGC）。表1 和表2中展示了該文算法與3 個(gè)對(duì)比算法在兩個(gè)數(shù)據(jù)集上進(jìn)行10 次實(shí)驗(yàn)的平均結(jié)果。

表1 算法在COIL20數(shù)據(jù)集上的運(yùn)行結(jié)果

表2 算法在Mfeat數(shù)據(jù)集上的運(yùn)行結(jié)果

從表1 和表2 中可以看出，該文算法在COIL20、Mfeat 數(shù)據(jù)集上的性能更優(yōu)，其歸一化互信息NMI(Normalized Mutual Information)、精確度ACC(Accuracy)和純度PU(Purity)值均高于另外3 種算法。RMSC 算法在Mfeat 數(shù)據(jù)集上的效果要遠(yuǎn)差于其他對(duì)比算法，其原因可能在于該算法的參數(shù)選擇方法限制了其在不同數(shù)據(jù)集上的通用性。

4 結(jié)論

該文提出了一種基于譜聚類的自動(dòng)加權(quán)多視圖聚類算法。該算法通過對(duì)相似度矩陣使用秩約束，來使矩陣的連通分量個(gè)數(shù)與簇個(gè)數(shù)相同，從而可以直接通過圖的結(jié)構(gòu)得到聚類結(jié)果。通過最小化全局圖與各單視圖優(yōu)化后的相似度矩陣之間的距離得到最終的相似度圖。該算法還考慮到了每個(gè)視圖的重要性的差異，通過添加自動(dòng)加權(quán)的方式，減少了模型的參數(shù)個(gè)數(shù)，使得模型具有更好的魯棒性。該算法在兩個(gè)真實(shí)數(shù)據(jù)集上運(yùn)行，并與其他3 個(gè)多視圖算法進(jìn)行對(duì)比，在多個(gè)評(píng)價(jià)指標(biāo)上取得了更優(yōu)的結(jié)果，可以認(rèn)為該算法具有更優(yōu)的性能。

在未來的工作中，將會(huì)考慮使用其他的距離度量方式，來提高算法應(yīng)對(duì)噪聲的能力，即提高算法的魯棒性。