涂志輝，陳 龍，張子長，朱雪芳，胡文玉

(贛南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 贛州 341000)

1 引言

近年來，隨著互聯(lián)網(wǎng)發(fā)展迅速，數(shù)據(jù)收集變得越來越容易，最直接的結(jié)果是導(dǎo)致數(shù)據(jù)集變得越來越龐大和復(fù)雜，且這些數(shù)據(jù)通常由多種高維模式產(chǎn)生.然而，觀測到的高維數(shù)據(jù)集通常源自于多個(gè)低維子空間的聯(lián)合分布.因此需要一種能夠查找多個(gè)低維子空間，并同時(shí)將數(shù)據(jù)聚類到不同子空間的技術(shù).上述問題稱為子空間聚類(Subspace Clustering, SC)，近年來備受關(guān)注，已經(jīng)廣泛應(yīng)用于圖像處理和計(jì)算機(jī)視覺等實(shí)際問題.

在最近的20年，許多子空間聚類方法被提出，包括迭代方法、代數(shù)方法、統(tǒng)計(jì)方法和譜聚類方法[1].其中，基于譜聚類的方法在處理實(shí)際數(shù)據(jù)時(shí)顯示出了優(yōu)越性.基于譜聚類的方法包括2個(gè)主要步驟：首先找到一個(gè)能刻畫數(shù)據(jù)間拓?fù)潢P(guān)系的關(guān)聯(lián)矩陣，然后基于該關(guān)聯(lián)矩陣?yán)镁垲惙椒▽?shù)據(jù)劃分到不同的子空間中.假若數(shù)據(jù)滿足自表達(dá)性，即原始數(shù)據(jù)中每一個(gè)樣本能由其余樣本線性表示，譜聚類的一般模型可以表述為：

(1)

其中X表示原始數(shù)據(jù)矩陣，Z表示系數(shù)(關(guān)聯(lián))矩陣，φ(·)和δ(·)分別表示數(shù)據(jù)擬合項(xiàng)和正則項(xiàng)，Δ為系數(shù)矩陣Z的約束條件，λ為正則項(xiàng)的參數(shù).

譜聚類方法成功的關(guān)鍵在于關(guān)聯(lián)矩陣Z的構(gòu)建，常見方法有稀疏子空間聚類方法(SparseSubspaceClustering,SSC)[1]，低秩表示方法(LowRankRepresentation,LRR)[2]和自適應(yīng)子空間分割方法(CorrelationAdaptiveSubspaceSegmentation,CASS)[3].其中SSC方法使用l1范數(shù)針對每個(gè)點(diǎn)找最稀疏的表示，LRR方法使用核范數(shù)去找低秩的關(guān)聯(lián)矩陣，而CASS自適應(yīng)考慮了數(shù)據(jù)間的相關(guān)性.然而，實(shí)際數(shù)據(jù)往往受到噪聲的污染，并且噪聲的統(tǒng)計(jì)分布十分復(fù)雜.正如[4-5]所指出，如果不能有效地描述噪聲，系數(shù)矩陣將無法捕獲數(shù)據(jù)間的內(nèi)在拓?fù)潢P(guān)系，這將降低子空間聚類的性能.

為了解決這個(gè)問題，Lu等人[6]提出了通過cappedl1范數(shù)的魯棒子空間聚類算法去懲罰噪聲項(xiàng)，但該算法利用Frobenius范數(shù)作為矩陣秩的正則化，不能較好地逼近秩函數(shù).針對上述問題，本文提出聯(lián)合capped范數(shù)極小化的子空間聚類算法(JointCappedNormsMinimizationforSubspaceClusering,CNSC)，使用capped核范數(shù)代替Frobenius范數(shù)，使模型能較好地刻畫數(shù)據(jù)的低秩性，同時(shí)對數(shù)據(jù)噪聲和異常值魯棒.

2 相關(guān)工作

稀疏子空間聚類方法(SSC)[1]試圖尋找每個(gè)數(shù)據(jù)點(diǎn)的稀疏表示，其模型在數(shù)學(xué)上可表述為：

(2)

SSC方法的不足是SSC單獨(dú)尋找每個(gè)數(shù)據(jù)點(diǎn)的稀疏表示, 所得的矩陣Z可能過于稀疏，從而導(dǎo)致過度分割.

低秩表示方法(LRR)[2]目標(biāo)是共同尋求所有數(shù)據(jù)的最低秩表示，LRR模型的優(yōu)化模型表為：

(3)

Lu等人[7]提出最小二乘回歸方法(LeastSquaresRegression,LSR).該方法采用Frobenius范數(shù)來替代秩函數(shù)，所得模型是：

(4)

可以證明，當(dāng)數(shù)據(jù)來自獨(dú)立子空間且無噪聲時(shí)，SSC，LRR和LSR均可以得到塊對角型的系數(shù)矩陣Z.這些方法主要聚焦于關(guān)聯(lián)矩陣的構(gòu)造，而忽視了噪聲對聚類性能的影響.然而，真實(shí)數(shù)據(jù)總是會(huì)受到噪聲或異常值的污染，通過上述求解方案得到的關(guān)聯(lián)矩陣可能并不是塊對角的.

最近，Lu等人[6]利用cappedl1范數(shù)作為噪聲懲罰項(xiàng)，來提升聚類結(jié)果對噪聲的魯棒性.其優(yōu)化模型如下：

(5)

3 聯(lián)合capped范數(shù)的子空間聚類

首先介紹capped核范數(shù)的定義，然后給出聯(lián)合cappedl1范數(shù)和capped核范數(shù)的聚類模型和求解算法，最后給出算法的收斂性證明.

3.1 capped核范數(shù)定義

(6)

由定義可知，相比于核范數(shù)，capped核范數(shù)是秩函數(shù)更好的近似.這是因?yàn)椋寒?dāng)矩陣的最大奇異值不斷變大時(shí)，矩陣的秩始終保持不變，但是矩陣的核范數(shù)卻會(huì)隨之發(fā)生很大改變.另一方面，由于capped核范數(shù)僅僅最小化小于ε的奇異值，故而奇異值的極端變化不會(huì)改變，甚至仍保持capped核范數(shù)的值.

圖1給出了函數(shù)f(x)=min(|x|,ε)的函數(shù)圖像，其中取ε=1.如圖所示，f(x)在(-∞,-1)∪(1,+∞)區(qū)域上保持常值.可知，通過選擇合適的ε，capped核范數(shù)能減少矩陣大奇異值對子空間聚類性能的影響.

圖1 capped函數(shù)f(x)的函數(shù)圖像(ε=1)

3.2 子空間聚類模型

我們聯(lián)合矩陣的cappedl1范數(shù)與capped核范數(shù)建立如下的子空間聚類模型(CNSC)：

(7)

特別地，式(7)可以等價(jià)寫為：

(8)

其中n表示數(shù)據(jù)樣本的個(gè)數(shù)，xi∈Rd表示數(shù)據(jù)矩陣X的第i個(gè)樣本向量，zi表示關(guān)聯(lián)表示向量，r=min(d,n).從式(8)可以看出，當(dāng)ε1,ε2趨于無窮大時(shí)，目標(biāo)函數(shù)變成了LRR模型，說明LRR方法是本文的一個(gè)特例.

問題(8)的求解看似非常困難，因?yàn)槭?8)的兩項(xiàng)都是凹函數(shù).然而，受重加權(quán)(re-weighted)技巧的啟發(fā)[8]，這個(gè)問題能夠簡單地得以解決.首先，構(gòu)造輔助變量D、si，并且使用下列的規(guī)則依次更新si、D和Z：

(9)

(10)

(11)

其中Z=U∑VT表示矩陣Z的奇異值分解，U=[u1,u2,…,ud],V=[v1,v2,…,vn],∑=diag(σ1,σ2,…,σr),奇異值σi從小到大排列，假設(shè)小于ε2的奇異值個(gè)數(shù)為k.

為求解子問題(11)，我們將它分解成n個(gè)獨(dú)立的子問題.具體的計(jì)算過程如下：

(12)

(13)

(14)

3.3 求解算法

通過上述分析，問題(7)和(8)的最優(yōu)解可以通過迭代方法求得.我們將整個(gè)迭代過程描述成如下算法：

算法1聯(lián)合capped范數(shù)的子空間聚類(CNSC)算法

輸入 數(shù)據(jù)矩陣X，最大迭代數(shù)kmax，參數(shù)λ、ε1、ε2,k=1,Z0=單位矩陣；

輸出 系數(shù)矩陣Z.

Step 3 根據(jù)式(14)更新Zk；

Step 4 若k≥kmax或收斂，輸出結(jié)果；否則，k=k+1，轉(zhuǎn)至step 1.

3.4 收斂性證明

受文獻(xiàn)[10]啟發(fā)，本小節(jié)證明算法1的收斂性.為此，需要引入如下幾個(gè)引理：

引理1[9]對兩個(gè)任意給定的Hermitian矩陣A、B∈Rn×n，假設(shè)它們的特征值滿足λ1(A)≤λ2(A)≤…≤λn(A),λ1(B)≤λ2(B)≤…≤λn(B)，則

(15)

(16)

于是，我們有

其中第一個(gè)不等式利用了凹函數(shù)性質(zhì)，最后一個(gè)等式利用了特征值與矩陣跡的關(guān)系，而最后一個(gè)等式利用了引理1中式(15)的前半部分.移項(xiàng)即得式(16).

(17)

于是根據(jù)凹函數(shù)的性質(zhì)，可得

移項(xiàng)整理后，得式(17).

定理1通過算法1，目標(biāo)函數(shù)(8)隨著迭代的進(jìn)行而單調(diào)遞減，直到收斂.

由Dk-1的定義，上式可改寫為

(18)

也即

(19)

(20)

依次累加式(18)(19)和(20)的兩邊，從而得到：

最后，由于目標(biāo)函數(shù)(8)有下界0，故算法1必收斂.

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

將CNSC和3種經(jīng)典的聚類方法進(jìn)行對比，即稀疏子空間聚類方法(SSC)[1]、低秩表示子空間聚類方法(LRR)[2]，cappedl1范數(shù)子空間聚類算法(cappedl1)[6].實(shí)驗(yàn)中，使用準(zhǔn)確率(Accuracy，ACC)作為算法性能的衡量指標(biāo)：

(21)

其中ri表示xi的各類算法預(yù)測的聚類標(biāo)簽，li表示真實(shí)的聚類標(biāo)簽，n表示子空間數(shù)量.為了保證實(shí)驗(yàn)對比的公平性，所有算法都獨(dú)立進(jìn)行10次實(shí)驗(yàn)，比較各算法運(yùn)行結(jié)果的平均值.

根據(jù)式(8)，本文的算法需要調(diào)整3個(gè)參數(shù)ε1,ε2,λ.我們參照文獻(xiàn)[10]提到的方法進(jìn)行調(diào)整.

4.1 合成數(shù)據(jù)

表1 四種方法聚類效果比較(合成數(shù)據(jù))

由圖2可知，本文提出的算法在噪聲影響下仍可獲得清晰的分塊對角型系數(shù)矩陣，LRR和SSC方法都無法保持正確的塊對角結(jié)構(gòu).相比之下，cappedl1和本文提出的CNSC算法擁有良好的分塊對角特征，但是CNSC對角矩陣塊更稠密.

圖2 4種算法在合成數(shù)據(jù)上的關(guān)聯(lián)矩陣對角特征比較

4.2 人臉數(shù)據(jù)聚類

圖3 數(shù)據(jù)集部分例子

從表2和表3可以看出，在真實(shí)數(shù)據(jù)含有噪聲和異常值的情況下，本文提出的CNCS方法迭代步數(shù)少，精確度最高.說明本文提出的算法聚類性能較好且對異常值魯棒.

表2 4種方法在人臉集的聚類效果比較(5類)

表3 4種方法在人臉集的聚類效果比較(10類)

5 結(jié)束語

本文提出了一種聯(lián)合capped范數(shù)的子空間聚類算法(CNCS)，即分別使用cappedl1范數(shù)處理數(shù)據(jù)噪聲和異常值和capped核范數(shù)逼近數(shù)據(jù)的低秩性.而且，通過數(shù)值實(shí)驗(yàn)，說明了本文算法的優(yōu)越性.將來，我們將把本文算法推廣至?xí)r序數(shù)據(jù)的子空間聚類問題.