基于PCA和多鄰域粗糙集的腫瘤特征基因選擇算法

徐久成， 穆輝宇， 馮 森

(1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453007； 2.河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心 河南 新鄉(xiāng) 453007)

DOI: 10.13705/j.issn.1671-6841.2017096

基于PCA和多鄰域粗糙集的腫瘤特征基因選擇算法

徐久成1,2， 穆輝宇1,2， 馮 森1,2

(1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453007； 2.河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心 河南 新鄉(xiāng) 453007)

針對(duì)鄰域粗糙集采用全局鄰域求解近似，存在計(jì)算時(shí)間復(fù)雜度高且無(wú)法對(duì)基因表達(dá)譜精確描述的問(wèn)題，構(gòu)造了基于主成分分析(PCA)和改進(jìn)鄰域粗糙集(NRS)算法的PNRS模型.首先采用PCA算法獲得低維的特征基因空間；然后利用改進(jìn)的多鄰域粗糙集算法進(jìn)行特征基因選擇，即采用歐氏距離計(jì)算每列屬性鄰域值，選取所有屬性鄰域集合計(jì)算鄰域決策系統(tǒng)的近似；最后采用啟發(fā)式搜索算法選擇特征基因子集.實(shí)驗(yàn)結(jié)果表明，PNRS模型能夠在選擇出較小的基因子集的情況下獲得較高的分類精度，從而驗(yàn)證了該方法的有效性.

特征選擇； 主成分分析； 多鄰域粗糙集； 歐氏距離

DOI: 10.13705/j.issn.1671-6841.2017096

0 引言

腫瘤的致病機(jī)理復(fù)雜且難以治愈，給人類的健康帶來(lái)巨大的威脅.《2015年中國(guó)癌癥統(tǒng)計(jì)數(shù)據(jù)》指出，我國(guó)癌癥的發(fā)病率和死亡率越來(lái)越高，基因微陣列技術(shù)為癌癥的診斷和治療提供了新途徑[1].基因表達(dá)譜數(shù)據(jù)的樣本維度高、樣本量小等特性為特征基因選擇帶來(lái)了困難[2].文獻(xiàn)[3]指出，基因表達(dá)譜分類問(wèn)題重在特征選擇的方法，而非分類器的選擇.因此，特征基因選擇方法成為研究的關(guān)鍵.文獻(xiàn)[4]提出了一種用于癌癥分類的過(guò)濾特征選擇方法，該方法使用相關(guān)系數(shù)的排序來(lái)提取出與癌癥相關(guān)的基因.文獻(xiàn)[5]用遞歸特征消除方法進(jìn)行特征基因選擇.因基因表達(dá)譜具有高維、低樣本、冗余多等特點(diǎn)，使得這些選擇模型存在計(jì)算時(shí)間復(fù)雜度高和正確識(shí)別率不高等問(wèn)題.文獻(xiàn)[6]在粗糙集模型基礎(chǔ)上提出鄰域粗糙集特征選擇的模型，在敏感特征選擇方面取得較好的效果.在該方法中，鄰域的大小是跟閾值的設(shè)置直接相關(guān)的，閾值的不同設(shè)置，直接影響著最終的分類精度和提取的特征基因數(shù)[7].近年來(lái)一些學(xué)者針對(duì)鄰域選擇進(jìn)行了很多研究.文獻(xiàn)[8]提出了基于標(biāo)準(zhǔn)差計(jì)算鄰域的粗糙集模型，對(duì)輸送帶缺陷電磁查驗(yàn)信號(hào)進(jìn)行仿真試驗(yàn).文獻(xiàn)[9]采用非對(duì)稱結(jié)構(gòu)的鄰域形式，得到了較好的分類結(jié)果.目前，鄰域粗糙集模型采用全局定鄰域的形式，但數(shù)據(jù)復(fù)雜多變，目前這些鄰域取值方式不能對(duì)數(shù)據(jù)進(jìn)行精確的描述，分類結(jié)果會(huì)隨著鄰域的改變產(chǎn)生較大的差異，進(jìn)而影響算法的穩(wěn)健性.

本文基于主成分分析(PCA)和改進(jìn)鄰域粗糙集(NRS)的理論，研究了特征基因的選擇問(wèn)題，構(gòu)造了基于PCA和NRS的PNRS模型.首先采用PCA方法得到低維特征空間，減少計(jì)算鄰域的時(shí)間復(fù)雜度.多鄰域粗糙集算法采取集合鄰域半徑，即為每個(gè)基因計(jì)算不同的鄰域值，這種計(jì)算方式可提升對(duì)數(shù)據(jù)分布的描述能力.然后利用順序向前的啟發(fā)式搜索算法，保證了重要度較大的屬性不被刪除，選擇得到最優(yōu)或者較優(yōu)的特征基因子集，提高模型的分類精度.針對(duì)標(biāo)準(zhǔn)的基因數(shù)據(jù)集，驗(yàn)證了PNRS模型的有效性.結(jié)果表明，PNRS模型可選擇較小的特征基因子集，與其他相關(guān)方法對(duì)比，在分類精度等方面都有較好的表現(xiàn).

1 基本概念

1.1 主成分分析

主成分分析(PCA)是一種統(tǒng)計(jì)學(xué)方法，其基本原理是通過(guò)少數(shù)幾個(gè)主成分來(lái)揭示多個(gè)變量間關(guān)系，即從原始變量中選擇出少數(shù)幾個(gè)主成分，使它們盡可能多地保留原始變量的信息，且彼此間互不相關(guān)[10].

1.2 鄰域粗糙集

文獻(xiàn)[6]提出的鄰域粗糙集模型在解決數(shù)值型問(wèn)題時(shí)表現(xiàn)出了較優(yōu)的特性.

定義1[6]在給定的N維實(shí)數(shù)空間Ω中，I為實(shí)數(shù)集，IN為N維實(shí)數(shù)向量空間，M=IN×IN→I，則M稱為IN上的一個(gè)度量.

定義2[6]在給定實(shí)數(shù)空間Ω上的非空有限集合U={x1,x2,…，xn}，對(duì)?xi的鄰域δ定義為δ(xi)=(xx∈U,Δ(x,xi)≤δ)，其中δ≥0.

定義3[6]給定一非空有限集合U={x1,x2,…，xn}，A是表述U的實(shí)數(shù)型特征集合，D是決策屬性，如果A生成論域上的一族鄰域關(guān)系，則稱NDS=〈U,A∪D〉為一鄰域決策系統(tǒng).

定義4[6]給定一鄰域決策系統(tǒng)NDS=〈U,A∪D〉，決策屬性D將論域U劃分為N個(gè)等價(jià)類(X1,X2,…，XN)，?B?A，則決策屬性D關(guān)于子集B的上近似和下近似分別為

(1)

(2)

同樣可得決策系統(tǒng)的邊界為

(3)

鄰域粗糙集的正域?yàn)?/p>

(4)

鄰域粗糙集的負(fù)域?yàn)?/p>

(5)

決策屬性D對(duì)條件屬性B的依賴度為

(6)

定義5[6]條件屬性a和條件屬性集B對(duì)于決策屬性D的重要度SIG公式為

SIG(a,B,D)=γB∪{a}(D)-γB(D)，

(7)

式中：a為條件屬性；B為條件屬性集；D為決策屬性.

2 PCA和多鄰域粗糙集的特征基因選擇方法

2.1 歐氏距離的多鄰域計(jì)算

本文算法從特征選擇方法模型泛化的角度考慮，選用歐氏距離函數(shù)作為計(jì)算基因數(shù)據(jù)間相似程度的度量，并且能解決過(guò)擬合問(wèn)題，是處理實(shí)數(shù)型數(shù)據(jù)較為常用的方法.

定義6給定一個(gè)決策表DT=(U,C∪D, {Va},fa)a∈C，任意兩點(diǎn)x,y∈U在特征子集R?C上的歐氏距離Δ(x,y,R)為

(8)

在特征基因子集R中，采用的基于歐氏距離的多鄰域計(jì)算，需要針對(duì)每個(gè)屬性計(jì)算鄰域，用于構(gòu)建鄰域集合.則基于歐氏距離的多鄰域定義為

(9)

式中：a∈R；r為計(jì)算鄰域設(shè)定的參數(shù).

2.2 PCA和多鄰域粗糙集的腫瘤特征基因選擇方法

采用PCA算法對(duì)基因表達(dá)譜數(shù)據(jù)構(gòu)建新的低維特征空間，并將改進(jìn)的鄰域粗糙集應(yīng)用于特征基因的選擇，以便提取的特征基因子集能較大程度地維持原數(shù)據(jù)集的分類性能.基于PCA和多鄰域粗糙集的腫瘤特征基因選擇算法描述見算法1.

算法1基于PCA和多鄰域粗糙集的腫瘤特征基因選擇算法.

輸入：基因數(shù)據(jù)集S=(x1, x2,…, xN), 鄰域決策系統(tǒng)NDS=〈U, A∪D〉，計(jì)算屬性鄰域半徑的參數(shù)r及屬性的重要度下限參數(shù)β；

輸出：特征基因集合SD.

Step 1： 首先采用PCA算法對(duì)基因數(shù)據(jù)集S降維處理，選取貢獻(xiàn)率η大于1%的基因數(shù)據(jù)集SA.

Step 2： 初始化約簡(jiǎn)集合red=?.

Step 3： 計(jì)算屬性ai鄰域δ(xi)=Δ(xi)/r.

Step 4： 對(duì)SA中的ai∈SA-red；//ai表示特征基因集合SA的屬性列.

Step 5： 計(jì)算ai的正域及其重要度SIG.

Step 6： 獲取屬性ai的正域集合Posk(D).

Step 7： 判斷重要度SIG是否大于設(shè)定的下限β.

Step 8： 若SIG≤β，記錄k值，red=red+ak，SA=SA-Posk，返回Step 7；若SIGgt;β，輸出約簡(jiǎn)結(jié)果red.

Step 9： 根據(jù)red對(duì)應(yīng)的屬性，獲取較優(yōu)的特征基因集合SD.

Step 10： 結(jié)束.

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

表1 數(shù)據(jù)集信息

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

為了驗(yàn)證該算法的有效性，在Leukemia、Colon Tumor、Lung Cancer、Prostate Cancer 4個(gè)公開的基因表達(dá)譜數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，前2個(gè)數(shù)據(jù)集從(http://featureselection.asu.edu/datasets.php)下載，后2個(gè)數(shù)據(jù)集從(http://datam.i2r.a-star.edu.sg/datasets/krbd/)下載，實(shí)驗(yàn)選用的4個(gè)數(shù)據(jù)集均為用于測(cè)試的兩分類數(shù)據(jù)集，其詳細(xì)信息如表1所示.

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

為了減少計(jì)算多鄰域粗糙集模型的時(shí)間復(fù)雜度，先采用PCA算法對(duì)4個(gè)基因表達(dá)譜數(shù)據(jù)進(jìn)行特征提取，并對(duì)提取的候選特征基因子集繪制各主成分解釋方差的帕累托圖，結(jié)果如圖1所示.

圖1 數(shù)據(jù)集各主成分解釋方差的帕累托圖Fig.1 Pareto diagram of the principal components explained variance on datasets

由圖1可以看出，實(shí)驗(yàn)的4個(gè)基因表達(dá)譜數(shù)據(jù)，當(dāng)基因?qū)傩詡€(gè)數(shù)為50時(shí)，其貢獻(xiàn)率多數(shù)可達(dá)90%以上，Lung在70個(gè)主成分時(shí)，貢獻(xiàn)率達(dá)到90%以上.為了避免一定程度上的基因信息丟失，使得所提取的特征基因子集能最大限度地保持原數(shù)據(jù)集的分類能力，選取主成分貢獻(xiàn)率大于1%的主成分，將它們應(yīng)用于特征基因的提取中.

表2 特征基因數(shù)目及對(duì)應(yīng)的閾值取值

在鄰域粗糙集模型的基礎(chǔ)上，對(duì)鄰域半徑的選取進(jìn)行了優(yōu)化，經(jīng)過(guò)多次試驗(yàn)比較，鄰域閾值r的取值在區(qū)間[0, 2]上較為合適，不同的基因數(shù)據(jù)分別設(shè)置不同的閾值r.重要度下限β取值較小，本文取β=0.01.通過(guò)以上處理，篩選出了分辨能力強(qiáng)、冗余度較低的特征基因，篩選后的特征基因數(shù)目及對(duì)應(yīng)的閾值取值如表2所示.

為了檢驗(yàn)所提出的PNRS算法對(duì)基因數(shù)據(jù)處理的有效性，從以下2個(gè)方面對(duì)選擇得到的特征基因的分類能力進(jìn)行檢驗(yàn).

1) 分類器

為了驗(yàn)證所提出模型的分類性能，使用Weka工具里幾種常用的分類器對(duì)基因數(shù)據(jù)進(jìn)行分類驗(yàn)證，并與直接對(duì)原始數(shù)據(jù)進(jìn)行分類測(cè)試的方法進(jìn)行對(duì)比.實(shí)驗(yàn)均采用十折交叉方法進(jìn)行驗(yàn)證，結(jié)果如表3所示.

表3 不同分類器的分類精度對(duì)比

注：斜線左側(cè)數(shù)據(jù)為未經(jīng)特征基因提取的分類精度實(shí)驗(yàn)結(jié)果，右側(cè)為經(jīng)過(guò)特征基因提取的分類精度實(shí)驗(yàn)結(jié)果.

從表3可以看出，本文算法選擇得到的特征基因子集對(duì)致病組織和正常組織樣本表現(xiàn)出了良好的分類性能.比如白血病數(shù)據(jù)采用Lib-SVM分類，分類精度從65.27%增加到了100.0%，準(zhǔn)確率提高了34.73%，從而說(shuō)明本文的PNRS模型可行有效.

2) 基因選擇方法

實(shí)驗(yàn)選取了一些單一的特征選擇方法和學(xué)者提出或改進(jìn)的相關(guān)算法進(jìn)行對(duì)比實(shí)驗(yàn).本文PNRS算法與ODP(original data processing)、PCA和NRS特征提取的方法進(jìn)行對(duì)比，為保證對(duì)比實(shí)驗(yàn)的可行性和有效性，NRS的閾值設(shè)置與本文的PNRS模型閾值設(shè)置一致.另外，與文獻(xiàn)[11]的BQPSO算法、文獻(xiàn)[12]的IGA算法以及文獻(xiàn)[13]的GSIL算法進(jìn)行特征選擇對(duì)比.采用Weka工具里的Lib-SVM分類器進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表4所示，各方法提取的特征基因數(shù)目如表5所示.

由表4可以看出，采用ODP方法測(cè)試的準(zhǔn)確率最低.例如Prostate基因數(shù)據(jù)集，ODP方法測(cè)試的準(zhǔn)確率為56.61%，相比PCA方法的65.41%、NRS方法的69.87%、BQPSO方法的99.25%、IGA方法的98.82%、GSIL方法的96.08%以及本文PNRS方法的99.41%均偏低，表明原基因表達(dá)譜數(shù)據(jù)集中含有較多冗余信息，相比另外幾種方法都采用特征基因選擇的過(guò)程，說(shuō)明在去除冗余噪聲的基因后，提高了基因的分類能力，較多特征基因并不會(huì)提高模型的分辨能力.

表4 不同基因選擇方法的分類精度對(duì)比

表5 不同基因選擇方法提取的特征基因數(shù)目

從表4、表5可以看出，與PCA、NRS算法相比，PNRS模型提取的特征基因個(gè)數(shù)較少，并且基因測(cè)試的準(zhǔn)確率均有大幅度提高.對(duì)比BQPSO、IGA、GSIL算法，雖然個(gè)別方法的準(zhǔn)確率比本文的PNRS模型偏高，但是它們選擇的特征基因數(shù)量較多，例如Lung數(shù)據(jù)集采用BQPSO、IGA、GSIL模型的準(zhǔn)確率均比PNRS模型偏高，但是它們選擇出的特征基因數(shù)目分別為10、14、7，比PNRS模型選擇出的6個(gè)特征基因子集偏多.綜合來(lái)看，本文提出的PNRS模型在分類準(zhǔn)確率上高于BQPSO、IGA、GSIL等算法，并且選擇出的特征基因子集的數(shù)目較少，驗(yàn)證了本文提出的特征選擇模型的有效性.

4 小結(jié)

PCA可以刪除關(guān)系緊密的變量，提取出較少的特征變量，NRS約簡(jiǎn)算法可以有效地進(jìn)行特征選擇.本文根據(jù)基因表達(dá)譜的空間分布特點(diǎn)，首先采用PCA獲得低維的特征空間，減小計(jì)算的時(shí)間復(fù)雜度；然后利用多鄰域粗糙集算法，采用歐氏距離對(duì)每列屬性計(jì)算鄰域值，根據(jù)鄰域集合來(lái)計(jì)算近似；最后采用啟發(fā)式搜索選擇出特征基因子集.與鄰域粗糙集模型相比，采用多鄰域的形式能夠?qū)?shù)據(jù)進(jìn)行更加精確的描述.結(jié)果表明，本文的PNRS算法選擇出了較少的特征基因，且得到了較高的分類精度.

[1] CHEN W, ZHENG R, BAADE P D, et al. Cancer statistics in China, 2015[J]. CA Cancer J Clin, 2016, 66(2): 115-132.

[2] 徐天賀, 馬媛媛, 徐久成. 一種基于鄰域互信息最大化和粒子群優(yōu)化的特征基因選擇方法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(8): 1775-1779.

[3] SCH?LKOPF B, TSUDA K, VERT A. Gene expression analysis: joint feature selection and classifier design[M]. Cambridge: MIT Press, 2004.

[4] 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(2): 531-537.

[5] FURLANELLO C, SERAFINI M, MERLER S, et al. Entropy-based gene ranking without selection bias for the predictive classification of microarray data[J]. BMC bioinformatics, 2003, 4(1): 54-59.

[6] 胡清華,于達(dá)仁，謝宗霞. 基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡(jiǎn)[J]. 軟件學(xué)報(bào), 2008, 19(3): 640-649.

[7] 黃德雙. 基因表達(dá)譜數(shù)據(jù)挖掘方法研究[M]. 北京:科學(xué)出版社, 2009.

[8] 毛清華, 馬宏偉, 張旭輝. 改進(jìn)鄰域粗糙集的輸送帶缺陷特征約簡(jiǎn)算法[J]. 儀器儀表學(xué)報(bào), 2014, 35(7): 1676-1680.

[9] 惠景麗, 潘巍, 吳康康,等. 基于非對(duì)稱變鄰域粗糙集模型的屬性約簡(jiǎn)[J]. 計(jì)算機(jī)科學(xué), 2015, 42(6): 282-287.

[11] XI M, SUN J, LIU L, et al. Cancer feature selection and classification using a binary quantum-behaved particle swarm optimization and support vector machine[J]. Computational and mathematical methods in medicine, 2016，12(9): 1-9.

[12] 范方云, 孫俊, 王夢(mèng)梅. 一種基于改進(jìn)的遺傳算法的癌癥特征基因選擇方法[J]. 江南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,14(4): 413-418.

[13] 張靖, 胡學(xué)鋼, 李培培, 等. 基于迭代Lasso的腫瘤分類信息基因選擇方法研究[J]. 模式識(shí)別與人工智能, 2014, 27(1): 49-59.

(責(zé)任編輯：孔 薇)

TumorFeatureGeneSelectionMethodBasedonPCAandMultipleNeighborhoodRoughSet

XU Jiucheng1,2, MU Huiyu1,2, FENG Sen1,2

(1.CollegeofComputerandInformationEngineering,HenanNormalUniversity,Xinxiang453007,China; 2.EngineeringTechnologyResearchCenterforComputingIntelligenceandDataMiningofHenanProvince,Xinxiang453007,China)

To solve the problems in higher time complexity and blurry description toward the gene expression profile in the approximation calculation using the global neighborhood, an effective PNRS model was proposed based on principal component analysis (PCA) and neighborhood rough set (NRS). First of all, the low dimensional feature space was obtained by using PCA algorithm; then the multiple neighborhood rough set algorithm was adopted for feature gene selection, namely calculating neighborhood attribute values through Euclidean distance, followed by approximation of neighborhood decision system. Finally, feature gene set was obtained by using the heuristic search method. The experimental results showed that the PNRS model achieved higher classification accuracy with respect to smaller gene subsets. The simulation results showed the validity of the proposed method.

feature selection; principal component analysis; multiple neighborhood rough set; Euclidean distance

2017-04-26

國(guó)家自然科學(xué)基金項(xiàng)目(61370169,61402153)；河南省科技攻關(guān)重點(diǎn)項(xiàng)目(142102210056,162102210261)；河南師范大學(xué)青年科學(xué)基金項(xiàng)目(2014QK28)；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(16A520057).

徐久成(1964—)，男，河南洛陽(yáng)人，教授，主要從事粒計(jì)算、粗糙集、數(shù)據(jù)挖掘和生物信息學(xué)研究，E-mail:xjc@htu.cn；通信作者：穆輝宇(1990—)，男，河南滑縣人，主要從事粗糙集、生物信息學(xué)研究，E-mail:15516578001@163.com．

TP18

A

1671-6841(2017)04-0028-06