數據增強的自適應權重稀疏子空間聚類算法

江雨燕，陶承鳳，李 平

（1.安徽工業大學 管理科學與工程學院，安徽 馬鞍山 243002；2.復雜系統多學科管理與控制 安徽普通高校重點實驗室，安徽 馬鞍山 243002；3.南京郵電大學 計算機學院，江蘇 南京 210023）

0 引言

聚類根據內在相似性對數據進行分組的過程。在實際應用領域中，數據具有高維性、復雜性，但是高維數據并不是均勻分布在所有維度空間，而是集中在某些低維結構中，可理解為若干個低維子空間的并集上。子空間聚類方法[1,2]能夠將源于不同子空間的高維數據映射至相應的潛在子空間，在圖像聚類、模式識別以及生物醫藥等多研究領域受到廣泛關注。

子空間聚類方法主要分為四種：（1）基于迭代的方法[3]，（2）基于統計的方法[4]，（3）基于代數的方法[4]，（4）基于譜聚類的方法[5]。最具影響力的子空間聚類方法利用數據構建鄰接矩陣，將譜聚類方法應用于鄰接矩陣，得到聚類結果。因此，譜聚類成為子空間聚類方法的主流，而該方法的難點在于如何構建一個好的鄰域矩陣。具有代表性的方法包括：稀疏子空間聚類(Sparse Subspace Clustering，SSC)[6,7]、基于低秩表示的子空間聚類(Subspace Clustering based on Low-rank Representation,LRR)[8]，它們之間的區別在于對鄰接矩陣的正則化方法不同。另外，結構化稀疏子空間聚類(Structured Sparse Subspace Clustering)[9]通過一種結構正則化方法來量化鄰接矩陣和分割矩陣之間的差異，從而將鄰接矩陣和子空間聚類兩個模塊相結合。文獻[10]采用鄰接矩陣的學習和聚類步驟共同進行的方法，將原始數據的空間信息納入考慮范圍。文獻[11]加入了運用判別信息的遷移學習，使之在特征域中與稀疏子空間聚類同時進行。文獻[12]提出了基于核理論的非線性拓展的方法。

但是原始數據中往往存在噪聲和其他干擾，直接對原始數據進行自表示得到的鄰域矩陣也受到噪聲或干擾的影響，不一定能反映數據的真實子空間隸屬關系，導致數據誤分類在網絡訓練過程中，兩個簇邊界附近的樣本可能不能被準確地分配到集群中心，這可能會混淆甚至誤導網絡的訓練過程，導致泛化性能下降。針對以上問題，本文提出數據增強的自適應權重稀疏子空間聚類模型(Self-Weighted Sparse Subspace Clustering based on Data Augmentation,SWSSC-DA)，該方法的創新主要包括：

（1）使用數據增強技術對原始數據進行隨機剪切、旋轉、翻轉和扭曲等方式進行變換獲取更多的樣本，此方法僅提前引入先驗知識，以適當的方式轉換圖像，但不會改變其身份。

（2）采用自適應權重學習，給每個樣本賦予不同的特征權重，每次傾向于選擇“簡單”（靠近聚類中心）的樣本作為訓練集，并逐步添加“較難”（邊界附近）的樣本。自適應權重學習的變量不存在超參數，并且總是保留邊界樣本。

1 相關理論

1.1 稀疏子空間聚類模型

稀疏子空間聚類[13]模型如圖1 所示，該模型是基于稀疏表示理論，利用一個數據樣本和所有樣本間的鄰域關系作為新特征來學習其自表示系數，通過自表示系數矩陣進一步構建相似度矩陣，最后借助譜聚類方法得到聚類結果。稀疏表示的目的是用盡量少的原子基來表示數據，這種方法對解決全局優化問題具有重要作用。

圖1 稀疏子空間聚類模型

為了求解最稀疏的zi值，最小化目標函數為：

式(2)中?0范數是指非零元素的個數，考慮數據的高維度特征，求解?0范數是NP-Hard 問題，因此使用?1范數來凸松弛?0范數，將式(2)改寫為：

矩陣形式的公式為：

考慮噪聲和離群值，式(4)可改寫為：

其中λ1、λ2是平衡參數，用于平衡目標函數；C∈?D×N表示離群點；E∈?D×N表示噪聲，‖·‖表示Frobenius 范數。

利用式(5)中的等式約束，消除E：

令Y=|C|+|C|T，其中Y為數據的相似度矩陣，將Y輸入譜聚類算法，獲得最終聚類結果。

1.2 自適應權重學習

自權重學習[14,15]模擬了人類的學習過程：從簡單到復雜。例如，給出一些新任務的樣本時，算法在每次迭代過程中首先傾向于選擇簡單樣本進行學習，逐漸選擇復雜樣本。規定具有較小損失的樣本為簡單樣本，具有較大損失的樣本為復雜樣本。自權重學習算法經過選擇樣本、調整模型的過程，在調整完模型后，再次選擇損失相對較小的樣本，并調整模型，不斷進行這樣的迭代。因此，在自權重學習中樣本的選擇并不是隨機的，也不是在一次迭代中全部納入訓練過程中，而是通過一種由簡到難的方式進行選擇。

給出學習模型f，其學習參數為v，并將D={(x1,y1),(x2,y2),(x3,y3),…,(xn,yn)} 作為訓練樣本，則傳統的機器學習目標可表示為：

而自權重學習的目標：

其中W=[w1,w2,…,wn]T為各個樣本的權重，g(λ,W)被稱作自權重正則化項，λ 作為衡量損失函數“簡單性”的標準。λ 和W通過交替搜索策略(ASS)進行優化。對于簡單的自權重學習，有g(λ,W)=-λW,W∈[0,1]。即：

給定樣本權值W，v上的最小化是一個加權損失最小化問題。當模型參數v固定時，最佳W具有如下閉式解：

自權重學習算法中λ 通常被設置為開始時損失的中位數，然后每隔幾次迭代增加步長δ。由于在訓練過程中，樣本的損失也在減少，因此步長δ難以選擇?；谝陨戏治?，模型根據訓練過程中損失的統計數據進行設置：

其中Lt表示第t次迭代中的所有損失，μ(*)和σ(*)為損失的平均值和標準差，T為最大迭代次數，由學習模型決定，不是一個獨立的超參數。圖2(a)顯示了傳統算法選擇樣本的情景，圖2(b)顯示了在開始時使用虛線圈中的樣本進行迭代更新，即自適應權重選擇樣本的情景。

圖2 選擇樣本迭代更新的過程

1.3 數據增強技術

深度神經網絡很容易導致數據過擬合，這一問題可以通過獲取更多的訓練數據、限制深度神經網絡的能力或提前停止來解決。而數據增強是擴展訓練數據集的一種有效方法，對于一個給定的圖像樣本，在將它輸入網絡之前，通過隨機旋轉、移位、剪切及扭曲等方式進行變換獲取更多的樣本，如圖3 所示。數據增強技術提前引入先驗知識，以適當的方式轉換圖像但不會改變其身份。數據增強技術現已在監督模型中應用，但是在無監督聚類分析中被忽視[16]。

圖3 數據增強技術

2 數據增強的自適應權重稀疏子空間聚類

2.1 提出的模型

在深度神經網絡訓練過程中，數據增強技術通過隨機旋轉、移動、裁剪、剪切等方式進行圖像變換，擴展了訓練數據集，解決了數據的過擬合問題。受其啟發，本文提出在稀疏子空間聚類模型進行稀疏表示之前，對原數據進行數據增強處理，以適當的方式轉換圖像，但并不會改變數據本身。

由于稀疏子空間聚類模型在迭代過程中，總是隨機選擇樣本進行訓練，并沒有考慮兩個簇邊界的樣本會誤導訓練效果。本文提出使用自適應權重學習對每個樣本賦予不同的權重，由“簡單”（靠近聚類中心）樣本到“較難”（邊界附近）樣本的先后順序進行迭代。求出優化解、獲得鄰域矩陣，將其進行譜聚類，數據增強的自適應權重稀疏子空間聚類模型如圖4 所示。

圖4 數據增強的自適應權重稀疏子空間聚類模型

為了使模型更具魯棒性，提出對原樣本xi∈X(X∈?D×N)設置不同的權重，每次迭代選擇最具說服力的樣本，特別地，這種自適應權重學習的方式不會改變數據的結構信息。因此，式(6)可以改寫為：

定義映射Λ 表示數據增強函數，可以是任意旋轉、移位、剪切、扭曲等的組合，數據增強后的樣本表示為=Λ(X),X∈[x1,x2,…,xn]T。將上式中的原樣本X替換為增強樣本，式(12)改寫為：

實際上，數據位于放射子空間而非線性子空間的并集。為了將位于仿射子空間并集中的數據點進行聚類，稀疏子空間方程可優化為：

引入輔助變量A∈?N×N，加入參數λ3和2 個懲罰因子：

引入拉格朗日乘子δ∈?N，Δ ∈?N×N得到數據增強的自適應權重稀疏子空間聚類算法的目標函數：

其中，λ 由（11）計算，上式的優化解通過交替方向乘子法計算；令S=|C|+|C|T，其中C為稀疏表示矩陣，S為數據的相似度矩陣，最終使用譜聚類方法得到聚類結果。

表1 參數符號說明

2.2 算法優化

1.固定Z,C,W,δ,Δ，通過更新A極小化L：

其中，λ 由（11）計算。

2.3 時間復雜度

本文算法中更新變量A,C,W,δ,Δ 的計算復雜度均為O(n2)，更新鄰域關系矩陣需要求解Sylvester 方程，則計算復雜度為O(n3)，因此算法的總計算復雜度為T×O(n3)，其中T 為迭代次數。

3 實驗設置及結果分析

本文的實驗環境為Microsoft Windows 10，處理器為英特爾酷睿i7，內存容量8 GB，顯卡配置為MVIDIA GeForce 920 M。模型在同一數據集進行5 次獨立實驗，取平均值作為最終實驗結果。

3.1 數據集

模型在常見數據集上進行大量實驗，以驗證所提算法的有效性，數據集包括：MNIST[17]、USPS[18]、ORL[19]數據集，圖5 展示了這些數據集中的部分圖像。

圖5 部分樣本圖片

（1）MNIST 數據集：由訓練集中60 000 個樣本和測試集中10 000 個樣本組成。本文取訓練集每類手寫字的前100 幅圖像來進行了實驗，將圖像大小調整為28×28。

（2）USPS 數據集：含有11 000 張圖像，是由“0”-“9”共10 個手寫數字的類組成。本文使用每個手寫數字的前100 張圖像的子集進行實驗，將圖像大小調整為16×16。

（3）ORL 數據集：有40 名受試者，每名受試者有10 個樣本，則人臉圖像共計400 張。每名受試者圖像在不同的光照條件下拍攝，帶有不同的面部表情(睜眼/閉眼、微笑/不微笑)或面部飾品(有/無眼鏡)，將圖像大小調整為32×32。

3.2 評價指標

為了評估聚類算法的性能，本文采用了準確度（ACC）評價指標，ACC 的值越大，聚類性能就越好。

ACC 被定義為：

其中yi是標簽，ci是模型的聚類分配，m(·)是聚類分配和標簽之間的映射函數，1(·)是指示器函數返回1 或0。

3.3 與其他方法的對比分析

本文將該方法與以下幾種方法在上述數據集上進行了比較，其包括：SSC、LRR、LSR、SSSC、SRR。

稀疏子空間聚類(Sparse Subspace Clustering,SSC)：利用稀疏線性組合特征表示數據點之間的關系，并構造子空間近鄰矩陣。

低秩表示(Low Rank Representation,LRR)：此方法的鄰域矩陣是通過對數據施加低秩約束來獲取，從而捕獲數據的全局結構。

最小二乘回歸(Least Squares Regression,LSR)[20]：對自表示系數采用范數正則化，具有將高度相關的數據聚集在一起的優點，但也會導致類內類間的自表示都是均勻的，不利于分離不同類別數據。

結構化稀疏子空間聚類(Structured sparse subspace clustering,SSSC)：利用結構化稀疏線性組合特征表示數據點之間的關系，同時引入聯合正則化項實現系數矩陣和聚類標簽的聯合學習，使得模型直接輸出得到聚類標簽。

基于結構化稀疏關系表示的子空間聚類(Subspace clustering via structured sparse relation representation,SRR)[21]：首先對原始數據進行自表示得到鄰域關系矩陣，反映了每個數據與其它數據的某種相關性；然后將每個數據的自表示向量作為數據的新特征，對其再進行二階自表示得到重構系數矩陣，由此矩陣構造相似度，并用譜聚類得到最終聚類結果。

將本文算法與上述幾種算法結果匯總，如表2-3 所示。為確保實驗的公平性，上述算法實驗均由作者提供的代碼進行，具體參數根據論文設置為最優。

表2 不同算法在MNIST、USPS、ORL 數據集上聚類準確度(%)對比

由表2 可知，在3 個公開數據集上，本算法精確度相比其他子空間聚類算法均得到一定的提高。相比最優算法SRR，在數據集MNIST 上精確度提升了3.77%、在USPS 上精確度提升了4.30%、在ORL 上精確度提升了2.45%。這說明模型使用隨機位移和旋轉對原樣本進行數據增強，通過交替地使用增強樣本來訓練和優化自編碼器，并更新樣本的集群分配，能夠學習到穩健的特征；并且，為了穩定網絡訓練，利用無需額外超參數的自適應自步學習，在每次迭代中選擇最具說服力的樣本能夠較好地提高泛化能力。

將所有模型在3 個數據集中指定數據上的運行時間進行對比，由表3 可知，算法LSR 的運行時間最少。運行時間長短與算法的計算復雜度有關，本文算法與SRR 算法同為3 階計算復雜度，但本文算法的實際運行時間少于SRR，說明在運行時間上有一定的提升。

表3 不同算法在MNIST 訓練集每個數字前100 幅圖片、USPS 訓練集每個數字前100 幅圖片、ORL 的40 個對象的運行時間（秒）對比

3.4 SWSSC-DA 不同部分的結果分析

在實驗中，通過消融實驗分析本文提出的數據增強(DA)和自適應權重學習(SW)兩個部分的貢獻，從SWSSC-DA 中刪除DA 意味著在（16）中用替換。在SWSSC-DA 中禁用SW 對應于在（16）中固定W=1。移除所有這三個部分的配置視為稀疏子空間聚類(SSC)。

表4 顯示了不同配置下的SWSSC-DA 的結果，分別將DA、SW 之一添加到SSC 中時，性能在大多數情況下都會有所提高。由表4 可以得出：在SSC 算法中單獨加入DA 比單獨加入SW 的精確度更高，這是因為數據增強技術通過隨機位移和旋轉對原數據集進行擴充，獲得了更多的樣本數據圖像。雖然在USPS 數據集上單獨加入DA或SW 的效果并不是特別的出眾，但是兩個一起加入時也有提升。通過引入所有這三個部分，SWSSC-DA 成功地在所有數據集上實現了最好的性能。

表4 不同配置下的SWSSC-DA 的結果對比

3.5 超參數靈敏度分析

在涉及深度神經網絡時，存在一些無法避免的超參數，本文研究了超參數在數據增強中的敏感性。在實驗中，只使用隨機旋轉和移位。采用0o,10o,...,60o進行旋轉，采用0,1,...,6 像素進行移位轉換，在每個得到的49 個網格上運行SWSSCDA 算法兩次，并取平均結果。由于過多信息的丟失會導致模型的性能急劇下降，如圖6 所示，在MNIST 數據集上旋轉[0o,30o]和移動[0,3]像素的范圍內，在USPS 數據集上旋轉[0o,40o]和移動[0,4]像素的范圍內，在ORL 數據集上旋轉[0o,40o]和移動[1,4]像素的范圍內，該模型的性能較穩定，總體來說，本文提出的算法對大范圍內的數據增強所引入的超參數不敏感。

圖6 隨機旋轉和移位在數據增強中的敏感性

4 結束語

本文提出了數據增強的自適應權重稀疏子空間聚類模型（SWSSC-DA）來學習魯棒的面向聚類特征。模型在網絡訓練中通過自適應權重學習優先選擇易分類的樣本，將集群邊界附近的樣本排除在訓練之外，避免難分類樣本產生誤導性的記憶。將數據增強技術引入稀疏子空間聚類，通過隨機旋轉和移位擴充數據樣本。模型在三個公開數據集上進行實驗，獲得了比傳統聚類算法更好的聚類效果，提高了聚類精確度。通過消融實驗、超參敏感度和收斂性分析等加強驗證了本文所提算法的有效性。將對抗性學習方法引入子空間聚類，生成對抗自編碼器能更加精準地對樣本進行聚類分配并提高聚類精度是下一步研究的方向。