稀疏子空間聚類算法研究

黃佳雯，王麗娟，王利偉

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

0 引言

高維數據廣泛存在于圖像處理、計算機視覺、模式識別、生物計算機學等領域[1]。高維數據識別算法需要具有較好的時間和空間性能。同時由于噪聲的影響，處理過程中容易產生“維數災難”，嚴重影響算法識別性能。研究發(fā)現，高維數據具有低維子空間結構，即數據通常分布在多個低維子空間的并集上。例如，圖1 所示的兩個變化的兩個人臉圖像位于兩個低維空間上[2]?；謴蛿祿牡途S子空間潛在結構不僅有助于數據的存儲和管理，而且也能降低維數災難對于數據識別的影響，提高算法性能。子空間聚類算法可以有效恢復數據的低維子空間結構，并根據這種子空間結構將數據正確地劃分到每一個子空間所隸屬的數據類別[3]。

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

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

1 稀疏子空間聚類算法概述

圖像、視頻、文本和生物信息等數據廣泛存在，它們普遍具有高維、稀疏和噪音的性質，在識別過程中容易產生維數災難，影響影響識別效果。高維即是其數據維度多，有時甚至遠超樣本量。稀疏是指這些高維數據（維度h）映射到的低維子空間（維度d）上的表示系數矩陣呈現很強的稀疏性，其中d<

其中Zi表示第i 個子空間中數據的表示系數矩陣[5]。反之，當得到具有塊對角結構的Z時，即可得到輸入數據的子空間結構。稀疏子空間聚類算法就是利用不同的范數約束Z，使其盡可能具有塊對角的理想結構，從而探索到數據的子空間結構。它的流程如圖2所示，首先學習到表示系數矩陣Z，然后使用Z構造相似度矩陣W=(Z+ZT)/2，最后對W進行譜聚類即可得到聚類結果。

圖2 稀疏子空間聚類流程圖

2 稀疏子空間聚類算法研究

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

2.1 經典稀疏子空間聚類模型

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

SSC 使用l1范數約束Z，同時約束Zii=0 來避免每個數據僅用它自己表示的特殊情況。這種方法求得的Z，在數據所屬子空間獨立的情況下呈現塊對角結構，Z中塊的個數揭示了輸入數據子空間的個數，塊的大小揭露了各個子空間的維數。LRR 使用核范數來約束Z，它的模型如下：

它通過對表示系數矩陣Z的秩逼近得到數據的子空間表示。相比于SSC 的單獨考慮每個數據的稀疏表示，這種低秩約束有利于捕捉數據的全局結構。

2.2 最新的稀疏子空間聚類模型

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

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

（1）正則項改進

l0范數可以約束得到數據本質子空間，但對于l0范數的求解是一個NP 難問題。使用正交匹配追蹤（OMP）方法可以對其求解，但當數據量大的時候，這種方法效率很低。Li 等人[8]提出一種學習型OMP 方法（LOMP）來加速求解。它通過對OMP 方法得到的l0稀疏表示的學習得到單個隱藏神經網絡（SHNN），再將學習到的SHNN 用于新的數據稀疏表示矩陣學習上，從而提高效率。Hashemi 等人[9]在l0范數約束的基礎上引入正交最小二乘法的變體來加速求解，同時更有效地找到高維數據的底層子空間。

表1 幾種典型的子空間聚類模型

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

LRR 使用核范數來約束Z，這種方法擁有封閉解，解法簡單，但需要很強的子空間獨立假設且對數據質量有要求。Lu 等人[11]提出了一種k 塊對角約束，直接約束表示系數矩陣呈現塊對角結構，這種方法相對于LRR 無需那么強的子空間獨立假設。

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

（2）抗噪性改進

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

（3）子空間投影改進

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

（4）過程改進

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

（5）結合深度學習

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

3 算法應用

由于稀疏子空間聚類算法簡單高效，近年來在機器學習領域很受關注，并在人臉識別、運動分割、生物信息學等方面取得了成功的應用。

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

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

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

圖3 一些具有Hopkins155數據集特征的樣本

4 結語

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