張鵬濤，陳曉云，簡(jiǎn)彩仁

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

?

基于局部坐標(biāo)稀疏表示和最小二乘的基因表達(dá)數(shù)據(jù)分類

張鵬濤1，陳曉云1，簡(jiǎn)彩仁2

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

局部坐標(biāo)稀疏表示可以使測(cè)試樣本由其近鄰樣本線性近似表示，借鑒此思想，在稀疏表示模型中引入局部距離加權(quán)并添加非負(fù)約束，求解得到測(cè)試樣本在訓(xùn)練集上的表示系數(shù)，根據(jù)表示系數(shù)的大小剔除訓(xùn)練集中的噪聲點(diǎn)，在新的訓(xùn)練集上進(jìn)行最小二乘子空間分類。在6個(gè)基因表達(dá)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，所提算法可以進(jìn)一步改善分類質(zhì)量。

局部坐標(biāo)表示；稀疏表示；最小二乘

0 引言

DNA微陣列技術(shù)[1]的出現(xiàn)使得人們可以獲得大量的基因表達(dá)數(shù)據(jù)，如何對(duì)這些數(shù)據(jù)進(jìn)行分析、整理、歸納、注釋對(duì)研究人類的基因突變以及重大疾病有著重大現(xiàn)實(shí)意義，這也是分子生物信息學(xué)[2]的重點(diǎn)研究課題。

基因表達(dá)數(shù)據(jù)存在著高維、小樣本、多噪聲等復(fù)雜特性[3]，致使直接利用基因表達(dá)數(shù)據(jù)進(jìn)行腫瘤分類面臨嚴(yán)峻挑戰(zhàn)。近年來(lái)，大量學(xué)者通過(guò)對(duì)基因表達(dá)數(shù)據(jù)建立有效的分類模型，實(shí)現(xiàn)了在分子水平上對(duì)腫瘤類型準(zhǔn)確識(shí)別。文獻(xiàn)[4]中對(duì)多種類的微陣列基因數(shù)據(jù)分類模型進(jìn)行了全面評(píng)估，結(jié)果表明多類支持向量機(jī)(SVM)算法優(yōu)于k-近鄰算法、反向傳播和概率神經(jīng)網(wǎng)絡(luò)模型，并建立了一個(gè)可以公開(kāi)使用的基因表達(dá)模型選擇系統(tǒng)(Gene Expression Model Selector ,GEMS)。

稀疏表示分類最早在人臉識(shí)別[5]方面取得成功應(yīng)用。文獻(xiàn)[6]中進(jìn)一步將稀疏表示模型應(yīng)用到基因表達(dá)數(shù)據(jù)分類，提出稀疏表示分類算法(SRC)，該算法將測(cè)試樣本用訓(xùn)練樣本的線性組合表示，通過(guò)L1-正則約束計(jì)算出表示系數(shù)進(jìn)而重構(gòu)測(cè)試樣本，最后通過(guò)最小化每一類的重構(gòu)殘差以達(dá)到分類的目的。實(shí)驗(yàn)結(jié)果顯示該算法優(yōu)于SVM算法。然而SRC模型的求解需要用到牛頓內(nèi)點(diǎn)法[7]迭代計(jì)算,時(shí)間復(fù)雜度較高。文獻(xiàn)[8]進(jìn)一步提出一種有效的交替方向優(yōu)化算法解決SRC稀疏模型。文獻(xiàn)[9]中利用同樣的自表示方法提出非負(fù)最小二乘算法(NNLS)，對(duì)缺失值和噪聲點(diǎn)有很好的強(qiáng)健性。文獻(xiàn)[10]進(jìn)一步提出最小二乘回歸分類算法(LSRC)，可以對(duì)腫瘤數(shù)據(jù)有效分類，但LSRC依賴于正則參數(shù)的選擇，容易出現(xiàn)奇異矩陣求逆的問(wèn)題，并且上述模型都沒(méi)有考慮到待測(cè)樣本和訓(xùn)練集之間的距離關(guān)系，訓(xùn)練集中可能存在噪聲樣本，直接利用原始訓(xùn)練集表示測(cè)試樣本會(huì)引起分類精度降低。針對(duì)此，本文借鑒局部坐標(biāo)表示的思想，引入局部距離加權(quán)信息和非負(fù)約束到稀疏表示模型中，利用得到的表示系數(shù)剔除訓(xùn)練集中與測(cè)試樣本相關(guān)性小的噪聲樣本，再結(jié)合最小二乘模型和最近鄰子空間準(zhǔn)則進(jìn)行分類。

1 稀疏表示

給定n個(gè)類標(biāo)簽已知的訓(xùn)練樣本X=[x1,x2,…,xn]∈Rd×n，考慮一個(gè)類標(biāo)簽未知的測(cè)試樣本y∈Rd，通過(guò)下式用訓(xùn)練樣本線性表示該測(cè)試樣本：

y=x1z1+x2z2+…+xnzn

(1)

其中zi(i=1,2,…,n)是表示系數(shù)，zi值越大表示測(cè)試樣本y與訓(xùn)練樣本xi的相關(guān)程度越大，能更好地表示y。通常為方便寫成如下矩陣形式：

y=Xz

(2)

其中z=[z1,z2,…,zn]T∈Rn。

在稀疏表示分類模型(SRC)[6]中,通過(guò)下列模型求得測(cè)試樣本y在訓(xùn)練集X上的表示系數(shù)：

(3)

在有噪聲的情況下，轉(zhuǎn)換為下列模型：

(4)

2 局部坐標(biāo)稀疏表示最小二乘分類

2.1 局部坐標(biāo)稀疏表示剔除噪聲

盡管SRC模型得到的表示系數(shù)通常能較好地分類，但它容易出現(xiàn)過(guò)稀疏[11]的情況，且運(yùn)行速度很慢。針對(duì)訓(xùn)練集X中存在噪聲的問(wèn)題，本文引入局部坐標(biāo)編碼的思想，提出局部坐標(biāo)稀疏表示模型剔除噪聲樣本。

局部坐標(biāo)編碼(LocalCoordinateCoding，LCC)[12]的思想是:在給定字典下，尋找一個(gè)測(cè)試樣本的稀疏表示，并且它的表示系數(shù)是由該測(cè)試樣本的局部近鄰字典的線性組合所編碼。本文在SRC模型的基礎(chǔ)上，同時(shí)借鑒LCC局部近鄰表示的思想，用訓(xùn)練集X作為字典矩陣，添加非負(fù)約束，旨在用測(cè)試樣本的局部近鄰樣本重構(gòu)測(cè)試樣本，得到以下局部坐標(biāo)稀疏表示(LCSR)模型：

s.t.z≥0

(5)

其中X*i表示訓(xùn)練集中的第i個(gè)樣本,zi表示系數(shù)z的第i個(gè)元素，上面模型中第一項(xiàng)表示重構(gòu)誤差，第二項(xiàng)為正則項(xiàng)，確保測(cè)試樣本由局部近鄰樣本線性近似表示。近鄰樣本通常屬于同一類，這樣近鄰樣本在重構(gòu)表示測(cè)試樣本時(shí)占有較大的比重，式(5)第二項(xiàng)能自適應(yīng)地給這些近鄰樣本分配較大的權(quán)重系數(shù)。文獻(xiàn)[13]進(jìn)一步指出局部性比稀疏性更重要，因?yàn)榫植啃酝ǔ？梢缘玫揭粋€(gè)較好的稀疏性，但反過(guò)來(lái)稀疏性通常并不能得到局部性，這樣引入局部信息得到的表示系數(shù)更具有判別能力。

式(5)也相當(dāng)于在SRC模型中添加距離加權(quán)和非負(fù)約束，得到的表示系數(shù)z具有稀疏性、非負(fù)和局部近鄰表示的性質(zhì)，這樣通過(guò)設(shè)置一個(gè)相關(guān)程度閾值ε，剔除zi<ε所對(duì)應(yīng)的訓(xùn)練樣本xi，得到新的訓(xùn)練集Xnew。本文采用文獻(xiàn)[8]中提出的非負(fù)加權(quán)稀疏編碼算法解決式(5)表示的模型。

2.2 最小二乘模型

對(duì)于基因表達(dá)數(shù)據(jù),通常d>>n,因此(2)式是一個(gè)超定方程，求精確解沒(méi)有意義，本文采用最小二乘法得到以下模型：

(6)

z=(XTX)-1XTy

(7)

但上式中矩陣XTX極易接近奇異矩陣，為此，文獻(xiàn)[10]在上面模型中添加L2-范數(shù)正則項(xiàng)，提出LSRC模型：

(8)

其中λ是正則參數(shù)，式(8)表示的模型是凸問(wèn)題，可直接求導(dǎo)得到解析解：

z=(XTX+λI)-1XTy

(9)

式(9)可以在一定程度上避免奇異矩陣求逆的問(wèn)題，也可得到較好的分類效果，但該模型依賴于參數(shù)λ的選擇，并且沒(méi)有考慮到訓(xùn)練集中存在噪聲樣本的情況。因此，本文在新的訓(xùn)練集Xnew上通過(guò)最小二乘模型求得測(cè)試樣本y新的表示系數(shù)znew，將Xnew代入到式(7)得：

(10)

2.3 最近鄰子空間準(zhǔn)則分類[10]

假設(shè)訓(xùn)練集有K個(gè)類標(biāo)簽l1,l2,…,lK，求得測(cè)試樣本y在訓(xùn)練集X上的表示系數(shù)向量z，定義y在第k類訓(xùn)練樣本上的重構(gòu)余量如下

(11)

其中y是測(cè)試樣本，X是訓(xùn)練集，δk(z):Rn→Rn表示y在第k類樣本的重構(gòu)系數(shù)，定義如下：

(12)

最后，測(cè)試樣本y所屬的類標(biāo)簽為：

(13)

2.4 局部坐標(biāo)稀疏表示最小二乘分類

通?？梢园淹活惖臉颖疽暈橐粋€(gè)子空間，理想情況下，測(cè)試樣本僅由屬于同一子空間的樣本數(shù)據(jù)線性表示,而與其他子空間的樣本線性無(wú)關(guān)，表示系數(shù)為0或者非常小,屬于同一子空間樣本的表示系數(shù)相對(duì)較大。本文利用最近鄰子空間分類準(zhǔn)則，將2.1節(jié)得到的訓(xùn)練樣本集Xnew和式(10)求得的表示系數(shù)znew代入式(11)～(13)得到y(tǒng)的類標(biāo)簽，具體算法如下：

局部坐標(biāo)稀疏表示最小二乘分類算法(LCSR-LSC)

輸入：訓(xùn)練集Xtrain，測(cè)試樣本y，參數(shù)λ,訓(xùn)練集類標(biāo)簽ltrain，閾值ε

輸出：測(cè)試樣本y的類標(biāo)簽ltest

表2 分類準(zhǔn)確率(ACC+time,對(duì)比試驗(yàn)降維) (s)

1.將數(shù)據(jù)標(biāo)準(zhǔn)化預(yù)處理；

2.求解LCSR模型式(5)得到表示系數(shù)z，根據(jù)閾值ε剔除zi<ε所對(duì)應(yīng)的訓(xùn)練樣本xi，得到新的訓(xùn)練樣本集Xnew；

3.將Xnew代入到公式(10)求得新的表示系數(shù)znew；

4.利用最近鄰子空間準(zhǔn)則公式(11)～(13)得到待測(cè)樣本y的類標(biāo)簽ltest。

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

在6個(gè)基因表達(dá)數(shù)據(jù)上驗(yàn)證所提算法LCSR-LSC的有效性，對(duì)比算法有：傳統(tǒng)分類算法1-NN、SVM、稀疏表示分類SRC、最小二乘回歸分類LSRC,非負(fù)最小二乘分類NNLS以及LCSR模型結(jié)合最近鄰子空間準(zhǔn)則算法LCSR-C。

表3 分類準(zhǔn)確率(ACC+time,對(duì)比試驗(yàn)未降維) (s)

實(shí)驗(yàn)環(huán)境：Windows 7系統(tǒng)，內(nèi)存4 GB，MATLAB2012b，所有實(shí)驗(yàn)統(tǒng)一在GEMS系統(tǒng)[14]下按十字交叉法進(jìn)行，將數(shù)據(jù)集分為十組，九組用于訓(xùn)練，一組用于測(cè)試。

LCSR-LSC正則參數(shù)λ取(0.001,0.005,0.01，0.02,0.03,0.04,0.05,0.06,0.07，0.08, 0.09, 0.1)，相關(guān)程度閾值ε取很小的正常數(shù)(實(shí)驗(yàn)選取3×10-5)，SVM算法選擇libsvm工具箱[15]，取RBF核函數(shù)，默認(rèn)核參數(shù)1。

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

實(shí)驗(yàn)選用GEMS公開(kāi)的基因表達(dá)數(shù)據(jù)集[14]：SRBCT、Leukemia1、Leukemina2、DLBCL、Prostate_Tumor、11_Tumors，數(shù)據(jù)集描述如表1所示。

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

所有樣本數(shù)據(jù)進(jìn)行規(guī)范化處理：

(14)

其中x表示一個(gè)樣本數(shù)據(jù)。

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

實(shí)驗(yàn)結(jié)果用計(jì)算得到的類標(biāo)簽與真實(shí)類標(biāo)簽求得分類準(zhǔn)確率(ACC)以及算法運(yùn)行時(shí)間(T(s))衡量。本文用PCA將訓(xùn)練樣本和測(cè)試樣本降到m維(m≤d),實(shí)驗(yàn)取m=100，由于本文算法用PCA降維，而對(duì)比試驗(yàn)有些算法并沒(méi)有進(jìn)行降維處理，為了試驗(yàn)對(duì)比的合理性，分別將本文算法得到的實(shí)驗(yàn)結(jié)果與對(duì)比試驗(yàn)在降維和未降維兩種情況下進(jìn)行比較，結(jié)果見(jiàn)表2和表3。

在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖1所示。結(jié)果表明，對(duì)于降維和未降維數(shù)據(jù)，LCSR-LSC算法的分類準(zhǔn)確率都高于對(duì)比算法，其中SRC和LSRC算法對(duì)數(shù)據(jù)降維最為敏感，降維后的分類精度大幅度降低，甚至低于傳統(tǒng)的分類算法1-NN、SVM和LCSR-C算法，NNLS算法在降維前后都能取得較高的分類準(zhǔn)確率，未降維的LSRC算法的分類準(zhǔn)確率優(yōu)于SRC和NNLS算法，而未降維的SRC、NNLS、LSRC都優(yōu)于傳統(tǒng)的1-NN、SVM算法，說(shuō)明采用稀疏表示和最小二乘的算法能取得較好的分類效果，并且這三種算法分類效果也優(yōu)于LCSR-C算法，但分類準(zhǔn)確率低于LCSR-LSC算法，可以看出本文提出的先用LCSR剔除噪聲點(diǎn)的方法可以進(jìn)一步增強(qiáng)LSRC的分類效果。

從運(yùn)行時(shí)間上分析，在保證較高分類準(zhǔn)確率的情況下，由于未降維SRC采用內(nèi)點(diǎn)法迭代求解，時(shí)間開(kāi)銷遠(yuǎn)遠(yuǎn)大于其他幾種算法，LSRC、1-NN的運(yùn)行時(shí)間低于NNLS、SVM，而LCSR-LSC的時(shí)間成本遠(yuǎn)遠(yuǎn)低于SRC，也能實(shí)現(xiàn)較為理想的時(shí)間開(kāi)銷。

3.3 降維以及參數(shù)選擇

討論降維維數(shù)以及參數(shù)對(duì)分類準(zhǔn)確率的影響，在6個(gè)基因表達(dá)數(shù)據(jù)集上降維維數(shù)分別取{10,20, 30,40,50,60,70,80,90, 100}，參數(shù)λ取{0.001,0.005,0.01,0.02, 0.03,0.04,0.05, 0.06, 0.07,0.08, 0.09, 0.1}，得到不同的分類準(zhǔn)確率，如圖2所示。通過(guò)分析可以看出，所選取的維數(shù)以及參數(shù)并沒(méi)有引起分類準(zhǔn)確率很大的改變，當(dāng)正則參數(shù)λ取0.05～0.08時(shí)，降維數(shù)取80～100時(shí)可以得到較高的分類精度。此外，LCSR-LSC算法的正則參數(shù)出現(xiàn)在LCSR模型中，用于剔除噪聲樣本，相比于LSRC、SRC、NNLS其他模型直接用于求得表示系數(shù)對(duì)分類準(zhǔn)確率影響較小。

圖1 降維和參數(shù)λ取不同位時(shí)LCSR-LSC在6組數(shù)據(jù)集上的分類準(zhǔn)確率

4 結(jié)論

本文利用局部坐標(biāo)稀疏表示模型求得的表示系數(shù)具有稀疏、非負(fù)以及局部近鄰表示的良好性質(zhì)，剔除訓(xùn)練集的噪聲樣本，然后在新的訓(xùn)練集上結(jié)合最小二乘模型和最近鄰子空間準(zhǔn)則進(jìn)行分類，并應(yīng)用在基因表達(dá)數(shù)據(jù)集上，可以取得理想的分類效果，進(jìn)一步提高LSRC的分類準(zhǔn)確率，且能高于SRC、NNLS算法的準(zhǔn)確率，時(shí)間成本低于SRC算法。如何設(shè)計(jì)更有效的解決稀疏表示的優(yōu)化算法以及怎樣更為有效地剔除噪聲樣本是今后需要研究的問(wèn)題。

[1] SABER H B, ELLOUMI M. DNA microarray data analysis: a new survey on biclustering[J]. International Journal for Computational Biology (IJCB), 2015, 4(1): 21-37.

[2] GOLUB T R, SLONIM D K, TAMAYO P, et al. Molecular classification of cancer: class discovery and class prediction by gene expression monitoring[J]. Science, 1999, 286(5439): 531-537.

[3] 林莉媛, 陳曉云, 簡(jiǎn)彩仁. 融入距離信息的最小二乘回歸子空間分割[J]. 微型機(jī)與應(yīng)用, 2016, 35(6):63-65.

[4] STATNIKOV A, ALIFERIS C F, TSAMARDINOS I, et al. A comprehensive evaluation of multicategory classification methods for microarray gene expression cancer diagnosis[J]. Bioinformatics, 2005, 21(5): 631-643.

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

[6] Hang Xiyi, Wu Fengxiang. Sparse representation for classification of tumors using gene expression data[J]. BioMed Research International, 2009(403689).

[7] KIM S J, KOH K, LUSTIG M, et al. An interior-point method for large-scale-regularized least squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2007,1(4): 606-617.

[8] Yang Junfeng, Zhang Yin. Alternating direction algorithms forell_1-problems in compressive sensing[J]. SIAM Journal on Scientific Computing, 2011, 33(1): 250-278.

[9] Li Yifeng, NGOM A. Classification approach based on non-negative least squares[J]. Neurocomputing, 2013, 118(2): 41-57.

[10] Chen Xiaoyun, Jian Cairen. A tumor classification model using least square regression[C].International Conference on Natural Computation. IEEE, 2014:753-758.

[11] Zhang Zheng, Xu Yong, Yang Jian, et al. A survey of sparse representation: algorithms and applications[J]. IEEE Access, 2015,3: 490-530.

[12] Yu Kai, Zhang Tong, Gong Yihong. Nonlinear learning using local coordinate coding[C].Advances in Neural Information Processing Systems, 2009: 2223-2231.

[13] Wang Jinjun, Yang Jianchao, Yu Kai, et al. Locality-constrained linear coding for image classification[C]. Computer Vision and Pattern Recognition, 2010: 3360-3367.

[14] STATNIKOV A, TSAMARDINOS I, DOSBAYEV Y, et al. GEMS: a system for automated cancer diagnosis and biomarker discovery from microarray gene expression data[J]. International Journal of Medical Informatics, 2005, 74(7): 491-503.

[15] CHANG C C, LIN C J. LIBSVM: a library for support vector machines[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2(3): 27.

Gene expression data classification based on local coordinate sparse representation and least squares

Zhang Pengtao1, Chen Xiaoyun1, Jian Cairen2

(1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China；2. Tan Kah Kee Colleage, Xiamen University, Zhangzhou 363105, China)

The local coordinate sparse representation can ensure that each test sample can be locally approximated by a linear combination of its nearby train samples. Based on the idea, the local weighted distance and negative constraint are introduced into the sparse representation model in this paper, and we obtain the representation coefficients of the test sample in the trainset by solving the model. Then, according to the size of representation coefficient, the noise points are eliminated and we use the least squares and the nearest neighbor subspace criteria for classification in the new training set. Experimental results on six genetic expression data show that our proposed method can further improve the quality of classification.

local coordinate coding; sparse representation; least squares

TP391; TP311

A

10.19358/j.issn.1674- 7720.2017.12.006

張鵬濤，陳曉云，簡(jiǎn)彩仁.基于局部坐標(biāo)稀疏表示和最小二乘的基因表達(dá)數(shù)據(jù)分類[J].微型機(jī)與應(yīng)用，2017,36(12)：19-22,28.

2016-12-28)

張鵬濤(1991-)，男，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、模式識(shí)別。

陳曉云(1970-)，通信作者，女，博士，教授，主要研究方向：數(shù)據(jù)挖掘、模式識(shí)別。E-mail:c_xiaoyun@21cn.com。

簡(jiǎn)彩仁(1988-)，男，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、模式識(shí)別等。