系數增強最小二乘回歸子空間聚類法

簡彩仁，翁 謙，夏靖波

1.廈門大學 嘉庚學院 信息科學與技術學院，福建 漳州 363105

2.福州大學 數學與計算機科學學院，福州 350108

隨著互聯網的不斷發展，對計算機視覺和模式識別等領域提出了許多研究目標，聚類分析是其中的一個重要分支。子空間聚類是最流行的聚類分析技術之一，在圖像表示[1]、運動分割[2]、人臉聚類[3-7]、基因表達數據聚類[8]等領域有著廣泛的應用。假設高維數據近似于低維子空間的并集，則子空間聚類旨在尋求一組適合的子空間對給定的數據集進行分割，并基于識別出的子空間進行聚類[5]。

在過去的幾十年中，子空間聚類法得到了很好的發展，可以將其大致分為以下四類：迭代方法[9]、統計方法[10]、代數方法[11]和基于譜聚類的方法[1-8，12-13]。近年來，基于譜聚類的方法得到了更多的關注，并在計算機視覺等眾多領域中取得了良好的性能[5，6-7，12-13]。這種方法的關鍵是找到一個塊對角親和力矩陣（affinity matrix），其中親和力矩陣的元素表示兩個對應數據點之間的相似度，而塊對角結構意味著類內有非零相似度，而類間的相似度為零。為了獲得塊對角線親和力矩陣，一些研究人員提出在譜聚類法中使用自表示策略來測量相似性[3]。具體來說，它們將每個樣本點表示為數據集本身中其他樣本點的線性組合，然后使用表示系數矩陣構建親和力矩陣。這些方法之間的主要區別在于求解表示系數矩陣的不同。例如，稀疏子空間聚類（SSC）[3]假設每個樣本點都可以由最少的其他樣本點線性表示，并最小化表示系數矩陣的L1-范數約束。低秩表示子空間聚類（LRR）[4]確保表示系數矩陣為低秩矩陣，以捕獲輸入數據的全局結構，LRR對表示系數矩陣最小化核-范數約束。與SSC和LRR不同，最小二乘回歸子空間聚類（LSR）[5]采用F-范數約束求解表示系數矩陣，以獲得內聚性更強的表示系數矩陣。這些方法在子空間聚類中顯示出令人鼓舞的性能。但是由于SSC和LRR需要迭代計算，計算效率低，而LSR具有解析解，因此LSR得到了飛速的發展。近幾年，基于LSR的擴展模型層出不窮。核截斷回歸表示子空間聚類（KTRR）[12]將數據集映射到高維空間，利用最小二乘回歸模型求解表示系數，增強KTRR求解的表示系數矩陣刻畫數據集非線性的能力。縮放單純形表示子空間聚類（SSRCS）[13]對最小二乘回歸模型的表示系數矩陣加上非負約束和縮放單純形約束，SSRCS的非負約束有利于聚合來自相同子空間的數據，同時抑制來自不同子空間的數據，縮放單純形約束將每個系數向量的和限制得到更有區分性的表示系數矩陣[14]。

利用表示理論求解表示系數矩陣，表示系數矩陣元素的大小反映了樣本間的相似度，因此樣本相似度對求解表示系數矩陣有重要的作用，而最小二乘回歸子空間聚類法在求解表示系數矩陣時忽略了樣本間的相似度。針對這一不足，利用樣本相似度保持的思想定義系數增強項改進LSR，提出一種更加魯棒的求解表示系數矩陣的方法，從而提出系數增強最小二乘回歸子空間聚類法。

1 子空間聚類法概述

基于自表示理論的子空間聚類法的關鍵在于表示系數矩陣。LSR利用正則F-范數求解表示系數矩陣且具有解析解，得到了許多學者的青睞，因此本章介紹LSR及其擴展方法。

X=[x1,x2,…,xn]∈Rm×n的每一列xi表示具有m個特征的樣本，X是有n個樣本的數據集。在某種約束條件下，利用X重構X，并求解表示系數矩陣C。LSR[5]利用F-范數的內聚性求解表示系數矩陣：

其中，D=(XTX+λI)-1,I是單位矩陣。

KTRR[12]將樣本xi和除xi外的樣本集Xi=[x1,…,xi-1,xi+1…,xn]∈Rm×(n-1)用非線性映射φ:Rm→H轉化為核空間H上的數據φ(xi)和φ(Xi)，并利用最小二乘回歸模型求解表示系數：

不難得到ci=(Ki+λI)-1ki,其中Ki=φ(Xi)Tφ(Xi) 是核矩陣，ki=φ(Xi)Tφ(xi)是核向量。根據文獻[12]的研究，選用高斯核函數將表示系數合并，并保持主對角線元素全為0，可以得到表示系數矩陣C。

SSRCS[13]對最小二乘回歸模型的表示系數矩陣加上非負約束和縮放單純形約束，得到如下的模型：

其中，1是所有元素為1的列向量，s是表示系數向量中各項總和的標量，根據文獻[13]的研究，取為1?？梢岳媒惶娣较虺俗臃ǎˋDMM）求解該模型，公式（4）可以快速收斂，根據文獻[13]的研究，迭代次數取為5。

LSR、KTRR和SSRCS求解得到表示系數矩陣C，定義親和力矩陣為最后利用標準化分割方法（normalized cuts，Ncut）[12]對A分割實現聚類。

2 CELSR方法

針對最小二乘回歸子空間聚類法在求解表示系數時忽略了樣本相似度的不足，利用系數增強手段定義系數增強項改進LSR，提出系數增強最小二乘回歸子空間聚類法（CELSR）。

2.1 系數增強最小二乘回歸模型

假設D=(Dij)n×n是相似度矩陣，其元素Dij刻畫樣本xi和xj的相似度，一種理想的相似度矩陣是分塊對角矩陣，來自相同類的樣本的相似度很大，而來自不同類的樣本相似度為0。對表示系數矩陣C=(Cij)n×n而言，越大的|Cij|表示樣本xi和xj的相似度越高。因此表示系數矩陣跟相似度矩陣有很大的關系，當xi和xj為來自相同的類別時，Dij和|Cij|都很大，當xi和xj為來自不同的類別時，Dij=|Cij|=0?；谶@一發現，希望求解的表示系數矩陣能刻畫樣本間的相似度，因此C和D越接近越好。定義系數增強項為：

考慮到現實數據往往有非線性、多噪聲等特點，相似度矩陣D很難達到理想狀態，因此需要調節表示系數矩陣C和相似度矩陣D的大小，為此加入平衡參數β＞0。

將公式（1）和公式（5）合并得到系數增強最小二乘回歸模型：

其中，γ≥0是正則參數，當γ=0時退化為LSR。第一項是重構損失項；第二項是F-范數懲罰項，使求得的表示系數矩陣有更好的聚合性，保持LSR的優點；第三項是系數增強項，使求得的表示系數矩陣能更好地刻畫樣本間的相似度。

2.2 模型求解

公式（5）的一種簡單直觀的解法是，將X=[x1,x2,…,xn]∈Rm×n按一個一個的樣本求解表示系數。最后拼接成主對角線元素全為0的表示系數矩陣C=(Cij)n×n。顯然這種方法需要求解n次的逆矩陣，計算時間復雜度為O(n4+mn2)。

針對這一不足，給出一種計算效率更高的求解公式（5）的方法。重寫公式（5）為：

其中，ei是示性列向量，它的第i個元素為1，其余元素為0，di是D的第i列，約束條件eTi ci=0使得ci的第i個元素為0，這樣求得的ci可以滿足diag(C)=0。利用矩陣的跡tr和拉格朗日乘數法將公式（7）寫為：

關于ci求導得：

其中，qi=P(XTxi+βdi)，P=(XTX+λI+γI)-1。將表示系數ci拼接成表示系數矩陣C*=[c1,c2,…,cn]。

注意到上面的求解過程只涉及到一次矩陣求逆，因此計算時間復雜度可以降低為O(n3+mn2)。

2.3 系數增強最小二乘回歸子空間聚類法

對表示系數矩陣C=(Cij)n×n而言，越大的|Cij|表示樣本xi和xj的相似度越高?？紤]到表示系數矩陣C和親和力矩陣A的主對角線元素全為0，將相似度矩陣D也取為主對角線元素全為0的矩陣。因此為操作簡便，基于2.1節的分析，本文直接利用公式（1）求解表示系數矩陣C=(Cij)n×n,定義相似度矩陣用于刻畫數據集X的全局相似結構。

利用2.2節給出的方法可以快速求到CELSR的表示系數矩陣C*，從而親和力矩陣為，利用Ncut方法對A進行分割完成聚類。

綜上所述，將系數增強最小二乘回歸子空間聚類法（coefficient enhanced least square regression subspace clustering method，CELSR）歸納如下：

輸入：樣本數據X,正則參數λ,γ,β,類別數K。

輸出：K個類簇。

步驟1由公式（1）得到表示系數矩陣C=(Cij)n×n，并得到相似度矩陣

步驟2由公式（10）得到表示系數ci，并構造表示系數矩陣C*=[c1,c2,…,cn]；

步驟3由C*得親和力矩陣，應用Ncut方法將X聚成K個類簇。

3 實驗分析

本章通過實驗驗證CELSR的有效性，包括對比實驗、參數討論和運行效率方面的分析。

3.1 實驗方法與實驗數據

對比方法為傳統聚類法KMEANS，基于最小二乘回歸模型的子空間聚類法及其擴展方法LSR、KTRR、SSRSC。為了便于討論各種方法的聚類效果，將正則參數λ統一取為0.01。其他方法的關鍵參數設置如下，KTRR的核函數采用高斯核函數，SSRSC的參數s取為1，CELSR的參數γ取為0.1，β取為1.2。

實驗數據為常用的標準數據集（https：//jundongl.github.io/scikit-feature/datasets.html），它們分別是4個基因表達數據集Carcinom、lung、lymphoma和nci9，4個圖像數據集ORL、orlraws10P、warpAR10P和Yale。它們的簡要信息如表1所示。

表1 數據集描述Table 1 Summary of datasets

為了更加全面地比較各種方法的聚類性能，選取聚類準確率（ACC）[14]和標準化互信息（NMI）[14]兩個指標比較各種方法的聚類結果。

3.2 對比實驗

由于子空間聚類法最后都采用Ncut實現聚類，為了避免隨機性，所有方法都運行100次。表2給出了各種方法的聚類準確率平均值±標準差，表3給出了各種方法的標準化互信息平均值±標準差。

從表2和表3的對比實驗結果發現，在Carcinom上，CELSR的聚類準確率低于SSRSC，但標準化互信息高于SSRSC。因此在Carcinom上，CELSR和SSRSC的聚類性能差異不大。在Yale上，CELSR的標準化互信息低于KTRR，但聚類準確率高于KTRR。因此在Yale上，CELSR和KTRR的聚類性能差異不大。除此之外，CELSR在聚類準確率和標準化互信息都是最好的。與KMEANS對比，CELSR在聚類準確率和標準化互信息兩個指標上的優勢更加明顯，這一結果說明，CELSR比傳統的基于歐氏距離的聚類法更適合高維數據的聚類。與LSR對比，CELSR在聚類準確率和標準化互信息兩個指標上有明顯的提高，這一結果說明，系數增強項可以求解更加有效的表示系數矩陣，因此考慮保持樣本相似度的思想確實可以改進LSR的聚類性能。

表2 聚類準確率對比Table 2 Clustering accuracy comparison 單位：%

表3 標準化互信息對比Table 3 Normalized mutual information comparison 單位：%

3.3 參數討論

CELSR有3個參數λ、γ和β，由于不同參數下，聚類準確率的平均值和標準化互信息的平均值的變化趨勢差異不大。本節僅討論參數對聚類準確率的影響，實驗結果如圖1所示。每個數據有4個子圖，依次為β取0.4,0.8,1.2,1.6時，參數λ取0.001,0.01,0.1,1,10,100,γ取0.01,0.1,1,10，CELSR運行100次的平均聚類準確率。從圖1的實驗結果不難發現，隨著參數的變化CELSR的聚類準確率發生明顯的變化。當β發生改變時，CELSR的聚類準確率變化不大。除nci9數據集外，較大的λ和γ往往會降低CELSR的聚類準確率。因此在選擇λ和γ時，不宜過大。實驗結果表明，當λ較小時，CELSR的聚類準確率較為理想，這一結果與LSR的研究結論是一致的。一般的，當λ和γ較小時，γ＞λ的情形下，CELSR的聚類準確率較高，這說明系數增強項能獲得更好的表示系數矩陣。

圖1 不同λ、γ和β下CELSR在8個數據集上的聚類準確率Fig.1 Clustering accuracy of CELSR on 8 datasets with different λ,γ and β

3.4 運行效率

本節從運行效率的角度比較各種方法的性能，由于LSR、KTRR、SSRSC和CELSR同屬于最小二乘回歸子空間聚類法的擴展模型，故僅比較4種方法的運行時間。不失公平性，比較各種方法求解表示系數矩陣C的運行時間，各種方法運行500次取平均值，結果如表4所示。

表4的實驗結果表明LSR的效率最高，因為LSR具有并行解析解。KTRR、SSRSC、CELSR從不同的角度改進LSR。從表4的結果不難發現，CELSR的運行效率優于KTRR和SSRSC，主要原因是KTRR涉及求解核矩陣，而SSRSC需要迭代求解。這一結果也說明本文給出的CELSR的求解方法具有較高的運行效率。表4的實驗結果表明LSR的效率最高，因為LSR具有并行解析解。KTRR、SSRSC、CELSR從不同的角度改進LSR。從表4的結果不難發現，CELSR的運行效率優于KTRR和SSRSC，主要原因是KTRR涉及求解核矩陣，而SSRSC需要迭代求解。這一結果也說明本文給出的CELSR的求解方法具有較高的運行效率。

表4 運行時間對比Table 4 Running time comparison 單位：s

4 結語

本文利用樣本相似度保持的思想定義系數增強項，提出系數增強最小二乘回歸子空間聚類法（CELSR）。該方法通過系數增強對最小二乘回歸子空間聚類法（LSR）進行改進。在常用的8個數據集上的實驗結果表明，CELSR可以明顯提高LSR的聚類性能。CELSR的聚類結果受參數的影響，如何利用仿生人工智能方法，如蟻群算法等搜索參數，將在以后的研究中給出。