簡彩仁，翁謙

（1．廈門大學(xué)嘉庚學(xué)院，福建漳州363105；2．福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建福州350116）

基于局部強(qiáng)化最小二乘回歸子空間分割的基因表達(dá)數(shù)據(jù)聚類

簡彩仁1，翁謙2

（1．廈門大學(xué)嘉庚學(xué)院，福建漳州363105；2．福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建福州350116）

利用局部約束協(xié)同表示法改進(jìn)最小二乘回歸子空間分割方法，提出局部強(qiáng)化最小二乘子空間分割方法（LSLSR）。該方法通過近鄰樣本的協(xié)同作用強(qiáng)化重構(gòu)系數(shù)使得LSLSR有更好的抗噪能力，結(jié)果表明該方法有較高的聚類準(zhǔn)確率。

局部強(qiáng)化；最小二乘回歸子空間分割；基因表達(dá)數(shù)據(jù)；聚類

聚類是模式識別研究的重要方向之一，其目標(biāo)是將未知類別的數(shù)據(jù)根據(jù)某種特性分成不同的簇，使得每個簇都有相似的特點。聚類方法多種多樣，傳統(tǒng)的聚類方法：(1)基于劃分的聚類方法，比如k-means算法[1]；(2)基于層次的聚類算法，比如BIRCH算法[2]；(3)基于密度的聚類算法，比如DBSCAN算法[3]；(4)基于網(wǎng)格的方法，比如STING算法[4]。傳統(tǒng)的算法不斷改進(jìn)和發(fā)展，出現(xiàn)了模糊聚類，譜聚類等。譜聚類[5]是一種基于圖論的聚類算法，適合于各種形狀的數(shù)據(jù)集的聚類，因而得到廣泛應(yīng)用。譜聚類的關(guān)鍵是構(gòu)造圖拉普拉斯矩陣。本文主要研究譜聚類。

子空間分割(subspace segmentation)是近年來模式識別研究的熱點問題之一，已經(jīng)廣泛應(yīng)用在圖像分割、人臉識別和機(jī)器視覺等領(lǐng)域[6-8]，并且在基因表達(dá)數(shù)據(jù)識別中也有廣泛應(yīng)用[9]。子空間分割方法的目標(biāo)是將數(shù)據(jù)集分割成不同的簇。子空間分割的主要思想是，假設(shè)每一個數(shù)據(jù)集都是從混合子空間采樣的，其目標(biāo)是將數(shù)據(jù)集分割成幾個簇，每一個簇對應(yīng)于一個子空間[8]。子空間分割方法多種多樣，文獻(xiàn)[8]將子空間分割方法分為4類:代數(shù)方法、迭代方法、統(tǒng)計方法和譜聚類方法。低秩表示子空間分割方法[7]和最小二乘回歸子空間分割方法[8]是基于譜聚類的子空間分割方法的典型代表，但是這些方法存在易受噪聲樣本影響的不足。

本文的研究旨在改進(jìn)子空間分割方法易受噪聲樣本影響的不足。模式識別的方法不僅要求有較好的識別能力，還要有較好的抗噪能力。文獻(xiàn)[10]的局部約束協(xié)同表示法表明通過局部強(qiáng)化不僅可以提高圖像識別的準(zhǔn)確率，而且可以提高抗噪聲能力。本文借鑒該思想改進(jìn)最小二乘回歸子空間分割方法，提出局部強(qiáng)化的最小二乘回歸子空間分割方法。

1相關(guān)理論

子空間分割是譜聚類的一種，其核心是構(gòu)造樣本的相似矩陣。子空間分割的目標(biāo)是將數(shù)據(jù)集分割成對應(yīng)于不同子空間的簇。

定義[8]子空間分割(subspace segmentation)

給定一個數(shù)據(jù)向量集合X=[x1，x2，…，xn]∈Rm×n其中，m是特征個數(shù)，n是樣本個數(shù)。假設(shè)X從K個子空間的并集中抽樣{Si}Ki=1，子空間分割的目標(biāo)是將數(shù)據(jù)根據(jù)樣本采樣的子空間將樣本分割成不同的簇。

子空間分割方法有許多類型，比如代數(shù)方法，迭代方法等[8]?；谧V聚類的子空間分割是近年來的研究熱點。比如，低秩表示子空間分割（low rank representation，LRR）[7]和最小二乘回歸子空間分割（least square regression，LSR）[8]是基于譜聚類的子空間分割方法的典型代表?；谧V聚類的子空間分割方法的核心問題是求解仿射矩陣Z。仿射矩陣Z中的每個元素Zij用來度量樣本xi和xj的相似度，比如0就可以用來構(gòu)造仿射矩陣Z。然而僅僅考慮兩個樣本間的距離不能很好地刻畫數(shù)據(jù)的本質(zhì)特征[10]。低秩表示子空間分割和最小二乘回歸子空間分割從全局考慮了樣本間數(shù)據(jù)的關(guān)系可以很好地克服這樣的不足。

低秩表示子空間分割和最小二乘回歸子空間分割方法將每個樣本點xi表示為其它樣本點的線性組合接著用（）/2表示xi和xj之間的相似度。這兩種方法的不同在于表示系數(shù)的懲罰函數(shù)。

低秩表示子空間分割[9]的求解目標(biāo)是秩最小問題，但是這是NP難的，文獻(xiàn)[7]將其退化成一個凸問題

最小二乘回歸子空間分割[8]方法本質(zhì)上是嶺回歸在子空間分割中的應(yīng)用，其目標(biāo)是

利用低秩表示子空間分割和最小二乘回歸子空間分割方法可以得到仿射矩陣，最后可以利用標(biāo)準(zhǔn)分割（normalized cuts）[11]方法實現(xiàn)聚類。這兩種方法可以方便的求出仿射矩陣，但是容易受到噪聲的干擾。

2局部強(qiáng)化最小二乘回歸子空間分割

最小二乘回歸子空間分割方法具有解析解，本文將最小二乘回歸子空間分割方法進(jìn)行改進(jìn).通過強(qiáng)化局部樣本對子空間分割的影響，提出局部強(qiáng)化最小二乘回歸子空間分割（local strengthen least square regression，LSLSR）.

2.1目標(biāo)函數(shù)

利用數(shù)據(jù)集X∈Rm×n線性重構(gòu)某個樣本y∈Rm×1，即

最小二乘回歸子空間分割方法[8]所研究的嶺回歸模型

該方法容易受到噪聲樣本的影響。

基于這一不足，強(qiáng)化局部樣本對子空間分割的影響提出局部強(qiáng)化最小二乘回歸子空間分割方法如下，

其中，SL是局部強(qiáng)化項，代表局部樣本對子空間分割的影響，γ是正則參數(shù)。局部強(qiáng)化項SL的定義是多種多樣的[10]。將近鄰樣本視為局部樣本，用文獻(xiàn)[10]的方法定義如下的局部強(qiáng)化項

其中bi∈N（y）是樣本y的近鄰樣本，K表示近鄰樣本的個數(shù),SL反映了局部樣本對重構(gòu)系數(shù)的影響。由此，得到如下的目標(biāo)函數(shù)

公式(1)的第一項是樣本重構(gòu)項，第二項是局部強(qiáng)化項，參數(shù)γ（0＜γ＜1）用于平衡樣本重構(gòu)項和局部強(qiáng)化項，最后一項是嶺回歸懲罰項，γ＞0是正則參數(shù)γ＞0。

2.2目標(biāo)函數(shù)求解

本節(jié)研究目標(biāo)函數(shù)的求解，令目標(biāo)函數(shù)(1)為O（w），則

這里Tr（X）表示求跡，并且應(yīng)用了Tr（X）=Tr（XT）和Tr（XY）=Tr（YX）。對w求導(dǎo)得

2.3局部強(qiáng)化最小二乘子空間分割算法

首先，對每個樣本通過(2)的求解得到該問題的解w，進(jìn)而可以構(gòu)造矩陣Z*=（wi）n得到仿射矩陣接著應(yīng)用譜聚類方法：標(biāo)準(zhǔn)分割方法（normalized cuts）[11]對仿射矩陣進(jìn)行分割.將這一過程歸納為如下的局部強(qiáng)化最小二乘子空間分割算法（local strengthen least square regression，LSLSR）

算法：局部強(qiáng)化最小二乘子空間分割算法（LSLSR）；

Input：數(shù)據(jù)矩陣X，類數(shù)k，局部樣本數(shù)量K，正則參數(shù)λ，γ；

Output：k個類簇；

Step1：對于每個樣本通過(2)解決問題(1)得到解w；

Step2：將n(為樣本個數(shù))個w構(gòu)成矩陣Z*計算仿射矩陣（

Step3：應(yīng)用標(biāo)準(zhǔn)分割方法將數(shù)據(jù)分成個子空間。

3實驗及結(jié)果分析

本節(jié)從聚類準(zhǔn)確率的角度來驗證局部強(qiáng)化最小二乘回歸子空間分割算法（LSLSR）對基因表達(dá)數(shù)據(jù)聚類的有效性.對比方法為經(jīng)典的子空間分割方法：低秩表示子空間分割方法（LRR）和最小二乘回歸子空間分割方法（LSR），傳統(tǒng)的聚類方法:K均值聚類（K-means）和層次聚類法（HC）。聚類準(zhǔn)確率的定義[12]為：對給定樣本，令ri和si分別為聚類算法得到的類標(biāo)簽和樣本自帶的類標(biāo)簽，那么準(zhǔn)確率的計算公式為

其中n為樣本總數(shù)，δ（x，y）是一個函數(shù)，當(dāng)x=y時，值為1，否則為0,map（ri）是一個置換函數(shù)，將每一個類標(biāo)簽ri映射成與樣本自帶的類標(biāo)簽等價的類標(biāo)簽。

3.1數(shù)據(jù)描述

選用6個常用的基因表達(dá)數(shù)據(jù)集來驗證LSLSR的有效性，這些數(shù)據(jù)來源于文獻(xiàn)[13]的研究，將其總結(jié)成表1。

所有數(shù)據(jù)集都標(biāo)準(zhǔn)化為具有單位L2范數(shù)，即用式(3)標(biāo)準(zhǔn)化，

其中x表示一個樣本。

表1數(shù)據(jù)集描述

3.2實驗結(jié)果與分析

實驗過程中，LSLSR、LSR、LRR等子空間分割方法存在參數(shù)設(shè)置問題，采用搜索策略來設(shè)置參數(shù)：LSLSR、LSR、LRR這3種方法的正則參數(shù)λ均采用統(tǒng)一的取值0.0001,0.001,0.01,0.1,1；LSLSR的正則參數(shù)的取值為0.1到0.9;局部樣本數(shù)量取值為2到10。為避免隨機(jī)性，每種方法運行10次，取聚類平均值。表2以聚類平均值±方差的方式給出實驗結(jié)果。

表2聚類準(zhǔn)確率

由實驗結(jié)果可以看出，LSLSR可以取得較好的聚類準(zhǔn)確率。對比所有方法，在全部數(shù)據(jù)集上LSLSR的聚類準(zhǔn)確率都是最高的。

LSLSR方法與經(jīng)典的子空間分割方法LSR和LRR對比，可以發(fā)現(xiàn)，LSLSR的聚類準(zhǔn)確率顯著高于后兩者。這表明LSLSR考慮了局部樣本可以更好地適應(yīng)基因表達(dá)數(shù)據(jù)的多噪聲特點，具有更好的魯棒性。因此，本文提出的局部強(qiáng)化思想是可以改進(jìn)子空間分割方法的聚類性能的。

對比傳統(tǒng)的K-means和層次聚類兩種方法，LSLSR的優(yōu)勢依然明顯.這說明傳統(tǒng)的聚類方法不能很好地適應(yīng)高維數(shù)小樣本多噪聲的基因表達(dá)數(shù)據(jù)的聚類。造成這樣的原因是基因表達(dá)數(shù)據(jù)的高維數(shù)小樣本特點導(dǎo)致距離度量不準(zhǔn)確，難以取得理想的聚類結(jié)果.這一實驗結(jié)果也反映了LSLSR比傳統(tǒng)聚類方法更加適合基因表達(dá)數(shù)據(jù)的聚類。

3.3參數(shù)討論

局部強(qiáng)化最小二乘子空間分割算法（LSLSR）有3個重要參數(shù)：局部樣本數(shù)量和兩個正則參數(shù)。文獻(xiàn)[8-9]的研究最小二乘回歸子空間分割方法在正則參數(shù)較小時會有較好的聚類結(jié)果，以這一研究為依據(jù)，本文取λ=0.01，討論局部樣本數(shù)量和正則參數(shù)對實驗結(jié)果的影響。圖1給出了不同參數(shù)下LSLSR的聚類準(zhǔn)確率。

圖1 K、γ不同時LSLSR在6個數(shù)據(jù)集上的聚類準(zhǔn)確率

從圖1，可以發(fā)現(xiàn)不同的實驗參數(shù)對聚類準(zhǔn)確率會產(chǎn)生影響.當(dāng)較小時，LSLSR的聚類準(zhǔn)確率較高，這反映了在聚類過程中，更加強(qiáng)調(diào)原樣本的影響，但是局部樣本也對實驗結(jié)果產(chǎn)生了影響。當(dāng)較小時，LSLSR有較好的聚類準(zhǔn)確率，隨著近鄰數(shù)量的增加準(zhǔn)確率會下降（SRBCT除外），這符合基因表達(dá)數(shù)據(jù)的小樣本多噪聲的特點，進(jìn)一步說明LSLSR有較好的抗噪能力。

4結(jié)束語

局部強(qiáng)化最小二乘子空間分割算法（LSLSR），通過局部樣本的限制加強(qiáng)了近鄰樣本對樣本聚類的影響，可以較好地提高樣本的抗噪能力。實驗結(jié)果表明LSLSR是一種有效的聚類算法。對于研究基因表達(dá)數(shù)據(jù)聚類，LSLSR聚類效果明顯優(yōu)于經(jīng)典的子空間分割方法LRR和LSR。LSLSR需要分別求取每個樣本的重構(gòu)系數(shù)，時間消耗比LSR多，但是LSLSR有解析解，并且基因表達(dá)數(shù)據(jù)的低維數(shù)特點，因此不會減弱LSLSR的實用性.LSLSR的有3個重要參數(shù)，如何自適應(yīng)的選擇參數(shù)需要進(jìn)一步的研究。

［1］HAMERLY G，ELKAN C．Alternatives to the k－means algorithMthat find better clusterings［C］／／International Con-ference on Information and Know ledge Management，2002：600－607．

［2］ZHANG T，RAMAKRISHNAN R，LIVNY M．BIRCH：an efficient data clusteringmethod for very large databases［J］．AcMSigmod Record，1999，25：103－114．

［3］BIRANT D，KUT A．ST－DBSCAN：a n algorithMfor clustering spatial–temporal data［J］．Data＆Know ledge Engineering，2007，60（1）：208－221．

［4］WANG W，YANG J，MUNTZ R R．STING：a statistical information grid approach to spatialdataMining［C］//Proceedings of the 23rd International Conference on Very Large Data Bases．[s.l.]：Morgan Kaufmann Publishers Inc．，1997：186－195．

［5］NG A Y，JORDAN MI，WEISSY Y．On spectral clustering：analysis and an algorithm［J］．Proceedings of Advances in Neural Information Processing Systems，2001，14：849－856．

［6］ELHAMIFAR E，VIDAL R．Sparse subspace clustering［C］//Proceedingsof 23rd IEEE Conference on Computer Vision and Pattern Recognition，2009：2790－2797．

［7］LIU G，LIN Z，YU Y．Robustsubspace segmentation by low－rank representation［C］//Proceedingsof the27th InternationalConference on Machine Learning，2010：663－670．

［8］LU C Y，MIN H，ZHAO Z Q，et al．Robust and efficient subspace segmentation via least squares regression［C］//Proceedingsof the 12th European Conference Computer Vision，2012：347－360．

［9］CHEN X，JIAN C．Gene expression data clustering based on graph regularized subspace segmentation［J］．Neurocomputing，2014，143（16）：44–50．

［10］PENG X，ZHANG L，YIZ，etal．Learning locality－constrained collaborative representation for robust face recognition［J］．Pattern Recognition，2014，47（9）：2794–2806．

［11］S HI J，MALIK J．Normalized cuts and image segmentation［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888－905．

［12］CAID，HEX，WU X，etal．Non－negativematrix factorizationonmanifold［C］．//Proceedingsof the 8th IEEE International Conference on Data Mining，2008：63－72．

［13］STATN IKOV A，TSAMARDINOS I，DOSBAYEV Y，et al．GEMS：a systeMfor automated cancer diagnosis and biomarker discovery from Microarray gene expression data［J］．International journal ofmedical informatics，2005，74（7）：491－503．

（責(zé)任編輯：朱聯(lián)九）

Gene Expression Data Clustering Based on Local Strengthen Least Square Regression Subspace Segmentation

JIAN Cai-ren1,WENG Qian2

（1.Tan Kah Kee Colleage,Xiamen University,Zhangzhou,363105，China;2.College of Mathematics and Computer Science,Fuzhou University,Fuzhou,350116，China）

Subspace segmentation segments the data set into different clusters,which is broadly used in pattern recognition.Authors improve least squares regression subspace segmentation by using locality-constrained collaborative representation.Local strengthen least square regression subspace segmentation is proposed.The proposed method strengthens the reconstruct coefficientby using neighbor data samples,so that LSLSR has the ability to robustagainst various corruptions and occlusions.The experimental results show that themethod can achieve a high clustering accuracy.

local strengthen;leastsquare regression subspace segmentation;gene expression data;clustering

TP18

A

1673-4343（2016）06-0001-07

10．14098／j．cn35－1288／z．2016．06．001

2016-06-08

福建省科技創(chuàng)新平臺建設(shè)項目(2009J1007)；福建省教育廳科技項目(JK2010001）

簡彩仁，男，福建永定人，助教。主要研究方向：數(shù)據(jù)挖掘、模式識別。