結(jié)構(gòu)圖正則低秩子空間聚類

劉 婕，馬 帥

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安 710126

1 引言

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

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

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

2 結(jié)構(gòu)圖正則低秩子空間聚類

2.1 相關(guān)工作

在基于譜聚類的方法中，假設(shè)每一個(gè)樣本點(diǎn)都可以用來自同一個(gè)子空間的樣本點(diǎn)線性表示，即X=XZ，其中Z為表示系數(shù)矩陣，當(dāng)有噪聲時(shí)，表示為X=XZ+E，其中E為噪聲。通?；谧V聚類的方法統(tǒng)一可以寫為以下形式：

2.2 SGRLRSC模型

本文在子空間結(jié)構(gòu)范數(shù)上，增加了低秩表示，在集群內(nèi)部定義了分組效應(yīng)作為正則項(xiàng)，給出了一個(gè)新的統(tǒng)一優(yōu)化模型，稱為結(jié)構(gòu)圖正則低秩子空間聚類。

首先，為了能夠充分利用數(shù)據(jù)相似度與分割的依賴事實(shí)，獲得一個(gè)聯(lián)合學(xué)習(xí)相似度矩陣與聚類結(jié)果的統(tǒng)一框架，本文通過最小化‖Z‖Q來懲罰表示系數(shù)矩陣與分割矩陣的不一致性?！琙‖Q有效地結(jié)合了數(shù)據(jù)相似度矩陣與聚類結(jié)果，在迭代過程中，使得表示系數(shù)矩陣Z與分割矩陣Q變得一致。

其次，好的相似度矩陣會(huì)使得聚類結(jié)果更加魯棒。對于相似度矩陣的連接性來說，希望模型能夠自動(dòng)地把相關(guān)性高的數(shù)據(jù)聚集在一起，即，同一子空間的數(shù)據(jù)點(diǎn)之間的連接性應(yīng)該為1，不同空間的數(shù)據(jù)點(diǎn)之間的連接性應(yīng)該為0。為此，本文定義了分組效應(yīng)：

由定義可知，最大化cos

其中wij用來度量數(shù)據(jù)點(diǎn)xi與數(shù)據(jù)點(diǎn)xj的空間距離，如果，那么上式可等價(jià)于：

最后，SSSC模型中l(wèi)0-范數(shù)單獨(dú)尋找每個(gè)數(shù)據(jù)的稀疏表示，缺乏對表示系數(shù)的全局約束，由于低秩表示能從全局對子空間表示進(jìn)行處理，因此本文對所有數(shù)據(jù)進(jìn)行了低秩表示，來捕獲數(shù)據(jù)的全局結(jié)構(gòu)。綜上所述，本文提出的模型為：

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

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

等價(jià)于

因此模型（5）等價(jià)于：

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

3 模型求解

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

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

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

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

（1）表示系數(shù)矩陣Z的求解

給定Q，式（8）等價(jià)于：

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

其中

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

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

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

由上式可知J有解析解：

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

由上式可知E有解析解：

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

便于直觀的表述，算法1總結(jié)了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,

循環(huán)執(zhí)行以下操作：

1.用式（11）更新 Z ；

2.用式（12）更新C ；

3.用式（14）更新 J；

4.用式（16）更新 E ；

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

（2）分割矩陣Q的求解

在給定Z時(shí)，問題式（8）變?yōu)椋?/p>

又因?yàn)椋?/p>

因此上式變?yōu)椋?/p>

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

最后利用譜聚類對上述問題進(jìn)行求解。

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

算法2（SGRLRSC模型求解）

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

輸出：Q

初始條件：P0=0

循環(huán)執(zhí)行以下操作：

1.當(dāng)給定Q時(shí)，通過算法1求解問題式（9）得到Z；

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

4 數(shù)值實(shí)驗(yàn)

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

圖1 實(shí)驗(yàn)樣本圖

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

4.1 CMU-PIE數(shù)據(jù)集

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

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

表1 在CMU-PIE數(shù)據(jù)集上的聚類錯(cuò)誤率 %

圖3 聚類錯(cuò)誤率隨CMU-PIE數(shù)據(jù)集數(shù)目增多的變化圖

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

4.2 COIL20數(shù)據(jù)集

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

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

4.3 MINIST數(shù)據(jù)集

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

表2 COIL20數(shù)據(jù)集的聚類誤差率 %

表3 MINIST數(shù)據(jù)集的聚類誤差率 %

表4 不同求解算法在各個(gè)數(shù)據(jù)庫的運(yùn)行時(shí)間 s

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

5 結(jié)束語

本文在子空間結(jié)構(gòu)范數(shù)的基礎(chǔ)上，引入分組效應(yīng)和低秩表示，給出了一種新的子空間聚類模型，其優(yōu)點(diǎn)是該模型不但利用了學(xué)習(xí)相似度和聚類結(jié)果的統(tǒng)一，而且還可以同時(shí)捕獲數(shù)據(jù)的全局結(jié)構(gòu)與內(nèi)在幾何結(jié)構(gòu)。自適應(yīng)懲罰的線性化交替法也被引入來尋找模型的最優(yōu)解。大量實(shí)驗(yàn)表明本文提出的方法優(yōu)于其他子空間聚類算法。