基于圖正則平滑低秩表示的基因表達(dá)譜特征選擇

楊國亮　康樂樂

(江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院　江西 贛州 341000)

0　引　言

癌癥的產(chǎn)生和發(fā)展是一個(gè)較為復(fù)雜的研究領(lǐng)域。癌癥的高發(fā)態(tài)勢對(duì)人類的生產(chǎn)和生活帶來嚴(yán)重影響，因此癌癥的防范與治療成為熱門的世界性話題。隨著基因表達(dá)譜的出現(xiàn)與廣泛應(yīng)用，為癌癥的治療帶來新的曙光，同時(shí)也得到廣大學(xué)者的關(guān)注和研究。Xu等[1]提出最小生成樹(MST)理論的基因表達(dá)譜分析方法，把復(fù)雜的基因表達(dá)譜數(shù)據(jù)轉(zhuǎn)化成簡單的最小生成樹。王年等[2]利用基因表達(dá)譜數(shù)據(jù)構(gòu)造Laplacian矩陣進(jìn)行分類，提高了算法性能。文獻(xiàn)[3]把流形學(xué)習(xí)和多任務(wù)學(xué)習(xí)應(yīng)用于基因表達(dá)譜數(shù)據(jù)分類研究中，不僅如此，基因表達(dá)譜數(shù)據(jù)分析在基因工程、新藥研制等方面也起到至關(guān)重要的作用。但其高維小樣本的特點(diǎn)也給腫瘤治療與研究帶來巨大困難。因此，如何有效地降低基因表達(dá)譜數(shù)據(jù)維數(shù)，從而進(jìn)行有效的聚類和識(shí)別就成為重中之重。

近年來，基于圖的聚類算法在計(jì)算機(jī)視覺和機(jī)器學(xué)習(xí)等領(lǐng)域中得到廣泛應(yīng)用，例如圖像分割[4]、半監(jiān)督學(xué)習(xí)[5]和維數(shù)約減[6]，主要是通過學(xué)習(xí)一個(gè)有判別性的圖去描述數(shù)據(jù)樣本點(diǎn)的關(guān)系。如何構(gòu)造合適的圖去捕捉數(shù)據(jù)結(jié)構(gòu)是該類算法的難點(diǎn)。

文獻(xiàn)[7]提出了低秩表示LRR(Low Rank Representation),通過求解核范數(shù)最小化問題構(gòu)造低秩圖，可以捕獲數(shù)據(jù)的全局結(jié)構(gòu)。文獻(xiàn)[8]提出拉氏正則低秩表示LLRR(Laplacian-regularized LRR)，有效地捕捉數(shù)據(jù)局部結(jié)構(gòu)和全局結(jié)構(gòu)，提高數(shù)據(jù)結(jié)構(gòu)信息表達(dá)力。文獻(xiàn)[9]提出非負(fù)低秩稀疏圖NNLRS(Non-Negative Low Rank and Sparse Graph)，聯(lián)合低秩表示和稀疏表示同時(shí)捕獲數(shù)據(jù)的全局和局部結(jié)構(gòu)，提高了半監(jiān)督算法的性能。

上述的低秩表示及其擴(kuò)展算法都是使用核范數(shù)代替秩函數(shù)估計(jì)矩陣的秩，從而得到最低秩系數(shù)矩陣，然而核范數(shù)作為秩函數(shù)的凸包絡(luò)，在許多實(shí)際問題中并不能準(zhǔn)確地估計(jì)矩陣的秩[10]。文獻(xiàn)[11]使用平滑Schatten-p函數(shù)代替秩函數(shù)，算法適應(yīng)性得到有效提高。王斯琪等[12]使用Max極小化模型代替秩函數(shù)，在魯棒主成分問題上得到成功應(yīng)用。文獻(xiàn)[13]提出的對(duì)數(shù)行列式函數(shù)，在子空間聚類問題上提高了算法性能[14]。

本文提出的改進(jìn)算法是在構(gòu)建目標(biāo)函數(shù)時(shí)，利用對(duì)數(shù)行列式函數(shù)代替核函數(shù)，平滑地估計(jì)秩函數(shù)，準(zhǔn)確地得到全局?jǐn)?shù)據(jù)結(jié)構(gòu)。在此基礎(chǔ)上，又引入流形正則項(xiàng)，充分保護(hù)了數(shù)據(jù)的局部線性結(jié)構(gòu)，然后采用有效的后處理方法重構(gòu)權(quán)重矩陣，最后使用Ncuts得到最終的聚類結(jié)果。

1　低秩圖

假設(shè)存在一個(gè)訓(xùn)練數(shù)據(jù)集X=[x1,x2,…,xn]∈Rd×n，d表示樣本維數(shù)，n表示樣本數(shù)。低秩表示的目的是最小化系數(shù)矩陣的秩描述子空間流形結(jié)構(gòu)[15]。將X本身作為字典，并且在實(shí)際問題中考慮噪聲影響，那么低秩表示優(yōu)化目標(biāo)函數(shù)如公式所示：

(1)

(2)

2　本文的改進(jìn)算法

2.1　平滑低秩表示

對(duì)數(shù)行列式函數(shù)可以平滑地估計(jì)秩函數(shù)，更加準(zhǔn)確地捕獲數(shù)據(jù)的全局子空間結(jié)構(gòu)，在子空間聚類問題上獲得更好的聚類效果[10]，函數(shù)表達(dá)式如下所示：

(3)

式中：Z表示需求解的系數(shù)矩陣，δi表示Z的第i個(gè)奇異值，使用式(3)代替式(1)中的核范數(shù)，得到的函數(shù)表達(dá)式為：

(4)

2.2　圖正則平滑低秩表示

2.2.1構(gòu)建目標(biāo)函數(shù)

流形理論[16]假設(shè)，原始數(shù)據(jù)空間中xi和xj有相近的幾何結(jié)構(gòu)，那么它們?cè)诹餍慰臻g對(duì)應(yīng)的嵌入映射zi和zj也是相近的。這個(gè)假設(shè)在維數(shù)約減[17]、子空間聚類[18]和半監(jiān)督學(xué)習(xí)[5]等起到重要的作用。

(5)

為了滿足流形假設(shè)，最小化下列目標(biāo)函數(shù)：

Tr(ZDZT)-Tr(ZWZT)=Tr(ZLZT)

(6)

在上述的平滑低秩表示中加入流形正則項(xiàng)，就得到圖正則平滑低秩表示模型，目標(biāo)函數(shù)如下所示：

(7)

2.2.2求解最優(yōu)化問題

為了使得目標(biāo)函數(shù)能夠交替更新時(shí)可分，引入輔助變量J:

(8)

式(8)的增廣拉格朗日函數(shù)：

L=logdet(I+JTJ)+αTr(ZLZT)+λ‖E‖2,1+

(9)

式中：Y1和Y2代表拉格朗日乘子，μ>0是懲罰參數(shù)。通過固定其中兩個(gè)變量，可以交替更新參數(shù)J、Z、E，然后更新參數(shù)Y1、Y2。更新規(guī)則如下：

(10)

(11)

(12)

式(10)有一個(gè)閉合解：

(13)

式(11)可以轉(zhuǎn)化成標(biāo)量最小化問題，通過定理1求得它的解。文獻(xiàn)[14,19]已經(jīng)對(duì)定理1進(jìn)行了證明。

(14)

式(12)的解為：

(15)

式中：Ω為l2,1范數(shù)最小化運(yùn)算符[20]，假設(shè)Y=Ωε(X)，則Y的第i列由式(16)獲得。

(16)

圖正則平滑低秩表示完整求解見算法1。

算法1圖正則平滑低秩表示模型求解

輸入：數(shù)據(jù)矩陣X∈Rd×n,參數(shù)α>0,λ>0

初始化：Z=J=0,E=0,Y1=Y2=0

While not converged do

1.更新J:如式(11)；

2.更新Z:如式(13)；

3.更新E:如式(15)；

4.更新Y1，Y2：

Y1=Y1+μ(X-XZ-E);

Y2=Y2+μ(Z-J);

5.更新參數(shù)μ：

μ=min(ρμ,μmax);

6.檢查收斂條件：

‖X-XZ-E‖∞<εand ‖Z-J‖∞<ε;

End while

輸出：Z

2.3　構(gòu)造數(shù)據(jù)圖結(jié)構(gòu)

(17)

得到權(quán)重矩陣WG后，直接采用Ncuts求得最終的聚類結(jié)果。

圖正則平滑低秩表示的特征選擇算法見算法2。

算法2圖正則平滑低秩表示基因表達(dá)譜特征選擇算法

輸入：基因表達(dá)譜數(shù)據(jù)X

1.利用算法1求得系數(shù)矩陣Z*;

2.對(duì)Z*瘦奇異值分解Z*=U*S*(V*)T；

4.通過式(17)構(gòu)造圖權(quán)重矩陣；

5.采用Ncuts得到聚類結(jié)果。

輸出：聚類準(zhǔn)確率

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

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

為了驗(yàn)證本文算法的有效性，本文選用3個(gè)公共基因表達(dá)數(shù)據(jù)集，分別是DLBCL、NCI、Lung。DLBCL數(shù)據(jù)集有141個(gè)樣本，661個(gè)基因，是3分類問題；NCI數(shù)據(jù)集有63個(gè)樣本，2 308個(gè)基因，是4分類問題；Lung數(shù)據(jù)集有156個(gè)樣本，675個(gè)基因，為2分類問題。

選用的3個(gè)基因表達(dá)數(shù)據(jù)集的相關(guān)信息匯總?cè)绫?所示。

表1　基因數(shù)據(jù)集

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

本節(jié)將在以上3個(gè)基因表達(dá)譜數(shù)據(jù)集上進(jìn)行聚類實(shí)驗(yàn)，并同稀疏子空間聚類SSC[21]、低秩表示LRR[15]、對(duì)數(shù)行列式估計(jì)LDA[19]、圖正則低秩表示GLRR[22]進(jìn)行比較。LDA算法是對(duì)LRR進(jìn)行改進(jìn)，利用對(duì)數(shù)行列式代替核范數(shù)估計(jì)矩陣的秩[10]。GLRR算法是在傳統(tǒng)LRR算法中加入流形正則項(xiàng)，更好地捕捉數(shù)據(jù)全局和局部結(jié)構(gòu)。不同算法在3個(gè)數(shù)據(jù)集的聚類準(zhǔn)確率如表2所示。對(duì)比圖如圖1所示。

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

圖1　五種不同方法的實(shí)驗(yàn)結(jié)果對(duì)比圖

從表2與圖1對(duì)比實(shí)驗(yàn)結(jié)果可以看到：

(1) SSC算法忽略了數(shù)據(jù)之間的結(jié)構(gòu)屬性，所以相比其他算法聚類準(zhǔn)確率最低。

(2) LDA和LRR相比較，在3個(gè)數(shù)據(jù)集上的聚類準(zhǔn)確率明顯提高，最高可提升15%。本文算法與GLRR算法相比較，不同數(shù)據(jù)集上聚類準(zhǔn)確率也有明顯提高，但對(duì)于不同的數(shù)據(jù)集提高的程度不一樣。例如在Lung數(shù)據(jù)集上，前者比后者聚類準(zhǔn)確率提高9%，而NCI數(shù)據(jù)集上只有4%，但總體上，提高的聚類準(zhǔn)確率平均達(dá)到5%以上。由此說明對(duì)數(shù)行列式相比核函數(shù)能夠更好地估計(jì)秩函數(shù)，有效地得到數(shù)據(jù)最低秩表示。

(3) GLRR和LRR相比較，GLRR算法在LRR基礎(chǔ)上加入流形正則項(xiàng)，在不同的數(shù)據(jù)集上獲得的聚類準(zhǔn)確率比LRR算法更高。本文算法是在LDA算法基礎(chǔ)上也加入圖正則項(xiàng)，且在3個(gè)數(shù)據(jù)集上獲得更高的聚類準(zhǔn)確率，比LDA算法平均高出5%，由此說明了數(shù)據(jù)局部保持能力的重要性。

(4) 本文算法在LRR算法的基礎(chǔ)上進(jìn)行兩方面的改進(jìn)，分析對(duì)比實(shí)驗(yàn)結(jié)果，在不同的基因表達(dá)數(shù)據(jù)集上均獲得最高的聚類準(zhǔn)確率，最高可達(dá)到96%，平均增長率約為12%，論證了本文算法的有效性。

由以上分析進(jìn)一步說明，本文算法相比較其他算法，利用對(duì)數(shù)行列式代替核函數(shù)平滑估計(jì)秩函數(shù)，準(zhǔn)確地捕獲了數(shù)據(jù)全局結(jié)構(gòu)。同時(shí)在目標(biāo)函數(shù)中加入流形正則項(xiàng)，很好地彌補(bǔ)了低秩表示的缺陷，準(zhǔn)確地捕獲了數(shù)據(jù)局部線性結(jié)構(gòu)，提高了數(shù)據(jù)空間結(jié)構(gòu)信息的表達(dá)力。

3.3　參數(shù)選擇

本文算法包含兩個(gè)參數(shù)，其中α用來平衡流形正則項(xiàng)，λ用來平衡噪聲項(xiàng)。本節(jié)分析了這兩個(gè)參數(shù)在不同的基因表達(dá)譜數(shù)據(jù)集上對(duì)聚類準(zhǔn)確率的影響。由圖2可以觀察到，參數(shù)α在0.5～1范圍變化時(shí)，本文算法分類準(zhǔn)確率較高。但是在不同的數(shù)據(jù)集上，參數(shù)α的選擇也略有差別，為了實(shí)現(xiàn)較高的聚類準(zhǔn)確率，參數(shù)λ在3個(gè)數(shù)據(jù)集上的選擇差異性較大。具體參數(shù)設(shè)置由圖2和圖3得到。

圖2　不同數(shù)據(jù)集上參數(shù)α對(duì)聚類準(zhǔn)確率的影響

圖3　不同數(shù)據(jù)集上參數(shù)λ對(duì)聚類準(zhǔn)確率的影響

4　結(jié)　語

本文提出一種圖正則平滑低秩表示的特征選擇算法，使用對(duì)數(shù)行列式代替核函數(shù)平滑的估計(jì)秩函數(shù)，準(zhǔn)確地得到數(shù)據(jù)的全局子空間結(jié)構(gòu)；同時(shí)利用流形正則項(xiàng)準(zhǔn)確地捕獲數(shù)據(jù)的局部線性結(jié)構(gòu)，然后利用全新的方式重構(gòu)數(shù)據(jù)的圖結(jié)構(gòu)。該算法具有全局一致性和局部保持力，提高數(shù)據(jù)結(jié)構(gòu)信息的表達(dá)力。在3個(gè)公共基因表達(dá)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明，本文提出的算法有更好的聚類準(zhǔn)確率。

[1] Xu Y,Olman V,Xu D.Clustering gene expression data using a graph-theoretic approach:an application of minimum spanning trees[J].Bioinformatics,2002,18(4):536-545.

[2] 王年,莊振華,唐俊,等.基于Fiedler向量的基因表達(dá)譜數(shù)據(jù)分類方法[J].中國生物工程雜志,2010,30(12):82-86.

[3] 田貝貝.基于流形學(xué)習(xí)和多任務(wù)學(xué)習(xí)的腫瘤基因表達(dá)數(shù)據(jù)分類方法研究[D].武漢科技大學(xué),2015.

[4] Li T,Wu X,Ni B,et al.Weakly-supervised scene parsing with multiple contextual cues[J].Information Sciences An International Journal,2015,323(C):59-72.

[5] Yang S,Feng Z,Ren Y,et al.Semi-supervised classification via kernel low-rank representation graph[J].Knowledge-Based Systems,2014,69(1):150-158.

[6] Pang Y,Wang S,Yuan Y.Learning regularized LDA by clustering[J].IEEE Transactions on Neural Networks & Learning Systems,2014,25(12):2191-2201.

[7] Liu G,Lin Z,Yan S,et al.Robust recovery of subspace structures by low-rank representation[J].Pattern Analysis & Machine Intelligence IEEE Transactions on,2013,35(1):171-184.

[8] Yin M,Gao J,Lin Z.Laplacian Regularized Low-Rank Representation and Its Applications[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2016,38(3):504-517.

[9] Zhang X,Ma Y,Lin Z,et al.Non-negative low rank and sparse graph for semi-supervised learning[C]//Computer Vision and Pattern Recognition.IEEE,2012:2328-2335.

[10] 張濤,唐振民.一種基于非負(fù)低秩稀疏圖的半監(jiān)督學(xué)習(xí)改進(jìn)算法[J].電子與信息學(xué)報(bào),2017,39(4):915-921.

[11] Mohan K,Fazel M.Iterative reweighted algorithms for matrix rank minimization[J].Journal of Machine Learning Research,2012,13(1):3441-3473.

[12] 王斯琪,馮象初,張瑞,等.基于最大范數(shù)的低秩稀疏分解模型[J].電子與信息學(xué)報(bào),2015,37(11):2601-2607.

[13] Fazel M,Hindi H,Boyd S P.Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices[C]//American Control Conference,2003.Proceedings of the.IEEE,2003,3:2156-2162.

[14] Kang Z,Peng C,Cheng J,et al.LogDet Rank Minimization with Application to Subspace Clustering[J].Computational Intelligence & Neuroscience,2015,2015(1-2):68.

[15] 楊國亮,謝乃俊,王艷芳,等.基于低秩稀疏評(píng)分的非監(jiān)督特征選擇[J].計(jì)算機(jī)工程與科學(xué),2015,37(4):649-656.

[16] Liu Y,Liao Y,Tang L,et al.General subspace constrained non-negative matrix factorization for data representation[J].Neurocomputing,2016,173(P2):224-232.

[17] Zhang Z,Yan S,Zhao M.Similarity preserving low-rank representation for enhanced data representation and effective subspace learning[J].Neural Networks,2014,53(5):81-94.

[18] Liu J,Chen Y,Zhang J,et al.Enhancing Low-Rank Subspace Clustering by Manifold Regularization[J].IEEE Transactions on Image Processing,2014,23(9):4022-4030.

[19] Kang Z,Peng C,Cheng Q.Robust Subspace Clustering via Smoothed Rank Approximation[J].IEEE Signal Processing Letters,2015,22(11):2088-2092.

[20] Liu G,Lin Z,Yu Y.Robust Subspace Segmentation by Low-Rank Representation[C]//International Conference on Machine Learning.DBLP,2010:663-670.

[21] Elhamifar E,Vidal R.Sparse subspace clustering:algorithm,theory,and applications[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2013,35(11):2765-2781.

[22] He W,Chen J X,Zhang W.Low-rank representation with graph regularization for subspace clustering[J].Soft Computing,2017,21(6):1-13.