基于分布式低秩表示的子空間聚類算法

許　凱　吳小俊　尹賀峰

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院　江蘇無錫　214122)

?

基于分布式低秩表示的子空間聚類算法

許凱吳小俊尹賀峰

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院江蘇無錫214122)

(xukai347@sina.com)

摘要針對基于低秩表示的子空間分割算法運(yùn)算時(shí)間較長、聚類的準(zhǔn)確率也不夠高，提出一種基于分布式低秩表示的稀疏子空間聚類算法(distributed low rank representation-based sparse subspace clustering algorithm, DLRRS)，該算法采用分布式并行計(jì)算來得到低秩表示的系數(shù)矩陣，然后保留系數(shù)矩陣每列的前k個(gè)絕對值最大系數(shù)，其他系數(shù)置為0，用此系數(shù)矩陣構(gòu)造一個(gè)稀疏的樣本關(guān)系更突出的相似度矩陣，接著用譜聚類得到聚類結(jié)果.但是其不具備增量學(xué)習(xí)功能，為此再提出一種基于分布式低秩表示的增量式稀疏子空間聚類算法(scalable distributed low rank representation based sparse subspace clustering algorithm, SDLRRS)，如果有新增樣本，可以利用前面的聚類結(jié)果對新增樣本進(jìn)行分類得到最后的結(jié)果.實(shí)驗(yàn)結(jié)果表明:所提2種子空間聚類算法不僅有效減少算法的運(yùn)算時(shí)間，還提高了聚類的準(zhǔn)確率，從而驗(yàn)證算法是有效可行的.

關(guān)鍵詞低秩表示；子空間聚類；并行計(jì)算；增量學(xué)習(xí)；系數(shù)重建

高維數(shù)據(jù)在信息技術(shù)高速發(fā)展的今天變得越來越普遍，它們通常分布在不同的子空間，這不僅增加了計(jì)算機(jī)內(nèi)存的需求量和算法的執(zhí)行時(shí)間，還會對算法[1]的性能產(chǎn)生不利影響，使得很多傳統(tǒng)的聚類算法不再適用.

最近幾年，子空間聚類技術(shù)已經(jīng)吸引了很多學(xué)者的關(guān)注，它基于高維數(shù)據(jù)固有的維數(shù)通常要比外圍空間的維數(shù)低很多的思想，用多個(gè)子空間對高維數(shù)據(jù)進(jìn)行聚類，并且發(fā)現(xiàn)適合每一組數(shù)據(jù)的低維子空間.這在計(jì)算機(jī)視覺、機(jī)器學(xué)習(xí)和模式識別等方面已經(jīng)有很多的應(yīng)用，尤其在圖像表示[2]、聚類[3]、運(yùn)動(dòng)分割[4]這3個(gè)應(yīng)用上的性能優(yōu)異.

可以將存在的子空間聚類算法分成主要的4類：代數(shù)方法[5]、迭代方法[6-7]、統(tǒng)計(jì)方法[8]和基于譜聚類的方法[9-10].在這些方法中，基于譜聚類的方法已經(jīng)顯示出其在計(jì)算機(jī)視覺等方面的優(yōu)越性能[11-12].

譜聚類算法[13]的核心是構(gòu)建一個(gè)合適的相似度矩陣.通常用2種方法來構(gòu)造相似度矩陣，即距離的倒數(shù)和重建系數(shù).1)通過計(jì)算2個(gè)數(shù)據(jù)點(diǎn)間的距離倒數(shù)來得到相似度，例如歐氏距離.基于距離倒數(shù)的方法可以得到數(shù)據(jù)集的局部結(jié)構(gòu)，但它的值僅僅取決于2個(gè)數(shù)據(jù)點(diǎn)之間的距離，所以對噪聲和異常值很敏感.2)基于表示系數(shù)的方法，假設(shè)每個(gè)數(shù)據(jù)點(diǎn)可以被其他數(shù)據(jù)點(diǎn)的線性組合進(jìn)行表示，并且表示系數(shù)可以被認(rèn)為是一種度量.這種度量對噪聲和異常值是魯棒的，因?yàn)橄禂?shù)的值不僅取決于2個(gè)相連的數(shù)據(jù)點(diǎn)，還取決于其他的所有數(shù)據(jù)點(diǎn).最近的幾篇文章已經(jīng)說明在子空間聚類中表示系數(shù)的性能是優(yōu)于距離倒數(shù)的.例如基于低秩表示的子空間分割算法(low rank representation, LRR)[14]和基于稀疏表示的稀疏子空間聚類算法(sparse subspace clustering, SSC)[3].

雖然LRR子空間聚類算法已經(jīng)取得了不錯(cuò)的聚類效果，但是此算法仍有很大的改進(jìn)空間.我們將文獻(xiàn)[15]中的并行計(jì)算思想和文獻(xiàn)[16]中的增量式學(xué)習(xí)框架相結(jié)合，這樣不僅能充分利用當(dāng)前的多核計(jì)算機(jī)資源，還能直接處理新增的樣本，不需要重新聚類，達(dá)到充分利用資源節(jié)省運(yùn)算時(shí)間的目的.最主要地，相似度矩陣中的元素衡量的是對應(yīng)樣本的相似程度，是譜聚類算法的核心，構(gòu)造一個(gè)合適的相似度矩陣可以有效地提高算法的準(zhǔn)確率.LRR子空間聚類算法直接用低秩表示所得的系數(shù)矩陣來構(gòu)造相似度矩陣，這樣會包含過多的冗余關(guān)系.本文通過保留系數(shù)矩陣每列的前k個(gè)絕對值最大系數(shù)、其他位置置0，得到一個(gè)新的系數(shù)矩陣，再用此系數(shù)矩陣構(gòu)造一個(gè)稀疏的樣本關(guān)系更突出的相似度矩陣.在AR數(shù)據(jù)集和Extended Yale B人臉庫上的實(shí)驗(yàn)結(jié)果表明本文所提DLRRS(distributed low rank representation-based sparse subspace clustering algorithm)和SDLRRS(scalable distributed low rank representation based sparse subspace clustering algorithm)這2種算法不僅有效減少運(yùn)算時(shí)間，還提高了聚類的準(zhǔn)確率.SDLRRS算法還具備增量式學(xué)習(xí)功能.

1基于低秩表示的子空間分割算法

研究數(shù)據(jù)空間的結(jié)構(gòu)在很多領(lǐng)域都是一個(gè)非常具有挑戰(zhàn)性的任務(wù)，這通常涉及到秩最小化問題.LRR算法通過求解式(1)來得到秩最小化問題的近似解:

(1)

算法1. LRR算法[14].

① 解決核范數(shù)最小化式(1)得到C=[c1,c2,…,cn]；

② 得到相似度矩陣W=|C|+|C|T；

③ 對相似度矩陣W使用譜聚類；

④ 輸出數(shù)據(jù)集矩陣Y的類分配.

2基于分布式低秩表示的子空間聚類算法

2.1基于分布式低秩表示的稀疏子空間聚類

低秩子空間分割算法可以很精確地處理小規(guī)模的數(shù)據(jù)集，但不能有效處理大規(guī)模數(shù)據(jù)集.為此，文獻(xiàn)[15]中提出了一種分布式低秩子空間分割算法，該算法將大規(guī)模數(shù)據(jù)集矩陣Y按列分割成t個(gè)小規(guī)模的數(shù)據(jù)矩陣{Z1,Z2,…,Zt}，然后再對這t個(gè)小規(guī)模數(shù)據(jù)矩陣進(jìn)行并行處理.其中第i個(gè)LRR子問題的處理形式為

(2)

運(yùn)用此分而治之的思想，不僅保證了算法所得結(jié)果的準(zhǔn)確率，還充分利用計(jì)算機(jī)的多核硬件資源，極大地降低算法的運(yùn)算時(shí)間.在分別得到t個(gè)子系數(shù)矩陣后，本文不采用文獻(xiàn)[15]中的投影方式來得到最后的系數(shù)矩陣，而是直接按列排成最后的系數(shù)矩陣.

另外，基于低秩表示的子空間分割和分布式低秩子空間分割這2個(gè)算法中，都是在得到系數(shù)矩陣C后，直接用此系數(shù)矩陣來構(gòu)造相似度矩陣，這樣會產(chǎn)生大量冗余的關(guān)系，降低算法所得結(jié)果的準(zhǔn)確率.為此，本文在得到系數(shù)矩陣后，先對系數(shù)矩陣中的每個(gè)元素取絕對值；然后保留每列的前k個(gè)最大值，其他位置的元素置為0；再次用新得到的系數(shù)矩陣來構(gòu)造相似度矩陣；最后用譜聚類來得到聚類結(jié)果.具體實(shí)現(xiàn)過程如算法2所示.

算法2. DLRRS算法.

① 將數(shù)據(jù)集矩陣Y按列分割成t個(gè)子數(shù)據(jù)矩陣{Z1,Z2,…,Zt}；

② 進(jìn)行并行計(jì)算

?

⑥ 對相似度矩陣W使用譜聚類；

⑦ 輸出數(shù)據(jù)集矩陣Y的類分配.

2.2分布式低秩增量式稀疏子空間聚類

在我們已經(jīng)完成聚類得到聚類結(jié)果后，如果此時(shí)有新的樣本加入，傳統(tǒng)的聚類算法只有重新聚類所有樣本，不具備增量學(xué)習(xí)的功能，會導(dǎo)致計(jì)算資源的浪費(fèi).在文獻(xiàn)[16]中，提出了一種先聚類后分類的增量式聚類算法.本文參考此結(jié)構(gòu)，先進(jìn)行聚類，然后再用協(xié)同表示分類算法對新增的樣本進(jìn)行分類.協(xié)同表示分類需要求解的目標(biāo)函數(shù)為

(3)

(4)

(5)

其中，δj(c*)表示保留系數(shù)列向量c*中對應(yīng)第j類的元素，其他元素置為0；rj(y)表示樣本y屬于第j類的標(biāo)準(zhǔn)化殘差.

最后通過式(5)得到最終的分類結(jié)果.基于分布式低秩表示的可拓展稀疏子空間聚類算法的實(shí)現(xiàn)過程如算法3所示.

算法3. SDLRRS算法.

② 在數(shù)據(jù)矩陣X上運(yùn)行DLRRS算法，得到聚類結(jié)果；

⑥ 輸出數(shù)據(jù)矩陣Y的類分配.

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

(6)

本節(jié)我們使用子空間聚類準(zhǔn)確率(式(6))和歸一化互信息(normalized mutual information, NMI)來評估本文基于分布式低秩表示的子空間聚類算法的性能.同時(shí)，為了驗(yàn)證本文算法的有效性，實(shí)驗(yàn)通過3方面來進(jìn)行比較分析：1)通過實(shí)驗(yàn)將本文算法的參數(shù)調(diào)到最佳；2)討論并行計(jì)算分割數(shù)t對DLRRS算法的影響；3)討論SDLRRS算法增量學(xué)習(xí)功能的有效性.

其中用到的參考算法有分布式低秩子空間分割算法(distributed low-rank subspace segmentation, DFC-LRR)[15]、基于低秩表示的子空間分割算法(low rank representation, LRR)[14]、稀疏子空間聚類算法(sparse subspace clustering, SSC)[3]、可拓展的基于低秩表示的子空間分割算法(scalable low rank representation, SLRR)[16]和可拓展的稀疏子空間聚類算法(scalable sparse subspace clustering, SSSC)[16].后2種算法分別用LRR和SSC算法先進(jìn)行聚類，當(dāng)有新樣本加入時(shí)再用分類的方法得到結(jié)果.實(shí)驗(yàn)在同一臺PC機(jī)(CPU：3.20 GHz，內(nèi)存：8 GB)上進(jìn)行，操作系統(tǒng)版本為64位Windows 8，實(shí)驗(yàn)工具為MATLAB R2013a.

實(shí)驗(yàn)選用2個(gè)常用的人臉數(shù)據(jù)集：AR數(shù)據(jù)集和Extended Yale B數(shù)據(jù)集.其中AR數(shù)據(jù)集包含超過4 000幅126個(gè)人(70個(gè)男性、56個(gè)女性)的人臉圖片，這些圖片是在不同的表情、不同光照和偽裝(戴墨鏡或圍巾)下得到的.每個(gè)人有26幅圖片，其中14幅“干凈”圖片、6幅戴墨鏡、6幅戴圍巾.這里我們參照文獻(xiàn)[17]，從50個(gè)男性和50個(gè)女性的圖片中隨機(jī)選出1 400幅“干凈”的人臉圖片.Extended Yale B人臉庫中有38個(gè)人，每個(gè)人在不同光照條件下得到64張正面人臉圖像,每個(gè)人臉圖像經(jīng)過裁

Table 1　Datasets Used in Our Experiments

剪后有192×168個(gè)像素.為了降低所有算法的計(jì)算復(fù)雜度和對內(nèi)存的需求量，我們將AR數(shù)據(jù)集中的圖片下采樣到55×40，Extended Yale B人臉庫中的圖片都下采樣到48×42個(gè)像素，并且對它們進(jìn)行PCA保留98%的信息.各個(gè)數(shù)據(jù)集的詳細(xì)信息如表1所示.

3.1參數(shù)對本文算法的影響

本文所提的2種子空間聚類算法包含3個(gè)參數(shù)：平衡參數(shù)λ、每列保留的系數(shù)個(gè)數(shù)k和并行計(jì)算的分割數(shù)t.本節(jié)只討論平衡參數(shù)λ和每列保留的系數(shù)個(gè)數(shù)k對DLRRS和SDLRRS這2種算法聚類質(zhì)量的影響，先設(shè)置t=1，3.2節(jié)再詳細(xì)討論參數(shù)t對算法的影響.

圖1(a)(b)展示了在AR數(shù)據(jù)集上參數(shù)λ和k對DLRRS算法的影響.當(dāng)λ逐漸增大的時(shí)候，對應(yīng)的聚類準(zhǔn)確率和NMI也逐漸升高，然后趨于穩(wěn)定.當(dāng)k從3變到8時(shí)，對應(yīng)的聚類準(zhǔn)確率從65.36%變到85.93%，NMI從81.78%變到93.66%;當(dāng)k繼續(xù)增大時(shí)，對應(yīng)的聚類準(zhǔn)確率和NMI呈現(xiàn)出緩慢下降的趨勢.所以DLRRS算法在AR數(shù)據(jù)集上的參數(shù)選擇為平衡參數(shù)λ=2.2和保留的系數(shù)個(gè)數(shù)k=8.

圖1(c)(d)展示了在Extended Yale B數(shù)據(jù)集上參數(shù)λ和k對本文算法的影響.當(dāng)λ從0.05變到2時(shí)，對應(yīng)的聚類準(zhǔn)確率從29.41%變到86.45%，NMI從38.37%變到91.15%;當(dāng)λ從2變到3.8時(shí)，對應(yīng)的聚類準(zhǔn)確率和NMI基本保持不變.當(dāng)k從3變到9時(shí)，對應(yīng)的聚類準(zhǔn)確率從71.58%變到86.62%，NMI從81.70%變到91.84%;在k=9時(shí)DLRRS算法取得最好的聚類質(zhì)量;當(dāng)k從9變到20時(shí)，對應(yīng)的聚類準(zhǔn)確率從86.62%一直下降到78.38%，NMI從91.84%下降到86.27%.所以DLRRS算法在Extended Yale B數(shù)據(jù)集上的參數(shù)選擇為平衡參數(shù)λ=2和保留的系數(shù)個(gè)數(shù)k=9.

由于篇幅所限，在此直接給出SDLRRS算法的參數(shù)設(shè)置，在AR數(shù)據(jù)集上為平衡參數(shù)λ=3.1和保留的系數(shù)個(gè)數(shù)k=6，在Extended Yale B數(shù)據(jù)集上為平衡參數(shù)λ=2.9和保留的系數(shù)個(gè)數(shù)k=5.

3.2分割數(shù)t對算法質(zhì)量的影響

由于實(shí)驗(yàn)室只有4核處理器，所以分割數(shù)t取1～4，然后在AR和Extended Yale B數(shù)據(jù)集上進(jìn)行DLRRS和DFC-LRR這2個(gè)算法的對比實(shí)驗(yàn).

1) 橫向比較.從表2可以看出，在AR數(shù)據(jù)集上，本文DLRRS算法的聚類準(zhǔn)確率較DFC-LRR算法高出5%左右，兩者的運(yùn)算時(shí)間基本一致，DLRRS算法稍優(yōu)一點(diǎn);在Extended Yale B數(shù)據(jù)集上，DLRRS算法在聚類準(zhǔn)確率方面高出DFC-LRR算法18%左右，在運(yùn)算時(shí)間方面可以節(jié)省10 s左右.主要有2方面原因使得本文DLRRS算法完全優(yōu)于DFC-LRR算法:①保留系數(shù)矩陣每列的前k個(gè)絕對值最大系數(shù)，其他位置置0，然后再構(gòu)造稀疏的相似度矩陣是有效提高本文算法準(zhǔn)確率的關(guān)鍵;②在并行計(jì)算時(shí)，不采用投影的方式，而是直接按列排成最后的系數(shù)矩陣，在保證聚類準(zhǔn)確率的同時(shí)可以減少算法的運(yùn)算時(shí)間.

Fig. 1　Clustering quality of DLRRS with varying parameters.圖1　參數(shù)對本文DLRRS算法聚類質(zhì)量的影響

ParametertQualityARExtendedYaleBDLRRSDFC-LRR[15]DLRRSDFC-LRR[15]1Accuracy0.85300.80010.84590.6860NMI0.93800.90720.91030.7439RunningTime∕s64.1764.7162.4980.162Accuracy0.84860.80440.85580.6698NMI0.93750.91180.91190.7388RunningTime∕s52.3852.8156.3264.543Accuracy0.84840.80210.86180.6757NMI0.93960.91400.91800.7451RunningTime∕s48.4849.8453.4662.24Accuracy0.84990.80400.85000.6764NMI0.94010.91760.91230.7427RunningTime∕s46.1946.3754.6363.42

2) 縱向比較.表2所示為并行計(jì)算的分割數(shù)t對算法的影響.可以很直觀地看出，隨著t的增大，DLRRS和DFC-LRR這2個(gè)算法的聚類準(zhǔn)確率在AR和Extended Yale B數(shù)據(jù)集上幾乎不受影響，但卻可以大幅降低算法的執(zhí)行時(shí)間;t=4時(shí)較t=1時(shí)在AR數(shù)據(jù)集上可以節(jié)省28%左右的時(shí)間，在Extended Yale B數(shù)據(jù)集上可以節(jié)省13%左右的時(shí)間.由于實(shí)驗(yàn)室的計(jì)算機(jī)只有4核，當(dāng)t從1變到2時(shí)，DLRRS算法在2個(gè)數(shù)據(jù)集上的執(zhí)行時(shí)間降幅最大，分別為18%和9.8%;當(dāng)t從2變到3時(shí)，執(zhí)行時(shí)間的降幅會變小;當(dāng)t從3變到4時(shí)，執(zhí)行時(shí)間的降幅變得不是很明顯，在Extended Yale B數(shù)據(jù)集上相較t=3時(shí)還出現(xiàn)了小幅度的上升，這是由于實(shí)驗(yàn)室CPU只有4核，在t=4滿負(fù)荷運(yùn)算時(shí)不可能只執(zhí)行并行計(jì)算的代碼，還要執(zhí)行其他指令，這并不影響本文算法的有效性.綜上，我們可以預(yù)見如果計(jì)算機(jī)的核數(shù)變得更多、數(shù)據(jù)集的規(guī)模變大，本文DLRRS算法在犧牲有限準(zhǔn)確率的同時(shí)，節(jié)省運(yùn)算時(shí)間的優(yōu)勢會更加明顯.

3.3增量學(xué)習(xí)功能

對已經(jīng)聚類好的樣本，如果此時(shí)有新樣本加入，DLRRS算法需要重新聚類.為此，本文在DLRRS算法的基礎(chǔ)上提出SDLRRS算法使其具備增量學(xué)習(xí)功能.為了驗(yàn)證SDLRRS算法的性能，我們分別將AR和Extended Yale B數(shù)據(jù)集中的一半樣本隨機(jī)選出作為新加入的樣本進(jìn)行測試，并和同樣具備增量學(xué)習(xí)功能的SLRR算法和SSSC算法進(jìn)行對比.對于DLRRS，LRR和SSC這3種不具備增量學(xué)習(xí)功能的聚類算法直接使用全部樣本進(jìn)行聚類測試.表3給出了不同算法在AR和Extended Yale B數(shù)據(jù)集上的聚類結(jié)果，同時(shí)列出了各個(gè)算法使用的參數(shù)，其中λ是平衡參數(shù)，k指系數(shù)矩陣中每列保留的系數(shù)個(gè)數(shù)，t是并行計(jì)算的分割數(shù)，μ是進(jìn)行交替方向乘子法計(jì)算時(shí)的懲罰參數(shù). 3.2節(jié)我們已經(jīng)知道并行計(jì)算分割數(shù)t對DLRRS算法的聚類準(zhǔn)確率影響很小，為了方便討論SDLRRS算法增量學(xué)習(xí)的效果，本節(jié)我們設(shè)置t=1.

Table 3　Clustering Quality Comparison of Different Algorithms on Datasets

從表3可以看出，SDLRRS算法和DLRRS算法的聚類準(zhǔn)確率分別較SLRR算法，LRR算法在AR數(shù)據(jù)集上有4%左右的提升，在Extended Yale B數(shù)據(jù)集上有17%的提升.當(dāng)有新的樣本加入時(shí)，DLRRS，LRR，SSC這3種算法不得不對所有樣本重新聚類，導(dǎo)致大量資源浪費(fèi).而可拓展的3種聚類算法SDLRRS，SLRR，SSSC可以直接處理新加入的樣本，不需要對所有樣本重新聚類.在AR數(shù)據(jù)集上的準(zhǔn)確率，SDLRRS算法比DLRRS算法低3.80%，SLRR算法比LRR算法低1.62%，SSSC算法比SSC算法低7.71%；在Extended Yale B數(shù)據(jù)集上的準(zhǔn)確率，SDLRRS算法比DLRRS算法低2.19%，SLRR算法比LRR算法低1.31%，SSSC算法比SSC算法低11.41%，可以驗(yàn)證可拓展算法的有效性.尤其是本文的可拓展聚類算法SDLRRS，比進(jìn)行了重新聚類的LRR算法在AR數(shù)據(jù)集上的準(zhǔn)確率還高出1.52%，在Extended Yale B數(shù)據(jù)集上高出15.54%；比SSC算法在AR數(shù)據(jù)集上高出3.97%，在Extended Yale B數(shù)據(jù)集上高出17.73%.另外，SDLRRS算法的運(yùn)算時(shí)間相較LRR算法和SSC算法至少節(jié)省一半以上，所以SDLRRS算法不僅可以用來處理新增加的樣本，必要的時(shí)候還可以用來快速聚類整個(gè)數(shù)據(jù)集，足見本文算法是非常有效可行的.

4結(jié)束語

本文首先設(shè)計(jì)了一種基于分布式低秩表示的稀疏子空間聚類算法，此算法運(yùn)用并行計(jì)算思想，并且通過保留系數(shù)矩陣每列的前k個(gè)絕對值最大系數(shù)、其他系數(shù)置為0，達(dá)到簡化突出樣本間相似程度的目的，此算法具有充分利用計(jì)算資源節(jié)省運(yùn)算時(shí)間和提高聚類準(zhǔn)確率的優(yōu)點(diǎn).但它不具備增量學(xué)習(xí)功能，為此，又提出一種基于分布式低秩表示的增量式稀疏子空間聚類算法，在AR數(shù)據(jù)集和Extended Yale B人臉庫上的聚類效果優(yōu)異.但是，本文的研究工作還有待進(jìn)一步深入和擴(kuò)展，如新增加的樣本不屬于前面聚類的類，這時(shí)就不可以簡單地根據(jù)前面的聚類結(jié)果對新增樣本進(jìn)行分類.

參考文獻(xiàn)

[1]Ying Wenhao, Xu Min, Wang Shitong, et al. Fast adaptive clustering by synchronization on large scale datasets[J]. Journal of Computer Research and Development, 2014, 51(4): 707-720 (in Chinese)(應(yīng)文豪, 許敏, 王士同, 等. 在大規(guī)模數(shù)據(jù)集上進(jìn)行快速自適應(yīng)同步聚類[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(4): 707-720)

[2]Hong W, Wright J, Huang K, et al. Multiscale hybrid linear models for lossy image representation[J]. IEEE Trans on Image Processing, 2006, 15(12): 3655-3671

[3]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

[4]Zhuang L, Gao H, Lin Z, et al. Non-negative low rank and sparse graph for semi-supervised learning[C]Proc of IEEE CVPR’12. Piscataway, NJ: IEEE, 2012: 2328-2335

[5]Vidal R, Ma Y, Sastry S. Generalized principal component analysis (GPCA)[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(12): 1945-1959

[6]Zhang T, Szlam A, Lerman G. Median k-flats for hybrid linear modeling with many outliers[C]Proc of the 12th Int Conf on Computer Vision Workshops. Piscataway, NJ: IEEE, 2009: 234-241

[7]Lu L, Vidal R. Combined central and subspace clustering for computer vision applications[C]Proc of the 23rd Int Conf on Machine learning. New York: ACM, 2006: 593-600

[8]Rao S, Tron R, Vidal R, et al. Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1832-1845

[9]Favaro P, Vidal R, Ravichandran A. A closed form solution to robust subspace estimation and clustering[C]Proc of IEEE CVPR’11. Piscataway, NJ: IEEE, 2011: 1801-1807

[10]Elhamifar E, Vidal R. Clustering disjoint subspaces via sparse representation[C]Proc of IEEE ICASSP’10. Piscataway, NJ: IEEE, 2010: 1926-1929

[11]Vidal R. A tutorial on subspace clustering[J]. IEEE Signal Processing Magazine, 2010, 28(2): 52-68

[12]Li Qingyong, Liang Zhengping, Huang Yaping, et al. Sparseness representation model for defect detection and its application[J]. Journal of Computer Research and Development, 2014, 51(9): 1929-1935 (in Chinese)(李清勇, 梁正平, 黃雅平, 等. 缺陷檢測的稀疏表示模型及應(yīng)用[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(9): 1929-1935)

[13]Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416

[14]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

[15]Talwalkar A, Mackey L, Mu Y, et al. Distributed low-rank subspace segmentation[C]Proc of IEEE ICCV’13. Piscataway, NJ: IEEE, 2013: 3543-3550

[16]Peng X, Zhang L, Yi Z. Scalable sparse subspace clustering[C]Proc of IEEE CVPR’13. Piscataway, NJ: IEEE, 2013: 430-437

[17]Wright J, Yang A Y, Ganesh A, et al. Robust face recognition via sparse representation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227

Xu Kai, born in 1989. Master. His main research interests include pattern recogni-tion and data mining.

Wu Xiaojun, born in 1967. Professor and PhD supervisor. Senior member of China Computer Federation. His main research interests include pattern recognition, computer vision, fuzzy systems, neural networks, and intelligent systems.

Yin Hefeng, born in 1989. PhD candidate. Student member of China Computer Federation. His main research interests include feature extraction, sparse repres-entation and low rank representation.

收稿日期：2014-12-09；修回日期：2015-06-09

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(61373055)；江蘇省自然科學(xué)基金項(xiàng)目(BK20140419)；江蘇省高校自然科學(xué)研究計(jì)劃重大項(xiàng)目(14KJB520001)

通信作者：吳小俊(wu_xiaojun@jiangnan.edu.cn)

中圖法分類號TP18; TP391.4

Distributed Low Rank Representation-Based Subspace Clustering Algorithm

Xu Kai, Wu Xiaojun, and Yin Hefeng

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi,Jiangsu214122)

AbstractVision problem ranging from image clustering to motion segmentation can naturally be framed as subspace segmentation problem, in which one aims to recover multiple low dimensional subspaces from noisy and corrupted input data. Low rank representation-based subspace segmentation algorithm (LRR) formulates the problem as a convex optimization and achieves impressive results. However, it needs to take a long time to solve the convex problem, and the clustering accuracy is not high enough. Therefore, this paper proposes a distributed low rank representation-based sparse subspace clustering algorithm (DLRRS). DLRRS adopts the distributed parallel computing to get the coefficient matrix, then take the absolute value of each element of the coefficient matrix, and retain the k largest coefficients per column and set the other elements to 0 to get a new coefficient matrix. Finally, DLRRS performs spectral clustering over the new coefficient matrix. But it doesn’t have incremental learning function, so there is a scalable distributed low rank representation-based sparse subspace clustering algorithm (SDLRRS) here. If new samples are brought in, SDLRRS can use the former clustering result to classify the new samples to get the final result. Experimental results on AR and Extended Yale B datasets show that the improved algorithms can not only obviously reduce the running time, but also achieve higher accuracy, which verifies that the proposed algorithms are efficient and feasible.

Key wordslow rank representation; subspace clustering; parallel computing; incremental learning; coefficients reconstruction

This work was supported by the National Natural Science Foundation of China (61373055), the Natural Science Foundation of Jiangsu Province of China (BK20140419), and the Major Program of Research Plan of the Natural Science in Higher Education of Jiangsu Province of China (14KJB520001).