基于核最小二乘回歸子空間分割的高維小樣本數(shù)據(jù)聚類

簡彩仁,翁 謙,陳曉云

(1. 廈門大學(xué)嘉庚學(xué)院, 福建 漳州 363105; 2. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福建 福州 350116)

0 引言

高維小樣本數(shù)據(jù)廣泛存在于現(xiàn)實(shí)生活中,如基因表達(dá)數(shù)據(jù)、 人臉圖像數(shù)據(jù)等,如何識別高維小樣本數(shù)據(jù)是近年來模式識別研究的熱點(diǎn)[1-6]. 高維小樣本數(shù)據(jù)集的樣本數(shù)量通常為幾十到幾百個(gè),然而特征屬性往往是成千上萬的. 高維小樣本數(shù)據(jù)集往往是非線性的,因此,許多傳統(tǒng)的線性模式識別方法難以適應(yīng)高維小樣本數(shù)據(jù)的識別[2-5]. 針對高維小樣本數(shù)據(jù)提出一種基于子空間分割的非線性聚類方法.

子空間分割方法是近年來聚類方法研究的熱點(diǎn)問題[7-10],其目標(biāo)是將數(shù)據(jù)集分割(或聚集)成幾個(gè)簇,并使每一個(gè)簇對應(yīng)于一個(gè)子空間. 子空間分割方法已經(jīng)成功應(yīng)用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺等相關(guān)研究中. 同一類的數(shù)據(jù)樣本構(gòu)成一個(gè)子空間,不同的子空間混合構(gòu)成混合子空間,而現(xiàn)實(shí)中的數(shù)據(jù)近乎可以視為是混合子空間,因此子空間分割方法在圖像聚類、 圖像分割、 運(yùn)動物體識別和基因表達(dá)數(shù)據(jù)識別等領(lǐng)域有著廣泛的應(yīng)用[7-10]. 子空間分割的目標(biāo)是將混合采樣的數(shù)據(jù)集分割成不同的子空間,從而實(shí)現(xiàn)聚類.

近幾年的子空間分割研究得到了很好的發(fā)展,基于表示理論的子空間分割方法的優(yōu)勢是對噪聲是魯棒的. 其主要思想是利用表示理論得到表示矩陣,接著用表示矩陣構(gòu)建相似矩陣,最后利用文獻(xiàn)[11]提出一種經(jīng)典的譜聚類方法： 標(biāo)準(zhǔn)化分割方法實(shí)現(xiàn)聚類. 例如,低秩表示子空間分割方法[8]旨在通過秩最小化來構(gòu)建相似矩陣; 最小二乘回歸子空間分割方法[9]通過F-范數(shù)正則化達(dá)到內(nèi)聚度. 現(xiàn)實(shí)中的數(shù)據(jù)往往在非線性流形上采樣,高維小樣本數(shù)據(jù)是非線性的,因此基于線性表示理論的子空間分割方法,不利于發(fā)現(xiàn)高維小樣本數(shù)據(jù)集的本質(zhì)特征. 為了彌補(bǔ)這一不足,受非線性表示理論的啟發(fā),利用核理論改進(jìn)最小二乘回歸子空間分割方法,將其推廣到非線性數(shù)據(jù)集的識別中.

1 基于表示理論的子空間分割法

例如,最小二乘回歸子空間分割方法最小化Z的F-范數(shù)

針對噪聲數(shù)據(jù)的擴(kuò)展模型為

最小二乘回歸子空間分割方法對噪聲是魯棒的,并且有很好的聚集性能. 然而高維小樣本數(shù)據(jù)往往是非線性的,因此基于線性表示理論的最小二乘回歸子空間分割方法不能很好地適應(yīng)高維小樣本數(shù)據(jù)的非線性性質(zhì).

2 核最小二乘回歸子空間分割法

最小二乘回歸子空間分割方法是在線性空間考慮的,不利于發(fā)現(xiàn)高維小樣本數(shù)據(jù)的非線性性質(zhì). 針對這一不足,本研究利用核理論將最小二乘回歸子空間分割方法擴(kuò)展成適合非線性流形學(xué)習(xí)的核最小二乘回歸子空間分割法.

給定非線性特征空間映射Φ:Rm→M,其中Rm是高維樣本空間,M是低維流形空間,因此原始高維數(shù)據(jù)X的低維流形表示為Φ(X). 對低維流形樣本Φ(X)進(jìn)行子空間分割研究,因此非線性的最小二乘回歸子空間分割方法可以寫為

其中,λ>0是正則參數(shù),diag(Z)=0表示方陣Z的主對角線為0.

對問題(1)的求解，

一種簡單的思路是分別對每個(gè)樣本求解表示系數(shù). 對第i個(gè)樣本求解表示系數(shù)[Z*]i,假設(shè)Φ(X)=[Φ(x1),Φ(x2), …,Φ(xn)]∈Rm×n,去掉Φ(X)的第i列,得到Φ(Yi)=[Φ(x1), …,Φ(xi-1),Φ(xi+1), …,Φ(xn)],則問題(1)變?yōu)?/p>

顯然這樣對每個(gè)樣本求解的方法是低效的. 下面的證明過程給出了一種可以并行求解問題(1)的方法,該問題的解析解為Z*=-D(diag(D))-1, diag(Z*)=0,其中,D=(Φ(X)TΦ(X)+λI)-1.

證明 利用D=(Φ(X)TΦ(X)+λI)-1來計(jì)算[Z*]i.

首先,利用初等變換Φ(X)P=[Φ(Yi)Φ(xi)]將Φ(X)重新排序,其中P是置換矩陣,PPT=PTP=I. 則有

[PT(Φ(X)TΦ(X)+λI)P]-1=PTDP

(2)

接著,利用Woodbury公式[12]計(jì)算

其中

[Z*]i=-bi正是本研究所要求解的,由P的性質(zhì)從式子(2)可以得到bi,于是

可以將這一結(jié)果寫為Z*=-D(diag(D))-1, diag(Z*)=0.

更一般的,去掉約束條件diag(Z)=0,問題(1)退化成嶺回歸方程

(3)

Z=(Φ(X)TΦ(X)+λI)-1Φ(X)TΦ(X)

直接定義非線性映射Φ(X)是困難的,而核表示理論給出了一種不需要定義非線性映射的技術(shù)[2, 13]. 設(shè)KYY∈Rn×n是一個(gè)半正定核矩陣,它們的元素定義為

[KYY]ij=[(Φ(X),Φ(X))M]ij=Φ(xi)TΦ(xj)=k(xi,xj)

根據(jù)核表示理論,將非線性最小二乘回歸子空間分割方法擴(kuò)展為核最小二乘回歸子空間分割法,因此問題(1)的解可以寫為

Z*=-D(diag(D))-1, diag(Z*)=0

(4)

問題(3)的解可以寫為

Z*=DK

(5)

其中:D=(K+λI)-1,K是核矩陣.

類似于LSR,核最小二乘回歸空間分割方法也是一種基于譜聚類的子空間分割方法,首先通過式(4)～(5)得到該問題的解Z*,那么仿射矩陣為(|Z*|+|(Z*)T|)/2,接著應(yīng)用標(biāo)準(zhǔn)分割方法(normalized cuts,NC)[11]對仿射矩陣進(jìn)行分割. 至此,本研究歸納核最小二乘回歸子空間分割(kernel least square regression subspace segmentation,KLSR)方法如下

算法:核最小二乘回歸子空間分割算法(KLSR)Input:數(shù)據(jù)矩陣X,正則參數(shù)λ,核函數(shù)參數(shù)σ,類數(shù)kOutput:k個(gè)類簇Step1:通過解決問題得到矩陣Z*Step2:計(jì)算仿射矩陣Z*+(Z*)T()/2;Step3:應(yīng)用標(biāo)準(zhǔn)分割方法將數(shù)據(jù)分成k個(gè)子空間.

3 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證核最小二乘回歸子空間分割方法的有效性,本節(jié)將用KLSR和子空間分割方法, 即最小二乘回歸子空間分割法(least square regression subspace segmentation,LSR)[9],低秩表示子空間分割法(low rank representation,LRR)[8], 以及傳統(tǒng)的聚類算法： K均值聚類法(K-means)和層次聚類法(hierarchical clustering,HC)從聚類準(zhǔn)確率的角度進(jìn)行比較. 為區(qū)別問題(1)和問題(3),將式(4)、 (5)分別記為KLSR1、 KLSR2. 聚類準(zhǔn)確率的定義如下，

對一個(gè)給定的樣本,令ri和si分別為聚類算法得到的類標(biāo)簽和樣本自帶的類標(biāo)簽,那么準(zhǔn)確率的計(jì)算公式[14]為

(6)

其中:n為樣本總數(shù)；δ(x,y)是一個(gè)函數(shù),當(dāng)x=y時(shí),值為1,否則為0；map(ri)是一個(gè)正交函數(shù),將每一個(gè)類標(biāo)簽ri映射成與樣本自帶的類標(biāo)簽等價(jià)的類標(biāo)簽.

參數(shù)設(shè)置如下,子空間分割法的正則參數(shù)統(tǒng)一設(shè)置為{0.000 1,0.001,0.01,0.1,1,2,3,4,5,10},KLSR的核函數(shù)選用高斯核函數(shù),其參數(shù)σ設(shè)置為{0.5,1.0,1.5,2.0,2.5,3.0,3.5,5.0}. 實(shí)驗(yàn)過程采用遍歷以上實(shí)驗(yàn)參數(shù)的方法給出實(shí)驗(yàn)結(jié)果.

3.1 數(shù)據(jù)集

本研究選用10個(gè)廣泛應(yīng)用在模式識別研究的高維小樣本數(shù)據(jù)集作為研究. 它們是基因表達(dá)數(shù)據(jù)集：ALLAML、CLL_SUB_111、leukemia、lymphoma、nci9 、TOX_171 和圖像數(shù)據(jù)集：ORL、pixraw10P、warpPIE10P、Yale. 將它們的簡要信息整理歸納,見表1.

表1 數(shù)據(jù)集描述Tab.1 Summary of the data sets

3.2 實(shí)驗(yàn)結(jié)果與分析

本研究的實(shí)驗(yàn)環(huán)境為Windows7系統(tǒng),內(nèi)存2 GB,所有方法都用Matlab2011b編程實(shí)現(xiàn),為避免聚類過程的隨機(jī)性,實(shí)驗(yàn)過程中每種方法運(yùn)行50次,求取聚類準(zhǔn)確率的平均值. 表2以聚類準(zhǔn)確率的均值±標(biāo)準(zhǔn)差的形式給出實(shí)驗(yàn)結(jié)果.

表2的實(shí)驗(yàn)結(jié)果表明,在所有的數(shù)據(jù)集上,KLSR都有較好的聚類結(jié)果,在ALLAML和leukemia數(shù)據(jù)集上的聚類準(zhǔn)確率比其它方法高出20%. 將KLSR的方法去掉限制條件diag(Z)=0的擴(kuò)展方法KLSR2也可以取到較理想的聚類準(zhǔn)確率.

表2 聚類準(zhǔn)確率對比Tab.2 Clustering accuracy comparison (%)

對比經(jīng)典的非線性子空間分割方法LSR和LRR,兩種KLSR方法都可以取到較理想的聚類準(zhǔn)確率,這表明基于核理論的非線性子空間分割方法能更適合高維小樣本數(shù)據(jù)的聚類研究. 因此,KLSR可以較好地反映高維小樣本數(shù)據(jù)的非線性性質(zhì),取得較好的聚類準(zhǔn)確率.

與傳統(tǒng)的聚類方法K-means和HC對比,子空間分割方法的聚類準(zhǔn)確率明顯優(yōu)于傳統(tǒng)的聚類方法. 原因是因?yàn)閭鹘y(tǒng)聚類方法以歐氏距離為度量,不能很好適應(yīng)高維小樣本數(shù)據(jù)的非線性性質(zhì). 與傳統(tǒng)的聚類方法對比,KLSR的聚類優(yōu)勢更加明顯,這也顯示出KLSR可以較好地適應(yīng)高維小樣本數(shù)據(jù)的聚類.

上述的實(shí)驗(yàn)結(jié)果比較表明KLSR是一種有效的適合高維小樣本數(shù)據(jù)聚類的一種方法.

3.3 運(yùn)行時(shí)間比較

KLSR能較好地適應(yīng)高維小樣本數(shù)據(jù)的非線性,本節(jié)討論KLSR的運(yùn)行效率. 對比各種方法的運(yùn)行時(shí)間,KLSR、 LSR和LRR等三種子空間分割方法的正則參數(shù)選定為0.01,KLSR的核函數(shù)參數(shù)選為1,各種方法運(yùn)行50次,取平均運(yùn)行時(shí)間進(jìn)行對比,表3給出了所有方法的平均運(yùn)行時(shí)間.

表3 運(yùn)行時(shí)間對比Tab.3 Running time comparison (s)

從表3的運(yùn)行時(shí)間對比分析,發(fā)現(xiàn)LSR的運(yùn)行效率最高,這是因?yàn)長SR有解析解的緣故. 由于KLSR需要構(gòu)造核函數(shù)并且也有解析解,因此KLSR的運(yùn)行時(shí)間比LSR的略長. 此外本研究注意到,除了ORL數(shù)據(jù)集和Yale數(shù)據(jù)集,KLSR方法會比傳統(tǒng)方法有更好的運(yùn)行效率,其原因是ORL數(shù)據(jù)集和Yale數(shù)據(jù)集的屬性與樣本比是所有數(shù)據(jù)集中最小的,也體現(xiàn)了KLSR能更好地適應(yīng)高維小樣本數(shù)據(jù)的聚類.

3.4 參數(shù)選擇

KLSR能適應(yīng)高維小樣本數(shù)據(jù)的非線性性質(zhì),需要構(gòu)造核函數(shù),與經(jīng)典的子空間分割方法對比,多了一個(gè)參數(shù)σ. 本節(jié)討論,正則參數(shù)λ和核函數(shù)參數(shù)σ的變化對聚類準(zhǔn)確率的影響.

圖1顯示了正則參數(shù)λ和核函數(shù)參數(shù)σ的變化對聚類準(zhǔn)確率的影響. 不同的參數(shù)設(shè)置會得到不同的聚類準(zhǔn)確率. 總體來說,較小的λ具有較高的聚類準(zhǔn)確率,這和LSR[9]的研究結(jié)論是一致的. 當(dāng)給定一個(gè)較小的λ時(shí),較大的參數(shù)σ有較好聚類準(zhǔn)確率,這說明較大的σ更能適應(yīng)高維小樣本數(shù)據(jù)的非線性性質(zhì). 另一方面,較大的參數(shù)σ,有較好的平滑程度,因此有較好的容噪能力,從而得到更好的聚類準(zhǔn)確率. 從圖1的實(shí)驗(yàn)結(jié)果分析,較小的正則參數(shù)λ和較大的核函數(shù)參數(shù)σ是一組較為理想的參數(shù)選擇. 這使得KLSR有很好的應(yīng)用價(jià)值.

(a) ALLAML

(b) CLL_SUB_111

(c) leukemia

(d) lymphoma

(e) nci9

(f) TOX_171

(g) ORL

(h) pixraw10P

(i) warpPIE10P

(j) Yale圖1 λ, σ不同時(shí)KLSR在10個(gè)數(shù)據(jù)集上的聚類準(zhǔn)確率Fig.1 Clustering accuracy of KLSR on 10 datasets with different λ and σ

3.5 不同核函數(shù)的影響

核最小二乘回歸子空間分割方法是以核表示理論為基礎(chǔ)的,因此核函數(shù)的選擇對聚類準(zhǔn)確率會產(chǎn)生影響. 本節(jié)在不同的核函數(shù)下,對KLSR的聚類準(zhǔn)確率進(jìn)行分析. 選用多項(xiàng)式核函數(shù)(Poly)與高斯核函數(shù)(Gauss)進(jìn)行對比,高斯核函數(shù)參數(shù)σ設(shè)置為{0.5,1.0,1.5,2.0,2.5,3.0,3.5,5.0},多項(xiàng)式核函數(shù)的a設(shè)為0,b設(shè)置為{0.5,1.0,1.5,2.0,2.5,3.0,3.5,5.0}. 表4以平均聚類準(zhǔn)確率的形式給出實(shí)驗(yàn)結(jié)果.

表4 不同的核函數(shù)下KLSR在10個(gè)數(shù)據(jù)集上的聚類準(zhǔn)確率Tab.4 Clustering accuracy of KLSR on 10 datasets with different kernel function (%)

注： 限于篇幅,表4的數(shù)據(jù)集名稱用表1中的序號代替.

從表4的實(shí)驗(yàn)結(jié)果不難發(fā)現(xiàn)核函數(shù)的選擇會影響KLSR的聚類準(zhǔn)確率,這反映了高維小樣本數(shù)據(jù)聚類研究的復(fù)雜性. 在第2個(gè)和第6個(gè)數(shù)據(jù)集上,多項(xiàng)式核函數(shù)下KLSR的聚類準(zhǔn)確率更為理想,但總體來說高斯核函數(shù)的聚類準(zhǔn)確率優(yōu)于多項(xiàng)式核函數(shù)的聚類準(zhǔn)確率,這說明高斯核函數(shù)具有更好的魯棒性. 此外,兩種核函數(shù)下的KLSR的聚類準(zhǔn)確率都優(yōu)于其他方法,因此提出的KLSR針對高維小樣本數(shù)據(jù)的聚類有一定的優(yōu)勢.

4 結(jié)論

本研究提出一種非線性子空間分割方法： 核最小二乘回歸子空間分割方法(KLSR),并將其成功應(yīng)用在高維小樣本數(shù)據(jù)的聚類研究中. 實(shí)驗(yàn)結(jié)果表明, KLSR可以很好地適應(yīng)基因表達(dá)數(shù)據(jù)和圖像數(shù)據(jù)等高維小樣本數(shù)據(jù)的非線性性質(zhì),比現(xiàn)有的LSR和LRR等子空間分割方法更適合高維小樣本數(shù)據(jù)的聚類. 但基于表示理論的子空間分割方法存在如何自動識別聚類類簇等問題的不足,這需要更多的理論支持,將在今后的研究給出.

[1] BROWN P O, BOTSTEIN D. Exploring the new world of the genome with DNA microarrays[J]. Nature Genetics, 1999, 21: 33-37.

[2] BISHOP C M. Pattern recognition and machine learning(information science and statistics)[M]. New York: Springer-Verlag Inc, 2006.

[3] WRIGHT J, YANG A Y, GANESH A,etal. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2): 210-227.

[4] ZHU X, HUANG Z, YANG Y,etal. Self-taught dimensionality reduction on the high-dimensional small-sized data[J]. Pattern Recognition, 2012, 46(1): 215-229.

[5] 何進(jìn)榮, 丁立新, 崔夢天, 等. 基于矩陣指數(shù)變換的邊界Fisher分析[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(10): 2196-2205.

[6] 王文俊. 基于稀疏類別保留投影的基因表達(dá)數(shù)據(jù)降維方法[J]. 電子學(xué)報(bào), 2016, 44(4): 873-877.

[7] ELHAMIFAR E, VIDAL R. Sparse subspace clustering[C]//Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition. Miami: [s.n.], 2009: 2790-2797.

[8] LIU G, LIN Z, YU Y. Robust subspace segmentation by low-rank representation[C]// Proceedings of the 27th International Conference on Machine Learning. Haifa: [s.n.], 2010: 663-670.

[9] LU C Y, MIN H, ZHAO Z Q,etal. Robust and efficient subspace segmentation via least squares regression[C]// Proceedings of the 12th Computer Vision. Florence: Springer, 2012: 347-360.

[10] 簡彩仁, 陳曉云. 基于投影最小二乘回歸子空間分割的基因表達(dá)數(shù)據(jù)聚類[J]. 模式識別與人工智能, 2015, 28(8): 728-734.

[11] SHI J, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[12] 張賢達(dá). 矩陣分析與應(yīng)用[M]. 2版. 北京: 清華大學(xué)出版社, 2013.

[13] SCH?LKOPF B, SUNG K K, BURGES C J C,etal. Comparing support vector machines with Gaussian kernels to radial basis function classifiers[J]. IEEE Transactions on Signal Processing, 1996, 45(11): 2758-2765.

[14] CAI D, HE X, WU X,etal. Non-negative matrix factorization on manifold[C]// Proceedings of the 8th IEEE International Conference on Data Mining. Pisa: IEEE, 2008: 63-72.