徐久成， 穆輝宇， 馮 森

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

DOI: 10.13705/j.issn.1671-6841.2017096

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

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

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

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

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

DOI: 10.13705/j.issn.1671-6841.2017096

0 引言

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

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

1 基本概念

1.1 主成分分析

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

1.2 鄰域粗糙集

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

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

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

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

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

(1)

(2)

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

(3)

鄰域粗糙集的正域為

(4)

鄰域粗糙集的負域為

(5)

決策屬性D對條件屬性B的依賴度為

(6)

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

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

(7)

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

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

2.1 歐氏距離的多鄰域計算

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

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

(8)

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

(9)

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

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

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

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

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

輸出：特征基因集合SD.

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

Step 2： 初始化約簡集合red=?.

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

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

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

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

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

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

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

Step 10： 結(jié)束.

3 實驗分析

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

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

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

3.2 實驗結(jié)果

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

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

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

表2 特征基因數(shù)目及對應的閾值取值

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

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

1) 分類器

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

表3 不同分類器的分類精度對比

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

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

2) 基因選擇方法

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

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

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

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

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

4 小結(jié)

PCA可以刪除關系緊密的變量，提取出較少的特征變量，NRS約簡算法可以有效地進行特征選擇.本文根據(jù)基因表達譜的空間分布特點，首先采用PCA獲得低維的特征空間，減小計算的時間復雜度；然后利用多鄰域粗糙集算法，采用歐氏距離對每列屬性計算鄰域值，根據(jù)鄰域集合來計算近似；最后采用啟發(fā)式搜索選擇出特征基因子集.與鄰域粗糙集模型相比，采用多鄰域的形式能夠?qū)?shù)據(jù)進行更加精確的描述.結(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]. 小型微型計算機系統(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] 胡清華,于達仁，謝宗霞. 基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡[J]. 軟件學報, 2008, 19(3): 640-649.

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

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

[9] 惠景麗, 潘巍, 吳康康,等. 基于非對稱變鄰域粗糙集模型的屬性約簡[J]. 計算機科學, 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] 范方云, 孫俊, 王夢梅. 一種基于改進的遺傳算法的癌癥特征基因選擇方法[J]. 江南大學學報(自然科學版), 2015,14(4): 413-418.

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

(責任編輯：孔 薇)

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

國家自然科學基金項目(61370169,61402153)；河南省科技攻關重點項目(142102210056,162102210261)；河南師范大學青年科學基金項目(2014QK28)；河南省高等學校重點科研項目(16A520057).

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

TP18

A

1671-6841(2017)04-0028-06