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

鄭 毅，馬盈倉，楊小飛，續秋霞

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

1 引言

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

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

圖1 子空間聚類數據示意圖

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

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

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

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

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

2 相關工作

2.1 稀疏子空間基礎模型

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

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

2.2 仿射矩陣基本約束

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

圖2 線性表示圖示

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

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

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

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

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

圖4 雙月數據集聚類結果示意圖

圖5 螺旋數據集聚類結果示意圖

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

3 模型建立及求解

3.1 模型建立

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

3.2 模型求解

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

此時，原問題（3）中的參數λ0不用調節，這說明該模型本身就自帶稀疏性。而參數λ1實質上在模型中調節著仿射矩陣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）只相差一個恒值常數。

3.2.2 問題（8）的求解

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

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

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

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

（2）更新迭代φ

由式（14），可以得到：

同理，根據KKT條件（11）～（13），結合式（16），可得：

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

k-LS3C算法偽代碼如下：

輸入：數據集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及拉格朗日參數γ、φ

7.while不收斂do

9.固定φ，求解γ?=

14.更新：t=t+1

15.endwhile

16.計算αi(idx)=

17.end for

4 實驗

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

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

4.1 評價指標

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

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

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

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

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

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

4.2 人造數據集

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

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

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

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

圖6 k-LS3C對雙月形及螺旋形數據集聚類結果

圖7 雙月形數據集鄰接圖

圖8 螺旋形數據集鄰接圖

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

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

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

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

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

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

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

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

4.3 隨機獨立子空間

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

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

4.4 人臉數據庫聚類

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

圖14 圖像數據集部分樣本圖像示例

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

4.5 真實數據集

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

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

表1 真實數據集描述

表2 不同算法在各數據集下的Acc比較

表3 不同算法在各數據集下的NMI比較

表4 不同算法在各數據集下的RI比較

4.6 含噪數據集

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

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

圖16 子空間數據集示意圖

圖17 含噪子空間數據集示意圖

5 結論和展望

圖18 k-LS3C對數據集的聚類結果

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