改進(jìn)的稀疏子空間聚類(lèi)算法*

張彩霞，胡紅萍，白艷萍（中北大學(xué)理學(xué)院，太原 030051）

改進(jìn)的稀疏子空間聚類(lèi)算法*

張彩霞，胡紅萍，白艷萍
（中北大學(xué)理學(xué)院，太原 030051）

在現(xiàn)有的稀疏子空間聚類(lèi)算法理論基礎(chǔ)上提出一個(gè)改進(jìn)的稀疏子空間聚類(lèi)算法:迭代加權(quán)的稀疏子空間聚類(lèi)。稀疏子空間聚類(lèi)通過(guò)解決l1最小化算法并應(yīng)用譜聚類(lèi)把高維數(shù)據(jù)點(diǎn)聚類(lèi)到不同的子空間，從而聚類(lèi)數(shù)據(jù)。迭代加權(quán)的l1算法比傳統(tǒng)的l1算法有更公平的懲罰值，平衡了數(shù)據(jù)數(shù)量級(jí)的影響。此算法應(yīng)用到稀疏子空間聚類(lèi)中，改進(jìn)了傳統(tǒng)稀疏子空間聚類(lèi)對(duì)數(shù)據(jù)聚類(lèi)的性能。仿真實(shí)驗(yàn)對(duì)Yale B人臉數(shù)據(jù)圖像進(jìn)行識(shí)別分類(lèi)，得到了很好的聚類(lèi)效果，證明了改進(jìn)算法的優(yōu)越性。

稀疏子空間聚類(lèi)，迭代加權(quán)，譜聚類(lèi)算法，人臉識(shí)別

0 引言

在很多實(shí)際應(yīng)用中，高維數(shù)據(jù)無(wú)處不在，如計(jì)算機(jī)視覺(jué)，圖像處理，運(yùn)動(dòng)分割，人臉識(shí)別等。實(shí)際中，高維數(shù)據(jù)可以被相應(yīng)的低維子空間分別表示。

近年來(lái)，子空間聚類(lèi)在壓縮感知問(wèn)題中的應(yīng)用已吸引了很多學(xué)者的注意，在信息科學(xué)中是一個(gè)很熱的研究領(lǐng)域。子空間聚類(lèi)的目的在于把高維數(shù)據(jù)劃分在其潛在的子空間并應(yīng)用到盡可能多的領(lǐng)域中。子空間聚類(lèi)算法有4種:迭代法［1-2］，代數(shù)法［3］，統(tǒng)計(jì)法［4］和譜聚類(lèi)方法［5-7］，而前3種方法都需要知道子空間的個(gè)數(shù)和維數(shù)或?qū)?shù)據(jù)初始值、噪聲、奇點(diǎn)比較敏感，譜聚類(lèi)算法利用數(shù)據(jù)點(diǎn)之間的信息建立相似性，能夠很好地避免上述缺點(diǎn)。

稀疏子空間聚類(lèi)是基于譜聚類(lèi)提出的一種稀疏表達(dá)的聚類(lèi)方法。Elhamifar等［8］利用稀疏恢復(fù)算法的先進(jìn)性提出一種稀疏子空間聚類(lèi)算法（Sparse Subspace Clustering，SSC），通過(guò)稀疏表示（Sparse representation，SR）構(gòu)造相似度矩陣，并應(yīng)用到譜聚類(lèi)算法中，從而聚類(lèi)數(shù)據(jù)。在稀疏算法中l(wèi)0最小化算法:是NP難問(wèn)題，不能求解。Chen，Donoho和Saunders［10］提出了應(yīng)用l1最小化算法:代替l0，這樣的轉(zhuǎn)變使難以解決的非凸優(yōu)化問(wèn)題轉(zhuǎn)化為凸優(yōu)化問(wèn)題。近年來(lái)l1范數(shù)優(yōu)化應(yīng)用十分廣泛，同時(shí)也引出了一個(gè)研究熱點(diǎn)，就是怎么能提升l1范數(shù)優(yōu)化性能。本文介紹了一種算法迭代加權(quán)的l1最小化算法［11］，迭代加權(quán)值平衡了l1和l0的差異，使得l1更能逼近l0。迭代加權(quán)的l1最小化算法應(yīng)用到稀疏子空間聚中，得到本文的改進(jìn)算法:迭代加權(quán)的稀疏子空間聚類(lèi)。通過(guò)迭代加權(quán)的l1最小化，得到了更加稀疏的系數(shù)矩陣，能夠?qū)?shù)據(jù)做有效的聚類(lèi)。仿真實(shí)驗(yàn)中用此改進(jìn)的稀疏子空間聚類(lèi)算法對(duì)Yale B人臉數(shù)據(jù)圖像進(jìn)行識(shí)別分類(lèi)，得出很好的聚類(lèi)效果。

1 稀疏子空間聚類(lèi)優(yōu)化算法

位于線性或仿射集合的高維數(shù)據(jù)可以稀疏地被同一個(gè)子空間的點(diǎn)線性或者仿射表示。本文通過(guò)文獻(xiàn)［8］中稀疏表示技巧獲得高維數(shù)據(jù)的稀疏表示。

設(shè)有N個(gè)D維數(shù)據(jù){yi}，處于RD空間的n個(gè)線性子空間{Sl}中，子空間的維數(shù)分別為{dl}ni=1，定義一個(gè)矩陣Y為:

其中，C為稀疏系數(shù)矩陣，E為稀疏奇異值矩陣，Z為噪聲矩陣，系數(shù)，。通常，稀疏子空間聚類(lèi)基于系數(shù)向量的一維稀疏性或系數(shù)矩陣的二維稀疏性來(lái)建立高維數(shù)據(jù)在低維子空間的表示，利用表示系數(shù)矩陣Z構(gòu)造數(shù)據(jù)的相似度矩陣，最后利用譜聚類(lèi)算法得到最終的聚類(lèi)結(jié)果。

本文的算法不需要提前知道子空間個(gè)數(shù)和維數(shù)最優(yōu)化的求解通過(guò)ADMM［12］（Alternating Direction Method of Multipliers）算法下完成，稀疏子空間聚類(lèi)算法過(guò)程如下:

1）把n維線性或仿射空間的數(shù)據(jù)點(diǎn){yi}Ni作為輸入利用稀疏子空間式（2），獲得稀疏系數(shù)矩陣C，算法實(shí)現(xiàn)在ADMM算法下完成；

3）根據(jù)稀疏系數(shù)矩陣建立相似加權(quán)圖，每個(gè)數(shù)據(jù)點(diǎn)只與其稀疏表示中的數(shù)據(jù)點(diǎn)連接，不同子空間的數(shù)據(jù)點(diǎn)無(wú)連接，權(quán)值矩陣為；

4）把相似加權(quán)圖應(yīng)用到譜聚類(lèi)算法［13］中，求Laplacian矩陣，L=I-D-1W其中

對(duì)L求特征值，得到子空間個(gè)數(shù)n為特征值零的次數(shù)，獲得前n個(gè)小特征值，把其對(duì)應(yīng)的特征向量形成N×n的矩陣U；

5）把U的每一行作為n維空間的一個(gè)向量，對(duì)U進(jìn)行K-means聚類(lèi)，N行所對(duì)應(yīng)的類(lèi)就是其N(xiāo)個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)的類(lèi)。得出輸出數(shù)據(jù)點(diǎn)所對(duì)應(yīng)的類(lèi)Y1，Y2，…，Yn。

2 迭代加權(quán)的l1最小化算法

Candes［14］等人通過(guò)多次試驗(yàn)證明了迭代更新權(quán)值的l1范數(shù)很好地恢復(fù)了l1最小化結(jié)構(gòu)的性能，l1范數(shù)和l0范數(shù)關(guān)鍵的不同可由l1范數(shù)和l0范數(shù)的定義可知，l1范數(shù)中系數(shù)越大懲罰值越大，系數(shù)越小懲罰值越小。然而l0范數(shù)中懲罰值都相等，它依賴(lài)于系數(shù)的大小。加權(quán)的l1范數(shù)比l1范數(shù)能夠有更公平的懲罰值，可以使系數(shù)結(jié)構(gòu)更稀疏。下面用一個(gè)例子加以說(shuō)明。

例:給出一個(gè)m×n的矩陣A，m≤n，非零向量b∈Rm，找出Ax=b的最稀疏解。且

上述問(wèn)題的解可為:p0，p1，pw0，pw1。其中由于P0中‖x‖0表示x中非零元的個(gè)數(shù)，矩陣A中m＜n，可能有無(wú)數(shù)的解。所以P0為非凸的NP難題，相似的解用P1代替 P1:。分別給P0和P1加上權(quán)值可得:解:，P1的解:。如果給定權(quán)值那么，因此，能夠看到Pw1比 P1更稀疏。而且Pw1的解更接近P0。

如何給定權(quán)值使得它能夠改進(jìn)線性方程Ax=b解的稀疏性，這是需要考慮的問(wèn)題。權(quán)值越大就會(huì)使xi的懲罰因子減小甚至接近于0，權(quán)值越小就會(huì)使xi的懲罰因子變大并且是非零的。加權(quán)算法已經(jīng)在很多研究領(lǐng)域應(yīng)用，Gorodnitsky和Ra0等人［14-18］提出應(yīng)用迭代的思想去求得有約束條件的稀疏解的加權(quán)值，迭代的過(guò)程為:

Step1:迭代次數(shù)l，wi（0）=1，i=1，…，n

Step2:解決加權(quán)的l1最小化問(wèn)題:

Step3:更新權(quán)值:

Step4:當(dāng)l達(dá)到最大迭代次數(shù)lmax時(shí)終止迭代，否則返回step2重新迭代。

在第3步迭代中ε＞0是為了提高穩(wěn)定性，確保x（l）中的零值部分可以存在較小的非零值，l1懲罰函數(shù)權(quán)值中和了數(shù)據(jù)數(shù)量級(jí)的影響。通常ε的選擇對(duì)數(shù)據(jù)的恢復(fù)過(guò)程具有很好的魯棒性。

3 改進(jìn)的稀疏子空間聚類(lèi)

本文把迭代加權(quán)的l1最小化算法應(yīng)用到稀疏子空間聚類(lèi)中，得到了改進(jìn)的稀疏子空間聚類(lèi):迭代加權(quán)的稀疏子空間聚類(lèi)，聚類(lèi)算法如下:

在仿射問(wèn)題中優(yōu)化算法（3）可以描述為:

其中，W為權(quán)值矩陣，C為稀疏系數(shù)矩陣，E為稀疏奇異值矩陣，Z為噪聲矩陣，A是一個(gè)輔助矩陣可以幫助獲得更快的更新，是兩矩陣的廣義乘法，系數(shù)。求解通過(guò)ADMM［12］（Alternating Direction Method of Multipliers）算法求解加權(quán)的l1最小化問(wèn)題，參數(shù)ρ＞0，δ∈Rn和Δ∈Rn×n作為拉格朗日乘子對(duì)于約束ATI=1，A=C-diag（C），式（4）通過(guò)ADMM算法可等價(jià)于:

ADMM算法是解決全局最優(yōu)的迭代算法，在每一步迭代中通過(guò)得到的稀疏矩陣C后更新權(quán)值矩陣，具體算法過(guò)程如下:

輸入:數(shù)據(jù)點(diǎn)集合Y∈Rm×n，初始化:max-Iter=200，k=0，W（0）=1，A（0）=C（0）=E（0）=δ（0）=0

輸出:稀疏系數(shù)矩陣C=C（k）

把得到的稀疏系數(shù)矩陣應(yīng)用到譜聚類(lèi)中最后得出聚類(lèi)結(jié)果。

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

實(shí)驗(yàn)數(shù)據(jù)來(lái)自Yale B數(shù)據(jù)集，為1 024維的高維數(shù)據(jù)，包含38個(gè)不同人的人臉數(shù)據(jù)圖像，每一個(gè)人在不同變換條件下的正面臉部圖像有64個(gè)，每一個(gè)圖像由1 024維向量表示，為了清楚的理解Yale B數(shù)據(jù)，把像素點(diǎn)表示為32×32的像素讀成圖片如圖1所示。

圖1 兩人的人臉圖像

為了突出對(duì)稀疏子空間聚類(lèi)算法做出的改進(jìn)，實(shí)驗(yàn)選取了10個(gè)不同人的人臉圖像，從算法平均聚類(lèi)錯(cuò)誤率來(lái)說(shuō)明迭代加權(quán)的稀疏子空間聚類(lèi)算法優(yōu)于傳統(tǒng)的稀疏子空間聚類(lèi)。error1表示傳統(tǒng)的稀疏子空間聚類(lèi)算法平均聚類(lèi)錯(cuò)誤率，error2表示改進(jìn)的稀疏子空間聚類(lèi)算法平均聚類(lèi)錯(cuò)誤率。N表示人臉圖像個(gè)數(shù)，S表示分類(lèi)個(gè)數(shù)，經(jīng)過(guò)多次試驗(yàn)驗(yàn)證選取迭代權(quán)值中的ε=2×10-4，所有的算法均在MATLAB R2014a下運(yùn)行。

從表1和圖2得出:人臉個(gè)數(shù)相同時(shí)，改進(jìn)的稀疏子空間聚類(lèi)算法的平均聚類(lèi)錯(cuò)誤率低于傳統(tǒng)的稀疏子空間聚類(lèi)算法的平均聚類(lèi)錯(cuò)誤率，并且兩種算法的平均聚類(lèi)錯(cuò)誤率都低于5%。當(dāng)分類(lèi)個(gè)數(shù)增加時(shí)，兩種算法的平均聚類(lèi)錯(cuò)誤率都呈增長(zhǎng)趨勢(shì)，但是改進(jìn)算法的增長(zhǎng)幅度低于傳統(tǒng)算法的增長(zhǎng)幅度，可以說(shuō)明改進(jìn)的算法對(duì)數(shù)據(jù)具有很好的魯棒性。人臉圖像的數(shù)據(jù)點(diǎn)會(huì)因?yàn)檎`差使得數(shù)據(jù)有損，可以表明此改進(jìn)算法可以處理因?yàn)檎`差而損失數(shù)據(jù)的能力。有效地恢復(fù)數(shù)據(jù)，減小了聚類(lèi)誤差。

表1 算法平均聚類(lèi)錯(cuò)誤率

圖2 兩算法的誤差對(duì)比

5 結(jié)論

本文提出了一種改進(jìn)的稀疏子空間聚類(lèi)算法:迭代加權(quán)的最小化算法應(yīng)用到稀疏子空間聚類(lèi)算法中，得到了迭代加權(quán)的稀疏子空間聚類(lèi)。稀疏子空間聚類(lèi)通過(guò)解決最小化問(wèn)題并且應(yīng)用譜聚類(lèi)算法把高維數(shù)據(jù)點(diǎn)聚類(lèi)到不同的子空間，從而聚類(lèi)數(shù)據(jù)。迭代加權(quán)的范數(shù)比傳統(tǒng)的范數(shù)能夠有更公平的懲罰值更接近可以使系數(shù)結(jié)構(gòu)更稀疏。此改進(jìn)算法對(duì)Yale B數(shù)據(jù)集10個(gè)不同人的人臉圖像進(jìn)行識(shí)別分類(lèi)，相比原來(lái)算法得到了很好的聚類(lèi)效果，降低了聚類(lèi)誤差，對(duì)高維數(shù)據(jù)集做有效的分類(lèi)，可以應(yīng)用到更多的研究領(lǐng)域特別是對(duì)大數(shù)據(jù)的處理。具有很強(qiáng)的實(shí)用性。

［1］TSENG P.Subspace clustering［J］.Signal Processing Magazine，2001，28（2）:52-68.

［2］HO J，YANG M H，LIM J，et al.Clustering appearances of objects under varying illumination conditions［C］//IEEE Conference on Computer Vision and Recognition，2003.

［3］ COSTERIRA J，KANADE T.A multibody factorization method for independently moving objects［J］.International Journal of Computer Vision，1998，29（3）:159-179.

［4］TIPPING M，BISHOP C.Mixtures of probabilistic principal component analyzers［J］.Neural Computation，1999，11 （2）:443-482.

［5］Ng A，Weiss Y，Jordan.On spectral clustering:analysis and algorithm［J］.Neural Information Processing Systems，2001: 849-856.

［6］YAN J，POLLEFEYS M.A general framework for motion segmentation:independent. articulated，rigid. non-rigid. Degenerate and non-degenerate［C］//in European Conf.On computer，2006:94-106.

［7］CHEN，LERMAN G.Spectral curvature clustering（SSC）［J］.International Journal of Computer Vision，2009，81 （3）:317-330.

［8］ELHAMIFAR E，VIDAL R.Sparse subspace clustering:algorithm，theory，and applications［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）: 2765-2781.

［9］BARANIUK R.A lecture on compressive sensing［J］.IEEE Signal Processing Magazine，2007（7）:22-25.

［10］CHEN S，DONOHO D，SAUNDERS M.Atimic decomposition by basis pursuit［J］.SIAM J Sci Comput，1998，20（1）: 33-61.

［11］ CANDES F J，MICHAEL V S，BOYD S P.Enhancing sparisity by reweightedminimization［J］.FourierAnal.Appl，2008，14（5）:877-905.

［12］BOYD S，PARIKH N，CHU E.et al.Distributed optimization and statistical learning via the alternating direction method multipliers［J］.Foundations and Trends in Machine Learning，2010，3（1）:1-122.

［13］LUXBURG U.A tutorial on spectral clustering［J］.Statistics and Computing，2007，17（4）:395-416.

［14］GORODNITSKY I F，RAO B D.Sparse signal reconstruction from limited data using focuss:a re-weighted minimum norm algorithm［J］.IEEETrans，Signal Process，1997，45 （3）:600-616.

［15］FAZEL M，HINDI H，BOYD S.Log-detheuristic for matrix rank minimization with applications to Hankel and Euclidean diatance matrices［C］//Proceedings of American Control Conference，2003.

［16］MOHAN H，F(xiàn)AZEL M.Iterative reweighted algorithms for matrix rank minimization［J］.Mach，Learn，Res，2012，13 （1）:3441-3473.

［17］MOHAN K，F(xiàn)ZAEL M.Reweighted nuclear norm minimization with application to system identifiction［C］//Proceedings of American Control Conference（ACC），2010.

［18］HARIKUMAR G，BRESLER Y.A new algorithm for computing sparse solutions to linear inverse problems［J］.IEEE Int.Conf.Acoustics Speech SignalProcess，1996（3）: 1331-1334.

Improved Sparse Subspace Clustering Algorithm

ZHANG Cai-xia，HU Hong-ping，BAI Yan-ping
（School of Science，North University of China，Taiyuan 030051，China）

Based on the existing theory of sparse subspace clustering algorithm，a modified sparse subspace clustering algorithm is put forward:iterative weighted sparse subspace clustering algorithm.In order to cluster data，sparse subspace clustering algorithm clusters high-dimensional data to different subspaces by solving minimization algorithm and applying spectral clustering.Iterative algorithm has more fair punishment value then the traditional algorithm，with balancing the influence of magnitude of data.The algorithm is applied to the sparse subspace clustering to improve the traditional sparse subspace clustering performance for data.Simulation experiment recognizing and classify Yale B face data image.The clustering effect is very good，proving the superiority of the improved algorithm.

sparse subspace clustering，iterative weighted，spectral clustering algorithms，face regulation

TP<301.6 class="emphasis_bold">301.6 文獻(xiàn)標(biāo)識(shí)碼：A301.6

A

1002-0640（2017）03-0075-05

2016-02-05

2016-03-11

國(guó)家自然科學(xué)基金（61275120）；2014年校自然科學(xué)基金資助項(xiàng)目

張彩霞（1989- ），女，山西應(yīng)縣人，碩士研究生。研究方向：現(xiàn)代最優(yōu)化算法。