非負(fù)局部約束低秩子空間聚類算法

解 昊，趙志剛，呂慧顯，劉馨月，劉成士，董曉晨

1.青島大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島 266000

2.青島大學(xué) 自動(dòng)化與電氣工程學(xué)院，山東 青島 266000

1 引言

在過(guò)去幾十年中，子空間學(xué)習(xí)[1]和聚類問(wèn)題在計(jì)算機(jī)視覺(jué)和機(jī)器學(xué)習(xí)領(lǐng)域成為重要的研究課題之一。通常高維的數(shù)據(jù)點(diǎn)是從多個(gè)低維子空間中抽取出來(lái)的，子空間聚類的基本任務(wù)是根據(jù)潛在的子空間對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類。根據(jù)聚類機(jī)制，目前已存在的子空間聚類方法可以分為代數(shù)方法[2-3]，迭代法[4]，統(tǒng)計(jì)方法[5-7]和譜聚類方法[8-11]。以上方法中，譜聚類是近年來(lái)最受歡迎的子空間聚類算法[12]。

譜聚類算法的關(guān)鍵步驟在于構(gòu)建親和度圖。構(gòu)建親和度圖的方案分為基于局部距離和基于全局線性表示兩種。基于局部距離的方法利用成對(duì)點(diǎn)之間的歐氏距離建立親和度圖，如拉普拉斯特征圖[13]，k近鄰[14]，若兩個(gè)數(shù)據(jù)點(diǎn)不相鄰，則將兩點(diǎn)之間的親和度置為0，否則置為1。基于局部距離的方案計(jì)算簡(jiǎn)單，但是這種構(gòu)建圖的方式對(duì)噪聲和異常值敏感。基于全局線性表示的方案假設(shè)每個(gè)數(shù)據(jù)點(diǎn)可以在一個(gè)過(guò)完備的字典（即X=DZ，其中D是過(guò)完備的字典）中被線性地表示。通過(guò)對(duì)表示矩陣Z應(yīng)用不同范數(shù)正則化，可以得到不同親和度來(lái)構(gòu)建圖，如線性平方回歸[8]，稀疏子空間聚類[9]，低秩表示[10]等。

與基于稀疏方法相比，基于低秩的方法旨在找到所有數(shù)據(jù)的最低秩表示，即rank(Z),s.t.X=XZ。此方法更適合追求數(shù)據(jù)空間的全局和內(nèi)在信息。然而，低秩表示算法不能利用數(shù)據(jù)之間局部線性結(jié)構(gòu)，這將導(dǎo)致構(gòu)造的親和度矩陣通常是密集的，并且低秩表示中的負(fù)值在構(gòu)建親和度矩陣上沒(méi)有任何意義。

為了兼顧數(shù)據(jù)的全局和局部結(jié)構(gòu)，本文提出了非負(fù)局部約束低秩子空間算法，該算法在低秩表示的基礎(chǔ)上，將數(shù)據(jù)的局部稀疏結(jié)構(gòu)作為約束集成到統(tǒng)一公式中。此外，原始數(shù)據(jù)作為字典不具有代表性，基于學(xué)習(xí)的字典對(duì)噪聲有良好的魯棒性。考慮到最終結(jié)果的準(zhǔn)確性，在預(yù)處理數(shù)據(jù)時(shí)，采用Wei[20]基于矩陣分解的分析，對(duì)字典進(jìn)行更新。

2 相關(guān)工作

2.1 子空間聚類問(wèn)題

令 X=[x1,x2,…,xn]是來(lái)自于 k個(gè)線性子空間的m維數(shù)據(jù)向量的集合，其中子空間S的維度i為ri。子空間聚類的任務(wù)是將存在于同一個(gè)子空間中的數(shù)據(jù)向量分離出來(lái)。為了標(biāo)記符號(hào)簡(jiǎn)單，可以假設(shè)X=[X1,X2,…,Xk]，其中Xi由存在于子空間Si中的數(shù)據(jù)向量組成。同時(shí)，假設(shè)子空間Si相互獨(dú)立，di表示為Xi中的向量數(shù)。那么存在至少一個(gè)塊對(duì)角矩陣Z=diag{Z1,Z2,…,Zk}滿足等式：

其中第i個(gè)塊Zi的維度為di×di。式（1）具有無(wú)窮多的解。任何一個(gè)解都可稱為表示系數(shù)矩陣。值得注意的是，矩陣Z的塊對(duì)角結(jié)構(gòu)直觀顯示了數(shù)據(jù)的分割（每個(gè)塊對(duì)應(yīng)于一個(gè)簇。因此，聚類任務(wù)相當(dāng)于找到塊對(duì)角線表示矩陣Z）。

2.2 低秩表示算法

低秩表示算法旨在探索多個(gè)子空間結(jié)構(gòu)，從而找到一組數(shù)據(jù)向量的最低秩表示。

對(duì)于無(wú)噪聲的情況，低秩表示算法將數(shù)據(jù)本身作為字典，并尋找最低秩表示矩陣Z：

由于秩函數(shù)不是凸的難以求得最優(yōu)值，式（2）最優(yōu)化問(wèn)題可以放寬到以下凸優(yōu)化問(wèn)題：

對(duì)于存在噪聲的情況，低秩表示算法通過(guò)向目標(biāo)函數(shù)（3）添加列和范數(shù)項(xiàng)處理噪聲數(shù)據(jù)，使得噪聲稀疏：

雖然實(shí)驗(yàn)結(jié)果表明[10]式（4）對(duì)于噪聲有強(qiáng)魯棒性，但是當(dāng)噪聲影響嚴(yán)重，或者異常值所占百分比較大時(shí)。使用原始數(shù)據(jù)X本身作為字典將導(dǎo)致聚類效果明顯下降。Wei[20]對(duì)于字典提出了一種改進(jìn)的低秩表示方法：

直觀地，該模型消除了大部分噪聲，并采用干凈數(shù)據(jù)作為字典，當(dāng)數(shù)據(jù)本身嚴(yán)重?fù)p壞時(shí)，最終的聚類效果比低秩表示算法有明顯提升。

3 非負(fù)局部約束低秩子空間算法

3.1 非負(fù)局部約束低秩模型

在2.1節(jié)中，說(shuō)明了對(duì)于塊對(duì)角矩陣Z如果字典是過(guò)于完備的（比如用數(shù)據(jù)本身作為字典）可以有無(wú)窮多個(gè)可行解，為了解決這個(gè)問(wèn)題，對(duì)所求的表示矩陣Z加入稀疏與低秩約束：

式（6）中β＞0是正則項(xiàng)參數(shù)平衡稀疏性與低秩性，表示矩陣Z的每一列zi揭示了數(shù)據(jù)xi與字典A的線性關(guān)系。然而，求解式（6）是一個(gè)NP難問(wèn)題，借由Liu[10]與Vidal[9]的處理將式（6）轉(zhuǎn)化如下：

同時(shí)，也要考慮到噪聲的影響，加入噪聲項(xiàng)E的同時(shí)，對(duì)字典進(jìn)行更新：

該模型具體來(lái)說(shuō)，每個(gè)數(shù)據(jù)點(diǎn)由其他數(shù)據(jù)點(diǎn)的線性組合得到，表示矩陣Z是非負(fù)且稀疏的[21]。非負(fù)值確保每個(gè)數(shù)據(jù)點(diǎn)位于其鄰點(diǎn)的凸包中，稀疏性確保所涉及的鄰點(diǎn)盡可能少。除了非負(fù)稀疏約束之外，表示矩陣Z強(qiáng)制為低秩，使相同子空間上的數(shù)據(jù)點(diǎn)聚類成同一個(gè)簇。

3.2 線性交替方向乘子法求解非負(fù)局部約束低秩模型

引理1令[U,S,V]=SVD(D)，則最優(yōu)化問(wèn)題，s.t.D=DZ的解是矩陣D的形狀相互作用矩陣，即Z*=VVT，目標(biāo)方程最優(yōu)值為：||Z*||*=rank(D)。

根據(jù)引理1可以將式（8）近似地轉(zhuǎn)化為如下兩式：

對(duì)于式（8），雖然在求解過(guò)程時(shí)固定其他變量求解單一變量可以確保函數(shù)為凸函數(shù)，但計(jì)算量仍非常巨大。因此在確定字典時(shí)，基于Wei[20]的分析結(jié)果，采用無(wú)噪聲時(shí)的低秩表示最優(yōu)解等于數(shù)據(jù)形狀相互作用矩陣[20]方案。

式（9）用核范數(shù)近似替代秩函數(shù)（rank），利用增廣拉格朗日方法去除約束條件后，借由Lin[22]提出的非精準(zhǔn)拉格朗日乘子算法（ALM）迭代求解最優(yōu)化問(wèn)題：

算法1求解式（9）

輸入：數(shù)據(jù)矩陣X，參數(shù)λ＞0

初始化參數(shù)：E0,Y0,u0＞0,umax＞u0,ρ＞1,ε＞0

1.更新D：

2.更新E：

3.更新乘子Y：

4.更新 u ：uk+1=min(ρuk,umax)

5.k←k+1

結(jié)束循環(huán)

輸出：新字典D

對(duì)于式（10），交替方向乘子法（ADM）在求解時(shí)需要引入兩個(gè)輔助變量，每個(gè)變量迭代都需要龐大的矩陣計(jì)算。因此，采用線性交替方向自適應(yīng)法（LADMAP）[23]解決此最優(yōu)化問(wèn)題。

首先，引入輔助變量H使目標(biāo)函數(shù)變量可分離：

式（12）的增廣拉格朗日方程為：

為后續(xù)計(jì)算簡(jiǎn)便，式（13）化簡(jiǎn)為：

線性交替方向自適應(yīng)法（LADMAP）通過(guò)求解單一變量時(shí)，固定其他變量為最小值來(lái)交替更新變量Z、H和E，其中二次項(xiàng)在前一次迭代中被其一階導(dǎo)數(shù)近似代替，然后添加近似項(xiàng)Z-Zk完成變量更新[22]。通過(guò)一些代數(shù)運(yùn)算，變量Z、H和E更新方案如下：

其中?為關(guān)于Z的偏微分操作，Θ、S、Ω分別是奇異值閾值操作、收縮閾值操作、l2-1最小值操作[10]，特別的，式中的

完整迭代算法流程見(jiàn)算法2。

算法2求解式（10）

當(dāng)||X-DZk-Ek||F/||X||F≥ε1或者ε2時(shí)：

1.按照式（16）更新 Z

2.按照式（17）更新 H

3.按照式（18）更新 E

4.更新乘子Y1：

5.更新乘子Y2：

6.更新ρ：

輸入：數(shù)據(jù)矩陣X ，字典D，β＞0,λ＞0

初始化參數(shù)：

7.更新 u ：uk+1=min(ρuk,umax)

結(jié)束循環(huán)

輸出：系數(shù)矩陣Z*，噪聲矩陣E*

3.3 構(gòu)建親和度矩陣

得到表示系數(shù)矩陣Z*之后，可以從中導(dǎo)出圖形鄰接結(jié)構(gòu)和親和度矩陣。實(shí)際上，由于存在數(shù)據(jù)噪聲，數(shù)據(jù)點(diǎn)xi對(duì)應(yīng)的表示系數(shù)向量密度較小，直觀表現(xiàn)為數(shù)值較小。由于構(gòu)建親和度矩陣時(shí)只對(duì)數(shù)據(jù)的全局結(jié)構(gòu)感興趣，所以可以對(duì)每個(gè)樣本的系數(shù)向量進(jìn)行歸一化處理（即），并設(shè)定閾值將較小值置為0。經(jīng)過(guò)閾值操作后會(huì)得到真正的稀疏表示系數(shù)矩陣，并將親和度矩陣W 定義為

3.4 非負(fù)局部約束低秩子空間算法

定義親和度矩陣W后，剩下工作為構(gòu)建親和度圖，圖中的每個(gè)頂點(diǎn)對(duì)應(yīng)著每個(gè)數(shù)據(jù)點(diǎn)xi，兩頂點(diǎn)xi,xj之間連線的權(quán)重對(duì)應(yīng)著親和度矩陣W的元素wi,j，采用譜聚類算法如歸一化切割[24]對(duì)親和度圖進(jìn)行劃分，劃分得到的每一部分為一個(gè)簇，即完成聚類操作。完整流程見(jiàn)算法3。

算法3非負(fù)局部約束低秩子空間算法

輸入：數(shù)據(jù)矩陣X,子空間數(shù)目k，閾值θ

步驟：

1.通過(guò)算法1得到干凈字典D

2.通過(guò)算法2得到表示系數(shù)矩陣Z*

3.對(duì)表示系數(shù)矩陣Z*數(shù)據(jù)歸一化：，并根據(jù)給定閾值θ篩選值：

4.對(duì)親和度矩陣W應(yīng)用歸一化切割譜聚類算法，根據(jù)輸入的k值，分成k個(gè)聚類。

4 實(shí)驗(yàn)

本章將評(píng)估非負(fù)局部約束低秩子空間算法（NLRSI）對(duì)合成數(shù)據(jù)和實(shí)際計(jì)算機(jī)視覺(jué)任務(wù)（運(yùn)動(dòng)分割和手寫(xiě)數(shù)字聚類）的性能。為了直觀表達(dá)效果，將與基于譜聚類的最先進(jìn)的子空間聚類算法，如稀疏子空間算法（SSC）[9]，低秩表示子空間算法（LRR）[10]，魯棒形狀相互作用矩陣算法（RSI）[20]和非負(fù)低秩稀疏表示算法（NNLRSR）[25]進(jìn)行對(duì)比。選擇這些方法作為基準(zhǔn)，是因?yàn)檫@些算法在上述任務(wù)中的表現(xiàn)效果很好。為了進(jìn)行公平比較，根據(jù)Tron[26]定義的子空間聚類誤差作為性能的度量：子空間聚類誤差=錯(cuò)誤分類數(shù)據(jù)點(diǎn)/總數(shù)據(jù)點(diǎn)。

對(duì)于比較的算法，采用引用文獻(xiàn)中的參數(shù)作為輸入?yún)?shù)，其中對(duì)于Hopkins155運(yùn)動(dòng)分割數(shù)據(jù)庫(kù)[27]，稀疏子空間算法λ=20；低秩表示子空間算法λ=4；魯棒形狀相互作用矩陣算法λ=10；低秩稀疏表示算法λ1=100,λ2=10；非負(fù)局部約束低秩子空間算法β=5,λ=4.2。對(duì)于USPS手寫(xiě)數(shù)字?jǐn)?shù)據(jù)庫(kù)，稀疏子空間算法λ=0.05；低秩表示子空間算法λ=0.18；魯棒形狀相互作用矩陣算法 λ=0.01；低秩稀疏表示算法 λ1=0.01,λ2=10；非負(fù)局部約束低秩子空間算法的參數(shù)為β=0.17,λ=5。

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

圖1 各個(gè)算法對(duì)噪聲污染魯棒性

當(dāng) p=0與 p=0.3時(shí)，圖2與圖3顯示了親和度矩陣W 或者表示系數(shù)矩陣Z*（對(duì)于SSC，LRR，RSI算法）的塊對(duì)角結(jié)構(gòu)。

圖2 p=0時(shí)得到的親和度矩陣或者系數(shù)矩陣塊對(duì)角結(jié)構(gòu)

圖3 p=0.3時(shí)得到的親和度矩陣或者表示系數(shù)矩陣塊對(duì)角結(jié)構(gòu)

通過(guò)圖2與圖3的對(duì)比可以看出，非負(fù)低秩稀疏表示算法（NNLRSR）與非負(fù)局部約束低秩算法（NLRSI）對(duì)噪聲的魯棒性能較好，這表明通過(guò)局部約束強(qiáng)制更改矩陣結(jié)構(gòu)可以消除大量無(wú)關(guān)噪聲，使得聚類效果提升，這也在圖1的準(zhǔn)確率變化趨勢(shì)圖中有所體現(xiàn)。

4.2 運(yùn)動(dòng)分割

運(yùn)動(dòng)分割是指從視頻序列中提取一組二維點(diǎn)軌跡，將軌跡對(duì)應(yīng)于不同的剛體運(yùn)動(dòng)。這里，數(shù)據(jù)矩陣X的尺寸為2F×N，其中N是二維軌跡的數(shù)量，F(xiàn)是視頻中的幀數(shù)。在仿射投影模型下，n個(gè)不同運(yùn)動(dòng)對(duì)象相關(guān)聯(lián)的二維軌跡位于n個(gè)仿射子空間的組成的R2F空間中，至此運(yùn)動(dòng)分割問(wèn)題轉(zhuǎn)化為將所有的二維軌跡聚類到不同的子空間中，每個(gè)子空間對(duì)應(yīng)于一個(gè)運(yùn)動(dòng)對(duì)象。

本部分采用Hopkins155數(shù)據(jù)庫(kù)[27]（圖4為部分視頻序列效果截圖）測(cè)試算法效果，Hopkins155數(shù)據(jù)庫(kù)由155個(gè)序列組成，包括104個(gè)室內(nèi)場(chǎng)景序列，38個(gè)戶外交通場(chǎng)景序列和13個(gè)非剛性序列。其中有120個(gè)序列具有2個(gè)運(yùn)動(dòng)物體，其余35個(gè)序列具有3個(gè)運(yùn)動(dòng)物體。為了測(cè)試簡(jiǎn)便，根據(jù)運(yùn)動(dòng)物體數(shù)量將數(shù)據(jù)分為兩組，分別對(duì)這兩組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

圖4 Hopkins155數(shù)據(jù)庫(kù)部分序列聚類效果截圖

表1顯示了Hopkins155數(shù)據(jù)庫(kù)中155個(gè)序列聚類誤差，圖5與圖6展示了155個(gè)序列應(yīng)用非負(fù)局部約束低秩子空間算法（NLRSI）各自的聚類誤差，明顯的，二物體比三物體聚類誤差更小。同時(shí)從表1中的數(shù)據(jù)可以看出NLRSI算法的聚類誤差比其他算法誤差小，雖然低秩表示算法（LRR）的中位值更低，但是從平均值結(jié)果來(lái)看，低秩表示算法對(duì)于某些序列的聚類效果不穩(wěn)定，導(dǎo)致了誤差過(guò)大，拉高了平均值。

表1 各類算法在Hopkins155數(shù)據(jù)庫(kù)中的聚類誤差 %

4.3 手寫(xiě)數(shù)字

圖5 Hopkins155數(shù)據(jù)庫(kù)NLRSI算法兩物體序列聚類錯(cuò)誤率

圖6 Hopkins155數(shù)據(jù)庫(kù)NLRSI算法三物體序列聚類錯(cuò)誤率

手寫(xiě)數(shù)字聚類是指由不同人筆跡構(gòu)成的一組數(shù)字圖像，將數(shù)字相同的圖像分離出。這里采用美國(guó)郵政手寫(xiě)數(shù)字?jǐn)?shù)據(jù)庫(kù)（USPS）測(cè)試算法的聚類效果。圖7顯示了部分?jǐn)?shù)據(jù)樣本。該數(shù)據(jù)庫(kù)包含9 298張圖像，每張圖像為一個(gè)數(shù)字（0～9任意一個(gè)，如圖7所示），圖像的大小為16像素×16像素，因此數(shù)據(jù)矩陣X的維度為256。由于數(shù)據(jù)樣本過(guò)于龐大，對(duì)每一個(gè)數(shù)字隨機(jī)抽取100張圖像，共1 000張圖像作為數(shù)據(jù)樣本。同時(shí)為了測(cè)試聚類效果的多樣性，聚類的數(shù)目k設(shè)置為2～9，即分別抽取2個(gè)數(shù)字到9個(gè)數(shù)字評(píng)估聚類結(jié)果。

圖7 USPS數(shù)據(jù)庫(kù)部分?jǐn)?shù)據(jù)樣本

從表2可以看出非負(fù)局部約束低秩子空間算法（NLRSI）的聚類誤差相比其他算法較小，當(dāng)聚類數(shù)目k處于小值的時(shí)候，各個(gè)算法的聚類誤差相差很小，隨著k值的增大，聚類誤差都在增大，圖8所示的子空間數(shù)據(jù)結(jié)構(gòu)圖可以直觀看出隨著簇的數(shù)量增多，噪聲點(diǎn)隨之增多，這是由于聚類數(shù)目增多會(huì)導(dǎo)致一些數(shù)據(jù)點(diǎn)同時(shí)存在于多個(gè)子空間中，造成重復(fù)計(jì)算。從圖9變化趨勢(shì)圖中觀察到NLRSI算法聚類誤差率增長(zhǎng)較為緩和，說(shuō)明NLRSI算法對(duì)于這些異常點(diǎn)的甄別較為精準(zhǔn)。

表2 各類算法在USPS數(shù)據(jù)庫(kù)中的聚類誤差%

圖9 各類算法隨著聚類數(shù)目增多聚類誤差變化走勢(shì)圖

5 總結(jié)

本文提出了非負(fù)局部約束低秩子空間算法（NLRSI），該算法利用數(shù)據(jù)的局部稀疏結(jié)構(gòu)和子空間的全局低秩特征，構(gòu)造體現(xiàn)數(shù)據(jù)向量之間特點(diǎn)的親和度矩陣。理論分析保證了算法獲得的最優(yōu)親和度矩陣具有良好的聚類效果。同時(shí)實(shí)驗(yàn)結(jié)果表明，非負(fù)局部約束低秩子空間算法在運(yùn)動(dòng)分割和手寫(xiě)數(shù)字聚類任務(wù)中，優(yōu)于現(xiàn)存的幾種最先進(jìn)的聚類算法。但是該算法也存有不足之處：為了保證聚類準(zhǔn)確性，優(yōu)先對(duì)數(shù)據(jù)字典做去噪處理，增加了運(yùn)算時(shí)間；其次對(duì)于聚類數(shù)目較多的數(shù)據(jù)，聚類結(jié)果誤差較大。未來(lái)的工作將在保證準(zhǔn)確性的同時(shí)，縮短運(yùn)算時(shí)間，減少聚類誤差。