簡彩仁，翁 謙，夏靖波

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

2.福州大學 數(shù)學與計算機科學學院，福州 350108

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

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

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

1 子空間聚類法概述

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

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

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

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

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

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

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

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

2 CELSR方法

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

2.1 系數(shù)增強最小二乘回歸模型

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

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

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

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

2.2 模型求解

公式（5）的一種簡單直觀的解法是，將X=[x1,x2,…,xn]∈Rm×n按一個一個的樣本求解表示系數(shù)。最后拼接成主對角線元素全為0的表示系數(shù)矩陣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和拉格朗日乘數(shù)法將公式（7）寫為：

關于ci求導得：

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

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

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

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

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

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

輸入：樣本數(shù)據(jù)X,正則參數(shù)λ,γ,β,類別數(shù)K。

輸出：K個類簇。

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

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

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

3 實驗分析

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

3.1 實驗方法與實驗數(shù)據(jù)

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

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

表1 數(shù)據(jù)集描述Table 1 Summary of datasets

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

3.2 對比實驗

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

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

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

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

3.3 參數(shù)討論

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

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

3.4 運行效率

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

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

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

4 結語

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