結(jié)構(gòu)加權(quán)相關(guān)自適應(yīng)子空間聚類

李 丹

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

1 引言

隨著科學(xué)技術(shù)的快速發(fā)展，大規(guī)模高維數(shù)據(jù)在社會(huì)、經(jīng)濟(jì)、工程等領(lǐng)域越來越普遍。大規(guī)模高維數(shù)據(jù)不僅增加了數(shù)據(jù)存儲(chǔ)的需求，也使得數(shù)據(jù)分析更加復(fù)雜。子空間聚類[1]的目的是將來自不同子空間的高維數(shù)據(jù)分割到本質(zhì)上所屬的低維子空間，從而揭示高維數(shù)據(jù)的低維結(jié)構(gòu)，是處理高維數(shù)據(jù)強(qiáng)有力的工具。目前，基于譜聚類的子空間聚類方法是聚類分析的研究熱點(diǎn)。例如，稀疏子空間聚類（Sparse Subspace Clustering，SSC）[2]、基于低秩表示的子空間聚類（Low-Rank Representation，LRR）[3]、最小二乘子空間聚類（Least Squares Regression，LSR）[4]、光滑表示子空間聚類（Smooth Representation，SMR）[5]、相關(guān)自適應(yīng)子空間聚類（Correlation Adaptive Subspace Segmentation，CA-SS）[6]，還有圖像分割的改進(jìn)稀疏子空間聚類方法[7]、基于加權(quán)稀疏子空間聚類多特征融合圖像分割[8]、基于相關(guān)自適應(yīng)加權(quán)回歸的圖像分割（Correlation Adaptive Weighted Regression，CAWR）[9]以及基于L0 約束的稀疏子空間聚類[10]，上述這些方法分兩步解決子空間聚類問題，首先，從數(shù)據(jù)中學(xué)習(xí)自表示矩陣，并用自表示矩陣構(gòu)造相似度矩陣，第二步利用譜聚類算法獲得聚類結(jié)果。這種方法雖然取得了較好的聚類結(jié)果，但是沒有考慮數(shù)據(jù)相似性度和分割之間的關(guān)系。

Li 等[11]提出的結(jié)構(gòu)稀疏子空間聚類（Structured Sparse Subspace Clustering，SSSC）將上述兩步合為一步，利用相似度和分割之間的依賴關(guān)系，同時(shí)得到相似度矩陣和聚類結(jié)果。SSSC模型的聚類性能優(yōu)于上述的兩步法，但是SSSC只考慮了標(biāo)簽的一致性，忽略了數(shù)據(jù)相似度的一致性。

為了解決上述問題，同時(shí)獲得優(yōu)化的相似度矩陣和聚類結(jié)果，本文引入數(shù)據(jù)點(diǎn)的相關(guān)系數(shù)對(duì)表示系數(shù)施加顯式懲罰，當(dāng)數(shù)據(jù)相關(guān)性較弱時(shí)，對(duì)表示系數(shù)用1-范數(shù)正則，使得不相關(guān)數(shù)據(jù)分離；當(dāng)數(shù)據(jù)高度相關(guān)時(shí)，對(duì)表示系數(shù)用2-范數(shù)正則，使得相關(guān)數(shù)據(jù)聚集，保證了系數(shù)矩陣的稀疏性和一致性；同時(shí)引入子空間的結(jié)構(gòu)范數(shù)，充分利用了相似度矩陣和分割的依賴關(guān)系，將子空間表示形式表述為結(jié)構(gòu)加權(quán)相關(guān)自適應(yīng)子空間聚類（SWCASC）問題。實(shí)驗(yàn)結(jié)果表明，在常用數(shù)據(jù)集上，提出的方法優(yōu)于其他的子空間聚類方法。

2 相關(guān)工作

定義1（子空間聚類）給定一組數(shù)，記作X=(x1,x2,…,xN)∈Rd×N，設(shè)這組數(shù)據(jù)屬于k個(gè)線性子空間的并。子空間聚類是指將這組數(shù)據(jù)分割成不同的類，在理想情況下，每一類對(duì)應(yīng)一個(gè)子空間。

在子空間聚類方法中，假設(shè)每個(gè)數(shù)據(jù)點(diǎn)均可以用同一子空間的其他數(shù)據(jù)點(diǎn)線性表示，即X=XZ，其中Z=[z1,z2,…,zN]∈RN×N是X的自表示系數(shù)矩陣。考慮到實(shí)際數(shù)據(jù)可能有噪聲或者干擾，通常將數(shù)據(jù)表示為X=XZ+E，其中E表示噪聲或者干擾。

為了得到有利于揭示數(shù)據(jù)子空間屬性的自表示，已有方法對(duì)自表示矩陣采用不同的約束。稀疏子空間聚類（SSC）采用1-范數(shù)以獲得每個(gè)數(shù)據(jù)點(diǎn)xi的稀疏表示，模型如下：

其中第一項(xiàng)稱為數(shù)據(jù)擬合項(xiàng)，用于度量表示誤差或干擾；第二項(xiàng)稱為正則項(xiàng)，用于約束自表示矩陣的結(jié)構(gòu)；λ>0 是調(diào)節(jié)參數(shù)，平衡兩項(xiàng)的作用。當(dāng)子空間獨(dú)立且數(shù)據(jù)無噪聲干擾時(shí)，稀疏表示具有塊對(duì)角結(jié)構(gòu)。然而，如果來自同一子空間的數(shù)據(jù)高度相關(guān)，稀疏表示會(huì)隨機(jī)選擇少量相關(guān)數(shù)據(jù)，而忽略其他相關(guān)數(shù)據(jù)。因此，SSC 不能將高度相關(guān)數(shù)據(jù)很好地分組。LRR 采用核范數(shù)懲罰表示系數(shù)，模型如下：

當(dāng)數(shù)據(jù)是無噪聲且子空間獨(dú)立時(shí)，LRR也能保證自表示矩陣具有塊對(duì)角結(jié)構(gòu)，但是實(shí)際數(shù)據(jù)通常有噪聲或干擾，此時(shí)LRR通常將相關(guān)數(shù)據(jù)分組在一起，但無法將不相關(guān)數(shù)據(jù)分離。LSR用F-范數(shù)來懲罰表示系數(shù)，模型如下：

LSR 和LRR 一樣，將高度相關(guān)的數(shù)據(jù)分組在一起，但也缺乏稀疏性。

多特征融合加權(quán)稀疏子空間聚類用高斯函數(shù)定義相似度，對(duì)表示系數(shù)采用加權(quán)1-范數(shù)，模型如下：

該模型使相似的數(shù)據(jù)盡可能參與到數(shù)據(jù)的自表示中，從而改善稀疏表示過稀疏并且不穩(wěn)定的局限性。但是高斯權(quán)依賴于參數(shù)σ，從而影響模型性能。

WCAR采用加權(quán)的1-范數(shù)和2-范數(shù)懲罰表示系數(shù)，模型如下：

上述聚類方法都分兩步，首先學(xué)習(xí)自表示矩陣，并由此計(jì)算相似度矩陣；然后利用譜聚類算法獲得聚類結(jié)果。但這些方法沒有充分利用相似度和數(shù)據(jù)類別之間的關(guān)系。Li和Vidal提出了結(jié)構(gòu)稀疏子空間聚類（SSSC），充分利用了相似度和數(shù)據(jù)類別之間的關(guān)系，其模型如下：

3 結(jié)構(gòu)加權(quán)相關(guān)自適應(yīng)子空間聚類（SWCASC）

為了使相似度同時(shí)具有稀疏性和一致性，并考慮相似度和分割之間的依賴關(guān)系。本文依據(jù)數(shù)據(jù)點(diǎn)的相關(guān)性，對(duì)表示系數(shù)矩陣采用不同約束作為正則項(xiàng)，同時(shí)利用相似度與分割之間的關(guān)系，對(duì)表示系數(shù)矩陣采用結(jié)構(gòu)范數(shù)，提出了一個(gè)新的子空間表示優(yōu)化模型，稱為結(jié)構(gòu)加權(quán)相關(guān)自適應(yīng)子空間聚類模型。

其次，為了充分利用數(shù)據(jù)相似度與分割的依賴關(guān)系，本文通過最小化懲罰系數(shù)矩陣和分割矩陣，在求解過程中交替迭代求解Z和Q，同時(shí)得到學(xué)習(xí)系數(shù)矩陣和相似度矩陣。有效的結(jié)合了數(shù)據(jù)相似度和聚類結(jié)果，使得表示系數(shù)矩陣和分割矩陣變的一致。

3.1 SWCASC模型

假設(shè)數(shù)據(jù)被2-范數(shù)標(biāo)準(zhǔn)化，W?ΡN×N是數(shù)據(jù)點(diǎn)的相關(guān)系數(shù)矩陣，其中測(cè)量數(shù)據(jù)點(diǎn)xi和xj之間的相關(guān)性，稱為相關(guān)系數(shù)。提出的結(jié)構(gòu)加權(quán)相關(guān)自適應(yīng)子空間聚類模型如下：

其中，第一項(xiàng)是數(shù)據(jù)擬合項(xiàng)，第二項(xiàng)和第三項(xiàng)是正則項(xiàng)，分別為加權(quán)的顯式相關(guān)系數(shù)懲罰1-范數(shù)和2-范數(shù)。第四項(xiàng)是結(jié)構(gòu)范數(shù)，α>0,β>0 是調(diào)節(jié)參數(shù)。運(yùn)算符⊙代表Hadamarrd乘積（即對(duì)應(yīng)元素的乘積）。11T是所有元素都是1 的矩陣。一方面，當(dāng)給定Q時(shí)，若wij較大即接近1 時(shí)，該模型用2-范數(shù)使xi和xj分為一類，當(dāng)wij較小即接近0 時(shí)，該模型用1-范數(shù)的稀疏性使xi和xj分到不同類，確保了數(shù)據(jù)相似度的一致性和稀疏性。另一方面，當(dāng)給定Z時(shí)，若zij≠0 或xi和xj在同一子空間，模型迫使q(1)=q(j)，使得數(shù)據(jù)有相同標(biāo)簽。該模型可以看做結(jié)構(gòu)化加權(quán)的1-范數(shù)和2-范數(shù)自適應(yīng)插值，具有自適應(yīng)性。模型聯(lián)合標(biāo)簽和相似度矩陣，確保了相似度矩陣的一致性和稀疏性，以及標(biāo)簽的一致性。

對(duì)于數(shù)據(jù)點(diǎn)x，問題（6）可以表述為：

其中，c=(c1,c2,…,cN)T是x的表示系數(shù)。

3.2 模型的求解

模型是非凸優(yōu)化問題，不能直接進(jìn)行求解。為了得到最優(yōu)解，交替迭代求解模型。將上述問題分為兩個(gè)子問題求解：

（1）給定Q，用交替方向乘子法求解Z；

（2）給定Z，用譜聚類方法求解Q。

3.2.1表示系數(shù)矩陣Z的求解

為了書寫方便，令B=11T-W，問題（7）重寫為：

模型（9）等價(jià)于：

式（9）的增廣拉格朗日[12]函數(shù)為：

更新Z，固定S,J：

由上式可知Z有解析解：

更新J，固定Z,S：

J可以通過軟閾值算子得到：

更新S，固定Z,J：

式（15）為凸優(yōu)化問題，可以通過直接求導(dǎo)得到S的解：

詳細(xì)求解Z的步驟如下。

算法1 用ADMM解問題（6）

輸入：數(shù)據(jù)矩陣X，模型參數(shù)α,β,γ。

初始條件：

輸出：最優(yōu)系數(shù)矩陣Z。

循環(huán)執(zhí)行以下步驟：

1.固定其他，用式(13)更新Z；

2.固定其他，用式(15)更新J；

3.固定其他，用式(17)更新S；

4.更新拉格朗日乘子Y1,Y2,：

5.更新參數(shù)μ，μt+1=min(μmax,ρμt)。

6.迭代終止條件

7.t=t+1

結(jié)束

3.2.2 矩陣Q的求解

給定Q，問題（6）轉(zhuǎn)化成以下形式：

因?yàn)椋?/p>

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

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

最后，使用譜聚類算法將數(shù)據(jù)分組。

算法2 概述了SWCASC 模型的求解過程。子問題（1）求解過程是特征選擇的過程，得到的系數(shù)矩陣Z作為特征向量進(jìn)行聚類；子問題（2）是凸松弛問題，求解過程是譜聚類的過程。雖然上述兩個(gè)子問題在理論上不能保證收斂，但是在實(shí)驗(yàn)中，當(dāng)選取合適的參數(shù)時(shí)，算法收斂。

算法2 SWCASC模型求解

輸入：數(shù)據(jù)矩陣X，參數(shù)α,β,γ。

輸出：Q。

初始條件：P0=0

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

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

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

4 實(shí)驗(yàn)結(jié)果

本章展示了SWCASC模型在一些常用數(shù)據(jù)庫上的聚類性能，包括Extended YaleB數(shù)據(jù)庫[14]、MINIST數(shù)據(jù)庫[15]、COIL20數(shù)據(jù)庫[16]。將所提出的算法與現(xiàn)有的SSC、LRR、LSR、CASS、SSSC 方法進(jìn)行比較，通過聚類精度acc=Nacc/Ntotal來評(píng)價(jià)所有方法的聚類性能。其中Nacc表示分類正確的數(shù)據(jù)樣本的個(gè)數(shù)，Ntotal表示數(shù)據(jù)樣本的總個(gè)數(shù)。圖1給出了3個(gè)數(shù)據(jù)集的實(shí)驗(yàn)樣本圖。

在實(shí)驗(yàn)中，為了公平起見，上述所有方法的參數(shù)都選取聚類效果最好的那個(gè)值。并且每個(gè)數(shù)據(jù)庫都進(jìn)行20次實(shí)驗(yàn)，結(jié)果取平均值。SWCASC模型中有3個(gè)參數(shù)α、β、γ。在參數(shù)調(diào)整過程中，先給參數(shù)選取一定的范圍，然后手動(dòng)調(diào)整參數(shù)進(jìn)行實(shí)驗(yàn)，觀測(cè)聚類精度比較好的參數(shù)范圍并記錄下來。然后，固定兩個(gè)參數(shù)調(diào)整第三個(gè)參數(shù)，使聚類效果達(dá)到最好，記錄對(duì)應(yīng)的參數(shù)值。以此類推，得到所有最優(yōu)參數(shù)值。當(dāng)γ=0.5 時(shí)，圖2 顯示了在Extended YaleB 數(shù)據(jù)集的前10 類上聚類精度隨參數(shù)α和β的變化圖。由于可看出當(dāng)α=0.01,β=0.1 時(shí)，聚類精度最高。

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

圖2 在前10類上聚類精度隨參數(shù)α 和β 的變化圖

4.1 Extended Yale B數(shù)據(jù)集

Extended Yale B 是一個(gè)人臉數(shù)據(jù)集，由38 個(gè)在不同姿勢(shì)和光照下的2 414 張正面人臉圖像組成，每個(gè)人大約有64張正面人臉圖像，每張圖像有192×168個(gè)像素點(diǎn)。對(duì)于子空間聚類任務(wù)，每個(gè)對(duì)象對(duì)應(yīng)一個(gè)子空間，每個(gè)子空間有64 個(gè)數(shù)據(jù)點(diǎn)。通過對(duì)該數(shù)據(jù)庫的5 個(gè)、8個(gè)和10個(gè)人面部圖像進(jìn)行聚類，構(gòu)建了3個(gè)子空間聚類任務(wù)。大量實(shí)驗(yàn)表明，當(dāng)α=0.01,β=0.1,γ=0.5 時(shí)，聚類效果最好。

表1 給出在不同類別下，各種方法在Extended Yale B 數(shù)據(jù)集上的聚類精度的平均值、中值和標(biāo)準(zhǔn)差；圖2 在Extended YaleB 數(shù)據(jù)集前10 類上聚類精度隨參數(shù)α和β的變化圖。

表1 Extended Yale B數(shù)據(jù)集的聚類精度 %

從表1 中可看出SWCASC 模型的平均聚類精度最高，表明SWCASC 模型比其他方法更好。為了更直觀地比較各方法在Extended Yale B數(shù)據(jù)集上的聚類性能，圖3 給出了各種方法在5 類、8 類和10 類上的聚類精曲線圖。從圖3 中可看出SWCASC 方法的聚類精度明顯高度其他方法，而且隨著類別的增加，其他方法的聚類精度下降很快，而SWCASC方法下降較為緩慢。

圖3 各方法聚類精度隨Extended YaleB數(shù)目增多的變化圖

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

MINIST 是包含數(shù)字 0～9 的 10 類手寫數(shù)字?jǐn)?shù)據(jù)集，每個(gè)圖像有28×28個(gè)像素，重新排列成784維向量，圖1（b）給出了實(shí)驗(yàn)樣本圖。在實(shí)驗(yàn)中，選擇數(shù)據(jù)庫前50個(gè)樣本進(jìn)行實(shí)驗(yàn)然后投影成60 維向量，分析了分割精度。當(dāng)α=0.1,β=10,γ=0.5 時(shí)，本文的方法聚類精度達(dá)到78.1%，明顯高于其他方法的性能。表2 給出了各方法的聚類精度。

表2 MINIST數(shù)據(jù)集的聚類精度 %

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

COIL20 數(shù)據(jù)集由20 個(gè)物體在不同角度下的1 440張灰度圖像構(gòu)成，圖1（c）給出了COIL20 數(shù)據(jù)集的部分樣本圖。實(shí)驗(yàn)中為了減少計(jì)算代價(jià)，每圖伸縮為32×32后向量化為2 014 維向量，并用主成分分析（PCA）[16]降到60維。同時(shí)實(shí)驗(yàn)時(shí)只采用每個(gè)物體的前50張作為樣本。大量實(shí)驗(yàn)結(jié)果表明，當(dāng)α=0.01,β=0.1,γ=0.6 時(shí)，SWCASC聚類效果最好。表3給出了各方法在COIL20數(shù)據(jù)集上的聚類精度，由表可知，本文方法明顯優(yōu)于其他方法。

表3 COIL20數(shù)據(jù)集的聚類精度 %

5 結(jié)論

本文用數(shù)據(jù)點(diǎn)的相關(guān)系數(shù)對(duì)表示系數(shù)施加顯式懲罰，采有1-范數(shù)和2-范數(shù)自適應(yīng)加權(quán)，同時(shí)利用相似度與分割之間的關(guān)系，對(duì)表示系數(shù)矩陣采用結(jié)構(gòu)范數(shù)，將子空間表示形式表述為結(jié)構(gòu)加權(quán)相關(guān)自適應(yīng)子空間聚類（SWCASC）問題。這種方法充分考慮了不相關(guān)數(shù)據(jù)的良好子空間選擇能力和高度相關(guān)數(shù)據(jù)的分組能力，同時(shí)利用數(shù)據(jù)相似度與分割的依賴關(guān)系，使相似度矩陣同時(shí)具有類間稀疏性和類內(nèi)一致性。實(shí)驗(yàn)結(jié)果表明，在常用數(shù)據(jù)集上，本文提出的方法優(yōu)于其他的子空間聚類算法。