基于近鄰圖改進(jìn)的塊對(duì)角子空間聚類算法

王麗娟 ，陳少敏，尹 明，許躍穎，郝志峰，4，蔡瑞初，溫 雯

（1.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州 510006；2.廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，廣州 510006；3.北京師范大學(xué)珠海分校信息技術(shù)學(xué)院，廣東珠海 519000；4.佛山科學(xué)技術(shù)學(xué)院數(shù)學(xué)與大數(shù)據(jù)學(xué)院，廣東佛山 528000）

0 引言

高維數(shù)據(jù)聚類是圖像表示和壓縮［1］、基因表達(dá)分析［2］和計(jì)算機(jī)視覺(jué)領(lǐng)域［3］中重要的研究課題之一。高維數(shù)據(jù)聚類會(huì)導(dǎo)致嚴(yán)重的維度災(zāi)難，同時(shí)花費(fèi)較大內(nèi)存和較長(zhǎng)的運(yùn)算時(shí)間。近年來(lái)，子空間聚類被視為高維數(shù)據(jù)聚類分析的有效方法之一。子空間聚類假設(shè)高維數(shù)據(jù)是多個(gè)低維子空間的并集，數(shù)據(jù)可以在低維空間中進(jìn)行重構(gòu)，從而降低高維數(shù)據(jù)對(duì)內(nèi)存和時(shí)間復(fù)雜度的要求［4］。

稀疏表示（Sparse representation）旨在通過(guò)特定空間數(shù)據(jù)的稀疏表示重構(gòu)數(shù)據(jù)或揭示數(shù)據(jù)本質(zhì)特征［5］。稀疏表示在新的基或字典基礎(chǔ)上使用盡可能少的非零系數(shù)重構(gòu)數(shù)據(jù)。Elhamifar 等［6］基于一維稀疏性提出了稀疏子空間聚類（Sparse Subspace Clustering，SSC），使每個(gè)數(shù)據(jù)僅用一個(gè)子空間其他數(shù)據(jù)的線性組合來(lái)表示。SSC 僅考慮每個(gè)數(shù)據(jù)的稀疏表示，缺乏對(duì)數(shù)據(jù)全局結(jié)構(gòu)的描述。為獲得數(shù)據(jù)集全局結(jié)構(gòu)，2010年，Liu等［7］進(jìn)一步利用了二維稀疏性提出了基于低秩表示（Low-Rank Representation，LRR）模型的子空間聚類方法。然而，LRR通過(guò)奇異值分解的方式來(lái)求解秩的最小化，復(fù)雜度較高，不利于實(shí)際應(yīng)用。在理想情況下，即子空間相互獨(dú)立的情況下，這些方法及其拓展方法通過(guò)稀疏或者低秩約束保證了系數(shù)表示矩陣的塊對(duì)角結(jié)構(gòu)。塊對(duì)角的系數(shù)表示矩陣能夠使得：同一子空間內(nèi)數(shù)據(jù)靠近，不同子空間數(shù)據(jù)遠(yuǎn)離，從而獲得較好的聚類結(jié)果。因此，系數(shù)矩陣呈塊對(duì)角結(jié)構(gòu)被認(rèn)為是解決子空間聚類問(wèn)題重要性質(zhì)。由于實(shí)際數(shù)據(jù)集往往含有噪聲和異常數(shù)據(jù)，無(wú)法滿足子空間聚類的理想條件。針對(duì)這些問(wèn)題，人們提出了一系列的改進(jìn)模型和方法。Feng 等［8］提出了顯式的塊對(duì)角約束的SSC（Block Diagonal-SSC，BD-SSC）和LRR（Block Diagonal-LRR，BD-LRR）通過(guò)在稀疏表示模型的基礎(chǔ)上加入塊對(duì)角約束使得稀疏表示模型的系數(shù)表示矩陣塊對(duì)角更加穩(wěn)定。Lu 等［9］提出了最小二乘回歸子空間聚類（Least Squares Regression for subspace clustering，LSR），可以將高度相關(guān)的數(shù)據(jù)聚合在一起，與此同時(shí)，LSR 對(duì)于噪聲具有一定的魯棒性。在LSR 提出的強(qiáng)制塊對(duì)角（Enforced Block Diagonal，EBD）的基礎(chǔ)上，Lu 等［10］繼續(xù)拓展了EBD，提出了塊對(duì)角表示（Block Diagonal Representation，BDR）模型，在數(shù)據(jù)稀疏優(yōu)化同時(shí)增加改進(jìn)塊對(duì)角約束，簡(jiǎn)化了優(yōu)化過(guò)程，提升了優(yōu)化效率。與SSC 和LRR 相比，BDR 的稀疏優(yōu)化和塊對(duì)角約束同時(shí)得以滿足實(shí)現(xiàn)，能夠確保子空間聚類結(jié)果更優(yōu)，使得同一類數(shù)據(jù)彼此靠近，不同類數(shù)據(jù)相互遠(yuǎn)離。

稀疏表示的子空間聚類方法希望用盡可能少的數(shù)據(jù)點(diǎn)線性組合來(lái)表達(dá)高維數(shù)據(jù)。實(shí)際上，高維數(shù)據(jù)集內(nèi)嵌不同的流形幾何結(jié)構(gòu)，而且數(shù)據(jù)點(diǎn)通常分布在這些流形結(jié)構(gòu)上。這些非線性流形幾何結(jié)構(gòu)中，往往蘊(yùn)含著一些關(guān)于圖像的細(xì)節(jié)內(nèi)容的描述，可以有助于模型對(duì)于數(shù)據(jù)的結(jié)構(gòu)學(xué)習(xí)。然而，線性的子空間表示方法無(wú)法有效利用高維數(shù)據(jù)中非線性的流形幾何結(jié)構(gòu)。針對(duì)這一問(wèn)題，研究者提出基于核的子空間聚類方法，學(xué)習(xí)高維數(shù)據(jù)中的非線性信息。Patel 等［11］提出了核稀疏子空間聚類（Kernel Sparse Subspace Clustering，KSSC）以及Xiao 等［12］提出了核低秩表示（Kernel Low-Rank Representation，KLRR）模型。這些方法通過(guò)在稀疏表示模型中引入核方法，強(qiáng)化模型學(xué)習(xí)非線性流形結(jié)構(gòu)的能力。Ji等［13］在自適應(yīng)低秩核子空間聚類（adaptive Low-Rank Kernel Subspace Clustering，LRKSC）中提出了一種能夠處理非線性模型的內(nèi)核子空間聚類方法，使得隱式特征空間中的映射數(shù)據(jù)不僅低秩，而且具有自表達(dá)能力；Xie 等［14］在隱式塊對(duì)角線低秩表示（Implicit Block Diagonal Low-rank Representation，IBDLR）模型中提出將隱式特征表示和塊對(duì)角線合并到LRR模型中，既解決了解決隱式特征空間中的聚類問(wèn)題，同時(shí)使得獲得的稀疏表示矩陣呈塊對(duì)角狀。但是，通過(guò)核方法求解高維數(shù)據(jù)聚類的方式往往需要較大時(shí)間和內(nèi)存開(kāi)銷，因此無(wú)法應(yīng)用于實(shí)際應(yīng)用之中。

為了解決上述問(wèn)題，本文提出一種基于近鄰圖的塊對(duì)角子空間聚類算法，即基于近鄰圖改進(jìn)的塊對(duì)角表示（improved Block Diagonal Representation based on Neighbor Graph，BDRNG）模型。通過(guò)近鄰圖學(xué)習(xí)，可以通過(guò)局部線性來(lái)擬合局部流形結(jié)構(gòu)，從而獲得局部流形結(jié)構(gòu)。相比起復(fù)雜耗時(shí)的核方法，近鄰圖學(xué)習(xí)簡(jiǎn)單，通過(guò)更少的時(shí)耗獲得數(shù)據(jù)集內(nèi)的流形結(jié)構(gòu)信息。BDRNG 通過(guò)塊對(duì)角約束來(lái)揭示高維數(shù)據(jù)的全局結(jié)構(gòu)；通過(guò)近鄰圖來(lái)學(xué)習(xí)高維數(shù)據(jù)內(nèi)在的局部流形結(jié)構(gòu)信息。本文通過(guò)仿真實(shí)驗(yàn)和真實(shí)數(shù)據(jù)集的驗(yàn)證表明，本文方法優(yōu)于其他相同類型的子空間聚類方法。

1 相關(guān)工作

1.1 子空間聚類

設(shè)數(shù)據(jù)集X=[x1，x2，…，xn]∈RD×n，數(shù)據(jù)屬于k個(gè)子空間的并集。稀疏子空間聚類將數(shù)據(jù)表示為同一子空間內(nèi)其他數(shù)據(jù)的線性組合，即，同一類數(shù)據(jù)可以相互表示X=XZ，其中Z∈Rn×n為稀疏系數(shù)矩陣。換言之，當(dāng)xi∈Xj(i≠j)時(shí)，Zi，j≠0；而不同類數(shù)據(jù)的表示系數(shù)Zi，j則為0，即當(dāng)xi?Xj(i≠j)時(shí)，Zi，j=0。在實(shí)際情況中，數(shù)據(jù)往往受到噪聲和奇異樣本影響，所以，數(shù)據(jù)常表示為X=XZ+E，E為奇異樣本或者噪聲。一般稀疏表示的子空間聚類模型可以統(tǒng)一描述為：

其中：J(Z)為目標(biāo)函數(shù)，F(xiàn)(E)為數(shù)據(jù)項(xiàng)，R(Z)為正則項(xiàng)或者懲罰項(xiàng)；C為系數(shù)矩陣Z的約束集合，λ≥0為正則參數(shù)。稀疏表示的子空間聚類算法對(duì)系數(shù)表示矩陣||Z||引入不同的稀疏約束來(lái)發(fā)現(xiàn)數(shù)據(jù)內(nèi)在的結(jié)構(gòu)，例如基于一維稀疏性的SSC 或者基于二維稀疏性的LRR 等。在理想子空間條件下，Z具有理想的塊對(duì)角結(jié)構(gòu)。最后，利用Z構(gòu)造數(shù)據(jù)的相似度矩陣并通過(guò)譜聚類算法［15］獲得最后的聚類結(jié)果。

1.2 塊對(duì)角約束

當(dāng)子空間聚類的系數(shù)表示矩陣具有塊對(duì)角結(jié)構(gòu)，聚類結(jié)果較好。從直觀意義上來(lái)理解，塊對(duì)角結(jié)構(gòu)可以很好地描述聚類目標(biāo)——類內(nèi)數(shù)據(jù)密集、類間數(shù)據(jù)稀疏。Feng 等［8］提出了BD-SSC和BD-LRR，將塊對(duì)角約束引入SSC和LRR。但是，塊對(duì)角約束屬于NP-hard 問(wèn)題，通過(guò)投影迭代法優(yōu)化，計(jì)算效率不高。Lu等［10］提出了塊對(duì)角表示模型BDR。在BDR中，塊對(duì)角約束通過(guò)?1-范數(shù)松弛，正則項(xiàng)可以有效優(yōu)化。BDR 直接約束系數(shù)表示矩陣為塊對(duì)角形式，具有較高的優(yōu)化效率，同時(shí)系數(shù)表示矩陣的塊對(duì)角形式更加穩(wěn)定。

假設(shè)矩陣Z∈Rn×n是系數(shù)表示矩陣，滿足Z≥0 且Z=ZT。Z的拉普拉斯矩陣記為L(zhǎng)Z，LZ=diag(Z1) -Z，其中，1 表示全為1 的向量。已知數(shù)據(jù)集為k類，k-塊對(duì)角正則項(xiàng)定義如下：

其中，λi(LZ)是LZ的降序特征值，i=1，2，…，n，且因?yàn)長(zhǎng)Z＞0所以λi(LZ)≥0，k代表類數(shù)。

1.3 近鄰圖學(xué)習(xí)

高維空間下，數(shù)據(jù)點(diǎn)沿著高維數(shù)據(jù)內(nèi)嵌的流形結(jié)構(gòu)分布。因此，流形學(xué)習(xí)被視作為高維數(shù)據(jù)非線性降維的常用方法。流形學(xué)習(xí)的局部不變性假定，對(duì)于某一特定的數(shù)據(jù)點(diǎn)以及在原始空間中與該點(diǎn)接近的鄰域點(diǎn)，在投影空間中依然接近［16］。這些局部幾何結(jié)構(gòu)可以由近鄰圖表達(dá)，通過(guò)近鄰圖局部線性擬合數(shù)據(jù)點(diǎn)，從而學(xué)習(xí)到局部幾何結(jié)構(gòu)。對(duì)于給定的數(shù)據(jù)集X，每個(gè)數(shù)據(jù)點(diǎn)xi的k個(gè)近鄰信息記錄在鄰接矩陣N(i)中，Wi，j表示第j數(shù)據(jù)點(diǎn)對(duì)于第i數(shù)據(jù)點(diǎn)局部線性擬合重建的權(quán)重貢獻(xiàn)。權(quán)重矩陣W學(xué)習(xí)的目標(biāo)函數(shù)旨在能夠通過(guò)局部線性表達(dá)擬合幾何結(jié)構(gòu)來(lái)盡可能多地保留局部信息，從而使得數(shù)據(jù)與其線性擬合重構(gòu)數(shù)據(jù)的誤差盡可能小，定義如下：

因此，通過(guò)利用近鄰圖捕獲的局部幾何結(jié)構(gòu)信息，可以彌補(bǔ)以往線性子空間聚類表示模型對(duì)于高維數(shù)據(jù)中流形幾何結(jié)構(gòu)信息處理的不足，從而提高子空間聚類表示模型對(duì)高維數(shù)據(jù)的聚類準(zhǔn)確度［17］。

2 近鄰圖增強(qiáng)塊對(duì)角子空間聚類

近鄰圖能夠有效地學(xué)習(xí)數(shù)據(jù)局部結(jié)構(gòu)信息，塊對(duì)角表示可以獲得全局的數(shù)據(jù)結(jié)構(gòu)信息，因此，本文提出在塊對(duì)角表示模型中引入了近鄰圖學(xué)習(xí)，從而改善目前子空間聚類算法無(wú)法有效利用高維數(shù)據(jù)的局部幾何結(jié)構(gòu)信息的問(wèn)題。本文將式（2）改寫為矩陣形式：

當(dāng)獲得權(quán)重矩陣的最優(yōu)解W*，設(shè)LM=(I-W*)T(I-W*)，可以構(gòu)建數(shù)據(jù)局部幾何結(jié)構(gòu)正則項(xiàng)——tr(XLMXT)。

2.1 近鄰圖正則化的塊對(duì)角表示模型

在基于塊對(duì)角表示模型的子空間算法引入數(shù)據(jù)局部結(jié)構(gòu)信息，從而增強(qiáng)模型對(duì)于高維數(shù)據(jù)內(nèi)嵌的流形結(jié)構(gòu)的學(xué)習(xí)。本文將tr(XLMXT)作為近鄰圖正則項(xiàng)加入到本文模型中，提出BDRNG模型如下：

其中：Z為系數(shù)表示矩陣，β、γ為用于平衡對(duì)應(yīng)項(xiàng)的正系數(shù)。由于數(shù)據(jù)集X學(xué)到的流形結(jié)構(gòu)對(duì)其對(duì)應(yīng)的塊對(duì)角表示系數(shù)矩陣Z也有相似的流形結(jié)構(gòu)，可以將X替換為Z［18］。塊對(duì)角約束需要強(qiáng)制Z為非負(fù)和對(duì)稱，從而限制Z的表示能力。根據(jù)文獻(xiàn)［10］，引入中間項(xiàng)B，減少塊對(duì)角約束對(duì)B的影響，并將模型改寫為：

其中：λ為平衡松弛項(xiàng)的正系數(shù)?？梢詫、B的求解子問(wèn)題變?yōu)橥箚?wèn)題，從而可以得到唯一的穩(wěn)定解。||B||k改寫為，其中0 ＜G＜1，tr(G)=k。根據(jù)本文1.2 節(jié)中的內(nèi)容，可以得到BDRNG最終的模型為：

2.2 求解BDRNG

本文將當(dāng)前迭代次數(shù)記作t，那么Bt就代表第t次迭代時(shí)矩陣B的值。BDRNG 可以通過(guò)交替更新G、Z、B來(lái)求解，獲得最后的系數(shù)表示矩陣。

固定B=BT，更新Zt+1、Gt+1：

而式（7）可以簡(jiǎn)化為分別更新Zt+1，Gt+1。對(duì)于Gt+1：

其中，式（8）通過(guò)Gt+1=UUT求解Gt+1，其中U∈Rn×k是由diag(B1) -B的k個(gè)最小的特征值對(duì)應(yīng)的特征向量組成［10］。對(duì)于更新Zt+1的子問(wèn)題，更新計(jì)算如式（9）：

把式（9）記為二次函數(shù)f(Z)，令f(Z)的導(dǎo)數(shù)為0，得到式（10）：

可以用西爾維斯特方程求得唯一解；

固定Z=Zt+1，G=Gt+1，更新B：

根據(jù)參考文獻(xiàn)［10］中的證明，式（11）可以通過(guò)Bt+1=(diag(G)1T-G)求解B。

利用譜聚類方法［15］將數(shù)據(jù)集劃分成k個(gè)簇，輸出最后聚類的結(jié)果。

算法1 BDRNG算法。

輸入 數(shù)據(jù)集矩陣X∈RD×n，聚類簇?cái)?shù)k，最大迭代次數(shù)Tmax，迭代終止閾值tol以及近鄰圖正則項(xiàng)LM；

步驟1 初始化B0、Z0、G0。

步驟2 更新G。

步驟3 更新Z。

步驟4 更新B。

步驟5 計(jì)算max(|Zt+1-Zt|，|Bt+1-Bt|)判斷是否小于或等于迭代終止閾值tol：如果小于tol，則結(jié)束循環(huán)，進(jìn)入步驟7；否則進(jìn)入步驟6。

步驟6 重復(fù)步驟2～5，達(dá)到最大迭代次數(shù)Tmax時(shí)，結(jié)束循環(huán)，進(jìn)入下一步。

步驟7 根據(jù)Z，B計(jì)算數(shù)據(jù)相似性矩陣Y，Y=

輸出 利用Y，通過(guò)譜聚類劃分成k個(gè)簇，輸出最后聚類的標(biāo)簽劃分。

2.3 時(shí)間復(fù)雜度分析

在BDRNG 中，LM的計(jì)算以及和Z的求解的時(shí)間復(fù)雜度較高，當(dāng)數(shù)據(jù)集為X∈Rn×n，局部線性表示的權(quán)重矩陣W*∈Rn×n的計(jì)算時(shí)間復(fù)雜度為O(Dn2+(D+K)K2n)，其中，K為KNN算法所設(shè)定的鄰域大小［18］。根據(jù)W*，LM的計(jì)算時(shí)間復(fù)雜度為O(n2)。Z∈Rn×n通過(guò)標(biāo)準(zhǔn)西爾維斯特方程進(jìn)行求解，時(shí)間復(fù)雜度為O(Tmax(n2))，Tmax為程序最大迭代次數(shù)。在模型學(xué)習(xí)中，LM只需要一次計(jì)算，不需要迭代更新，所以LM的計(jì)算時(shí)間復(fù)雜度不計(jì)入程序總時(shí)間復(fù)雜度。因此，算法總時(shí)間復(fù)雜度為O(T(n2))，其中T為BDRNG 迭代次數(shù)。BDRNG與其他算法運(yùn)行時(shí)間結(jié)果對(duì)比詳見(jiàn)本文3.4節(jié)。

2.4 收斂性證明

在本文中，本文通過(guò)交替最小化來(lái)更新模型。本文將式（3）標(biāo)記為f(Z，B，G)。并設(shè)，S1={diag(B)=0，B=BT，B≥0}，S1的指示函數(shù)記為lS1，以及S2={0 ＜G＜1，tr(G)=k}，S2的指示函數(shù)記為lS2。

在更新Gt+1子問(wèn)題中，有：

其中，Gt∈S2，可得||Gt||≤1，所以Gt是收斂的。

在更新Zt+1子問(wèn)題中，有：

這說(shuō)明Zt的更新也是收斂的。

在更新Bt+1子問(wèn)題中，有

綜上，本文將所有的子問(wèn)題合并之后，可以得到：

因此，f(Zt，Gt，Bt)+單調(diào)遞減。同時(shí)，Gt和diag(Bt1) -Bt均為半正定，所以，本文有因此，本文有f(Zt，Gt，Bt)+

綜上，當(dāng)t=0，1，2，…，∞時(shí)，本文有所以，本文有：

綜上所述，本文的模型是收斂的。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證BDRNG的有效性，本文分別在仿真數(shù)據(jù)集和標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。本文選用的測(cè)試對(duì)比算法包括：本文提出的算法BDRNG、稀疏子空間聚類（Sparse Subspace Clustering，SSC）［6］、低秩表示（Low-Rank Representation，LRR）模型［7］、塊對(duì)角表示（Block Diagonal Representation，BDR）模型［10］、自適應(yīng)低秩核子空間聚類（adaptive Low-Rank Kernel Subspace Clustering，LRKSC）［13］、隱式塊對(duì)角線低秩表示（Implicit Block Diagonal Low-rank Representation，IBDLR）模型［14］6 種算法。由于BDR 中會(huì)生成2 個(gè)可以作為最后聚類劃分的系數(shù)表示矩陣BDR（Z）和BDR（B），本文在具體對(duì)比結(jié)果評(píng)價(jià)中，將分別提供BDR（Z）和BDR（B）最后聚類結(jié)果作為對(duì)比方法的評(píng)價(jià)結(jié)果之一。由于其中一個(gè)矩陣作為另外一個(gè)矩陣的求解的中間項(xiàng)，例如BDR（B）作為BDR（Z）求解的中間項(xiàng)引入到模型中，兩者的迭代更新共享同一個(gè)更新過(guò)程。BDRNG同理。

本文采用聚類正確率（clustering Accuracy，ACC），歸一化互信息（Normalized Mutual Information，NMI）［19］和調(diào)整蘭德指數(shù)（Adjusted Rand Index，ARI）［20］作為評(píng)價(jià)指標(biāo)。

ACC 是衡量聚類表現(xiàn)最通用及簡(jiǎn)單的方法，可以作為評(píng)價(jià)整體聚類結(jié)束之后，數(shù)據(jù)集中正確聚類的數(shù)據(jù)點(diǎn)個(gè)數(shù)；但ACC無(wú)法說(shuō)明更多關(guān)于聚類結(jié)果好壞的原因。NMI可以測(cè)量聚類結(jié)果和原本類的預(yù)標(biāo)記標(biāo)簽之間的相互關(guān)系。如果聚類的結(jié)果和原來(lái)數(shù)據(jù)集標(biāo)簽非常相似，則說(shuō)明模型可以很好地對(duì)數(shù)據(jù)點(diǎn)進(jìn)行劃分。但是在聚類過(guò)程中，得到的類別標(biāo)簽無(wú)法很好地說(shuō)明聚類的準(zhǔn)確度。聚類更多考察的是這些類別的分布和樣本真實(shí)類別分布的相似度，換言之，同一個(gè)簇內(nèi)，樣本的相似度比其他不同類別的樣本相似度更好，才能說(shuō)明聚類的效果更好。蘭德指數(shù)（Rand Index，RI）將聚類的過(guò)程視作為一個(gè)決策的過(guò)程，對(duì)數(shù)據(jù)集上所有的點(diǎn)進(jìn)行兩兩配對(duì)，當(dāng)且僅當(dāng)兩個(gè)數(shù)據(jù)點(diǎn)相似時(shí)，才將其歸為一類。RI 的取值范圍在［0，1］區(qū)間，0 代表聚類效果非常差。但當(dāng)類數(shù)越來(lái)越多時(shí)，RI 對(duì)于兩個(gè)數(shù)據(jù)點(diǎn)隨機(jī)地劃分，其RI 值不為一個(gè)接近于0 的常數(shù)，即RI 值無(wú)法很好地反映真實(shí)的聚類結(jié)果。所以本文采用的是ARI 作為評(píng)價(jià)依據(jù)，ARI 可以很好解決RI 的隨機(jī)劃分問(wèn)題，ARI取值范圍在[-1，1]區(qū)間，ARI越接近1，說(shuō)明模型聚類的效果更符合真實(shí)樣本的分布［20］。

ACC、NMI、ARI 的值越大說(shuō)明聚類的表現(xiàn)效果越好。所有實(shí)驗(yàn)結(jié)果為各個(gè)模型在數(shù)據(jù)集上面調(diào)優(yōu)之后，分別運(yùn)行20次聚類的平均結(jié)果作為最后評(píng)價(jià)依據(jù)。

3.1 仿真數(shù)據(jù)集

本文在500維空間內(nèi)隨機(jī)選取5個(gè)不相交的子空間，每個(gè)子空間的秩為75 維，每個(gè)子空間隨機(jī)選取150 個(gè)樣本點(diǎn)。魯棒性實(shí)驗(yàn)數(shù)據(jù)在干凈數(shù)據(jù)集上隨機(jī)生成10%、20%、30%的高斯噪聲，即從無(wú)噪聲到含有30%噪聲的數(shù)據(jù)集。

如果系數(shù)表示矩陣如果有很好的塊對(duì)角屬性，那么子空間聚類算法將得到較好的聚類結(jié)果。圖1 中對(duì)比了BDRNG在仿真數(shù)據(jù)庫(kù)上從干凈數(shù)據(jù)集到30%噪聲的表現(xiàn)效果。在圖1 中可以看到，即使噪聲等級(jí)上升，BDRNG 所生成的系數(shù)表示矩陣依然保持不錯(cuò)的塊對(duì)角形式。

圖1 BDRNG 在不同噪聲比例下生成的系數(shù)表示矩陣可視化圖Fig.1 Visualization of coefficient representation matrices generated by BDRNG with different noise ratios

BDRNG 和LRR、SSC、IBDLR、BDR 四種方法在仿真數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表1 所示。從表1 中可以看出：BDRNG 具有較好的聚類性能。圖2為在20%噪聲下各方法的系數(shù)表示矩陣可視化圖?？梢钥闯鯞DRNG 在20%噪聲的仿真數(shù)據(jù)庫(kù)上相較于其他方法有更好的塊對(duì)角形式的表現(xiàn)。在20%噪聲下，LRR 的系數(shù)矩陣塊對(duì)角形式被嚴(yán)重破壞，SSC 的系數(shù)矩陣塊對(duì)角形狀隱約可見(jiàn)，BDR 的系數(shù)矩陣塊對(duì)角邊界模糊而IBDLR 的系數(shù)矩陣比上述3 種算法較好，然而依舊存在著塊對(duì)角形式外模糊的現(xiàn)象。由此可見(jiàn)，在20%噪聲下，對(duì)比方法都存在被噪聲不同程度干擾的現(xiàn)象，而B(niǎo)DRNG可以使得系數(shù)表示矩陣保持較好的塊對(duì)角形式。BDRNG 在BDR 的基礎(chǔ)上增加非線性學(xué)習(xí)正則算子。當(dāng)處理噪聲數(shù)據(jù)時(shí)，BDRNG 比BDR系數(shù)矩陣獲取的塊對(duì)角結(jié)構(gòu)更具有魯棒性。這說(shuō)明了引入的正則算子可以有效地利用非線性結(jié)構(gòu)數(shù)據(jù)，有助于模型對(duì)于數(shù)據(jù)內(nèi)在的結(jié)構(gòu)學(xué)習(xí)和提升了模型對(duì)于數(shù)據(jù)集的表達(dá)能力。

隨著噪聲比例變高，聚類問(wèn)題就會(huì)變得更加困難。為了更好地觀察、分析各個(gè)算法在不同噪聲程度下的影響，本文對(duì)比LRR、SSC、BDR、IBDLR 和BDRNG 在0～20%噪聲條件下的聚類表現(xiàn)。隨機(jī)初始化50 組參數(shù)進(jìn)行實(shí)驗(yàn)。所有參數(shù)均在{1E -5，1E+5}內(nèi)變化。在無(wú)噪聲的情況下，除了LRR 以外，其他所有方法最大聚類準(zhǔn)確度均可以保持100%完美的聚類表現(xiàn)。隨著噪聲等級(jí)上升的過(guò)程中，其他方法的平均聚類準(zhǔn)確度快速下降，而B(niǎo)DRNG的下降幅度相對(duì)較為平緩。在10%噪聲條件下，LRR、SSC、IBDLR 的平均聚類準(zhǔn)確度快速下降到50%及以下。由表1 可以看出，在噪聲比例上升的過(guò)程中，BDRNG 的聚類準(zhǔn)確度的中位數(shù)（Med）依舊可以保持在85%以上，而其他方法的50 次聚類準(zhǔn)確度的中位數(shù)已經(jīng)快速下降。由此可以看出，本文提出的方法在引入非線性結(jié)構(gòu)學(xué)習(xí)算子后，可以增強(qiáng)線性的子空間聚類算法的魯棒性。

圖2 各算法在20%噪聲條件下的仿真數(shù)據(jù)集下生成的系數(shù)表示矩陣可視化圖Fig.2 Visualization of coefficient representation matrices generated by different algorithms with 20%noise

表1 各算法在不同噪聲條件的仿真數(shù)據(jù)集上的聚類準(zhǔn)確度 單位：%Tab.1 ACCs of different algorithms on synthetic dataset with different noise ratiosunit：%

3.2 標(biāo)準(zhǔn)數(shù)據(jù)集

本節(jié)選用標(biāo)準(zhǔn)數(shù)據(jù)集：ORL［21］、COIL-20［22］和CIFAR-10［23］，通過(guò)這3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)比分析各個(gè)算法的聚類性能。ORL 數(shù)據(jù)集包含40 個(gè)人在不同光照條件、面部細(xì)節(jié)和面部表情下10 幅人臉圖像。COIL20 數(shù)據(jù)集是由20 個(gè)物體組成的總共1 440 幅灰色圖像。每個(gè)物體以5°為拍攝固定間隔角度進(jìn)行拍攝，總共拍攝72 幅圖片。CIFAR-10 數(shù)據(jù)集包含10 個(gè)類別：飛機(jī)、汽車、鳥(niǎo)類、貓、鹿、狗、青蛙、馬、船和卡車。每個(gè)類別包含6 000幅圖像。為了降低內(nèi)存和計(jì)算成本，在每個(gè)類別中隨機(jī)選擇100 個(gè)樣本，通過(guò)使用ILSVRC（ImageNet Large Scale Visual Recognition Challenge）［24］上的卷積神經(jīng)網(wǎng)絡(luò)作為特征提取器，將每個(gè)圖像表示為2 048維向量，因此，本文實(shí)驗(yàn)中使用的CIFAR-10 數(shù)據(jù)集大小為2 048×1 000。部分?jǐn)?shù)據(jù)集示例樣本如圖3所示。

圖3 部分?jǐn)?shù)據(jù)集示例樣本Fig.3 Partial samples of datasets

在本節(jié)實(shí)驗(yàn)中，選用了LRR、SSC、BDR（包括BDR（Z）和BDR（B））、IBDLR、LRKSC作為實(shí)驗(yàn)的對(duì)比方法。各個(gè)對(duì)比方法先通過(guò){1E -5，1E+5} 的區(qū)間內(nèi)進(jìn)行調(diào)整參數(shù)實(shí)驗(yàn)，具體實(shí)驗(yàn)設(shè)置可參考3.3 節(jié)；其次，再進(jìn)行隨機(jī)參數(shù)實(shí)驗(yàn)，即隨機(jī)進(jìn)行了2 000次的隨機(jī)參數(shù)設(shè)置，進(jìn)行實(shí)驗(yàn)；最后，選擇了聚類效果最佳的實(shí)驗(yàn)結(jié)果作為最后對(duì)比評(píng)價(jià)依據(jù)。

從表2可以得到如下結(jié)論：

1）BDR、IBDLR 和BDRNG 為塊對(duì)角表示模型為基礎(chǔ)或是引入塊對(duì)角約束正則項(xiàng)。實(shí)驗(yàn)結(jié)果表明，在這3 個(gè)數(shù)據(jù)集上，BDR、IBDLR、BDRNG均有明顯優(yōu)于LRR和SSC。這說(shuō)明了塊對(duì)角約束確實(shí)有效提高了聚類效果。此外，BDRNG 又在BDR 的基礎(chǔ)上，強(qiáng)化了數(shù)據(jù)局部幾何結(jié)構(gòu)的學(xué)習(xí)，補(bǔ)充了局部幾何結(jié)構(gòu)信息。相比起B(yǎng)DR，本文提出的BDRNG，包括BDRNG（Z）和BDRNG（B），均取得了更好的聚類效果。這說(shuō)明學(xué)習(xí)局部幾何結(jié)構(gòu)信息之后的子空間聚類算法對(duì)于最后聚類效果確實(shí)有所助益。

表2 在各標(biāo)準(zhǔn)數(shù)據(jù)集上各方法聚類表現(xiàn)比較 單位：%Tab.2 Comparison of clustering performance of different methods on different datasetsunit：%

2）ORL 為人臉數(shù)據(jù)集，人臉數(shù)據(jù)有強(qiáng)非線性結(jié)構(gòu)。在ORL 上，BDRNG 的表現(xiàn)明顯優(yōu)于其他算法。這是因?yàn)锽DRNG 通過(guò)近鄰圖學(xué)習(xí)了數(shù)據(jù)集的非線性結(jié)構(gòu)。通過(guò)BDRNG 和BDR 的比較，可以看出BDRNG 有效地提升了非線性結(jié)構(gòu)信息的學(xué)習(xí)效果。除BDRNG以外，ORL數(shù)據(jù)集上表現(xiàn)最佳為L(zhǎng)RKSC 算法。該方法中引入了核方法的學(xué)習(xí)，同樣有效提高了這類非線性結(jié)構(gòu)信息的學(xué)習(xí)效果。然而，通過(guò)后續(xù)運(yùn)行時(shí)間的分析，發(fā)現(xiàn)LRKSC 的耗時(shí)非常突出，不適用于大規(guī)模的高維數(shù)據(jù)的學(xué)習(xí)。BDRNG 通過(guò)近鄰圖得到數(shù)據(jù)局部非線性結(jié)構(gòu)信息，優(yōu)于核方法聚類性能，且時(shí)間性能更優(yōu)。

3.3 參數(shù)分析

在本節(jié)里，以O(shè)RL 數(shù)據(jù)庫(kù)為例，分析各個(gè)參數(shù)對(duì)于模型的影響程度，實(shí)驗(yàn)結(jié)果如圖4 所示。本文提出的模型BDRNG總共有3個(gè)平衡正則項(xiàng)：λ、γ和β。將這3個(gè)參數(shù)分別分組，在{1E -5，1E+5}的取值范圍內(nèi)變化其中兩個(gè)參數(shù)，保持另外一個(gè)參數(shù)不變（當(dāng)某一個(gè)參數(shù)固定時(shí)，分別固定變量值設(shè)置為λ=0.1，γ=1，β=1）。

觀察圖4，可以發(fā)現(xiàn)不同的參數(shù)對(duì)于BDRNG 學(xué)習(xí)影響各有強(qiáng)弱，其中，λ和β對(duì)聚類效果影響更大。首先，當(dāng)λ取值過(guò)小會(huì)導(dǎo)致模型學(xué)習(xí)效果不佳。在模型迭代更新的初期，B、Z還沒(méi)有充分學(xué)習(xí)。當(dāng)λ取值過(guò)小，該正則項(xiàng)對(duì)于迭代更新的影響變小，無(wú)法得到一個(gè)好的學(xué)習(xí)效果［10］。其次，當(dāng)β取值較大時(shí)，聚類結(jié)果下降明顯，這是因?yàn)榉蔷€性結(jié)構(gòu)學(xué)習(xí)影響過(guò)大，影響到了原有塊對(duì)角表示模型的學(xué)習(xí)，導(dǎo)致最后聚類效果下降明顯。當(dāng)β非常小的時(shí)候，BDRNG 獲得的數(shù)據(jù)局部幾何結(jié)構(gòu)信息非常少，對(duì)于模型學(xué)習(xí)貢獻(xiàn)較少。當(dāng)λ、β均比較小的時(shí)候，BDRNG 表現(xiàn)非常差，這是因?yàn)閴K對(duì)角表示和數(shù)據(jù)內(nèi)在非線性結(jié)構(gòu)信息均沒(méi)有有效學(xué)到數(shù)據(jù)信息，導(dǎo)致模型表現(xiàn)效果差。最后，通過(guò)結(jié)合各組參數(shù)影響圖發(fā)現(xiàn)，聚類效果變化趨勢(shì)由λ或者是β主導(dǎo)。相比起λ的變化對(duì)于模型學(xué)習(xí)效果的影響相對(duì)較弱，γ的變化沒(méi)有引起模型聚類效果的明顯變化。從直觀上來(lái)理解，γ對(duì)于模型的影響只有在更新矩陣B的過(guò)程中，同時(shí)，γ的作用還受到了λ的制約。所以，相比起λ和β，γ對(duì)于模型最后效果的影響不是非常的明顯。

圖4 各參數(shù)在ORL 數(shù)據(jù)集上對(duì)聚類準(zhǔn)確度的影響Fig.4 Impact of parameters on ACC on ORL dataset

此外，在本文中，除了λ、γ和β以外，還有一個(gè)隱藏的參數(shù)，即在構(gòu)造近鄰圖時(shí)使用到的近鄰數(shù)K。在多次實(shí)驗(yàn)中，發(fā)現(xiàn)構(gòu)造近鄰圖時(shí)所選擇的近鄰數(shù)K有一定的影響。K越小，則所構(gòu)造的近鄰圖會(huì)越集中于局部數(shù)據(jù)，近鄰點(diǎn)對(duì)于中心的影響也會(huì)越大，其中，受到噪聲的干擾影響也就越大；反之，K越大，近鄰會(huì)包括更多的數(shù)據(jù)點(diǎn)，在其中數(shù)據(jù)點(diǎn)越多，包含噪聲點(diǎn)的可能性也就越大，導(dǎo)致中心點(diǎn)的重改易受到更多噪聲點(diǎn)的干擾。以O(shè)RL數(shù)據(jù)集為例，從圖5可以看出，隨著近鄰數(shù)K的變大，聚類效果呈先升后降的趨勢(shì)，近鄰數(shù)K在樣本數(shù)的1/4處時(shí)，可以獲得較好的聚類結(jié)果。

圖5 在ORL數(shù)據(jù)集上構(gòu)造近鄰圖的近鄰數(shù)K對(duì)聚類結(jié)果的影響Fig.5 Impact of the number of neighbors K on clustering performance on ORL dataset

3.4 時(shí)間復(fù)雜度和收斂性分析

本節(jié)以O(shè)RL 數(shù)據(jù)庫(kù)為例，對(duì)比分析BDRNG 和其他方法的計(jì)算耗時(shí)和以及可視化BDRNG 模型迭代更新過(guò)程的收斂曲線。由于BDRNG（Z）、BDRNG（B）是共享同一個(gè)更新過(guò)程，本實(shí)驗(yàn)僅記錄模型求解的總耗時(shí)，不單獨(dú)計(jì)算BDRNG（Z）或BDRNG（B）耗時(shí)。BDR同理。本節(jié)實(shí)驗(yàn)隨機(jī)設(shè)置各個(gè)對(duì)比方法的參數(shù)，進(jìn)行100 次實(shí)驗(yàn)，最后將實(shí)驗(yàn)結(jié)果平均耗時(shí)作為該對(duì)比方法的評(píng)價(jià)依據(jù)（參數(shù)變化范圍在{1E -5，1E+5}之中）。

根據(jù)圖6（a）可以看出，LRR（ACC-56.84%）的計(jì)算耗時(shí)最少，但是聚類準(zhǔn)確度是所有對(duì)比方法中最低。IBDLR（ACC-75.41%）和LRKSC（ACC-80.25%）是耗時(shí)最長(zhǎng)的兩個(gè)方法。這是因?yàn)檫@些方法中還涉及到了核方法的運(yùn)算，耗時(shí)相對(duì)于其他方法長(zhǎng)。然而，高的時(shí)間開(kāi)銷并未換來(lái)更優(yōu)的聚類效果。本文提出的模型BDRNG（ACC-84.00%）耗時(shí)相對(duì)多，但是在ORL 數(shù)據(jù)集上，BDRNG 提升效果最明顯。這說(shuō)明，相比起核方法，BDRNG 通過(guò)更少的時(shí)間代價(jià)學(xué)習(xí)數(shù)據(jù)非線性結(jié)構(gòu)信息，顯著提升了聚類準(zhǔn)確度。

圖6 ORL 實(shí)驗(yàn)結(jié)果Fig.6 Results on ORL dataset

根據(jù)本文2.3 節(jié)中的內(nèi)容，算法總時(shí)間復(fù)雜度為O(T(n2))，其中T為BDRNG 迭代次數(shù)，n為數(shù)據(jù)樣本個(gè)數(shù)。圖6（b）為BDRNG 迭代更新中，各項(xiàng)值變化趨勢(shì)，可以看出BDRNG 的目標(biāo)函數(shù)值呈單調(diào)遞減，在有限的循環(huán)次數(shù)內(nèi)可以快速達(dá)到收斂閾值。綜合考慮耗時(shí)和聚類表現(xiàn)，BDRNG 是性價(jià)比最高的聚類模型。

4 結(jié)語(yǔ)

針對(duì)高維流形數(shù)據(jù)聚類問(wèn)題，本文提出了基于近鄰圖的塊對(duì)角子空間聚類算法——BDRNG。該方法不僅考慮原始數(shù)據(jù)的局部幾何結(jié)構(gòu)，并且結(jié)合了數(shù)據(jù)的全局結(jié)構(gòu)信息。BDRNG 通過(guò)近鄰圖擬合高維數(shù)據(jù)原始空間中局部幾何結(jié)構(gòu)；同時(shí)，通過(guò)塊狀稀疏范數(shù)優(yōu)化生成穩(wěn)定結(jié)構(gòu)的塊對(duì)角系數(shù)表示矩陣，描述全局結(jié)構(gòu)信息。實(shí)驗(yàn)表明，本文通過(guò)學(xué)習(xí)高維數(shù)據(jù)中的局部結(jié)構(gòu)，有效獲取高維數(shù)據(jù)中的流形結(jié)構(gòu)信息，提升線性子空間表示模型處理高維非線性結(jié)構(gòu)數(shù)據(jù)的能力。未來(lái)的工作將更進(jìn)一步研究如何快速和有效獲取高維數(shù)據(jù)流形信息。