判別性增強的稀疏子空間聚類

胡慧旗，張維強，徐晨

（深圳大學 數學與統計學院，廣東 深圳 518060）

0 概述

子空間聚類是一種非常有效的高維數據聚類方法，假設高維數據分布在幾個低維子空間的并中，其目的是將高維數據分成不同的類，一類對應一個子空間。目前，子空間聚類已被廣泛應用于計算機視覺［1］、圖像處理［2-3］、系統識別［4］等領域。基于譜聚類的子空間聚類算法因其計算簡單、聚類性能優異而成為研究熱點。稀疏子空間聚類（SSC）［5-6］、低秩表示子空間聚類（LRR）［7-8］和最小二乘回歸子空間聚類（LSR）［9］是基于譜聚類的子空間聚類中3 個經典的算法，它們的共同點是利用高維數據的自表示構建相似度矩陣，然后通過譜聚類得到聚類結果。3 種算法的不同點在于自表示系數的約束不同：SSC 對自表示系數矩陣采用l0或l1范數約束，希望每個數據的自表示是稀疏的，僅被其所屬子空間（即同類）的數據表示，但是稀疏約束會導致自表示過于稀疏，即僅從同類數據中挑選最相似的數據對其表示，忽略了其他相關的數據，不利于聚類；LRR 對自表示系數矩陣采用低秩約束，這是一種全局結構，但低秩表示可能導致過于稠密的自表示，即不同子空間的數據參與了表示，另外，當數據采樣不足時，低秩表示可能會失效；LSR 對自表示系數采用l2范數正則，這有利于將高度相關的數據聚集在一起，但也會導致類內類間的自表示都是均勻的，不利于分離不同類別的數據。

在子空間獨立的條件下，以上3 種算法都被證明自表示系數矩陣是一個分塊對角矩陣，即來自不同子空間數據間的表示系數為零。自表示系數矩陣的塊對角結構揭示了數據與低維空間的真實隸屬關系，從而相應相似度矩陣表現出類內相似度高、類間相似度低的特性，這有利于譜聚類產生正確的聚類標簽。因此，子空間聚類問題關鍵在于自表示系數矩陣的構造，理想的自表示系數矩陣應同時具有稀疏性和聚集性，即類間稀疏、類內聚集。鑒于這一考慮，很多算法［10-12］對數據的自表示矩陣同時進行稀疏約束和低秩約束，或者同時進行稀疏約束和l2范數約束，強制自表示系數矩陣具有稀疏性和聚集性。FENG等［13］指出自表示系數矩陣應具有塊對角結構，并通過添加顯式的硬約束，強迫SSC 和LRR 得到的自表示系數矩陣具有精確的塊對角結構。進一步地，LU等［14］提出K塊對角正則項，迫使自表示系數矩陣具有塊對角結構。考慮模型的整體性能，LI等［15］提出結構稀疏子空間聚類（SSSC）模型，通過引入聯合正則項實現系數矩陣和聚類標簽的聯合學習，使得模型直接輸出聚類標簽。受SSSC 模型啟發，ZHANG等［16］在LRR 模型中加入聯合正則項，提出低秩結構稀疏子空間聚類（LRS3C）模型，構建了一個聯合優化框架。在LRS3C 基礎上，YOU等［17］通過添加促使低相關數據盡量遠離的l1范數正則項，防止系數矩陣過于密集，加強了類間數據的稀疏性，進一步提升了聚類性能。

然而，原始數據中往往存在噪聲和其他干擾，直接對原始數據進行自表示得到的相似度矩陣也會受到噪聲或干擾的影響，導致不能準確反映數據的真實子空間隸屬關系，造成數據誤分類。針對此問題，SRR［18］對原始數據進行了二階自表示：首先對原始數據進行自表示，由于得到的自表示矩陣反映了每個數據與其他數據的某種相關性，因此稱其為鄰域關系矩陣；然后將每個數據的自表示向量作為數據的新特征，對新特征再進行二階自表示，也稱為重構系數矩陣；最后基于此矩陣構造相似度矩陣，并通過譜聚類得到最終聚類結果。實驗結果表明，該方法具有較高的聚類精度。

本文基于SRR 中數據的鄰域關系可準確反映數據類別屬性這一特點，提出一種兼顧相似度矩陣稀疏性和聚集性的子空間聚類方法。利用F 范數代替核范數，降低SRR 模型的求解難度，并構建一個新的正則項來增強不同類別數據之間表示系數的判別性。在此基礎上，使用人臉和手寫體數字數據集進行實驗，驗證本文方法的聚類效果。

1 符號定義與相關工作

考慮到原始數據中存在大量噪聲和干擾，WEI等［18］認為數據間的鄰域關系特征比原數據更能揭示其類別屬性，并提出如下SRR 模型：

其中：X表示原始數據矩陣，其中一列對應一個數據樣本；C為鄰域關系矩陣；Z為重構系數矩陣；用于刻畫數據中的離群點；用于處理鄰域關系矩陣中的高斯噪聲；λ1和λ2為權重參數。在SSR 模型中：首先鄰域關系矩陣C的每一列表達了原始數據矩陣X中的對應列與其他數據之間的某種相關性，并利用l1范數對其進行約束；然后將C作為原始數據X的新特征進行自表示或自重構，用核范數來約束重構系數矩陣Z；最后用Z計算相似度矩陣，并通過譜聚類得到聚類結果。實驗結果表明，該模型能夠顯著提升子空間聚類性能。

本文在SRR 模型基礎上進行改進，提出一個新的模型，并給出求解算法。

2 判別性增強的稀疏子空間聚類模型

2.1 模型構建

文獻［19］中證明，在一定條件下，基于F 范數的表示和基于核范數的表示是等價的，而平方F 范數最小化問題不需要矩陣奇異值分解運算。因此，本文利用平方F 范數代替SRR 中的核范數，使模型易于求解。F 范數能夠保證重構系數矩陣Z的類內一致性，但是不能保證類間判別性，而C的l1范數有利于保證C的類間判別性，不能保證類內聚集性。因此，本文引入新的正則項來保證Z的類間判別性和C的類內聚集性。實際上有兩重作用：當C給定時，若Ci、Cj不相似，即較大，則該正則項有利于使Zij接近于0，從而兩個對應數據的相似度較小，有利于將其分為不同類；反之，當Z給定時，若兩個數據的相似度|Zij|較大，則該正則項有利于使新特征Ci、Cj相似，從而保證特征的類內聚集性。

綜上，本文給出以下改進的SRR 模型：

其中：α是權衡參數；diag(Z)=0 防止出現平凡解。

2.2 模型求解

本文采用交替方向乘子法（ADMM）［20-21］求解式（2）模型，引入輔助變量J和P，使模型轉變為：

式（3）模型的增廣拉格朗日函數表示為：

其中：Y1、Y2、Y3、Y4是拉格朗日乘子；μ1、μ2、μ3、μ4是懲罰項。交替更新J、C、Z、P、E1、E2、Y1、Y2、Y3、Y4，更新一個變量的同時固定其他變量的值。

固定其他變量，關于J的子問題為：

利用軟閾值算子求解式（5），得到J的解為：

固定其他變量，關于C的子問題為：

式（9）是關于C的二次函數，其最優解滿足以下方程：

式（10）是一個標準的Sylvester 方程，可以通過Matlab 的lyap 函數解決。

固定其他變量，求解下列問題更新Z：

對變量Z量求導并令其為0，Z的閉式解如下：

式（13）可以通過軟閾值算子求解：

固定其他變量，更新E1即求解：

根據軟閾值算子可得E1的解為：

固定其他變量，更新E2即求解：

變量E2的解為：

更新拉格朗日乘子：

以上給出了利用ADMM 求解式（3）問題的各個變量的迭代公式。基于上述分析，給出以下迭代算法：

輸入數據矩陣X，類別個數k，權衡參數α、λ1、λ2

輸出聚類標簽

2.3 計算復雜度分析

本文算法中更新變量J、Z、P、E1、E2的計算復雜度均為O(n2)，更新式（10）中鄰域關系矩陣C需要求解Sylvester方程，其計算復雜度為O(n3)，因此，算法總的計算復雜度為T1×O(n3)，其中T1為迭代次數。由文獻［18］可知，SRR 的計算復雜度為T2×O(n3)，其中T2代表迭代次數。通過對比發現，本文模型求解算法和SRR 模型求解算法的計算復雜度均為3階。

3 實驗

在經典數據集Extended Yale B［23］、ORL［24］、USPS［25］和MNIST［26］上進行實驗來驗證本文方法的有效性。同時，將本文模型與SSC［6］、LRR［7］、LSR1［9］、LSR2［9］、SSSC［15］、BDR-B［14］、BDR-Z［14］和SRR［18］模型進行比較。使用聚類錯誤率作為性能評價指標，其定義為誤分類數據點個數與數據點總數的比值。聚類錯誤率越小，表示誤分類的數據點越少，聚類效果越好；反之亦然。

本文實驗在Intel?CoreTMi7-9700 CPU@3.00 GHz處理器配置下，Matlab R2018b 環境中進行。

3.1 參數分析

本文模型包含3 個權衡參數：α，λ1，λ2。參數α的取值越大，不同類別數據之間的自表示系數越小；參數λ1的取值大小決定了對原始數據奇異點進行處理的程度，設置適當的參數λ1，可以有效去除數據樣本中的噪聲，減小噪聲對獲取數據的新特征的影響；參數λ2用于進一步去除數據的新特征中的噪聲。在Extended Yale B上，各參數對聚類結果的影響如圖1所示。

圖1 Extended Yale B 數據集上聚類錯誤率隨參數的變化Fig.1 Clustering error rate versus parameters on Extended Yale B dataset

圖1（a）是固定α=0.005，聚類錯誤率隨另外2個參數變化的柱形圖。可以看出，本文模型的聚類錯誤率主要取決于參數λ1，當λ1=0.5時，參數λ2取{0.001，0.005，0.01，0.05，0.1，0.5，1}中的任意值，聚類錯誤率都處于較低水平，這表明相較于第2次自表示中的噪聲處理，第1次自表示對原始數據的噪聲適當處理更為重要。

圖1（b）是固定λ1=0.5，聚類錯誤率隨另外2個參數變化的柱形圖。可以看出，當α=0.001或0.005時，本文模型的聚類錯誤率較低，λ2取{0.001，0.005，0.01，0.05，0.1，0.5，1}中何值對聚類錯誤率影響不大，這表明本文提出的正則項對聚類性能起到重要作用。

綜上可知，當α=0.005、λ1=0.5、λ2=0.001時，本文模型的聚類錯誤率最低，因此，將此組參數值作為參考經驗最優參數。

3.2 人臉數據集實驗

本節為選用Extended Yale B 和ORL 數據集的實驗結果與分析。圖2（a）和圖2（b）分別為Extended Yale B數據集和ORL 數據集的部分人臉圖像。

圖2 Extended Yale B 與 ORL 數據集部分人臉圖像Fig.2 Some face images of Extended Yale B and ORL datasets

Extended Yale B人臉數據集包含38個人的2 414幅人臉圖像，其中每人約有64幅不同光照和姿勢下的人臉圖像。對于Extended Yale B數據集，本文遵循文獻［27］中的數據處理過程：1）將每幅圖像下采樣到48×42 像素；2）將38人分為4個小組：1～10，11～20，21～30，31～38，對每組考慮2、3、5、8 個不同人的人臉圖像的所有組合，對前3 組的每組考慮10 個不同人的人臉圖像的所有組合。在此數據集上，SSC、LRR、LSR1、LSR2 和SSSC 模型的聚類錯誤率數據參考文獻［27］。對BDR-B、BDRZ、SRR 和本文模型，通過選擇參數以達到最低的聚類錯誤率，然后計算所有實驗中聚類錯誤率的平均值、中值和標準差。

ORL 人臉數據集包含40 人在不同時間、光照、表情、角度、是否配戴眼鏡等環境下拍攝的400 幅人臉圖像，其中每人有10 幅人臉圖像。對于ORL 數據集，考慮到降低計算時間和復雜度，本文將每幅圖像下采樣到32×32 像素。在此數據集上，調節參數使得模型效果達到最優。

各模型在Extended Yale B 和ORL 數據集上的聚類錯誤率如表1 所示，其中加粗表示最優值。

表1 各模型在Extended Yale B 和ORL 數據集上的聚類錯誤率 Table1 Clustering error rate of each model on Extended Yale B and ORL datasets %

由表1 可以看出，本文模型在2 個人臉數據集上均實現了比其他模型更低的聚類錯誤率。雖然所有模型的聚類錯誤率隨著類別數目的增加都呈升高趨勢，但其他模型迅速升高，而本文模型增高幅度較小，聚類錯誤率穩定在2%以內，標準差也穩定在1%以內，表明隨著類別數目的增加，當聚類問題更具有挑戰時，本文模型更加魯棒。ORL 人臉數據集具有強非線性結構，對聚類方法提出了更大的挑戰，但本文模型依舊實現了較對比模型更低的聚類錯誤率，聚類性能更優。為了更直觀地對比不同方法，在Extended Yale B 數據集上，根據表1 的結果繪制了折線圖，如圖3 所示，從中可以明顯看出，本文模型的聚類錯誤率始終低于其他對比模型。

圖3 Extended Yale B 數據集上平均聚類錯誤率與類別數目的關系Fig.3 Relationship between average clustering error rate and number of subjects on Extended Yale B dataset

3.3 手寫數字數據集實驗

USPS 和MNIST 是2 個常用的手寫數字圖像數據集，USPS 和MNIST 均包含0～9 這10 個類別手寫數字圖像，部分圖像如圖4（a）和圖4（b）所示。

圖4 部分手寫數字圖像Fig.4 Some handwritten digital images

USPS 數據集包含9 298 幅手寫數字圖像，每幅圖像的尺寸為16×16 像素。在此數據集上，利用每個手寫數字的前100 幅圖像進行實驗，則可得到256×1 000 的數據矩陣。在MNIST 數據集上，取訓練集每類手寫字的前100 幅圖像。考慮到算法運行時間，將每幅圖像下采樣到28×28 像素，展開為一個784 維的向量，此時數據矩陣的大小為784×1 000。

各模型在USPS和MNIST數據集上的聚類錯誤率如表2所示，其中加粗表示最優值。可以看出，本文模型的聚類錯誤率遠小于其他模型，聚類性能最優。

表2 各模型在USPS 和MNIST 數據集上的聚類錯誤率 Table 2 Clustering error rate of each model on USPS and MNIST datasets %

3.4 運行時間對比

各模型在4 個數據集中指定數據上的運行時間如表3 所示。可以看出：統一模型SSSC 花費時間最多；LSR 模型（包括LSR1 和LSR2）花費時間最少；本文模型和SRR 模型雖然都具有3 階計算復雜度，但本文模型在4 個數據集上的實際運行時間均少于SRR 模型。

表3 各模型在4 個數據集上的運行時間 Table 3 Runtime of each model on four datasets 單位：s

4 結束語

本文對SRR 模型進行改進，首先用平方F 范數取代核范數，避免核范數求解需要的奇異值分解，并獲得解析解；然后引入類別屬性增強的正則項，提高不同類別數據的自表示系數的判別性。在多個人臉以及手寫數字數據集上的聚類結果表明，本文改進模型的聚類性能優于SSC、LRR、SSSC 等對比模型。下一步將考慮算法的收斂性，將模型擴展應用于多視角數據的子空間聚類問題。