簡(jiǎn)彩仁，翁 謙，夏靖波

1.廈門大學(xué) 嘉庚學(xué)院 信息科學(xué)與技術(shù)學(xué)院，福建 漳州 363105

2.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350108

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

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

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

1 子空間聚類法概述

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

X=[x1,x2,…,xn]∈Rm×n的每一列xi表示具有m個(gè)特征的樣本，X是有n個(gè)樣本的數(shù)據(jù)集。在某種約束條件下，利用X重構(gòu)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ù)文獻(xiàn)[12]的研究，選用高斯核函數(shù)將表示系數(shù)合并，并保持主對(duì)角線元素全為0，可以得到表示系數(shù)矩陣C。

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

其中，1是所有元素為1的列向量，s是表示系數(shù)向量中各項(xiàng)總和的標(biāo)量，根據(jù)文獻(xiàn)[13]的研究，取為1。可以利用交替方向乘子法（ADMM）求解該模型，公式（4）可以快速收斂，根據(jù)文獻(xiàn)[13]的研究，迭代次數(shù)取為5。

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

2 CELSR方法

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

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

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

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

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

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

2.2 模型求解

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

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

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

關(guān)于ci求導(dǎo)得：

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

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

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

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

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

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

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

輸出：K個(gè)類簇。

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

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

步驟3由C*得親和力矩陣，應(yīng)用Ncut方法將X聚成K個(gè)類簇。

3 實(shí)驗(yàn)分析

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

3.1 實(shí)驗(yàn)方法與實(shí)驗(yàn)數(shù)據(jù)

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

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

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

為了更加全面地比較各種方法的聚類性能，選取聚類準(zhǔn)確率（ACC）[14]和標(biāo)準(zhǔn)化互信息（NMI）[14]兩個(gè)指標(biāo)比較各種方法的聚類結(jié)果。

3.2 對(duì)比實(shí)驗(yàn)

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

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

表2 聚類準(zhǔn)確率對(duì)比Table 2 Clustering accuracy comparison 單位：%

表3 標(biāo)準(zhǔn)化互信息對(duì)比Table 3 Normalized mutual information comparison 單位：%

3.3 參數(shù)討論

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

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

3.4 運(yùn)行效率

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

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

表4 運(yùn)行時(shí)間對(duì)比Table 4 Running time comparison 單位：s

4 結(jié)語(yǔ)

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