結構圖正則低秩子空間聚類

劉 婕，馬 帥

西安電子科技大學 數學與統計學院，西安 710126

1 引言

當今社會，處于一個數據爆炸的時代，充分有效地利用這些數據成為人們的必然要求。由于大多數的數據都是高維的，這給數據分析帶來了不少困難。子空間聚類[1]往往是處理這類數據強有力的工具，同時可以有效地揭示高維數據的低維結構。目前，子空間聚類的方法有很多，大致可以分為四類：迭代方法[2-3]、統計方法[4-5]、代數方法[6]，以及基于譜聚類的方法。在子空間聚類的諸多方法中，基于譜聚類的方法最受歡迎，例如：稀疏子空間聚類（SSC）[7]、低秩表示（LRR）[8]、最小二乘回歸（LSR）[9]、光滑表示（SMR）[10]，以及相關自適應子空間聚類（CASS）[11]。這些方法在原理上可以分為兩步，第一步利用數據的自表示來學習相似度矩陣，第二步利用譜聚類算法得到最終的聚類結果。雖然基于譜聚類的方法取得了較好的聚類結果，但是卻沒有充分利用數據相似度與分割之間的依賴關系。

最近，Li和Vidal等人提出的結構稀疏子空間聚類（SSSC）[12]將上述兩步結合成一步，充分利用了數據相似度與分割之間的依賴事實，用數據類別標簽引導數據之間的相似度，同時利用數據相似度來引導分割。SSSC模型是SSC模型的延伸，而SSC模型單獨尋找每個數據的稀疏表示，缺乏對表示系數全局結構的約束，忽略了數據間的聯系和全局特征，不能很好地捕獲數據的內在幾何結構和全局結構。而且當多個數據與某個數據高度相關時，SSSC只會隨機地選取一個數據，不能保證相似度矩陣的連接性問題。張和王[13]等人發現SSSC不能保證同類數據相似度的一致性，在SSSC的基礎上增加了子空間結構低秩正則項，確保同類數據相似度矩陣的一致性，但卻不能捕獲數據的全局結構。Zhang和Li[14]等人受到SSSC模型的啟發，在低秩表示的基礎上，提出了聯合學習相似度矩陣和聚類結果的統一框架，雖然該方法捕獲了數據的全局結構，卻忽略了數據相似度矩陣的連接性。上述方法雖然取得了較好的聚類結果，但它們都是建立在SSSC模型基礎上，都存在SSSC模型存在的問題。

為了解決上述問題，同時獲得一個學習相似度矩陣與聚類結果的聯合優化模型，本文引入了表示系數矩陣的子空間結構范數，增加了低秩表示來揭示高維數據的全局結構。進一步，為了使相似度矩陣具有連接性，還定義了分組效應來捕獲數據的內部幾何結構，提出了結構化圖正則低秩子空間聚類模型（SGRLRSC）。實驗表明，在常用的數據集上，提出的方法優于其他先進的子空間聚類算法。

2 結構圖正則低秩子空間聚類

2.1 相關工作

在基于譜聚類的方法中，假設每一個樣本點都可以用來自同一個子空間的樣本點線性表示，即X=XZ，其中Z為表示系數矩陣，當有噪聲時，表示為X=XZ+E，其中E為噪聲。通常基于譜聚類的方法統一可以寫為以下形式：

2.2 SGRLRSC模型

本文在子空間結構范數上，增加了低秩表示，在集群內部定義了分組效應作為正則項，給出了一個新的統一優化模型，稱為結構圖正則低秩子空間聚類。

首先，為了能夠充分利用數據相似度與分割的依賴事實，獲得一個聯合學習相似度矩陣與聚類結果的統一框架，本文通過最小化‖Z‖Q來懲罰表示系數矩陣與分割矩陣的不一致性。‖Z‖Q有效地結合了數據相似度矩陣與聚類結果，在迭代過程中，使得表示系數矩陣Z與分割矩陣Q變得一致。

其次，好的相似度矩陣會使得聚類結果更加魯棒。對于相似度矩陣的連接性來說，希望模型能夠自動地把相關性高的數據聚集在一起，即，同一子空間的數據點之間的連接性應該為1，不同空間的數據點之間的連接性應該為0。為此，本文定義了分組效應：

由定義可知，最大化cos

其中wij用來度量數據點xi與數據點xj的空間距離，如果，那么上式可等價于：

最后，SSSC模型中l0-范數單獨尋找每個數據的稀疏表示，缺乏對表示系數的全局約束，由于低秩表示能從全局對子空間表示進行處理，因此本文對所有數據進行了低秩表示，來捕獲數據的全局結構。綜上所述，本文提出的模型為：

其中 λ,β,γ＞0為權衡參數，Ω={Q∈{0,1}N×k:Q1=1,rank(Q)=k}是分割矩陣的空間。上述模型稱為結構圖正則低秩子空間聚類，簡稱（SGRLRSC）。

當‖‖zi2=1(?i=1,2,…,N)，那么

等價于

因此模型（5）等價于：

一方面，表示系數矩陣不但是塊對角的，可以捕獲數據的全局結構，迫使不相關的數據之間盡量有較少的聯系，而且具有分組效應，能夠捕獲數據的內部幾何結構，迫使高度相關的數據集聚為一類；另一方面，在迭代過程中，表示系數矩陣Z與分割矩陣Q相互平衡。初始化P=0后，對表示系數矩陣進行求解，然后利用譜聚類得到相應的分割矩陣，得到分割矩陣后在修正表示系數矩陣，如此循環下去，表示系數矩陣與分割矩陣變得更加一致，以此來得到更好的聚類結果。

3 模型求解

模型（8）不是凸優化問題，不能直接進行求解，為了得到最優解，采用交替迭代最優化的方法求解模型。將上述問題分解為關于Q和Z的子問題，求取最優解：

（1）給定Q，本文使用帶自適應懲罰的線性化ADM方法（LADMAP）[16]來得到 Z 。

（2）給定Z，可以利用譜聚類得到Q。

線性交替乘子方法（LADMM）被廣泛地應用于子空間聚類算法的求解問題上，在SGRLRSC模型求解時，首先固定分割矩陣Q可以利用LADMM求解表示系數Z，得到表示系數后，再更正Q。在求解表示系數矩陣Z時，由于LADMM自身的特點（矩陣與矩陣乘法以及矩陣求逆，該方法會受到計算復雜性的影響），當遇到的數據庫比較大時，得到Z的最優解比較慢，那么更新Q的速度也會變慢，這樣會使得最終的運算效率下降。因此采用LADMAP進行求解，LADMAP方法與LADMM方法求解模型的思想是一致的，都是通過固定其他變量求解另一個變量。但是LADMAP方法不需要引入輔助變量和逆矩陣，從而減輕了矩陣與矩陣之間的運算。在參考文獻[16]中，作者在實驗中已經證明了LADMAP方法的運算效率比LADMM方法運算效率高。為了證明使用LADMAP方法求解在本文中可以提高運算效率，在實驗部分，在相同的條件下對比了利用LADMAP方法求解模型和利用LADMM方法求解模型在實驗數據集的運算時間，LADMAP方法可以縮短運算時間，提高運算效率。

（1）表示系數矩陣Z的求解

給定Q，式（8）等價于：

那么上述問題可以由LADMAP進行求解，式（9）的拉格朗日函數為：

其中

Y1,Y2,Y3是拉格朗日乘子，μ＞0是參數。

更新Z，固定C,J,E,Y1,Y2,Y3：

其中S(?)為軟閾值算子。更新J，固定Z,C,E：

由上式可知J有解析解：

更新E，固定Z,J,C：

由上式可知E有解析解：

更新拉格朗日乘子Y1,Y2,Y3。采用梯度下降的方法，即：

便于直觀的表述，算法1總結了LADMAP求解子問題Z的步驟。

算法1（LADMAP）

輸入：X,P0,λ,β,γ

輸出：Z

初始條件：Z=J=C=0,Y1=Y2=Y3=0,μ0=0.1,μmax=106,ρ=1.1,ε1=10-6,

循環執行以下操作：

1.用式（11）更新 Z ；

2.用式（12）更新C ；

3.用式（14）更新 J；

4.用式（16）更新 E ；

5.用式（17）更新Y1,Y2,Y3；

（2）分割矩陣Q的求解

在給定Z時，問題式（8）變為：

又因為：

因此上式變為：

由于式（21）非凸，因此松弛為：

最后利用譜聚類對上述問題進行求解。

便于更直觀顯示模型SGRLRSC的求解過程。算法2總結了模型求解的整個過程。子問題（1）是凸優化問題，求解步驟是特征選擇的過程，把表示系數Z作為特征向量來進行聚類。子問題（2）是凸松弛問題，求解步驟是譜聚類的過程。雖然上述兩個子問題在理論上不能保證收斂，但是在實驗中，選取一定參數，算法收斂。

算法2（SGRLRSC模型求解）

輸入：X,K,λ,β,γ

輸出：Q

初始條件：P0=0

循環執行以下操作：

1.當給定Q時，通過算法1求解問題式（9）得到Z；

2.給定Z時，通過譜聚類求解問題式（18）得到Q；

4 數值實驗

本文在常用的數據集CMU-PIE數據集[17]，COIL20數據集[18]以及MINIST數據集[19]來驗證SGRLRSC的聚類效果，并且與SSC、LRR、LSR、CASS、SMR以及SSSC方法進行比較，圖1給出了實驗數據集的樣本圖，最后，以錯誤率error=Nerror/Ntotal來評判上述所有方法的聚類性能。

圖1 實驗樣本圖

在實驗中，為了公平，上述所有方法的參數都選取能使聚類結果最好的那個值，并且每個數據庫都進行20次實驗，結果取其平均值。SGRLRSC中有三個參數，λ、β、γ。在參數調整過程中，首先選擇一個大的取值范圍，手動地調整三個參數多次進行實驗，使得聚類精度取得一個較好的結果，記下參數取值范圍，然后縮小范圍，通過固定其他參數的方式調整一個單獨參數，使得聚類效果達到最好，取對應的參數值，以此類推，得到全部最優的值。以CMU-PIE數據集的前30類為例，在參數調整過程中，發現當β=15，SGRLRSC會取得較好的聚類結果，固定 β ，當 λ∈[0.1,0.5]，γ∈[10,20]，聚類誤差相對較小，在實驗中，不斷地調整參數，使其取得最好的聚類結果。圖2顯示了在CMU-PIE數據集的前30類上聚類誤差隨參數λ和參數γ的變化圖。從圖像上可以看出，當λ=0.2,γ=15時，CMU-PIE數據集聚類精度最高。

4.1 CMU-PIE數據集

圖2 在CMU-PIE數據集的前30類上聚類誤差隨參數λ和參數γ的變化圖

該數據集包含13個不同的姿勢，403個不同的照明條件和四種不同表情的41 368張68個人的人臉圖像，每張圖像像素大小為32×32。圖1中的（a）給出了樣本圖。在實驗中，為了節省空間，僅選取每個人的21張圖片，構建了30、40、60和68類的四個子空間。大量測試實驗表明，當λ=0.2,β=15,γ=15時，聚類精度最高。表1顯示了各種方法在CMU-PIE數據集的聚類結果，對于不同類，選擇一樣的參數。從表中可以看出，SGRLRSC方法始終優于其他方法。便于更清楚地對比各個方法的聚類性能，圖3給出了各種方法在30、40、60和68類的四個子空間上的聚類錯誤率曲線圖，從曲線圖上可以看出隨著類別數目增多，SGRLRSC方法的聚類性能慢慢退化。

表1 在CMU-PIE數據集上的聚類錯誤率 %

圖3 聚類錯誤率隨CMU-PIE數據集數目增多的變化圖

為了進一步說明SGRLRSC模型的作用，圖4顯示了在不同錯誤率下，相似度矩陣A，自表示矩陣Z，相似度矩陣A的最小的三個特征值所對應的特征向量(Qˉ)以及連接矩陣P。為了可視化，都取其絕對值并且乘以800。由圖可知，隨著錯誤率變低，相似度矩陣A越來越接近塊對角矩陣，表示矩陣Z與分割矩陣Q也變得越來越一致。

4.2 COIL20數據集

圖4 SGRLRSC方法中矩陣A、Z、向量及矩陣P在不同錯誤率下的可視化圖

COIL20數據集是由20個物體在不同角度下構成的1 440張灰度圖像，圖1（b）給出了實驗樣本圖。每個物體只選取前50張圖片作為樣本，在實驗中，將每張圖片像素32×32向量化后，利用主成分分析（PCA）[20]降維成60維。大量實驗結果表明，當 λ=0.5,β=15,γ=0.1，SGRLRSC的聚類效果最好，表2給出了SGRLRSC方法在COIL20數據集的聚類精度，由表2可知SGRLRSC方法的聚類性最好。

4.3 MINIST數據集

MINIST數據集是一個在子空間聚類中經常會用到的包含數字0～9的10類手寫字體數據集。每個圖片的分辨率大小為28×28，對應于784維向量。圖1（c）給出了實驗樣本。在實驗中選取50個樣本作為數據集，并且將每個樣本投影成60維。在實驗中，取λ=0.05,β=90,γ=1.9，SGRLRSC的聚類效果最好。實驗結果如表3，由表3可知SGRLRSC方法提高了聚類精度，并優于其他算法。

表2 COIL20數據集的聚類誤差率 %

表3 MINIST數據集的聚類誤差率 %

表4 不同求解算法在各個數據庫的運行時間 s

最后為了證明使用LADMAP方法求解模型在本文中可以提高運算效率，表4給出了不同求解算法在各個數據庫的運行時間，由表4可知使用LAD MAP方法求解可以提高運算效率。

5 結束語

本文在子空間結構范數的基礎上，引入分組效應和低秩表示，給出了一種新的子空間聚類模型，其優點是該模型不但利用了學習相似度和聚類結果的統一，而且還可以同時捕獲數據的全局結構與內在幾何結構。自適應懲罰的線性化交替法也被引入來尋找模型的最優解。大量實驗表明本文提出的方法優于其他子空間聚類算法。