鄭 毅，馬盈倉，楊小飛，續(xù)秋霞

西安工程大學(xué) 理學(xué)院，西安710600

1 引言

隨著信息時代的蓬勃發(fā)展，對數(shù)據(jù)進行合理有效的分析和處理成為當(dāng)代科學(xué)研究領(lǐng)域越來越重要的課題。但現(xiàn)今的數(shù)據(jù)數(shù)量大、維度高，而且結(jié)構(gòu)也越來越復(fù)雜，使得相關(guān)研究面臨著很大的困難[1]。為此，人們提出了很多方法來解決這些問題，其中子空間聚類方法憑著其想法自然和假設(shè)合理的優(yōu)勢，受到人們的關(guān)注，并得到了深入的研究[2]。在過去幾年中，子空間聚類方法在機器學(xué)習(xí)[3]、圖像處理[4]、計算機視覺[5]以及系統(tǒng)辨識[6]等眾多領(lǐng)域都有著廣泛的應(yīng)用，并針對這些高維數(shù)據(jù)集取得了較為理想的結(jié)果[7]。

子空間聚類假設(shè)高維數(shù)據(jù)分布于多個低維子空間的并上，例如圖1[8]所示，其中的三維數(shù)據(jù)本質(zhì)上是由一個二維平面和兩條一維直線所組成。因此，在這一假設(shè)前提下，人們希望尋找出合理的子空間分割方案，以此來將數(shù)據(jù)分劃成不同的簇。經(jīng)過多年的發(fā)展和研究，人們已經(jīng)提出了很多子空間聚類方法，總體來說大致分為五類，分別是基于矩陣分解[9]、基于代數(shù)[10-11]、基于迭代[12-13]、基于統(tǒng)計[14-15]以及基于譜聚類[16-17]。

圖1 子空間聚類數(shù)據(jù)示意圖

稀疏子空間聚類是基于譜聚類的一種子空間聚類方法，作為近些年來的一個研究熱點[18]，其主要思想是將每一個數(shù)據(jù)都表示為除自己以外的其他數(shù)據(jù)的線性組合，以此來挖掘數(shù)據(jù)在空間分布中的結(jié)構(gòu)信息。因此，核心問題在于求解出恰當(dāng)?shù)姆律渚仃?，并以此?gòu)造出相似度矩陣用于譜聚類[19]，得到最終的聚類結(jié)果。為了得到更加“恰當(dāng)”的仿射矩陣，獲得更好的聚類結(jié)果，通常在算法模型中對仿射矩陣A加上各種形式的限制和約束，迫使A具有理想結(jié)構(gòu)，這種理想結(jié)構(gòu)能夠幫助發(fā)現(xiàn)和挖掘數(shù)據(jù)背后的潛在信息，以利于聚類。

稀疏子空間聚類模型（Sparse Subspace Clustering，SSC）[20]對仿射矩陣A施加l1范數(shù)，使得仿射矩陣A具有稀疏性，這樣可從全局角度自動選擇近鄰點，消除冗雜數(shù)據(jù)間的相關(guān)性。低秩表達(dá)模型（Low Rank Representation，LRR）[21]對仿射矩陣A施加核范數(shù)，使得仿射矩陣A具有低秩性，能夠更好地捕獲數(shù)據(jù)的全局結(jié)構(gòu)，尤其當(dāng)存在損壞的數(shù)據(jù)時可以進行穩(wěn)健的子空間分割。最小二乘子空間聚類模型（Least Squares Regression，LSR）[22]對仿射矩陣A施加F范數(shù)，可以保持?jǐn)?shù)據(jù)的聚集性。基于二部圖的快速聚類模型（Fast Clustering Based on Bipartite Graph，F(xiàn)CBG）[23]通過對A的拉普拉斯矩陣LA施加秩約束，可以保持其類簇結(jié)構(gòu)?；赥L1范數(shù)約束的子空間聚類模型（Subspace Clustering Method Based on TL1Norm Constraints）[24]對仿射矩陣A施加TL1范數(shù)，使A具有稀疏性并具有塊對角結(jié)構(gòu)，并在含噪的情況下具有優(yōu)越的魯棒性。二次規(guī)劃子空間分割模型（Subspace Segmentation via Quadratic Programming，SSQP）[25]要求矩陣ATA稀疏且A正定，以獲得更理想的聚類結(jié)果。隱低秩表示（Latent Low Rank Representation，LatLRR）模型[26]，對列表示系數(shù)矩陣和行表示系數(shù)矩陣同時施加低秩約束，用行數(shù)據(jù)信息彌補列數(shù)據(jù)信息的污染或缺損，極大地提高了聚類性能。這些年來，人們又陸續(xù)提出了很多范數(shù)（如范數(shù)[27]，范數(shù)[28]等）來約束仿射矩陣，都是為了使仿射矩陣具有更加理想的結(jié)構(gòu)，以利于聚類。

然而，目前提出的大多數(shù)稀疏子空間聚類方法都存在兩個共同的弊端。第一，在模型中對仿射矩陣A直接施加的各種約束本質(zhì)上是面向全局的，這樣沒有充分利用數(shù)據(jù)在局部的有效信息，在對整體進行優(yōu)化的過程中忽略了對數(shù)據(jù)局部結(jié)構(gòu)的挖掘。第二，由于譜聚類是基于圖論的，使用時要求相似矩陣是對稱正定的，因此在求解出仿射矩陣A后，人們一般考慮直接用得到相似矩陣，但從最初和實質(zhì)看來，仿射矩陣的含義在于數(shù)據(jù)進行線性表示時能夠更好地貼合原數(shù)據(jù)，雖然在某種程度上間接反映了數(shù)據(jù)間的相似關(guān)系，但兩者在本質(zhì)上不完全等同。

為了克服上述兩個問題，本文提出一種基于k-近鄰與局部相似度約束的稀疏子空間聚類算法（Sparse Subspace Clustering Based on k-Nearest Neighbors and Local Similarity，k-LSSSC，k-LS3C）。首先，引入k-近鄰，可以有效利用數(shù)據(jù)點的局部信息，挖掘出數(shù)據(jù)的局部結(jié)構(gòu)。其次，從圖論中相似矩陣的構(gòu)造獲得啟發(fā)，利用數(shù)據(jù)點間的距離來輔助構(gòu)造仿射矩陣A。具體來說，當(dāng)xj與xi距離較小時，Aij的值應(yīng)較大，這樣最終得到的相似矩陣中對應(yīng)的值也相對較大。反之，當(dāng)xj與xi距離較大時，Aij的值應(yīng)較小，這樣最終得到的相似矩陣中對應(yīng)的值也相對較小。

值得說明的是，引入k-近鄰后不僅可以發(fā)揮數(shù)據(jù)在局部的作用，還可以剔除大量的不相關(guān)點，使得計算更為簡便。而且，由于考慮了k-近鄰，仿射矩陣只在部分元素上存在用于線性表示的非零值，這也進一步加強了仿射矩陣的稀疏性。此外，k的選取比較靈活，當(dāng)數(shù)據(jù)的線性相關(guān)性很強時，選擇適當(dāng)少的k值就能達(dá)到很好的效果。當(dāng)數(shù)據(jù)的噪聲較多時，選擇適當(dāng)大的k值還能夠使得算法更加魯棒，不易被“錯誤”的數(shù)據(jù)所影響[29]。

2 相關(guān)工作

2.1 稀疏子空間基礎(chǔ)模型

對一組由n個d維數(shù)據(jù)點組成的數(shù)據(jù)集X=(x1,x2,…,xn)∈Rd×n，假設(shè)它本質(zhì)上屬于c個線性子空間的并。在理想的情況下，子空間聚類將數(shù)據(jù)分割成不同的類別，每一個類別對應(yīng)其中的一個子空間，屬于同一子空間內(nèi)的數(shù)據(jù)點互相之間有著較強的線性關(guān)系。

為了避免平凡解，即數(shù)據(jù)點不用自身進行自我表示，常常令A(yù)ii=0。同時為了使得仿射矩陣具有稀疏性，對A施加l1范數(shù)，這樣就得到了目前子空間聚類領(lǐng)域最基礎(chǔ)的模型之一，如式（2）所示：

2.2 仿射矩陣基本約束

由于仿射矩陣最后需要轉(zhuǎn)化為相似矩陣，一般約定數(shù)據(jù)在進行線性表示時選取的系數(shù)為正值，因此約束?i,j,Ai,j≥0。同時由于數(shù)據(jù)被分割到每一個低維的子空間后，彼此之間非常容易出現(xiàn)很強的線性關(guān)系，為了簡化計算，約定A的列和為1，即每個數(shù)據(jù)點由其他數(shù)據(jù)線性表示的系數(shù)之和為1。把系數(shù)值進行歸一化約束到[0，1]區(qū)間后，可以有效處理一些特殊的情形。如圖2所示，在某一平面內(nèi)，x1可以用x2,x3,x4進行線性表示，如果不加任何限制，表示系數(shù)可以有很多種不同的組合選擇，例如可以表示為x1=0.25x2+0.25x3+0.50x4,也可為x1=5x2+5x3+10x4。此時，若加上列和為1的限制，能夠增強模型的穩(wěn)定性，同時把數(shù)據(jù)約束在比較均衡的范圍內(nèi)，方便計算。

圖2 線性表示圖示

2.3 稀疏子空間模型引入k-近鄰的合理性

前面提到，仿射矩陣的構(gòu)造應(yīng)該同時考慮數(shù)據(jù)的“整體”和“局部”，尤其當(dāng)數(shù)據(jù)分割到低維的子空間后，局部信息有著不可忽略的作用。數(shù)據(jù)在局部的一個重要信息就是k-近鄰，本節(jié)為了說明數(shù)據(jù)局部信息的重要性，同時也為了說明在稀疏子空間聚類研究中引入k-近鄰的合理性，設(shè)計如下實驗。

由于稀疏子空間聚類是基于譜聚類的，在一般的譜聚類中，用數(shù)據(jù)點之間的距離信息就可以構(gòu)造相似矩陣。本節(jié)分別面向數(shù)據(jù)全局構(gòu)造全連接矩陣，以及面向數(shù)據(jù)局部構(gòu)造k-近鄰矩陣，構(gòu)造時采用最常用的數(shù)據(jù)間歐式距離。此外，k-means同樣是基于數(shù)據(jù)點的距離信息，將距離當(dāng)作數(shù)據(jù)點與簇中心的相似度進行聚類。上述三種聚類方法運用到一些二維數(shù)據(jù)集，結(jié)果如圖3～圖5所示。

圖3是典型的基于中心的簇，屬于凸?fàn)顢?shù)據(jù)集。對于這種凸?fàn)顢?shù)據(jù)集，上述三種方法都能準(zhǔn)確聚類。但圖4所示的雙月數(shù)據(jù)集以及圖5所示的螺旋數(shù)據(jù)集均屬于非凸數(shù)據(jù)集，對于這種非凸數(shù)據(jù)集，k-means依然將數(shù)據(jù)聚成凸形簇，不能取得理想的結(jié)果。同樣的，由于在全連接矩陣聚類中，數(shù)據(jù)點和其余所有點都有權(quán)值相連，這意味著簇間的連接復(fù)雜，影響了最后的聚類性能。而在k-近鄰矩陣聚類中，一般近鄰的數(shù)據(jù)都屬于同一簇，最后得到的聚類效果更優(yōu)。

另外，對比全連接矩陣聚類結(jié)果與k-近鄰矩陣聚類結(jié)果，容易看出引入k-近鄰后，在聚類決策上剔除了大量不相關(guān)點的影響，無論數(shù)據(jù)的規(guī)模大小與形狀分布如何，每個數(shù)據(jù)點只考慮最近鄰的k個數(shù)據(jù)點信息，排除了大量無關(guān)干擾，顯然這是有利于聚類的。

圖4 雙月數(shù)據(jù)集聚類結(jié)果示意圖

圖5 螺旋數(shù)據(jù)集聚類結(jié)果示意圖

由此看來，k-近鄰的距離信息對非凸數(shù)據(jù)集的聚類有更大的參考意義，在稀疏子空間聚類的研究中，可以使仿射矩陣有更理想的結(jié)構(gòu)，有利于子空間分割。

3 模型建立及求解

3.1 模型建立

在前面的章節(jié)中，已經(jīng)介紹了稀疏子空間聚類的核心問題是構(gòu)造具有理想結(jié)構(gòu)的仿射矩陣。接下來，對于給定的數(shù)據(jù)集X=(x1,x2,…,xn)∈Rd×n，本文在式（2）的基礎(chǔ)上，根據(jù)前文所述，引入k-近鄰思想，并利用數(shù)據(jù)點間的距離來輔助構(gòu)造仿射矩陣A，得到本文的目標(biāo)函數(shù)模型：其中，λ0與λ1是兩個正則項參數(shù)，αi表示仿射矩陣A的第i列。目標(biāo)函數(shù)模型第一項‖ XA-X利用仿射矩陣從整體刻畫了數(shù)據(jù)系數(shù)表示的誤差；第二項從整體約束了仿射矩陣的稀疏性；而模型第三項

3.2 模型求解

值得注意的是，在目標(biāo)函數(shù)中存在約束條件Aij≥0與1,容易知道=1,因此是一個常數(shù)。所以問題（3）簡化成問題（4）：

此時，原問題（3）中的參數(shù)λ0不用調(diào)節(jié)，這說明該模型本身就自帶稀疏性。而參數(shù)λ1實質(zhì)上在模型中調(diào)節(jié)著仿射矩陣A在“整體約束”和“局部約束”間的平衡。

接下來，針對問題（4），對A的每一列分別進行獨立求解。由式（1），容易知道xi=Xαi=x1A1i+x2A2i+…+xiAii+…+xnAni，當(dāng)約束Aii=0以及=0時，不妨將下標(biāo){j|xj∈Nk(xi)}重新記作{s1,s2,…,sk}，其中sm≠i(m=1,2,…,k)。于是，式（1）可以重新表示為xi=xs1As1,i+xs2As2,i+…+xskAsk,i。

為了描述方便，定義X-i=(xs1,xs2,…,xsk)∈Rd×k,=(As1,i,As2,i,…,Ask,i)T∈Rk×1，顯 然 可 以 得 到 公 式另外定義鄰接矩陣W，其中，顯然鄰接矩陣W是一個對稱矩陣，即Wij=Wji，且主對角線元素Wii=0。同樣地，用Wi∈Rn×1表示鄰接矩陣W的第i列，用∈Rk×1表示W(wǎng)i中第s1,s2,…,sk個元素組成的列向量。因此：

由此，式（4）可以重新寫成問題（5）：

不難驗證，式（6）和式（7）只相差一個恒值常數(shù)。

3.2.2 問題（8）的求解

容易知道，問題（8）的拉格朗日函數(shù)形式為：

因此，問題（8）的求解思路分如下兩個步驟：

根據(jù)KKT條件（11）～（13），結(jié)合式（14）：

若ujt-1-＞0,由于φ?j≥0,則則φ?j=0，故

（2）更新迭代φ

由式（14），可以得到：

同理，根據(jù)KKT條件（11）～（13），結(jié)合式（16），可得：

值得說明的是，在算法過程中借用牛頓迭代法，因此顯然是收斂的。為了加快算法的收斂速度，本文引入加速系數(shù)ct+1=(1+，并更新輔助變量

k-LS3C算法偽代碼如下：

輸入：數(shù)據(jù)集X=(x1,x2,…,xn)∈Rd×n，k，λ1。

輸出：A=(α1,α2,…,αn)∈Rn×n。

1.初始化α1,α2,…,αn

2.計算鄰接矩陣Wij=

3.for i=1,2,…,n do

4.計算idx(i)={j|xj∈Nk(xi)}

5.計算X-i=X(idx(i)),W(i,idx(i)),定義=αi(idx)

6.初始化β0i=αi及拉格朗日參數(shù)γ、φ

7.while不收斂do

9.固定φ，求解γ?=

14.更新：t=t+1

15.endwhile

16.計算αi(idx)=

17.end for

4 實驗

為驗證本文提出的稀疏子空間聚類方法的有效性，本文選用經(jīng)典聚類方法k均值（k-means）、規(guī)范劃割（Normalized Cut，Ncut），以及經(jīng)典子空間聚類方法LRR、SR、CLR_W（文獻(xiàn)[31]中構(gòu)造仿射矩陣的方法），與本文提出的方法k-LS3C進行比較，并從聚類準(zhǔn)確率（Accuracy，Acc）、標(biāo)準(zhǔn)互信息（Normalized Mutual Information，NMI）、蘭德指數(shù)（Rand Index，RI）等多個角度對聚類性能進行評價。用于實驗的數(shù)據(jù)集有人造數(shù)據(jù)集、隨機生成的子空間數(shù)據(jù)集、圖像數(shù)據(jù)集以及真實數(shù)據(jù)集。其中，人造數(shù)據(jù)集選用了具有代表性的雙月形和螺旋形數(shù)據(jù)集，圖像數(shù)據(jù)集選取的是The Extended Yale Database B人臉數(shù)據(jù)庫里的部分?jǐn)?shù)據(jù)，真實數(shù)據(jù)集有iris、TOX-171、lung、australian以及crx數(shù)據(jù)集。

在參數(shù)設(shè)置方面，LRR、SR以及k-LS3C的正則參數(shù)λ取值為{0.000 1，0.001，0.01，0.05，0.1，1，10，100}；Ncut的σ取值為{0.001，0.01，0.1，1，10，100}；近鄰點個數(shù)k取3～10。每個算法運行10次，取結(jié)果的最大值進行比較。實驗相關(guān)環(huán)境為Microsoft Windows 7系統(tǒng)，處理器為Intel?CoreTMi5-3210 CPU@2.50 GHz，內(nèi)存4.00 GB，采用編程軟件Matlab R2015b。

4.1 評價指標(biāo)

Acc是聚類最常用的評價指標(biāo)，計算公式為：

其中，ri和si分別為聚類算法得到的類標(biāo)簽和數(shù)據(jù)真實的類標(biāo)簽；n為樣本個數(shù)；δ(x,y)是一個函數(shù)，當(dāng)x=y時δ(x,y)=1，否則δ(x,y)=0；map(ri)是一個排列匹配函數(shù)，將ri標(biāo)簽映射成與si匹配的等效標(biāo)簽。Acc的結(jié)果值在[0,1]之間，值越大越好。

NMI用于確定聚類的質(zhì)量，計算公式為：

其中，ni表示聚類算法得到的每一類Ri(1≤i≤c)包含的數(shù)據(jù)點的個數(shù)；n?j表示真實類別Sj(1≤j≤c)包含的數(shù)據(jù)點的個數(shù)；ni,j表示聚類算法結(jié)果Ri和真實類別Sj交集中包含的數(shù)據(jù)點的個數(shù)。NMI的結(jié)果值在[0,1]之間，值越大越好。

RI是一種用排列組合原理對聚類進行評價的方法，計算公式為：

其中，n為樣本個數(shù)；a表示在真實類別Si的數(shù)據(jù)也隸屬于聚類算法結(jié)果Ri的個數(shù)；d表示不在真實類別Si的數(shù)據(jù)也不屬于聚類算法結(jié)果Ri的個數(shù)。RI的結(jié)果值在[0,1]之間，值越大越好。

4.2 人造數(shù)據(jù)集

本節(jié)選用雙月形數(shù)據(jù)集和螺旋形數(shù)據(jù)集兩個具有代表性的人造數(shù)據(jù)集來說明k-LS3C的有效性，同時探究近鄰數(shù)k和正則化參數(shù)λ對聚類結(jié)果的影響。

雙月形數(shù)據(jù)集是一類典型的非線性數(shù)據(jù)，形狀像兩個彎月，彼此嵌入于凹部，如圖4（a）所示。由于雙月形數(shù)據(jù)這種特殊分布，很多聚類算法非常容易將中間嵌入的地方混聚成一類。

螺旋形數(shù)據(jù)集是聚類算法研究中常用的一個數(shù)據(jù)集，由分布在3條螺旋曲線上眾多數(shù)據(jù)點相互纏繞而成，如圖5（a）所示。螺旋形數(shù)據(jù)整體看上去就像一個高斯圓，數(shù)據(jù)的相互纏繞也給聚類分析提出了更高的要求，因此想要得到較好的聚類效果，必須要合理地挖掘出數(shù)據(jù)的內(nèi)部結(jié)構(gòu)。

k-LS3C方法對雙月形數(shù)據(jù)集和螺旋形數(shù)據(jù)集的聚類結(jié)果如圖6所示。k-LS3C方法學(xué)習(xí)的鄰接圖如圖7和圖8所示?？梢钥闯觯琸-LS3C方法對這兩類數(shù)據(jù)集的聚類均能達(dá)到100%的準(zhǔn)確率。實驗中k-LS3C方法的運行時間較短，說明k-LS3C利用局部線性的思想明顯提高了運算速度。

圖6 k-LS3C對雙月形及螺旋形數(shù)據(jù)集聚類結(jié)果

圖7 雙月形數(shù)據(jù)集鄰接圖

圖8 螺旋形數(shù)據(jù)集鄰接圖

圖9給出了k-LS3C在兩個數(shù)據(jù)集上的仿射矩陣圖，可以看出，k-LS3C得到的仿射矩陣有著良好的對角結(jié)構(gòu)，而且從仿射矩陣圖以及鄰接圖都可以看出，k-LS3C得到的仿射矩陣具有很好的稀疏性。這是因為模型中有‖ ‖A1項，同時由于Ai,j≥0，模型中的另一個正則項也可以看作是對仿射矩陣A再次施加了以為加權(quán)系數(shù)的l范數(shù)。l范數(shù)作11為l0范數(shù)的最優(yōu)凸近似，很好地保證了仿射矩陣具有稀疏性。不過，從l1范數(shù)的定義可知，‖ ‖A1保證的其實是所有元素的絕對值之和最小。此時，約束條件中=0顯然進一步加強了仿射矩陣的稀疏性。

圖9 k-LS3C學(xué)習(xí)的仿射矩陣

圖10～圖13展示了參數(shù)k和λ對實驗結(jié)果影響。圖10和圖11展示了鄰近點個數(shù)k的選取對聚類準(zhǔn)確率的影響。從實驗結(jié)果可以看出，鄰近點的個數(shù)k取得過小或者過大時，都會使得聚類的準(zhǔn)確率降低，一般取5～10時效果較好。圖12和圖13展示了參數(shù)λ對聚類準(zhǔn)確率的影響。從實驗結(jié)果可以看出，當(dāng)確定了合適的k值后，參數(shù)λ對聚類結(jié)果的影響不大。這是因為當(dāng)k值確定后，等效于從局部對模型進行了約束，此時從一定程度上代替了參數(shù)λ的調(diào)節(jié)功能。

圖10 雙月形數(shù)據(jù)集上k對聚類精度的影響(λ=1)

圖11 螺旋形數(shù)據(jù)集上k對聚類精度的影響(λ=1)

圖12 雙月形數(shù)據(jù)集上λ對聚類精度的影響(k=7)

圖13 螺旋形數(shù)據(jù)集上λ對聚類精度的影響(k=4)

因此，基于k-LS3C模型具備這樣的特點，在進行調(diào)參工作時，首先應(yīng)尋找合適的參數(shù)k。由于近鄰數(shù)k是整數(shù)，因此尋找起來難度不大，根據(jù)經(jīng)驗，一般在5～10之間尋找，可以根據(jù)數(shù)據(jù)集特點靈活調(diào)整。如果數(shù)據(jù)集分布較散，類簇間距離較開，參數(shù)k可以適當(dāng)選擇大點。如果數(shù)據(jù)集分布較密，類簇間距離較近，參數(shù)k可以適當(dāng)選擇小點。當(dāng)確定了合適的參數(shù)k后，再對參數(shù)λ進行調(diào)節(jié)，遵循一般的調(diào)參方式即可。總體來說還是比較容易能夠調(diào)到合適的參數(shù)，得到理想的聚類結(jié)果。

4.3 隨機獨立子空間

依照文獻(xiàn)[32]的方法，首先構(gòu)造5個相互獨立的線性子空間，其中5個基矩陣由Ui+1=TUi(i=1,2,3,4)生成，T表示一個隨機旋轉(zhuǎn)矩陣，U1∈R100×100是一個隨機列正交矩陣，因此每個子空間都是100維的。若每個子空間里面由Xi=UiCi產(chǎn)生20個樣本，則得到的數(shù)據(jù)矩陣是X=[X1,X2,X3,X4,X5]∈R100×100,其中C1∈R100×20為獨立同分布的標(biāo)準(zhǔn)高斯矩陣。

實驗結(jié)果表明，當(dāng)k取5到10的任意整數(shù)，λ取{0.001，0.005，0.01，0.05，0.1，0.5，1}中的任意參數(shù)時，k-LS3C算法的準(zhǔn)確率均為100%。

4.4 人臉數(shù)據(jù)庫聚類

The Extended Yale Database B人臉數(shù)據(jù)庫，其包含了38個人的2 414張人臉前額圖像，每一個人都有59～64張在不同的實驗室可控光照條件下的人臉圖像，部分人臉圖像被嚴(yán)重的“陰影”污染。如圖14所示。每幅人臉灰度圖像的分辨率大小是192×168，為減小算法的計算時間和存儲空間，首先將所有圖像的分辨率重新調(diào)整為32×32，并將像素值規(guī)范化到[0,1]區(qū)間。

圖14 圖像數(shù)據(jù)集部分樣本圖像示例

本文使用The Extended Yale Database B數(shù)據(jù)庫中的前20類的人臉圖像，選取每類中的10張圖像，總共200張。本文模型中沒有考慮誤差，因此盡量選用噪聲比較少的圖像來進行實驗。把每張圖像轉(zhuǎn)換為1 024維行向量，形成數(shù)據(jù)矩陣X∈R200×1024。k-LS3C對該數(shù)據(jù)集的聚類結(jié)果如圖15所示。

4.5 真實數(shù)據(jù)集

本文采用5個常用的UCI真實數(shù)據(jù)集進行實驗，分別是iris、TOX-171、lung、Australian以及crx數(shù)據(jù)集，數(shù)據(jù)集的描述如表1所示。表2～表4分別采用Acc、NMI以及RI指標(biāo)評價了不同算法在這些數(shù)據(jù)集上的聚類結(jié)果。表中，數(shù)據(jù)加粗代表算法性能最優(yōu)，數(shù)據(jù)加下劃線代表算法性能次優(yōu)。

可以看出，本文提出的k-LS3C算法具有良好的聚類結(jié)果，在實驗的5個數(shù)據(jù)集以及3種評價指標(biāo)上，基本都表現(xiàn)出比k-means、Ncut、CLR_W、LRR以及SR更優(yōu)的性能。這主要是因為k-LS3C構(gòu)造的仿射矩陣更加合理，從整體和局部兩個角度綜合考慮，能夠?qū)ふ页鰯?shù)據(jù)的潛在結(jié)構(gòu)，得到更好的子空間劃分。

表1 真實數(shù)據(jù)集描述

表2 不同算法在各數(shù)據(jù)集下的Acc比較

表3 不同算法在各數(shù)據(jù)集下的NMI比較

表4 不同算法在各數(shù)據(jù)集下的RI比較

4.6 含噪數(shù)據(jù)集

圖15 k-LS3C對圖像數(shù)據(jù)集的聚類結(jié)果(Acc=90.88%)

為了測驗k-LS3C算法對含噪數(shù)據(jù)集的魯棒性，構(gòu)造子空間的典型數(shù)據(jù)集，如圖16所示。該三維數(shù)據(jù)集由一個二維平面和一條一維直線所組成，由圖16（b）可以看出，數(shù)據(jù)點處于完全的平面或直線內(nèi)。k-LS3C算法對其聚類結(jié)果如圖18（a）所示，聚類準(zhǔn)確率為100%。但由于現(xiàn)實生活中，數(shù)據(jù)會含有些許噪聲，可能呈現(xiàn)如圖17所示的樣子。圖17（b）顯示數(shù)據(jù)點不完全處于平面或直線內(nèi)，此時k-LS3C算法依然能準(zhǔn)確聚類，如圖18（b）所示。這是因為k-LS3C算法綜合考慮了數(shù)據(jù)分布的整體和局部，尤其是在引入k近鄰后，噪聲對數(shù)據(jù)點局部間的相似緊密-疏離關(guān)系影響不大，換而言之，即便存在少量噪聲，一般也不會影響到數(shù)據(jù)間的親疏關(guān)系。通過這樣的機制能夠加強模型的穩(wěn)定性，因此k-LS3C算法對含噪數(shù)據(jù)具備良好的魯棒性。

圖16 子空間數(shù)據(jù)集示意圖

圖17 含噪子空間數(shù)據(jù)集示意圖

5 結(jié)論和展望

圖18 k-LS3C對數(shù)據(jù)集的聚類結(jié)果

本文提出了一種全新的子空間聚類方法k-LS3C，在構(gòu)造仿射矩陣的過程中，引入了k-近鄰思想，并基于圖論知識設(shè)計了合適的正則項，不僅加強了數(shù)據(jù)局部信息的利用，也使仿射矩陣向相似矩陣的過渡更加合理自然。在多種數(shù)據(jù)集上與目前流行的稀疏子空間聚類算法進行了對比，結(jié)果證明本文算法能夠得到更優(yōu)的聚類結(jié)果。下一步，將繼續(xù)研究如何根據(jù)數(shù)據(jù)分布結(jié)構(gòu)自適應(yīng)地確定近鄰數(shù)k值。另外，在模型中對誤差進行更細(xì)致的考慮也是今后研究的一個方向。