改進重加權稀疏子空間聚類算法

趙曉曉, 周治平, 賈 旋

(江南大學物聯網技術應用教育部工程研究中心, 江蘇 無錫 214122)

0 引 言

當今社會,各種各樣的數據充斥在人們的生活中,尤其是高維數據,廣泛地存在于機器學習、信號和圖像處理、計算機視覺、模式識別等領域。對高維數據進行聚類分析,維數的升高不僅會增加算法的計算時間和存儲需求,而且容易引發“維數災難”。特別是當高維數據含有干擾信息時,傳統的聚類算法已經不能很好地處理這類數據。但是,考慮到高維數據往往分布于多個低維子空間的并上,獲得高維數據的低維結構不僅能夠降低算法的計算開銷和存儲需求,而且能夠降低數據中的噪聲干擾,提高聚類分析的性能[1]。因而產生了子空間聚類[2]問題,其目的是將不同子空間上的高維數據聚類到本屬的低維子空間中。

當前,子空間聚類算法一直備受關注,已有大量改進算法和應用研究[3-4],特別是基于譜聚類的子空間聚類算法。該方法首先使用每個數據的局部信息建立數據點與數據點之間的相似度矩陣,然后通過譜聚類算法獲得數據劃分。文獻[5-6]通過求解數據與數據之間的低秩表示獲得相似度矩陣,提出了一種基于低秩表示(low rank representation, LRR)聚類算法。文獻[7]提出對稱低秩表示的子空間聚類算法,考慮將協同表示用于低秩矩陣恢復,保留高維數據的子空間結構,通過對稱低秩矩陣優化求解避免迭代奇異值分解(singular value decomposition, SVD)計算降低復雜度。文獻[8]利用數據關聯的優點聚合高關聯性數據,提出基于最小二乘回歸(least squares regression, LSR)的子空間聚類算法,采用Frobenius范數對系數矩陣進行約束。文獻[9]深度分析了聚類效率,根據組效應建立相似度矩陣,提出了基于平滑表示框架(smooth representation, SMR)的子空間聚類算法。

文獻[10-11]提出的稀疏子空間聚類算法(sparse subspace clustering, SSC)是近年來子空間聚類算法的研究熱點,利用l1范數得到數據樣本的稀疏表示,利用系數矩陣構造相似度矩陣。能夠很好地處理高維數據的聚類問題,但當數據集被噪聲污染或者存在樣本缺失時效果較差。針對受噪聲影響或嚴重損壞的數據,文獻[12]將原始數據矩陣分解為干凈數據、高斯噪聲數據和系數誤差矩陣,利用低秩矩陣恢復得到干凈的字典,提高算法性能。文獻[13]針對稀疏子空間聚類中缺損字典的情況,提出和評估了兩種新的子空間聚類算法,在大比例缺損字典時有著更好的效果。為了提高子空間聚類算法的魯棒性,文獻[14]提出結合圖正則化和判別式字典來改進低秩表示方法,判別式字典的引入克服了噪聲數據對高維數據的影響,即使是受損嚴重的數據也能夠有效獲取高維數據的局部和全局結構特征。文獻[15]利用數據點的空間幾何結構在稀疏優化框架中對表示系數進行加權,提出了加權的稀疏優化框架。文獻[16]利用重加權的l1范數代替傳統l1范數,建立了重加權的l1最小化稀疏優化框架,并基于此提出一種重加權的SSC(reweighted SSC, RSSC)算法。文獻[17]提出結構化SSC(structured sparse subspace clustering,SSSC)算法,采用統一的優化框架來自動結合系數矩陣和譜聚類,將譜聚類輸出定義為子空間結構矩陣,反饋作為下一次迭代的重加權表示矩陣。文獻[18]提出基于正交匹配追蹤的可擴展SSC(scalable SSC by orthogonal matching pursuit, SSC-OMP)算法,用來求解稀疏子空間模型的稀疏解。文獻[19]針對OMP方法用于大規模數據時增加計算復雜度的問題,提出學習OMP(learning OMP,LOMP)算法來訓練單層神經網絡模型,用來加快基于l0編碼的SSC算法。文獻[20]利用改進的SSC算法選擇適當的波段帶子集,以解決高光譜圖像分類問題。文獻[21-22]利用加權SSC算法來解決圖像分割問題。

盡管目前關于SSC的研究很多,并取得了豐富的研究成果,但仍有一些問題有待進一步研究。SSC的核心在于利用合理的稀疏優化框架確保表示系數矩陣具有塊對角結構,從而揭示數據的子空間特性,指導聚類劃分。為了精確聚類,需要盡可能確保表示系數矩陣滿足類間稀疏、類內一致性。理論來說l0優化框架能夠很好地解決這一問題,但其優化問題是NP難問題。當前主要采用的l1優化框架求取數據稀疏表示,但是求得的表示系數矩陣存在一定的缺陷,不能很好地滿足類間稀疏、類內一致性。因此,本文在文獻[16]建立的重加權l1優化框架中引入反正切函數的概念,通過一個選擇函數使其能夠同時滿足l0最小化在數據較小時斜率趨于無窮和數據較大時斜率趨于零的兩個重要特征,從而更好地逼近l0最小化,并基于此提出了一種改進的RSSC(evolving RSSC, ERSSC)。

1 重加權的稀疏優化框架

為了獲得每個數據點的稀疏表示,采用重加權的l1最小化對其進行凸松弛處理。同時考慮到實際問題中,數據點通?；旌现∈璧钠嫣刂岛驮肼?。另外,數據常常分布于仿射子空間的并上而非線性子空間,從而建立重加權的稀疏優化框架,即

s.t.Y=YC+Z,1TC=1T, diag(C)=0

(1)

式中,C=[c1c2…cN]∈RN×N表示系數矩陣,每一列對應每個數據點的稀疏表示；diag(C)∈RN為矩陣C的對角元素組成的向量;W=[w1w2…wn]∈RN×N為加權對角矩陣;Z為噪聲矩陣;λz為噪聲系數。

2 本文算法

2.1 幾種函數的比較

SSC算法的原理在于根據數據自表征性,利用稀疏優化框架獲取最優的稀疏表示。最好的稀疏優化方法是l0最小化框架,即直接通過函數計算矩陣的非零個數,但這是一個NP難問題。因此,文獻[11]考慮l1最小化,并證明了在恰當的子空間排列和數據分布條件下,l1最小化能夠成功地求得期望的稀疏表示。文獻[16]采用重加權的l1最小化,以對數函數的形式逼近l0最小化,獲得比l1最小化更好的聚類結果。本文同時考慮反正切函數的形式,用以優化對數函數,使其能夠更好地逼近l0最小化。以上問題，可以通過一個簡單的例子說明。首先定義4個懲罰函數

f0(x)=1{x≠0}

(2)

f1(x)=x

(3)

flog(x)=log(x+ε)

(4)

(5)

相應的函數曲線如圖1所示。

(1)f0(x)函數能夠直接對非零個數進行計算,因而基于該函數的最小化框架能夠求得最稀疏解。但是,該函數卻是不連續函數,難以求解。因此,重點分析f0(x)的特性,以便更好地近似于該函數。其特性在于:在x→0+時,其斜率為正無窮,在x→0-時,其斜率為負無窮,值為0;在x≠0時,斜率為0,值為1。

(2)f1(x)函數是一個斜率恒為1的正比例函數,雖然不具備f0(x)函數的顯著特點,但是基于該函數的最小化框架能夠在合適的條件下近似求得數據的稀疏表示,其可行性在文獻[11]中已被證明。

圖1 四個懲罰函數的函數曲線圖Fig.1 Graph of four penalty functions

(3)flog(x)函數為一個對數函數,具有f0(x)函數的一個重要特點:ε→0時,在x→0+或x→0-時斜率為正無窮或負無窮。隨著x的增加其斜率逐漸趨近于0,但是卻過于緩慢,無法保證x≠0時的斜率。因此,采用該函數的重加權稀疏優化框架雖然能夠獲得相較于f1(x)函數更好的稀疏表示,卻仍有改進的余地。

(4) 對于反正切函數fatan(x),其性能隨著σ的變化而變化。fatan(x)函數在σ→0+時同對數函數flog(x)相似,同樣具有f0(x)函數的一個重要特點:其斜率在x→0+或x→0-時為正無窮或負無窮。但此時同樣不能保證x≠0時的斜率,甚至其斜率還要高于對數函數;當σ>0時,特別在σ較大時,雖然fatan(x)函數在x→0斜率較低,無法滿足優化要求,但是卻能滿足f0(x)函數的另一個特點:在x≠0時,其斜率趨近于0。

綜合可知:雖然反正切函數有著f0(x)函數的兩個特點,卻很難平衡參數σ,同時滿足需求。因此,考慮將對數函數和反正切函數的特點進行中和,設計了分段函數flog-atan(x)，即

(6)

該函數在x較小時為對數函數,較大時為反正切函數,使得flog-atan(x)函數能夠同時滿足f0(x)函數的兩個特點。

2.2 加權矩陣更新策略

本文以flog-atan(x)函數模型替換flog(x)函數模型,使其能夠更好地逼近模型稀疏解。同文獻[16]相似,為了將flog-atan(x)函數優化引入到子空間表示模型中,本文同樣采用重加權的l1最小化進行模型求解。下面將討論加權矩陣W的更新算法。

首先,考慮到flog-atan(x)函數是一個分段函數,為了不顯得加權矩陣W的更新過于突兀,引入選擇矩陣S,用來選擇不同狀態下的W更新措施,即

si=sign(max(ε,xi)-δ)

(7)

接著,考慮以下問題:

s.t.Ax=b

(8)

(9)

在第k個迭代周期,函數的局部最小化可以分成靜態部分和動態部分。式(9)中,只有xi為變量,其余全為常量。因此,第k+1個迭代周期的最小化問題,等價為求解式(9)動態部分的最小化,其數學模型為

s.t.Ax=b

(10)

式(10)由常量系數和x的l1最小化乘積構成。而重加權的l1最小化,就是通過不斷地更新常量系數優化函數模型,使其具有flog(x)函數和fatan(x)函數的導數性質,滿足l0最小化的兩個重要特征。其中,文獻[16]引入flog(x)函數,其加權矩陣更新公式為

(11)

確保在xi較小時,滿足斜率趨于無窮的特性。

(12)

最后,討論本文采用的flog-atan(x)函數形式的重加權l1最小化模型,其加權矩陣W在第k個迭代周期的更新方法為

(13)

2.3 算法流程

同RSSC[16]算法相同,本文算法的子空間模型仍然是一個可分離的凸規劃問題,采用交替方向乘子法,將模型求解轉化成多個子問題迭代求解,最終可求得模型解。此時求得模型解,即數據的自表征矩陣,從而可以建立數據的相似度矩陣。隨后,利用譜聚類方法可以獲得最終的聚類結果。其流程如下：

算法1ERSSC算法流程

輸入Y∈RM×N

初始化A(0),C(0),Δ(0),n,tol,ρ,k=0

1:while(‖A(k+1)-A(k)‖>tol或‖C(k+1)-C(k)‖>tol)do

2: 通過求解下式來更新A(k+1):

(λzYTY+ρI)A(k+1)=λzYTY+ρC(k)-Δ(k)

3: 更新C(k+1)=J-diag(J),其中

4: 根據式(7)更新S(k+1)

5: 根據式(13)更新W(k+1)

6:Δ(k+1)=Δ(k)+ρ(A(k+1)-C(k+1))

7:k=k+1

8:endwhile

9: 歸一化矩陣C的列向量ci=ci/‖ci‖∞

10: 建立相似度矩陣AF=|C|+|C|T

11: 根據AF執行譜聚類算法

輸出類標簽

3 實驗分析

對比算法均采用先進的子空間聚類算法,如LRR[6]、LSR[8]、SMR[9]、SSC[11]、RSSC[16],同時使用其作者提供的Matlab代碼進行測試。所有仿真實驗基于計算機硬件配置為:Intel Core i5-4200M CPU 2.5 GHz、4 GB RAM的Matlab 2010b平臺。同時,為了公平比較各聚類算法的性能,統一使用誤差率來評估所有算法的聚類性能。

3.1 參數選取

在對The Extended Yale B數據[24]測試時:對于LRR[6],參照原文獻,選定λ=0.15;對于LSR[8]的兩種方法LSR1和LSR2,選用文獻中采用的參數均為λ=0.004;對于SMR,設定α=20,獲得了同文獻[9]相似的結果;對于SSC[11],選用文獻中采用的參數α=20;對于RSSC[16],選用文獻中設定的參數α=20，ε1=9×10-3，ε2=2.7×10-3;本文算法,選用α=20，ε1=9×10-3，ε2=2.7×10-4,設定δ=1×10-5，σ=25。

3.2 The Hopkins 155 數據集

The Hopkins 155數據集包含155個視頻序列,其中120個序列有2個移動目標,35個序列有3個移動目標,分別對應二維或三維子空間。主要分為3類:棋盤格、交通和鏈接式或非剛性運動序列。這些視頻序列都非常短,時間往往低于1 s或幾秒。該數據集中的一些樣本序列如圖2所示。

圖2 The Hopkins 155 數據集中的部分樣本序列Fig.2 Some sample sequences from the Hopkins 155 dataset

實驗中分別對2F維特征軌跡數據和經過PCA算法投影2F維特征軌跡獲得的4n維子空間進行測試,n表示移動目標的個數。結果如表1和表2所示。

表1 在The Hopkins 155數據集的2F維數據的聚類誤差

表2 The Hopkins 155數據集的4n維數據的聚類誤差

由表1、表2中可知：

(1) 針對3移動目標,ERSSC算法的聚類誤差分別從2.01%和2.50%降到了1.96%和1.89%,聚類性能較其他子空間算法較優。在2F維移動軌跡中,ERSSC算法在2移動目標時,聚類誤差稍高于RSSC算法,卻遠低于其他子空間算法。同時,考慮到ERSSC算法為RSSC算法的改進算法,以選擇矩陣S的方式將RSSC算法的優點引入ERSSC算法中。假若在處理2移動目標時設定S為零矩陣,ERSSC算法就轉化成RSSC算法,能在各子空間算法中獲得性能最優的聚類結果。由此可以說明在該數據集上,ERSSC算法的聚類性能要優于其他子空間聚類算法。

(2) 相較于2F維移動軌跡,ERSSC算法在4n維移動軌跡中的聚類性能相較于其他子空間算法更加優越。一般由于數據經過PCA處理導致信息遺失,聚類算法在4n維移動軌跡中的聚類誤差要高于2F維移動軌跡。但是相較于其他子空間算法,尤其是性能較優的RSSC算法,ERSSC算法在處理4n維移動軌跡時聚類誤差波動較小,魯棒性更高。同時,不論是2移動目標還是3移動目標,ERSSC算法的聚類誤差都是最低的,性能優勢更加明顯。

3.3 The Extended Yale B 數據集

The Extended Yale B 數據集包含38個對象的人臉照片,每個對象含有64張在不同光照條件下拍攝的正面照,每張照片大小為192×168。該數據集中的一些樣本如圖3所示。

圖3 The Extended Yale B數據集中的部分樣本Fig.3 Some samples from the Extended Yale B dataset

為了降低計算復雜度和存儲開銷,對每張照片采樣減小為包含48×42像素的圖片,作為一個數據點。為了研究主體數目對聚類效果的影響,38個主體劃分為4個群組,即1:10,11:20,21:30,31:38。對于前3個群組,選取n∈{2,3,5,8,10}作為主體數；對于第4個群組,選取n∈{2,3,5,8}作為主體數。選取不同n值分別進行測試,實驗結果如表3所示。

表3 The Extended Yale 數據集上的聚類誤差

由表3可知:SMR、SSC、RSSC和ERSSC等子空間算法在the Extended Yale B數據集中都獲得了較好的聚類性能,RSSC和ERSSC算法的聚類誤差甚至低于5%。也就是說,相較于其他子空間算法,ERSSC算法有著更好的聚類性能,尤其是在主體數較低時,其性能優勢更加明顯,聚類誤差甚至低于1%。

4 結 論

本文將反正切函數的概念引入到重加權的l1最小化框架中,使其相較于原重加權l1最小化和l1最小化更逼近l0最小化。同時分析了重加權的l1最小化框架機制,討論了新加權矩陣的更新方法,提出了改進重加權SSC算法。通過實驗,將該算法同重加權稀疏子空間算法和其他子空間算法進行對比。結果表明,在the Hopkins 155數據集和the Extended Yale B數據集中,都獲得了相較于其他子空間聚類算法更優的聚類性能。

[1] 王衛衛, 李小平, 馮象初, 等. 稀疏子空間聚類綜述[J]. 自動化學報, 2015, 41(8): 1373-1384.

WANG W W, LI X P, FENG X C, et al. A survey on sparse subspace clustering[J]. Acta Automatica Sinica, 2015, 41(8): 1373-1384.

[2] PARSONS L, HAQUE E, LIU H. Subspace clustering for high dimensional data: a review[J]. ACM SIGKDD Explorations New-sletter, 2004, 6(1): 90-105.

[3] GAN G, NG M K P. Subspace clustering using affinity propagation[J]. Pattern Recognition, 2015, 48(4):1455-1464.

[4] PENG X, YI Z, TANG H. Robust subspace clustering via thresholding ridge regression[C]∥Proc.of the AIAA Conference on Artificial Intelligence,2015: 3827-3833.

[5] LIU G, LIN Z, YU Y. Robust subspace segmentation by low-rank representation[C]∥Proc.of the 27th International Conference on Machine Learning, 2010: 663-670.

[6] CHEN J, ZHANG H, MAO H, et al. Symmetric low-rank re-presentation for subspace clustering[J]. Neurocomputing, 2016, 173(P3): 1192-1202.

[7] LIU G, LIN Z, YAN S, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Trans.on Pattern Analysis and Machine Intelligence,2013,35(1):171-184.

[8] LU C Y, MIN H, ZHAO Z Q, et al. Robust and efficient subspace segmentation via least squares regression[C]∥Proc.of the European Conference on Computer Vision, 2012: 347-360.

[9] HU H, LIN Z, FENG J, et al. Smooth representation clustering[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2014: 3834-3841.

[10] ELHAMIFAR E, VIDAL R. Sparse subspace clustering[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2009: 2790-2797.

[11] ELHAMIFAR E, VIDAL R. Sparse subspace clustering: algorithm, theory, and applications[J]. IEEE Trans.on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2765-2781.

[12] VIDAL R, FAVARO P. Low rank subspace clustering (LRSC)[J]. Pattern Recognition Letters, 2014, 43(1): 47-61.

[13] YANG C, ROBINSON D, VIDAL R. Sparse subspace clustering with missing entries[C]∥Proc.of the 32nd International Conference on Machine Learning, 2015: 2463-2472.

[14] WANG J, SHI D, CHENG D, et al. LRSR: low-rank-sparse representation for subspace clustering[J]. Neurocomputing, 2016, 214: 1026-1037.

[15] PHAM D S, BUDHADITYA S, PHUNG D, et al. Improved subspace clustering via exploitation of spatial constraints[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Re-cognition, 2012: 550-557.

[16] XU J, XU K, CHEN K, et al. Reweighted sparse subspace clustering[J]. Computer Vision and Image Understanding, 2015, 138: 25-37.

[17] LI C G, VIDAL R. Structured sparse subspace clustering: a unified optimization framework[C]∥Proc.of the IEEE Confe-rence on Computer Vision and Pattern Recognition, 2015: 277-286.

[18] YOU C, ROBINSON D, VIDAL R. Scalable sparse subspace clustering by orthogonal matching pursuit[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2016: 3918-3927.

[19] LI J, KONG Y, FU Y. Sparse subspace clustering by learning approximationl0codes[C]∥Proc.of the AIAA Conference on Artificial Intelligence, 2017: 2189-2195.

[20] SUN W, ZHANG L, DU B, et al. Band selection using improved sparse subspace clustering for hyperspectral imagery classification[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2015,8(6):2784-2797.

[21] 李濤, 王衛衛, 翟棟, 等. 圖像分割的加權稀疏子空間聚類方法[J]. 系統工程與電子技術, 2014, 36(3): 580-585.

LI T, WANG W W, ZHAI D, et al. Weighted-sparse subspace clustering method for image segmentation[J]. Systems Engineering and Electronics, 2014, 36(3): 580-585.

[22] 岳溫川,王衛衛,李小平.基于加權稀疏子空間聚類多特征融合圖像分割[J].系統工程與電子技術,2016,38(9):2184-2191.

YUE W C, WANG W W, LI X P. Multi-feature fusion image segmentation based on weighted-sparse subspace clustering[J]. Systems Engineering and Electronics,2016,38(9):2184-2191.

[23] LEE K C, HO J, KRIEGMAN D J. Acquiring linear subspaces for face recognition under variable lighting[J]. IEEE Trans.on Pattern Analysis and Machine Intelligence, 2005, 27(5): 684-698.

[24] TRON R, VIDAL R. A benchmark for the comparison of 3rd motion segmentation algorithms[C]∥Proc.of the IEEE Conference on Computer Vision and Pattern Recognition, 2007: 1-8.