基于k-近鄰與局部相似度的稀疏子空間聚類

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

西安工程大學 理學院，西安710600

1 引言

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

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

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

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

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

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

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

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

2 相關工作

2.1 稀疏子空間基礎模型

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

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

2.2 仿射矩陣基本約束

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

圖2 線性表示圖示

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

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

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

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

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

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

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

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

3 模型建立及求解

3.1 模型建立

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

3.2 模型求解

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

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

接下來，針對問題（4），對A的每一列分別進行獨立求解。由式（1），容易知道xi=Xαi=x1A1i+x2A2i+…+xiAii+…+xnAni，當約束Aii=0以及=0時，不妨將下標{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表示Wi中第s1,s2,…,sk個元素組成的列向量。因此：

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

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

3.2.2 問題（8）的求解

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

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

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

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

（2）更新迭代φ

由式（14），可以得到：

同理，根據(jù)KKT條件（11）～（13），結合式（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 實驗

為驗證本文提出的稀疏子空間聚類方法的有效性，本文選用經典聚類方法k均值（k-means）、規(guī)范劃割（Normalized Cut，Ncut），以及經典子空間聚類方法LRR、SR、CLR_W（文獻[31]中構造仿射矩陣的方法），與本文提出的方法k-LS3C進行比較，并從聚類準確率（Accuracy，Acc）、標準互信息（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ù)庫里的部分數(shù)據(jù)，真實數(shù)據(jù)集有iris、TOX-171、lung、australian以及crx數(shù)據(jù)集。

在參數(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次，取結果的最大值進行比較。實驗相關環(huán)境為Microsoft Windows 7系統(tǒng)，處理器為Intel?CoreTMi5-3210 CPU@2.50 GHz，內存4.00 GB，采用編程軟件Matlab R2015b。

4.1 評價指標

Acc是聚類最常用的評價指標，計算公式為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 k-LS3C學習的仿射矩陣

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

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

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

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

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

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

4.3 隨機獨立子空間

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

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

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

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

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

本文使用The Extended Yale Database B數(shù)據(jù)庫中的前20類的人臉圖像，選取每類中的10張圖像，總共200張。本文模型中沒有考慮誤差，因此盡量選用噪聲比較少的圖像來進行實驗。把每張圖像轉換為1 024維行向量，形成數(shù)據(jù)矩陣X∈R200×1024。k-LS3C對該數(shù)據(jù)集的聚類結果如圖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指標評價了不同算法在這些數(shù)據(jù)集上的聚類結果。表中，數(shù)據(jù)加粗代表算法性能最優(yōu)，數(shù)據(jù)加下劃線代表算法性能次優(yōu)。

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

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

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

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

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

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

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

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

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

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

5 結論和展望

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

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