多局部約束自表示的譜聚類算法

蔣憶睿，裴 洋，陳 磊，王文樂，代江艷，易玉根

1.江西師范大學 軟件學院，南昌330022

2.濰坊學院 計算機工程學院，山東 濰坊261061

1 引言

子空間聚類（Subspace Clustering，SC）是機器學習、模式識別和計算機視覺等眾多領域中研究熱點之一[1-3]。近些年，子空間聚類受到研究者的廣泛關注，并提出了大量算法用于挖掘高維數據的低維結構[4-7]。根據采用方法的不同，大致可以將子空間聚類方法分為五類：基于代數方法、基于統計方法、基于迭代方法、基于矩陣分解方法和基于譜聚類的方法[8]。在上述方法中，由于基于譜聚類（Spectral Clustering）的方法具有較強的理論基礎，并且在圖像表示、圖像聚類等實際應用領域中取得優越的性能，因此，它已成為目前子空間聚類的主流技術之一[9-10]。

譜聚類方法首先通過計算樣本間的相似關系構建圖，然后對圖的拉普拉斯矩陣進行特征值分解得到相應的低維表示，最后利用k-mean 算法對其進行聚類[11-12]。因此，基于譜聚類方法的核心問題是如何有效地構建圖。傳統的圖構建方法，一類是基于數據的距離（如余弦距離或熱核距離），主要包括k-近鄰和ε-球方法[12]。而另一類方法則是通過最小化局部樣本重構誤差的方式實現圖的構建[13]。由于上述兩類方法具有直觀且易實現等特點，因此它們被廣泛用于譜聚類和基于圖的維數約簡等方法中，并取得較好的性能。然而，這些方法所涉及的鄰域參數和熱核參數在實際問題中難以選擇。參數一旦選取不恰當，將會導致聚類算法無法很好地挖掘數據的內在結構。另外，這些方法為所有樣本設置相同的參數，這也將導致算法不能很好地反映非均勻分布樣本的局部結構。

為了解決上述問題，相繼提出了大量基于數據驅動的自適應圖構建方法[14-15]。例如：Yang 等人[14]提出了樣本依賴圖（SG-graph）的方法，該方法根據計算每個樣本與所有樣本之間的平均相似性的差異尋找樣本近鄰。因此，它可以自適應地確定圖中每個樣本的近鄰數。隨著基于稀疏表示的方法在眾多領域中的成功應用，基于稀疏表示的構圖方法也相繼被提出[15]，也被稱為L1圖。如Elhamifar 等人[15]提出稀疏子空間聚類（Sparse Subspace Clustering，SSC）方法，該方法首先假設每個樣本可以用其他樣本線性表示，并對其表示系數加以基于l1-范數的稀疏約束。盡管基于稀疏表示的方法可以自適應選擇樣本的鄰域和計算樣本的權值，但該類方法需要分別求解每個樣本的稀疏表示，從而增加了算法時間代價。另外，由于單獨對每個樣本進行求解將導致所構建的圖不能很好地刻畫數據全局結構信息。

于是，為了解決上述方法存在的問題，Liu等人[16]提出基于低秩表示（Low-Rank Representation，LRR）的譜聚類方法，該方法通過求解數據的低秩表示獲取數據的全局結構。然而，由于LRR 方法在每次迭代求解過程中都需要進行奇異值分解并且收斂較慢，因此，該方法不適應于處理大規模高維數據。為了提高算法的效率，Lu等人[17]提出了一種基于最小二乘回歸（Least Squares Regression，LSR）的譜聚類方法，該方法充分利用數據的相關性將高度相關的數據聚集在一起。與LRR算法相比，LSR方法的求解簡單且高效。盡管通過LSR方法所構建的圖可以獲取樣本的全局結構，但其樣本的局部結構卻被忽略。換句話說，LSR方法并沒有考慮樣本點之間的距離關系，將導致在線性重構時選擇距離較遠的樣本進行重構，形成的圖并不能很好地反映數據的局部結構。然而，大量研究表明，數據的局部性在數據聚類和分類等任務中起著非常重要的作用。因此，Chen 等人[18]結合局部約束和LSR 方法提出一種局部約束最小二乘回歸（Locality-Constrained LSR，LCLSR）方法，充分繼承LSR 方法和局部約束的優點。文獻[18]中的實驗結果驗證LCLSR 方法的聚類性能要優于LSR 方法，但局部約束的選擇將會影響LCLSR方法的性能。

目前，提出了大量的距離度量方法，如基于指數函數的方法[19]、基于歐式距離的方法[20]、基于內積的方法[21]等。這些不同的距離度量方法都是基于不同的假設或準則提出的，它們可能僅適用于表征特定類型數據的結構。因此，如何有效選擇哪一種距離度量方法更適合特定任務和數據仍然是一個有待研究的問題。

本文為了解決上述方法存在的局限性，提出了一種多局部約束自身表示（Multiple Locality Constrained Self Representation，MLCSR）圖構建方法用于譜聚類，MLCSR 算法具有如下優點：（1）MLCSR 方法繼承了樣本的自表示能力和局部約束的優點，并將數據的自表示和局部性集成到一個統一的框架中。（2）MLCSR方法能夠自適應地將不同的距離度量函數組合到局部約束中，從而保證算法更具有靈活性和實用性。本文提出了一種基于迭代更新的優化策略來優化MLCSR 算法。另外，通過大量實驗驗證了MLCSR方法的有效性。

2 多局部約束自表示圖構建方法

2.1 目標函數

假設矩陣X=[x1,x2,…,xN]∈RD×N表示樣本集合，其中，包括N 個樣本，每個樣本的維度為D。

首先，假設集合中的任意樣本都可以由其他樣本線性表示。不同于LCLSR 方法，本文對表示系數加以非負約束使之更具有線性表示的物理意義，目標函數可定義為公式（1）：

其中，W=[w1,w2,…,wN]∈RN×N表示系數矩陣。

其次，為了在樣本重構時考慮數據的局部結構性，本文定義局部約束項如公式（2）所示：

其中，D=[dist(xi,xj)]N×N表示樣本間的距離矩陣，其元素dist(xi,xj)表示樣本xi和xj之間距離，dist(?)表示距離度量函數，||?||1則表示矩陣的l1范數，符號⊙表示矩陣元素的點乘操作運算。通過最小化公式（2）可以盡可能選擇距離與重構樣本較近的樣本進行重構。

同時，為了考慮不同距離度量函數對局部約束的影響，本文采用五種常用的距離度量函數[19-23]。如文獻[20]定義的一種基于歐式距離的函數，如公式（3）所示：

文獻[19]定義了一種基于指數的距離度量函數，如公式（4）所示：

其中，σ 是非零參數。在實驗中，本文將其設置為所有樣本歐式距離的均值。

文獻[21]定義了一種基于內積的距離度量函數，如公式（5）所示：

文獻[22]結合指數距離和內積距離函數定義為公式（6）：

其中，θ 是非零參數。實驗中本文將其設置為所有樣本內積的均值。

文獻[23]定義了一種基于l1范數的距離度量函數，如公式（7）所示：

其中，max(||xi-xj||1)i,j=1,2,…,N表示所有樣本的l1范數距離最大值。

然后，為了充分考慮不同距離度量函數之間互補性，本文將局部約束項重新定義為公式（8）：

其中，M 表示采用距離度量函數的數量（本文M=5），μ=[μ1,μ2,…,μM]為權值向量，α ＞0 為平衡參數。

最后，結合公式（1）和公式（8），MLCSR方法的最終目標函數如公式（9）所示：

其中，參數α 和β 平衡各項在目標函數中的貢獻。

2.2 優化求解

從目標函數公式（9）可以看出，有兩個變量（W 和μ）需要優化，然而對于這兩個變量而言，目標函數公式（9）為一個非凸函數，因此，無法給出目標函數的全局最優解。但對于單個變量而言，目標函數是一個凸函數，因此，本文給出一種基于迭代的優化算法對目標函數進行求解，即，固定其中一個變量，更新另一個變量。

2.2.1 固定μ，求解W

從目標函數中移除無關項，有關W 的優化問題可轉化為公式（10）：

對公式（10）進行運算，可簡化為：

求解公式（11），需引入拉格朗日乘子矩陣Λ，則公式（11）的拉格朗日函數定義為公式（12）：

對公式（12）求導并令其導數等于零，則有：

根據KKT條件ΛijWij=0[24]，則有：

根據公式（14），W 更新如公式（15）所示：

2.2.2 固定W，求解μ

從目標函數中移除無關項，有關μ 的優化問題可以轉換為公式（16）：

其中，qm=||Dm⊙W||1和。公式（16）是標準的凸二次規劃問題，本文采用文獻[25]的坐標梯度下降（Coordinate Descent Algorithm，CDA）方法求解。具體求解過程如下：考慮約束條件μm≥0 和，在每次迭代過程中僅更新權值向量μ 中的任意兩個成對的元素，而固定其他元素。首先，假設需要更新的成對元素為μk和μl(k ≠l)，固定其他元素μm(m ≠k,l)，根據上述約束條件，則有：

令ρ(μk)為目標函數，表示如下：

對公式（18）求導數，并令其等于零，則有：

根據公式（19），則有：

（3）否則有：

通過公式（22）至公式（24），成對更新μ 中的所有成對元素，直到目標函數達到收斂。

2.3 算法流程

本文提出的基于多局部約束的自表示圖構建算法如算法1所示。

算法1 基于多局部約束的自表示圖構建算法

輸入：樣本集X=[x1,x2,…,xN]∈RD×N，參數α 和β

1.通過公式（3）至（7）計算距離矩陣

2.循環迭代執行步驟3和4直到達到收斂條件

3. 通過公式（15）更新W 矩陣

4. 通過CDA方法求解權值向量μ

輸出：矩陣W ，權值向量μ

2.4 計算復雜度分析

本節主要對算法1 的計算復雜性進行分析。假設M 為本文所采用距離度量的數量，則其計算復雜度為O(MDN2)。根據文獻[25]，更新權值向量的計算復雜度為O(M2)，更新W 矩陣的計算復雜度為O(DN2)。因此，算法的總體計算復雜度為O(MDN2+T(M2+DN2))，其中T 表示算法的迭代次數。表1 給出不同圖構建算法的計算復雜度的對比結果。從表中可以看出，KNN算法的計算復雜度最小，L1、LRR 和MLCSR 三個算法的計算復雜度要高于其他方法。

表1 不同算法的計算復雜度

2.5 參數設置

從目標函數公式（9）中可知，本文方法包括兩個參數，分別為α 和β。參數α 主要用于控制局部約束項重要性，而參數β 用于控制不同拉普拉斯矩陣的權值。因此，參數的取值應根據數據庫特征進行設置。更為詳細的說，當來自同類的樣本具有較高的相似性，并與其他類樣本可以較容易分開，此時應該將參數α 設置較大的值使之能夠很好地保持數據的局部結構信息。相反，當樣本的鄰域樣本來自于不同類的樣本，此時將參數α 設置為較小值。對于參數β 而言，當β →∞，所有拉普拉斯矩陣的權值相同，此時，忽略了不同拉普拉斯矩陣的差異。當β 設置為零，權值向量μ 中僅有一個元素有值，也是說僅僅一個拉普拉斯矩陣被利用。因此，參數β 應該設置為適中的值。

2.6 算法收斂分析

本節主要對算法收斂性進行分析。首先，將目標函數公式（9）標記為φ(W,μ)，則有如下理論：

理論1 目標函數φ(W,μ)其函數值是遞減的。

證明 令φ(Wt,μt)表示目標函數在第t 次迭代時的目標函數值。首先，在第t+1 迭代時，固定μt，再求解子優化問題。對于該子優化問題的收斂性證明可以參閱文獻[26]。因此在每次迭代W 時，目標函數值隨著降低，故有如下不等式成立：

然后，固定Wt，繼續求解子優化問題對于求解此優化問題，本文采用CDA算法求解，可以獲得最優的μt+1。由于該優化問題屬于一個凸優化問題，故有如下不等式：

最后，結合不等式（25）和（26），可得到如下不等式：

綜上所述，理論1 已被證明。而且，由于目標函數公式（9）中的所有項都是大于等于零，因此，目標函數具有最小值。因此，根據柯西收斂準則[27]，本文提出方法的目標函數是收斂的。并且在數值實驗中也驗證了目標函數值隨著迭代次數的增加能夠快速趨于收斂。

3 實驗及分析

為了測試本文提出的MLCSR 算法的有效性，在3個標準的人臉圖像數據庫進行實驗（如Yale[28]、AR[29]和CMU PIE[30]）。三個圖像數據庫的具體信息如表2 所示，以及每個數據庫中的部分實例圖像如圖1所示。

表2 數據庫詳細信息

圖1 數據庫中部分實例圖

本實驗中將MLCSR方法與不同的圖構建方法比較，如KNN[12]、LLE[13]、L1[15]、LRR[16]、LSR[17]和LCLSR[18]。本文提出的方法和所有對比方法都是基于Matlab2016 編程實現的。實驗平臺為Intel?Core?i7-4790，雙核GPU，頻率為3.60 GHz，內存為8 GB，系統為64 位Windows 10 系統。此外，MLCSR 方法采用公式（3）至公式（7）的五個距離度量函數。在實驗中采用網格式搜索方式尋找各個方法中參數的最優取值。由于譜聚類中的kmeans 聚類算法的性能依賴于初始化，因此，實驗中將隨機執行50 次不同的初始化，然后統計其平均值和標準差作為最終結果。本文采用三個常用的度量準則：聚類準確率（ACC）、歸一化互信息（NMI）和純度（Purity）評價聚類算法的性能。不同方法在三個人臉數據庫上的實驗結果，如表3至表5所示。

表3 不同方法在Yale數據庫上聚類結果 %

表4 不同方法在AR數據庫上聚類結果 %

表5 不同方法在CMU PIE數據庫上聚類結果%

從表3至表5的實驗結果中可得到如下結論：

（1）基于KNN 和LLE 圖的聚類性能要低于其他構圖方法，其主要原因是基于歐式距離的KNN 和LLE 圖對數據中的噪聲點、局外點以及參數取值非常敏感。

（2）因為基于LRR 和LSR 的方法在構圖過程中考慮數據的全局結構，所以，它們的性能要優于L1 圖的方法。

（3）由于基于LRR和LSR的圖構建方法忽略了數據的局部結構，因此，它們聚類效果要低于LCLSR方法。

（4）由于本文提出的MLCSR 方法融合了多個距離度量準則，可以充分挖掘數據的局部結構特性，所以它的性能要優于所有對比方法。

其次，為了驗證采用不同距離度量的必要性。實驗中將測試單獨采用一種距離度量函數的算法聚類性能，其結果如表6所示。從表中可觀察到，僅僅用單一的距離度量函數的聚類正確率要低于融合使用多個距離度量函數的。因此，實驗結果說明了本文采用多個距離準則是有必要的。為了進一步驗證不同距離函數的權值對算法性能的影響，在實驗中將所有距離函數的權值設置為等同值，其結果如表7 所示，實驗結果驗證了權值分配對算法性能也有一定的影響。

表6 不同度量函數在數據庫上聚類準確率ACC %

表7 不同權值本文方法在數據庫上聚類準確率ACC %

接著，為了驗證算法收斂性，圖2 給出MLCSR 算法在3 個人臉圖像數據庫上的目標曲線圖。從圖中可以看出，MLCSR 算法在較少的迭代次數下就能達到收斂。

圖2 不同數據庫上的目標曲線圖

最后，表8給出不同算法在各個數據庫上的運行時間。從表8中看出，基于KNN、LLE和LSR和LCLSR的圖構建方法的運行時間總體要低于其他方法，但本文提出的構圖方法的運行時間要低于基于L1和LRR的構圖方法。

表8 不同方法在三個數據庫上運行時間 s

4 結論

通過融入多個距離度量準則，本文提出一種基于多局部約束的自表示圖構建方法用于譜聚類。不同于現有的方法，該方法不僅繼承了樣本間的自表示特性，同時還能充分挖掘數據的局部性。為了有效地求解目標函數，本文基于迭代思想提出一種優化算法，并在理論方法和數值實驗中驗證該優化算法的收斂性。最后，在三個數據庫上的實驗驗證了本文方法有效性。