基于Hessian正則化和非負約束的低秩表示子空間聚類算法

范莉莉，盧桂馥，唐肝翌，楊 丹

（安徽工程大學計算機與信息學院，安徽蕪湖 241000）

0 引言

在信息社會高速發展的今天，高維數據越來越多，結構越來越復雜，如何進行高維數據聚類分析已成為亟須解決的難題。人們通常假設高維數據分布于一個聯合的低維子空間中，這一合理假設推動了子空間聚類算法的發展。目前，子空間聚類［1-4］已成為解決高維數據聚類的一種重要方法，廣泛應用于計算機視覺、模式識別和機器學習等相關領域的研究中。

子空間聚類的思想［5］是將來自多個線性子空間的一組高維數據，根據類別的不同分割到相互獨立的子空間中。常用的子空間聚類算法主要有：迭代方法、代數方法、統計方法和基于譜聚類的方法。基于譜聚類的方法［6-7］因在算法效率和聚類精度上的較好效果，是目前子空間聚類算法的重點研究方向。該方法主要利用數據點周圍的局部信息或全局信息的相似性構造親和矩陣，然后運用譜聚類方法得到聚類結果。數據點間的最優表示直接影響后面的聚類效果。

稀疏子空間聚類（Sparse Subspace Clustering，SSC）算法［8］和低秩表示（Low-Rank Representation，LRR）子空間聚類算法［9-10］是代表性的兩種子空間聚類算法，它們通過基于稀疏和低秩表示來有效處理噪聲和異常值。SSC 算法利用L1范數設置類間相似性為0、類內相似性為1 來保證矩陣的稀疏性，但因忽略數據間的關聯性，使得系數矩陣表示過于稀疏，可能會降低聚類的準確性。LRR 算法解決了這一問題，其通過最小核范數尋求數據全局結構的低秩表示，并對含噪聲和重大污染的數據有較好的魯棒性。文獻［11］提出的最小二乘回歸（Least Squares Regression，LSR）子空間聚類算法在子空間獨立的假設下，能獲得矩陣的塊對角結構，更好地保持數據的聚集性。

上述經典算法為子空間聚類的研究奠定了很好的基礎，近年來，不斷有新的改進方法被提出來以提高聚類效果。文獻［12］利用矩陣的Forbenius 范數對系數矩陣進行約束，通過高效密集子空間聚類（Efficient Dense Subspace Clustering，EDSC）來有效處理噪聲和異常值，提高聚類準確度。文獻［13］使用具有對稱約束的低秩表示（Low-Rank Representation with Symmetric Constraint，LRRSC）來解決子空間聚類問題，通過將對稱約束集成到高維數據表示的低秩屬性中，擴展了原始的低秩表示算法。文獻［14］從原始數據的低維空間動態學習親和矩陣，通過低秩稀疏子空間（Lowrank Sparse Subspace，LSS）聚類方法提高聚類性能。然而這些算法都忽略了數據間的局部相關性，不能很好地揭示局部數據間的關系。為此，研究者們采用流形學習的方法來保持原有數據的拓撲和幾何結構，以體現數據的局部流形特征。

目前大多數基于流形學習的子空間聚類主要應用拉普拉斯正則化來提升算法性能。文獻［15］通過拉普拉斯正則化LRR（Laplacian regularized LRR，LapLRR）來探索數據的全局和局部流形結構，利用流形正則化來增強LRR 的性能。文獻［16］提出了一個廣義拉普拉斯正則化低秩表示框架，利用圖正則化不僅可以表示全局低維結構，而且可以捕獲局部數據結構中的非線性幾何信息。文獻［17］將圖正則化引入到LRR 中，提出的圖正則化LRR（Low-Rank Representation with Graph Regularization，LRRGR）算法集成了流形學習和低秩表示，可以很好地利用樣本的全局和局部結構信息，并對噪聲具有較好的魯棒性。文獻［18］提出的圖正則化最小二乘回歸（Graph-regularized Least Squares Regression，GLSR）算法，通過使用最小二乘回歸代替核范數來產生分組效應，同時利用流形約束來保留樣本的局部幾何結構。這些算法通過使用拉普拉斯正則項來對數據的局部相關性進行表示，都較好地提高了子空間聚類的性能。然而，已有研究［19-20］表明拉普拉斯正則化使得該項的極小解傾向于一個常數，不能很好地保持數據的局部拓撲結構，這也導致了拉普拉斯算子缺乏推測能力。與傳統的拉普拉斯正則化相比，Hessian 正則化有良好的推測能力，它不依賴于常量函數，該項的極小化使得最優函數為流形上的線性函數，從而可以更好地利用數據的拓撲信息，因此Hessian 正則化往往比拉普拉斯正則化更適合維護數據的局部流形結構。此外，現有算法求得的系數矩陣往往有正有負，而負值往往沒有實際的意義。

近幾年，隨著神經網絡的迅猛發展，深度學習在圖像處理領域顯示出了其強大的優勢。文獻［21］利用深度神經網絡，提出了一種深度嵌入式聚類（Deep Embedded Clustering，DEC）方法，通過特征學習在低維空間中迭代優化聚類目標。文獻［22］在深度自動編碼器的基礎上提出了一種無監督的深度子空間聚類網絡（Deep Subspace Clustering Networks，DSC-Nets），利用自表達層來學習親和矩陣。文獻［23］提出了一種有監督的深度學習方法來優化嵌入函數，降低時間復雜度。文獻［24］對稀疏子空間進行深度擴展，提出了L1范數的深度子空間聚類（Deep Subspace Clustering with L1-norm，DSC-L1）方法，可同時滿足親和矩陣的稀疏性及神經網絡的非線性特點。上述方法都利用深度網絡有效降低了分類錯誤率，體現出了良好的性能。然而，這些深度模型結構復雜、參數眾多（幾百萬甚至更多的參數），算法復雜度高。為了達到算法的最佳性能，需要不停地調參，所需時間很長，且其應用在中小規模數據集時容易產生過擬合，因而其往往更適合大規模數據集的數據處理。而本文提出的算法參數較少（三個參數），算法復雜度低，能比較容易地達到算法的最佳性能，實驗結果表明，其在一些常見的數據集上可以得到較好的聚類效果。

基于以上問題，本文提出了一種基于Hessian 正則化和非負約束的低秩表示子空間聚類算法（Low-Rank Representation subspace clustering algorithm based on Hessian regularization and Non-negative constraint，LRR-HN）。在LRR-HN 中：1）考慮到系數矩陣中的負值往往沒有實際意義，將非負約束引入低秩表示的目標函數，來保證系數矩陣的有效性；2）受流形學習的影響，考慮到Hessian 正則項在保持數據局部拓撲結構上的良好表現［25-26］，將Hessian 正則項作為懲罰函數加入到目標函數，來更好地保持數據間的局部幾何結構。此外，通過利用自適應懲罰的線性交替方向法，本文還設計了一種求解LRR-HN 的有效算法。在一些實際數據庫上的實驗表明，LRR-HN 優于現有的一些算法，具有更好的聚類性能。

1 相關算法

1.1 LRR 算法

給定一個數據矩陣X，X的N個數據點來自d個線性獨立子空間的并，子空間聚類的目標是求解子空間的數目d和它們的維數，并將數據點分割到對應的子空間中。

LRR 算法［10］的基本思想是將數據矩陣X表示成在字典矩陣A下的線性組合。最理想的情況為數據是干凈的。最小化模型的秩函數為：

由于秩函數的優化問題是NP-hard，很難求解。一般的處理方法是用核函數來代替秩函數，最小化模型的核函數為：

對于數據點有噪聲的情形，加入噪聲項E來增加魯棒性，得到LRR 的基本模型為：

1.2 Hessian 能

設fk是將高維數據點xi映射為Vki的函數，即fk(xi)=Vki。設Np(xi)為數據xi的p個最近鄰數據的集合，則fk在xi處的Hessian 可近似為：

2 Hessian 正則化的非負低秩表示

在本章中，針對LRR 算法數據局部相關性缺失及系數矩陣有正有負等問題，把非負約束和Hessian 正則項引入到目標函數（1），提出了基于Hessian 正則化和非負約束的低秩表示子空間聚類算法（LRR-HN）。

2.1 LRR-HN的目標函數

一般來說，從模型中獲得的系數矩陣有正有負，但在實際應用場景中，系數矩陣中的負值可能是不合理且沒有意義的。為了使系數矩陣更加合理和有意義，本文通過Z的非負約束，即Z≥0，保證每個數據點都位于其鄰接點的凸包中，更能體現數據點之間的關聯，使其在局部結構描述上更有意義。

另外，基于流形假設，即如果兩個數據點在數據分布的本質幾何結構中相近，那么這兩個數據點在嵌入或投影到新的空間中也相近。因此為了保持數據局部拓撲結構，鑒于Hessian 能的良好性能，本文把Hessian 正則項=tr(VTMV)作為懲罰項融入低秩表示的目標函數（1）中，來更好地表達局部數據間的相關性。

將系數矩陣Z代入Hessian 正則項，則LRR-HN 的目標函數最終定義為：

2.2 LRR-HN的求解算法

為求解問題（2），本文采用自適應懲罰的線性交替方向法（Linearized Alternating Direction Method with Adaptive Penalty，LADMAP）［27］求解。使用X作為字典并引入輔助變量C，將式（2）轉化為

式（3）的增廣拉格朗日函數為

其中：μ＞0是懲罰參數，Y1、Y2為拉格朗日乘子。

固定C，E，更新Z：

式（6）沒有閉合解。通過應用LADMAP［27］，本文將L1中的平滑部分表示為：

那么L1的最小化問題可替換為求解下列問題：

綜上所述，LRR-HN的求解算法如算法1所示。

算法1 LRR-HN的求解算法。

2.3 基于LRR-HN的子空間聚類

通過求解式（2）得到系數矩陣Z*后，本文采用文獻［17］的方法構造親和矩陣，然后應用K-means 方法得到最終的聚類結果。基于LRR-HN 的子空間聚類算法如算法2 所示。

算法2 基于LRR-HN的子空間聚類算法。

2.4 收斂和復雜性分析

算法1 是LADMAP 的直接應用，可收斂到式（2）的全局最優解。有關LADMAP 的收斂證明，可詳見文獻［27］。

通過奇異值閾值更新Z時，本文可以使用文獻［29］中提到的秩預測策略來預測Zk+1的秩r，然后對Z進行奇異值分解，取前r個奇異值及對應的向量。這使得奇異值分解的計算復雜度為O(rn2)，其中n為數據矩陣X的列數。但此時算法1 的復雜度仍為O(n3)，因為構造Zk是全尺度的矩陣乘法。采用文獻［27］中的Lanczos 方法，只需要Zk的縮減矩陣乘法，其中Z=Zk-?zq(Zk)/η1。這樣處理后，算法1 的迭代復雜性為O(rn2)。

3 實驗及結果分析

3.1 實驗設置

3.1.1 實驗所用的數據集

為了驗證算法的有效性，分別在Yale 數據集和ORL 數據集上進行了實驗。Yale 數據集由耶魯大學創建，里面包含15 個人的165 幅灰度人臉圖像。每個人在不同的表情、姿態、光照等條件下拍攝11 張照片。本實驗中，圖像的大小為32×32。圖1 為用于實驗的Yale 數據集中的部分圖像。

圖1 Yale數據集中的部分圖像Fig.1 Some images in Yale dataset

ORL 數據集由劍橋大學創建，里面包含40 個人的面部圖像。每個人在較暗的均勻背景下拍攝10 張照片，這些照片是在不同的時間、光照、面部表情和面部細節環境下采集的。本實驗中，圖像的大小為32×32。圖2 為用于實驗的ORL 數據集中的部分圖像。

圖2 ORL數據集中的部分圖像Fig.2 Some images in ORL dataset

3.1.2 方法比較

實驗中將本文算法分別與K均值（K-means）［30］、非負矩陣分解（Non-negative Matrix Factorization，NMF）［31］、主成分分析（Principal Component Analysis，PCA）［32］、歸一化切割（Normalized cut，Ncut）［33］、LRR［10］和自適 應低秩表示（Adaptive Low-Rank Representation，ALRR）［4］等6 種具有代表性的算法進行比較，以驗證本文所提算法的有效性。

K-means 是一種基于距離的聚類算法。其思想是隨機選擇幾個類作為初始的聚類中心，根據每個樣本與聚類中心的距離劃分類別，更新聚類中心，重復以上過程，直到收斂為止。

NMF 是一種無監督學習算法。NMF 算法能夠將一個任意給定的非負矩陣分解為左右兩個非負矩陣的乘積，從而對數據進行降維。本文實驗中將原始數據應用NMF 降維后采用K-means 進行聚類。

PCA 是一種常用的無監督數據降維方法。通過線性變換將原始數據變換為一組各維度線性無關的表示，可用于特征提取及噪聲去除。本文實驗中將原始數據應用PCA 降維后采用K-means 進行聚類。

Ncut 是一種譜聚類方法。其通過鄰接矩陣求解特征值及特征向量，將特征向量歸一化后構造新的矩陣，然后應用K-means 進行聚類。

LRR 是一種低秩表示的子空間聚類算法，通過尋找數據在自身數據字典上的低秩表示來求解親和矩陣，然后應用Ncut 方法進行聚類。

ALRR 是一種自適應低秩表示算法，可用于子空間聚類。其通過自適應字典學習策略獲取投影矩陣和低秩表示，然后將Ncut 方法應用于親和矩陣進行聚類。

3.1.3 評價準則

為評估所提出算法的性能，本文采用正確率（ACcuracy，AC）和歸一化互信息（Normalized Mutual Information，NMI）兩種評價準則［34］來對算法性能進行定量評價。

設xi為數據樣本，gi為樣本xi的真實類別，為樣本xi聚類求出的類別，則AC 方法定義為：

其中：n為樣本總數，δ(a，b)為delta 函數，當且僅當a=b時，δ(a，b)=1；否則，δ(a，b)=0。

設兩種聚類結果為D和D′，則NMI方法定義為：

其中：H(D)和H(D′)表示聚類D和D′的熵，MI(D，D′)表示D和D′的互信息。

本文算法中主要涉及3 個參數，分別是平衡參數λ1、λ2和λ3。在本次實驗中將會分析3 個參數在不同數據集中對AC 和NMI 兩個評價準則的影響。本文的實驗環境為Microsoft Windows 10，處理器為英特爾酷睿i5，內存容量16 GB，所有算法采用Matlab 2016a 編程實現。

3.2 聚類結果分析

Yale數據集中包含15個人，每人11張照片。為了更好地比較不同算法上的聚類結果，分別選用前m（5、8、12、15）個類別相關數據進行聚類。不同算法在Yale 數據集上的聚類結果如表1所示。

表1 不同算法在Yale數據集上的聚類結果 單位：%Tab.1 Clustering results of different algorithms on Yale dataset unit：%

ORL數據集中包含40個人，每人10張照片。分別選用前m（10、20、30、40）個類別相關數據進行聚類，不同算法在ORL數據集上的聚類結果如表2所示。

表2 不同算法在ORL數據集上的聚類結果 單位：%Tab.2 Clustering results of different algorithms on ORL dataset unit：%

表1、2中的每條數據都是重復進行20次實驗取平均得到的。其中LRR和ALRR 算法的聚類結果是在源代碼的基礎上通過搜索選取最優參數獲得的。由表1～2 中的數據可以看出，與經典的K-means、NMF、PCA、Ncut等算法相比，LRR 算法因低秩結構表現出了良好的聚類性能，AC和NMI的值遠高于這些經典算法。ALRR 算法在低秩表示基礎上增加了自適應性，實驗結果表明，ALRR 算法的聚類結果在ORL 數據集上優于LRR 算法，在Yale 數據集上與LRR 算法不相上下。而本文提出的LRR-HN，在AC 和NMI 上均高于LRR 算法，且在大多數情況下優于ALRR 算法。這表明Hessian 正則項的引入和系數矩陣的非負約束能夠更好地保持數據的局部拓撲結構，更能體現數據間的關聯，從而提高算法的聚類效果。

3.3 不同參數對本文算法的影響

在本文算法中，平衡參數λ1、λ2和λ3的取值對聚類結果的影響較大。為討論3 個參數對本文算法的影響，在本次實驗中，采用固定其中兩個參數，然后對另一個參數取不同的值來觀察AC 和NMI 的變化。

在Yale 數據集上，設置聚類數目為15，λ1=1，λ2=1.5，λ3=0.4。固定其余兩位參數的值，分別對λ1、λ2、λ3的不同取值進行實驗，AC 和NMI 的變化曲線如圖3～5 所示。從圖3～5中可以看到，AC 在λ1取值為｛10-3，10-2，10-1，100｝，λ2取值為｛1.5，2，2.5，3｝，λ3取值為｛0.005，0.01，0.05，0.1，0.5｝時，AC 的變化相對較小。而NMI 在λ1和λ2的取值區間中起伏較大，但最優性能顯著，在λ3的取值區間中變化基本平穩。

圖3 Yale數據集上不同λ1時的AC和NMI變化曲線Fig.3 Change curves of AC and NMI with different λ1 on Yale dataset

在ORL 數據集上，設置聚類數目為40，λ1=10-3，λ2=1.9，λ3=1.1。固定其余兩位參數的值，分別對λ1、λ2、λ3的不同取值進行實驗，AC 和NMI 的變化曲線如圖6～8 所示。從圖6～8中可以看到，AC 和NMI 在λ1取值為｛10-6，10-5，10-4，10-3｝，λ2取值為｛0.5，1，1.5，2，2.5，3｝時，變化基本平穩，在λ3取值為｛10-3，10-2，10-1，100，101｝時，AC 和NMI 略有起伏，但變化不大。

圖4 Yale數據集上不同λ2時的AC和NMI變化曲線Fig.4 Change curves of AC and NMI with different λ2 on Yale dataset

圖5 Yale數據集上不同λ3時的AC和NMI變化曲線Fig.5 Change curves of AC and NMI with different λ3 on Yale dataset

圖6 ORL數據集上不同λ1時的AC和NMI變化曲線Fig.6 Change curves of AC and NMI with different λ1 on ORL dataset

圖7 ORL數據集上不同λ2時的AC和NMI變化曲線Fig.7 Change curves of AC and NMI with different λ2 on ORL dataset

從圖3～8 可知，由于不同的數據集受噪聲影響程度不同，平衡參數的最優值也不相同；但在合適的參數區間上，本文提出的LRR-HN表現出了較好的穩定性。

圖8 ORL數據集上不同λ3時的AC和NMI變化曲線Fig.8 Change curves of AC and NMI with different λ3 on ORL dataset

4 結語

受流形學習思想的啟發，本文提出了一種基于Hessian正則化和非負約束的低秩表示子空間聚類算法。首先，該算法利用核范數來探索數據的全局結構，使得來自同一子空間的高相關數據劃分為同一類別。其次，引入了Hessian 正則項，采用近鄰樣本對數據線性表示，來加強數據間的局部相關性。為了更好地表征數據的局部結構，本文利用非負約束來保證解的有效性。最后，采用自適應懲罰的線性交替方向法求解，并在兩個標準數據集上進行實驗對比，表明了所提算法的可行性。