稀疏子空間聚類(lèi)算法研究

黃佳雯，王麗娟，王利偉

（1.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006；2.陸軍工程大學(xué)電子與光學(xué)工程系，石家莊050003）

0 引言

高維數(shù)據(jù)廣泛存在于圖像處理、計(jì)算機(jī)視覺(jué)、模式識(shí)別、生物計(jì)算機(jī)學(xué)等領(lǐng)域[1]。高維數(shù)據(jù)識(shí)別算法需要具有較好的時(shí)間和空間性能。同時(shí)由于噪聲的影響，處理過(guò)程中容易產(chǎn)生“維數(shù)災(zāi)難”，嚴(yán)重影響算法識(shí)別性能。研究發(fā)現(xiàn)，高維數(shù)據(jù)具有低維子空間結(jié)構(gòu)，即數(shù)據(jù)通常分布在多個(gè)低維子空間的并集上。例如，圖1 所示的兩個(gè)變化的兩個(gè)人臉圖像位于兩個(gè)低維空間上[2]?；謴?fù)數(shù)據(jù)的低維子空間潛在結(jié)構(gòu)不僅有助于數(shù)據(jù)的存儲(chǔ)和管理，而且也能降低維數(shù)災(zāi)難對(duì)于數(shù)據(jù)識(shí)別的影響，提高算法性能。子空間聚類(lèi)算法可以有效恢復(fù)數(shù)據(jù)的低維子空間結(jié)構(gòu)，并根據(jù)這種子空間結(jié)構(gòu)將數(shù)據(jù)正確地劃分到每一個(gè)子空間所隸屬的數(shù)據(jù)類(lèi)別[3]。

子空間聚類(lèi)算法作為一種有效的高維聚類(lèi)算法被眾多專(zhuān)家學(xué)者廣泛研究?，F(xiàn)有的方法可以分為四類(lèi)[4]：基于迭代的方法，基于代數(shù)的方法，基于統(tǒng)計(jì)的方法和基于譜聚類(lèi)的方法。近年來(lái)，由于基于譜聚類(lèi)的稀疏子空間聚類(lèi)算法的求解簡(jiǎn)單且聚類(lèi)效果好，這類(lèi)型的方法很為流行。它是一種以譜圖理論為基礎(chǔ)的數(shù)據(jù)聚類(lèi)方法，通過(guò)學(xué)習(xí)數(shù)據(jù)在低維子空間上的表示系數(shù)矩陣來(lái)還原數(shù)據(jù)本質(zhì)，幫助數(shù)據(jù)聚類(lèi)。

圖1 兩個(gè)人臉圖像的低維子空間近似表示[2]

1 稀疏子空間聚類(lèi)算法概述

圖像、視頻、文本和生物信息等數(shù)據(jù)廣泛存在，它們普遍具有高維、稀疏和噪音的性質(zhì)，在識(shí)別過(guò)程中容易產(chǎn)生維數(shù)災(zāi)難，影響影響識(shí)別效果。高維即是其數(shù)據(jù)維度多，有時(shí)甚至遠(yuǎn)超樣本量。稀疏是指這些高維數(shù)據(jù)（維度h）映射到的低維子空間（維度d）上的表示系數(shù)矩陣呈現(xiàn)很強(qiáng)的稀疏性，其中d<

其中Zi表示第i 個(gè)子空間中數(shù)據(jù)的表示系數(shù)矩陣[5]。反之，當(dāng)?shù)玫骄哂袎K對(duì)角結(jié)構(gòu)的Z時(shí)，即可得到輸入數(shù)據(jù)的子空間結(jié)構(gòu)。稀疏子空間聚類(lèi)算法就是利用不同的范數(shù)約束Z，使其盡可能具有塊對(duì)角的理想結(jié)構(gòu)，從而探索到數(shù)據(jù)的子空間結(jié)構(gòu)。它的流程如圖2所示，首先學(xué)習(xí)到表示系數(shù)矩陣Z，然后使用Z構(gòu)造相似度矩陣W=(Z+ZT)/2，最后對(duì)W進(jìn)行譜聚類(lèi)即可得到聚類(lèi)結(jié)果。

圖2 稀疏子空間聚類(lèi)流程圖

2 稀疏子空間聚類(lèi)算法研究

由于稀疏子空間聚類(lèi)算法簡(jiǎn)單高效，它從提出至今得到了廣泛關(guān)注。本節(jié)對(duì)它發(fā)展過(guò)程中的經(jīng)典模型和這四年最新的研究方向進(jìn)行了詳細(xì)介紹。

2.1 經(jīng)典稀疏子空間聚類(lèi)模型

最經(jīng)典的兩種子空間聚類(lèi)算法分別是基于一維稀疏的稀疏子空間聚類(lèi)（SSC）[6]方法和利用二維稀疏的基于低秩表示（LRR）[7]的子空間聚類(lèi)方法。其中SSC 的模型如下：

SSC 使用l1范數(shù)約束Z，同時(shí)約束Zii=0 來(lái)避免每個(gè)數(shù)據(jù)僅用它自己表示的特殊情況。這種方法求得的Z，在數(shù)據(jù)所屬子空間獨(dú)立的情況下呈現(xiàn)塊對(duì)角結(jié)構(gòu)，Z中塊的個(gè)數(shù)揭示了輸入數(shù)據(jù)子空間的個(gè)數(shù)，塊的大小揭露了各個(gè)子空間的維數(shù)。LRR 使用核范數(shù)來(lái)約束Z，它的模型如下：

它通過(guò)對(duì)表示系數(shù)矩陣Z的秩逼近得到數(shù)據(jù)的子空間表示。相比于SSC 的單獨(dú)考慮每個(gè)數(shù)據(jù)的稀疏表示，這種低秩約束有利于捕捉數(shù)據(jù)的全局結(jié)構(gòu)。

2.2 最新的稀疏子空間聚類(lèi)模型

本文對(duì)近四年的稀疏子空間聚類(lèi)算法進(jìn)行了梳理，其中大部分的模型可以用如下的一般形式表示：

正則項(xiàng)R(Z)約束Z 呈塊對(duì)角結(jié)構(gòu)，數(shù)據(jù)項(xiàng)F(E)處理噪聲。表1 列出了幾種典型的稀疏子空間聚類(lèi)模型，可以看出這些模型的主要區(qū)別在于正則項(xiàng)和數(shù)據(jù)項(xiàng)的不同范數(shù)設(shè)計(jì)，其目的分別是改進(jìn)系數(shù)矩陣塊對(duì)角約束和改進(jìn)抗噪性。圖2 是稀疏子空間聚類(lèi)算法的一般流程，近年來(lái)有些研究關(guān)注于子空間投影階段，結(jié)合了特征選擇方法改進(jìn)了稀疏子空間聚類(lèi)算法。還有一些方法關(guān)注于改進(jìn)算法流程，將原本流程中分為兩步的系數(shù)矩陣學(xué)習(xí)和譜聚類(lèi)步驟合二為一。最后由于深度學(xué)習(xí)的流行，有些研究嘗試將其與稀疏子空間聚類(lèi)算法結(jié)合。

（1）正則項(xiàng)改進(jìn)

l0范數(shù)可以約束得到數(shù)據(jù)本質(zhì)子空間，但對(duì)于l0范數(shù)的求解是一個(gè)NP 難問(wèn)題。使用正交匹配追蹤（OMP）方法可以對(duì)其求解，但當(dāng)數(shù)據(jù)量大的時(shí)候，這種方法效率很低。Li 等人[8]提出一種學(xué)習(xí)型OMP 方法（LOMP）來(lái)加速求解。它通過(guò)對(duì)OMP 方法得到的l0稀疏表示的學(xué)習(xí)得到單個(gè)隱藏神經(jīng)網(wǎng)絡(luò)（SHNN），再將學(xué)習(xí)到的SHNN 用于新的數(shù)據(jù)稀疏表示矩陣學(xué)習(xí)上，從而提高效率。Hashemi 等人[9]在l0范數(shù)約束的基礎(chǔ)上引入正交最小二乘法的變體來(lái)加速求解，同時(shí)更有效地找到高維數(shù)據(jù)的底層子空間。

表1 幾種典型的子空間聚類(lèi)模型

SSC 使用l1范數(shù)來(lái)松弛l0最小化問(wèn)題，這種方法的效率低，且在高噪聲下可能失效。Dong 等[10]使用一種p（0

LRR 使用核范數(shù)來(lái)約束Z，這種方法擁有封閉解，解法簡(jiǎn)單，但需要很強(qiáng)的子空間獨(dú)立假設(shè)且對(duì)數(shù)據(jù)質(zhì)量有要求。Lu 等人[11]提出了一種k 塊對(duì)角約束，直接約束表示系數(shù)矩陣呈現(xiàn)塊對(duì)角結(jié)構(gòu)，這種方法相對(duì)于LRR 無(wú)需那么強(qiáng)的子空間獨(dú)立假設(shè)。

對(duì)于Z的約束也可使用多種范數(shù)結(jié)合的方式。Wang 等人[12]將LRR 和稀疏表示結(jié)合起來(lái)，提出了一種低秩子空間稀疏表示框架，這種方法結(jié)合了兩種方法的優(yōu)點(diǎn)，對(duì)于全局信息和局部子空間信息都有考慮。Sui 等人[13]將低秩和稀疏約束分別施加在兩個(gè)級(jí)聯(lián)自表達(dá)式上，它首先利用全局信息使得樣本低秩，然后學(xué)習(xí)該低階表示的稀疏表示來(lái)捕獲領(lǐng)域結(jié)構(gòu)，最后對(duì)該稀疏表示進(jìn)行譜聚類(lèi)得到最終聚類(lèi)結(jié)果。

（2）抗噪性改進(jìn)

現(xiàn)實(shí)中的數(shù)據(jù)往往存在噪聲、異常值和缺失項(xiàng)，因此很多學(xué)者分別從理論和實(shí)踐上對(duì)算法的抗噪性進(jìn)行了研究。Wang 等人[14]對(duì)LASSO-SSC 算法處理帶有噪聲或損壞數(shù)據(jù)的情況進(jìn)行了理論分析，分析證明當(dāng)噪聲的大小不超過(guò)由半徑與子空間不相干之間的幾何間隙確定的閾值時(shí)，該算法恢復(fù)的子空間簇是正確的。Peng 等人[15]提出一種名為子空間內(nèi)投影優(yōu)勢(shì)（IPD）的理論，證明了l1、l2、l∞和基于核范數(shù)的投影空間共享的IPD 的性質(zhì)，即小值系數(shù)（平凡系數(shù)）總是對(duì)應(yīng)于誤差的投影。然后利用該理論設(shè)計(jì)了一種從線性投影空間中消除誤差的影響的方法。Li 等人[16]引入了柯西損失函數(shù)懲罰噪聲項(xiàng)，從而提升算法抗噪性。Fang 等人[17]引入一種轉(zhuǎn)換核范數(shù)和融合策略擴(kuò)展了原始的潛在低秩表示（LLRR）算法，增強(qiáng)了算法魯棒性。

（3）子空間投影改進(jìn)

傳統(tǒng)的子空間聚類(lèi)算法是在輸入空間使用自表示方法學(xué)習(xí)到數(shù)據(jù)的表示系數(shù)矩陣，但這種方法不能有效處理非線性流形聚類(lèi)。一種有效的方式就是將輸入空間投影到低維空間再進(jìn)行學(xué)習(xí)。Peng 等人[18]將特征選擇與子空間聚類(lèi)集成到一起，從而可以恢復(fù)具有最相關(guān)特征的子空間。Zhu 等人[19]在特征選擇基礎(chǔ)上還將傳統(tǒng)子空間聚類(lèi)數(shù)據(jù)表示和聚類(lèi)兩個(gè)步驟合一了，從而提升了算法效果。Song 等人[20]提出了一種基于結(jié)構(gòu)化稀疏PCA 的字典學(xué)習(xí)的方法，使用結(jié)構(gòu)信息以及數(shù)據(jù)稀疏性來(lái)學(xué)習(xí)降維字典和系數(shù)矩陣，再?gòu)膶W(xué)習(xí)到的字典系數(shù)向量的內(nèi)積構(gòu)造相似度矩陣。Tang 等人[21]提出一種基于魯棒子空間學(xué)習(xí)的低秩表示算法（RSLLRR），在子空間投影學(xué)習(xí)表示系數(shù)矩陣時(shí)，使用了線性投影和非線性投影將數(shù)據(jù)映射到低維空間中。

（4）過(guò)程改進(jìn)

一般稀疏子空間聚類(lèi)算法表示系數(shù)矩陣學(xué)習(xí)與聚類(lèi)過(guò)程是兩個(gè)步驟，其忽略了表示和聚類(lèi)過(guò)程存在彼此依賴的關(guān)系，因此不能保證最佳的效果。Li 等人[22]提出了一個(gè)結(jié)構(gòu)化稀疏子空間聚類(lèi)框架，將系數(shù)矩陣的學(xué)習(xí)和聚類(lèi)過(guò)程結(jié)合起來(lái)。該框架使用由相似度矩陣求出的拉普拉斯矩陣構(gòu)造連續(xù)實(shí)值分割矩陣，并在下一次迭代中用其對(duì)表示矩陣進(jìn)行加權(quán)，從而使用聚類(lèi)相關(guān)信息幫助矯正表示系數(shù)矩陣中的誤差。但這種方法僅考慮表示系數(shù)矩陣的結(jié)構(gòu)化稀疏屬性，Chen 等人[23]在此基礎(chǔ)上定義了組內(nèi)分組效應(yīng)的概念，以將同一子空間中的數(shù)據(jù)分組在一起。Yin 等人[24]提出了一種學(xué)習(xí)自適應(yīng)低秩圖表示系數(shù)矩陣的子空間聚類(lèi)方法，在統(tǒng)一框架下學(xué)習(xí)親和度矩陣和表示系數(shù)。Wu 等人[25]也是一種學(xué)習(xí)自適應(yīng)圖表示稀疏矩陣的子空間聚類(lèi)方法，但其學(xué)習(xí)數(shù)據(jù)的表示系數(shù)矩陣時(shí)使用的是最小二乘回歸法。

（5）結(jié)合深度學(xué)習(xí)

深度學(xué)習(xí)近年來(lái)廣受關(guān)注，很多研究者嘗試將稀疏子空間聚類(lèi)與其結(jié)合。Peng 等人[26]率先提出了基于深度學(xué)習(xí)架構(gòu)的具有先驗(yàn)的子空間聚類(lèi)算法，將輸入數(shù)據(jù)逐步轉(zhuǎn)換為非線性潛在空間，并同時(shí)學(xué)習(xí)了局部和全局子空間結(jié)構(gòu)。Pan 等人[27]在深度自動(dòng)編碼器和解碼器之間引入一個(gè)自表達(dá)層，以模仿傳統(tǒng)子空間聚類(lèi)中的“自表達(dá)”屬性，該層可通過(guò)標(biāo)準(zhǔn)的反向傳播過(guò)程來(lái)學(xué)習(xí)所有數(shù)據(jù)點(diǎn)之間的成對(duì)親和力。Zhu 等人[28]使用前饋神經(jīng)網(wǎng)絡(luò)將樣本映射到非線性空間，并在網(wǎng)絡(luò)的頂層執(zhí)行子空間聚類(lèi)，以迭代地學(xué)習(xí)映射功能和聚類(lèi)。Zhou 等人[29]引入了對(duì)抗學(xué)習(xí)來(lái)監(jiān)督學(xué)習(xí)樣本表示和子空間聚類(lèi)。其中，生成器產(chǎn)生子空間估計(jì)和樣本聚類(lèi)。鑒別器通過(guò)檢查來(lái)自估計(jì)子空間的重采樣數(shù)據(jù)是否具有一致的子空間屬性來(lái)評(píng)估當(dāng)前的聚類(lèi)性能，并監(jiān)督生成器以逐步改善子空間聚類(lèi)。Zhang 等人[30]提出神經(jīng)協(xié)作子空間聚類(lèi)。他們將子空間聚類(lèi)公式化為分類(lèi)問(wèn)題，從而從計(jì)算中刪除譜聚類(lèi)步驟。神經(jīng)模型由分類(lèi)和親和力學(xué)習(xí)兩個(gè)模塊組成，在訓(xùn)練和迭代過(guò)程中，后者學(xué)到的親和力矩陣來(lái)監(jiān)督前者計(jì)算出的親和力矩陣，同時(shí)前者可以用來(lái)提升后者的自表示能力，從而協(xié)作優(yōu)化來(lái)構(gòu)建更好的親和力矩陣。

3 算法應(yīng)用

由于稀疏子空間聚類(lèi)算法簡(jiǎn)單高效，近年來(lái)在機(jī)器學(xué)習(xí)領(lǐng)域很受關(guān)注，并在人臉識(shí)別、運(yùn)動(dòng)分割、生物信息學(xué)等方面取得了成功的應(yīng)用。

不同表情或光線變換條件下的同一個(gè)人臉圖像可以看作來(lái)自一個(gè)子空間的數(shù)據(jù)，不同條件下的不同人臉圖像數(shù)據(jù)可以看作多個(gè)子空間的并。子空間聚類(lèi)算法可以對(duì)人臉圖像特征進(jìn)行聚類(lèi)，同一個(gè)人的圖像被聚到一個(gè)子空間，從而達(dá)到人臉識(shí)別的目的。常用的人臉識(shí)別數(shù)據(jù)集有Yale B 人臉數(shù)據(jù)集[31]、PIE 人臉數(shù)據(jù)庫(kù)[32]和ORL 數(shù)據(jù)庫(kù)[33]等。

運(yùn)動(dòng)分割也是稀疏子空間聚類(lèi)算法的常見(jiàn)應(yīng)用。運(yùn)動(dòng)分割是根據(jù)視頻中不同的運(yùn)動(dòng)軌跡識(shí)別出不同的物體，主要目的是從固定背景中識(shí)別出作為前景的運(yùn)動(dòng)物體。利用子空間聚類(lèi)算法來(lái)進(jìn)行運(yùn)動(dòng)分割，可以將做剛性運(yùn)動(dòng)的物體的特征點(diǎn)進(jìn)行聚類(lèi)，聚類(lèi)的結(jié)果即為前景中的各個(gè)運(yùn)動(dòng)物體。如圖3 所示的Hopkins155 運(yùn)動(dòng)分割數(shù)據(jù)集[34]是常用的運(yùn)動(dòng)分割數(shù)據(jù)集，該數(shù)據(jù)集包含了視頻序列以及在幀中提取和跟蹤的特征，共計(jì)有155 個(gè)序列。

對(duì)生物學(xué)和醫(yī)學(xué)信息進(jìn)行信息挖掘也是稀疏子空間聚類(lèi)算法的一個(gè)新興應(yīng)用。例如，單細(xì)胞RNA 測(cè)序可用來(lái)分析細(xì)胞異質(zhì)性并從一堆細(xì)胞中鑒定出細(xì)胞的亞型。利用子空間聚類(lèi)算法，可以將同一類(lèi)型的細(xì)胞聚到一個(gè)子空間中，從而達(dá)到鑒定細(xì)胞類(lèi)型的目的[35]。

圖3 一些具有Hopkins155數(shù)據(jù)集特征的樣本

4 結(jié)語(yǔ)

稀疏子空間聚類(lèi)算法是有效處理高維數(shù)據(jù)的聚類(lèi)算法之一，它憑借著簡(jiǎn)單高效的優(yōu)勢(shì)被廣泛運(yùn)用在機(jī)器學(xué)習(xí)的各個(gè)領(lǐng)域，引起了學(xué)術(shù)界的廣泛關(guān)注。對(duì)稀疏子空間聚類(lèi)算法的研究將極大豐富高維數(shù)據(jù)處理方法，給高維數(shù)據(jù)的處理方法提供新的思路。本文詳細(xì)介紹了稀疏子空間聚類(lèi)算法的原理，經(jīng)典模型及近年的研究方向，并對(duì)算法的應(yīng)用和常用的公共數(shù)據(jù)集進(jìn)行了介紹，可望使讀者對(duì)稀疏子空間聚類(lèi)形成基本認(rèn)識(shí)，由此將該方法應(yīng)用到各種實(shí)際問(wèn)題上。