基于譜聚類的自加權多視圖聚類算法研究

徐浩琦，侯建，袁華強

（東莞理工學院計算機科學與技術學院，廣東東莞 523000）

現實中樣本的特征多是來自不同的視圖。多視圖聚類就是利用不同視圖的特征進行聚類[1]。多視圖數據融合策略一般可以分為三種，分別是一致性策略、互補性策略和兼容性策略。一致性策略算法一般會最大化不同視圖之間的相關性，然后從中提取出視圖間的共享成分進行分析[2]?；パa策略主要是顯示保留多視圖數據中視圖間的共享成分和每個單視圖的特有信息成分[3]。而兼容性策略主要是自適應地兼容共享信息和特有信息[4]。

文獻[5]提出將跨視圖圖擴散用于多視圖聚類統一圖的學習，但是該算法沒有考慮不同視圖之間重要性的差異。文獻[6]提出了一種基于子空間融合的多視圖聚類算法，但是該算法需要對不同視圖的權重進行單獨優化。該文提出了一種基于譜聚類的自加權多視圖聚類算法。該算法可以自動為視圖添加權重，同時利用秩約束來控制全局圖的連通分量，使連通分量個數與簇的個數相同，以直接從圖結構中獲得聚類結果。

1 相關工作

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

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

這里引入一個定理，以進行接下來的論述：

定理1：圖G的拉普拉斯矩陣L的0 特征值的重數等于圖G連通分量個數[8]。

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

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

2 多視圖聚類算法

2.1 自動加權算法

當面對多視圖數據時，不同的視圖可能具有不同的重要性。因此，需要給不同的視圖增加權重。一些算法選擇使用拉格朗日乘數法，通過最大梯度對權重進行優化，但是這種方法需要給權重添加一個超參數。過多的參數將會給算法帶來很大的不確定性，調整參數的過程也將會產生很大的計算開支。鑒于上述原因，選擇使用自加權[10-11]的方式對每個視圖進行加權。構造了如下形式的目標函數：

其中，W(v)=假設H(v)可以由式（2）進行計算，那么H(v)就可以用來更新之前的W(v)?？梢允褂醚h迭代的方式對上式進行優化。

2.2 全局圖的構造

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

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

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

選擇線性核來度量相似性的主要原因[12]在于，拉普拉斯譜聚類中使用的相似性度量已經考慮了數據中存在的非線性結構，并且嵌入矩陣H(·)是實值的聚類指標矩陣，因此可以認為該結構服從線性相似性。

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

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

圖1 算法思路

2.3 算法優化

目標問題可以分為兩個子問題，分別固定其中一個目標變量，更新另一個目標變量，交替循環迭代求解。

2.3.1 更新H(v)

第一個子問題中，將變量S固定視為常數，更新變量H(v)。此時，目標函數變為：

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

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

2.3.2 更新S

第二個子問題中，將變量H(v)固定視為常數，更新變量S，此時，目標函數變為：

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

其中，γ是權衡參數。

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

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

在式（1）和式（8）中出現的權衡參數α和γ是用來實現約束條件rank(L)=n-k的。它們將會在算法優化過程中自動求解。它們的初始值將會設置為1，并且在迭代期間會根據不斷優化，直到

2.4 算法步驟

算法整體流程如下所示：

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

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

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

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

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

步驟3：利用LS的前k個最小的特征值對應的特征向量組成H；

步驟4：重復步驟2-3，直到S恰有k個連通分量；

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

算法流程如圖2 所示。

圖2 算法流程圖

3 實驗

將該文算法在一些數據集上進行了實驗測試，以驗證算法的有效性。首先引入了兩個在多視圖聚類算法實驗中廣泛使用的數據集。然后將該算法與另外幾種常用于比較的多視圖聚類算法進行對比，并對實驗結果進行討論。

3.1 數據集

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

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

3.2 實驗結果與比較

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

表1 算法在COIL20數據集上的運行結果

表2 算法在Mfeat數據集上的運行結果

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

4 結論

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

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