解瑞飛 韓 斌 厲力華 祝 磊

(杭州電子科技大學(xué)生命信息與儀器工程學(xué)院，杭州 310018)

引言

高維、小樣本數(shù)據(jù)是生物醫(yī)學(xué)信息處理中經(jīng)常遇到的數(shù)據(jù)類型，如何剔除其冗余特征、提高數(shù)據(jù)質(zhì)量，成為研究識別和分類問題的關(guān)鍵[1-2]。

近年來，Draminski等結(jié)合隨機(jī)搜索策略[3]和決策樹[4]，提出 Monte Carlo(MC)特征選擇算法[5]。它是一種隨機(jī)搜索的特征選擇算法，降低了結(jié)果陷入局部最優(yōu)的風(fēng)險(xiǎn)，對高維數(shù)據(jù)具有較強(qiáng)的適應(yīng)性。同時(shí)，最終變量排名綜合考慮了分類率及變量的重要性，與經(jīng)典方法相比，克服了纏繞法(如SVMRFE)依賴分類器的缺點(diǎn)，以及單純依靠分類率所引起的弊 端[6-7];與 過濾法 ( 如 T-test[8])相 比，MC不需要樣本呈正態(tài)分布的假設(shè)，比T-test更加適合真實(shí)的基因微陣列數(shù)據(jù);和 SVMRFE[9]相比，MC可以更加快速高效地提取出高維數(shù)據(jù)中的顯著變量。

雖然MC方法比傳統(tǒng)方法有更多的優(yōu)點(diǎn)，但是其在搜索過程中沒有規(guī)劃，在不同的迭代間相互獨(dú)立并且不相關(guān)，沒有合理利用歷史成績和當(dāng)前排名，搜索效率低，結(jié)果穩(wěn)定性差。本研究在MC算法基礎(chǔ)上，提出基于職業(yè)網(wǎng)球選手排名(professional tennis player ranking，PTPR)的基因隨機(jī)選擇算法。實(shí)際上，選手排名和基因選擇面臨相似的問題，例如，注冊的職業(yè)選手有幾十萬人，其中參與PTPR官方網(wǎng)站排名的就有近1500人，但每年認(rèn)可的賽事大約70場，因此從特征選擇角度來看是典型的“維災(zāi)”問題，目的是通過大量選手(基因)隨機(jī)參加賽事(基因比較)來對選手進(jìn)行排名。此外，兩者還有許多類似的地方，見圖1。更重要的是，作為權(quán)威排名，職業(yè)網(wǎng)球選手的排名方法在解決排名問題上有很多可以借鑒的地方：一是通過不同賽事對選手進(jìn)行綜合滾動(dòng)排名，體現(xiàn)了選手的整體平均水平，而非由一場賽事決定最終的結(jié)果;二是考慮保留種子選手(根據(jù)以前比賽成績所選出的高水平選手)，把種子選手刻意劃分在不同的小組，可以最大限度地避免種子選手過早相遇而被淘汰，同時(shí)提高了每場賽事的水平;三是因不同賽事對選手排名的貢獻(xiàn)不同，PTPR選手的排名同樣也考慮了賽事本身的質(zhì)量對選手排名的影響。因此，借鑒PTPR的權(quán)威排名，筆者提出了基于PTPR排名的隨機(jī)選擇算法(稱為“PTPR算法”)，該算法保留了 MC算法的精髓，即隨機(jī)選擇，同時(shí)借鑒PTPR排名機(jī)制，引入了種子變量排名、排名滾動(dòng)更新，優(yōu)化了搜索過程，提高了搜索效率，保持了結(jié)果穩(wěn)定。

圖1 網(wǎng)球比賽和特征選擇類比Fig.1 The analogy between tennis competition and feature selection

1 方法

1.1 數(shù)據(jù)來源

采用的測試數(shù)據(jù)包括Leukemia[10]、Colon[11]、Glioma[12]、Prostate[13]及 Ovarian 共 5 個(gè)基因微陣列數(shù)據(jù)集。Leukemia、Colon、Prostate和 Glioma基因表達(dá)譜數(shù)據(jù)來自于公共數(shù)據(jù)庫，已被許多研究者進(jìn)行了分析和研究，Ovarian來自于美國 Duke大學(xué)醫(yī)學(xué)中心和美國Moffitt腫瘤研究中心，具體樣本見表1。

表1 數(shù)據(jù)集描述Tab.1 The description of data sets

1.2 特征選擇方法

基于職業(yè)網(wǎng)球選手排名的特征提取方法(PTPR)，根據(jù)對職業(yè)網(wǎng)球選手排名和基因選擇問題的分析，筆者把PTPR的思想引入到特征提取方法中，在MC算法的基礎(chǔ)上，形成一種新穎的特征選擇算法——基于PTPR的特征選擇算法，簡稱PTPR。

1.2.1 特征隨機(jī)選擇方法

特征隨機(jī)選擇(MC)算法通過建立成千上萬個(gè)決策樹，然后計(jì)算所有決策樹各節(jié)點(diǎn)(特征基因)的重要性，以此作為最終衡量基因排名的指標(biāo)，有

式中，k為決策的結(jié)點(diǎn)(特征基因)，wAcc為特征基因k所在決策樹的分類率，IG(nk(τ))為特征基因k在第樹中所在結(jié)點(diǎn) nk(τ)處的信息增益，no.in nk(τ)為結(jié)點(diǎn) nk(τ)處的樣本數(shù)，no.in τ 為第棵樹的根結(jié)點(diǎn)的樣本數(shù)。nk(τ)的信息增益為

式中，N為結(jié)點(diǎn)nk(τ)處的樣本數(shù)，N(vj)為子結(jié)點(diǎn)處的樣本數(shù)，為子結(jié)點(diǎn)出現(xiàn)的概率，I(n(τ))k為結(jié)點(diǎn)nk(τ)處的信息熵，可表示為

式中，pj為該結(jié)點(diǎn)中屬于某類的分類概率，I(vj)為子結(jié)點(diǎn)處的信息熵。

MC算法在每一次迭代過程中，先隨機(jī)選擇含m個(gè)基因的候選集，然后通過決策樹比較，累加各變量所對應(yīng)的 RI值(見式(1))。RI計(jì)算基于兩點(diǎn)：一是此次決策樹的分類率，二是基因在此次比賽中(決策樹中)的信息增益和正確分類樣本占總樣本的比率。待迭代截止后，對所有變量對應(yīng)的RI進(jìn)行排名，最終排名是基因隨機(jī)參加的所有決策樹中兩項(xiàng)組合(RI)的累計(jì)。

1.2.2 基于MC的PTPR算法

在整個(gè)迭代過程中，MC算法存在兩個(gè)問題：第一，基因在不同的比賽間相互獨(dú)立不相關(guān)，中間過程的成績沒有得到合理的利用，搜索效率低;第二，MC算法中的排名是基于選手相對其他所有選手的重要水平(RI)，由于選手參與賽事(決策樹)的基因完全隨機(jī)選擇。在迭代次數(shù)較少時(shí)，不同基因參加賽事的次數(shù)受隨機(jī)影響，多少不等，RI受賽事次數(shù)影響大，造成結(jié)果不公平;在迭代次數(shù)足夠多時(shí)，不同基因參加賽事的次數(shù)大致相同，所得到的RI也大致相同，利用RI區(qū)分基因不敏感，算法收斂慢。針對MC的問題，PTPR算法模擬了職業(yè)網(wǎng)球選手的排名方式，讓種子選手和普通選手參加不同等級、水平的賽事，然后根據(jù)嚴(yán)格的積分、排名機(jī)制，從成千上萬個(gè)選手中快速高效地篩選出優(yōu)秀的選手。本研究把網(wǎng)球賽中的“種子選手”思想、滾動(dòng)排名機(jī)制同隨機(jī)搜索思想結(jié)合起來，實(shí)現(xiàn)基因的快速提取。網(wǎng)球選手排名和基因排序的類比如圖1所示，基因變量相當(dāng)于選手，種子變量相當(dāng)于種子選手，決策樹相當(dāng)于各種賽事，而每次參與決策樹的基因相當(dāng)于每次參與賽事的選手。

本研究從搜索策略和排名機(jī)制兩方面做了改進(jìn)：首先引入了種子變量，在迭代中，普通變量以固定概率進(jìn)入賽事(決策樹建立)，而種子變量以較高的概率進(jìn)入賽事(因?yàn)榉N子變量的長度遠(yuǎn)遠(yuǎn)小于普通變量的長度)，保證種子變量參與每一場賽事，提高了賽事的水準(zhǔn)，從而提高了比賽的篩選效率。變量排名是List內(nèi)的種子選手到目前為止的歷史成績比較，同時(shí)算法逐次滾動(dòng)更新當(dāng)前種子變量排名，保證目前最優(yōu)秀的選手(基因)參與下一次的比較，進(jìn)一步提高比賽的篩選效率，有

式中：第一部分是分子RIk，表示基因k到目前為止參與所有賽事成績的累積，見式(1);第二部分是分母sum(RI.List)/length(List)，是當(dāng)前種子變量的平均歷史成績，其中List用來存放當(dāng)前的種子變量，length(List)為當(dāng)前種子變量的個(gè)數(shù)，RI.List為存放List中種子變量所對應(yīng)的重要性(每個(gè)種子變量的重要性用其 RI來衡量)，sum(RI.List)為當(dāng)前 List中種子變量的重要性總和。

式(3)表示基因k到目前為止其歷史成績與種子變量平均歷史成績的一個(gè)比較。需要特別說明的是，相對于MC算法是基于所有選手的獲勝記錄(RI累計(jì))來排名，PTPR算法的排名則是基于普通選手和種子選手的比較;wRIk是基因參與眾多賽事后，相對到目前為止“最優(yōu)種子選手”平均水平的一個(gè)衡量，對基因更具有甄別能力。同時(shí)注意的是，分母逐次遞增更新，意味著隨著迭代逐漸有真正的種子選手進(jìn)入種子名單，種子名單趨近最優(yōu)，保證對后面基因的篩選更加公平和高效。通過上面的分析可以看出，PTPR算法最重要的思想是：運(yùn)用種子變量(滾動(dòng)更新)及歷史信息，標(biāo)記并保留已搜索到的當(dāng)前最優(yōu)變量，并在下一步的迭代搜索中吸納更優(yōu)變量，避免因初解不同、盲目搜索對結(jié)果造成的動(dòng)蕩不穩(wěn)定，從而快速高效地篩選出重要基因，其流程圖和步驟如圖2所示。其中，d為變量候選集，m為變量子集(每次參與決策樹比較的變量個(gè)數(shù))，wRI判決為通過wRI公式計(jì)算每個(gè)變量的重要性，Seed為存放當(dāng)前的種子變量，List為存放滿足一定條件后的種子變量，d-List為集合d與集合List的差集(即種子變量之外的普通變量)，p為概率值，m為變量中來自普通變量的比例。

圖2 PTPR算法流程Fig.2 The scheme of the PTPR algorithm

PTPR算法由兩部分組成，一是自由競爭(或初始化)，獲得初始的種子變量;二是循環(huán)競爭，滾動(dòng)更新種子變量，得到最終變量排名。兩種算法分別包括以下步驟。

1.2.2.1 自由競爭：

步驟1：從d個(gè)基因候選集中，隨機(jī)選擇m個(gè)基因，構(gòu)成子集。

步驟2：對于此子集，按照一定比例隨機(jī) t次劃分訓(xùn)練集和測試集，訓(xùn)練集建立決策樹，測試集用來測試所構(gòu)建的決策樹。

步驟3：對步驟2中參與決策樹建立的基因，利用wRI公式計(jì)算后進(jìn)行排名，取前X%存入List。

步驟4：判斷 List長度。如果小于 n×L_List，重復(fù)步驟1;否則，初始化終止。利用 wRI，對 Seed中的基因進(jìn)行排名。

1.2.2.2 循環(huán)競爭

步驟1：判斷 List長度，刪除 List中 L_List之后的基因變量，得到List補(bǔ)集d-List。

步驟2：從集合d-List中隨機(jī)選擇 p×m個(gè)基因(0＜p＜1)，從集合 List中隨機(jī)選擇(1-p)×m個(gè)基因，組合為含有m個(gè)變量的子集;因d-List長度遠(yuǎn)遠(yuǎn)大于List長度，故List中的種子變量以高概率進(jìn)入決策樹，d-List中的普通變量以低概率進(jìn)入決策樹。

步驟3：對于此子集，按照一定比例隨機(jī) t次劃分訓(xùn)練集和測試集，訓(xùn)練集建立決策樹，測試集用來測試所構(gòu)建的決策樹。

步驟4：將步驟3中參與決策樹建立的基因加入到 List，在利用 wRI公式計(jì)算后，更新List排名。

步驟5：重復(fù)步驟1～步驟4至 s次，最后得到List排名。

1.3 PTPR算法驗(yàn)證實(shí)驗(yàn)設(shè)計(jì)原則

衡量一個(gè)特征提取算法是否能夠提取出有效的特征基因，可以從基因分類率和穩(wěn)定性兩個(gè)方面對算法做比較和評估。

1.3.1 基因穩(wěn)定性及顯著差異分析

MC算法和PTPR算法最終得到的都是基因重要性的相對排名，通過觀察基因排名隨迭代次數(shù)的變化規(guī)律，可以反映算法的收斂速度，顯示最終是否收斂達(dá)到穩(wěn)定性的結(jié)果。基因排名變化為

式中，s為迭代次數(shù)，k為第 k個(gè)基因，Rank(s，k)為基因k的排名位置，(s，s-20)為當(dāng)?shù)螖?shù)由 s-20變化到s時(shí)基因的相對排名變化量。隨著迭代次數(shù)s的連續(xù)增大，基因排名的變化越來越小，最終趨于穩(wěn)定。

在特征提取的過程中，從訓(xùn)練集中提取特征，測試集進(jìn)行分類率的計(jì)算，一般需重復(fù)多次。即使在其他條件完全相同的情況下(比如特征提取算法、參數(shù)及樣本比例分配等)，訓(xùn)練集具體樣本不同造成了所提取的特征基因不同。因此，在不同的訓(xùn)練集上，提取穩(wěn)定的特征基因成為特征提取算法的一項(xiàng)重要指標(biāo)。為了驗(yàn)證PTPR算法所提取基因的穩(wěn)定性，實(shí)驗(yàn)包括下列步驟。

步驟1：特征基因獲取。隨機(jī)生成M組訓(xùn)練集，利用MC算法和 PTPR算法，分別提取 M組特征基因。

步驟2：基因重復(fù)率定義。對于 PTPR(或 MC)算法所得到的M組特征基因，兩兩比較，得到前N(N=10，20)個(gè)基因的基因重復(fù)率，共組，分別為PPTPRN和 PMCN。其中，PPTPRN=[p1，p2，…，pC2M]，PMCN=[q1，q2，…，qC2M]。

步驟3：平均基因重復(fù)率。計(jì)算前N個(gè)基因的平均重復(fù)率PPTPRN和PMCN(N=10，20)，有

步驟4：基因重復(fù)率的顯著性分析。在生物信息學(xué)研究中，由于所用數(shù)據(jù)含有較少樣本，往往無法滿足經(jīng)典的參數(shù)檢驗(yàn)條件，可以考慮采用Permutation test進(jìn)行統(tǒng)計(jì)推斷。為了驗(yàn)證PTPR算法在基因重復(fù)率上是否顯著優(yōu)于MC算法，筆者利用PPTPRN和PMCN數(shù)據(jù)，根據(jù)Permutation原理(由于篇幅限制，原理見附錄)，計(jì)算 P-value，分析基因重復(fù)率的顯著性差異。

1.3.2 分類率比較

為了驗(yàn)證MC算法和PTPR算法所提取出的特征基因有效性，可以通過比較來挑出基因的分類能力。為了方便比較，數(shù)據(jù)劃分采用通用的劃分原則，即Leukemia數(shù)據(jù)集隨機(jī)選擇38個(gè)樣本作為訓(xùn)練集，其余34個(gè)樣本作為測試集[10];Colon數(shù)據(jù)集，隨機(jī)選擇33%的樣本作為測試集，其余樣本作為訓(xùn)練集[14];Glioma和 Prostate數(shù)據(jù)按照 9∶1隨機(jī)劃分訓(xùn)練集和測試集[15];Ovarian數(shù)據(jù)按照 7∶3，隨機(jī)劃分訓(xùn)練集和測試集。5個(gè)數(shù)據(jù)分別迭代10次，利用常用分類器支持向量機(jī)(support vector machine，SVM)、k 最近鄰(k-Nearest Neighbor，KNN，K=1)、Na?ve Bayes(NB)和 Random Forests(RF)，對測試集進(jìn)行分類比較。

2 結(jié)果和討論

2.1 基因穩(wěn)定性分析

圖3～圖7表示不同數(shù)據(jù)庫基因排名 Dist(s，s-20)和基因平均重復(fù)率(見式(5))隨迭代次數(shù)s的變化。PTPR和MC都是隨機(jī)搜索算法，靠多次的迭代而獲得最終相對穩(wěn)定的最優(yōu)解。隨著迭代次數(shù)的增加，基因排名變化幅度的大小體現(xiàn)了算法搜索的穩(wěn)定性。前后兩次迭代所引起基因排名變化越小，說明搜索過程越穩(wěn)定，從而體現(xiàn)出隨機(jī)算法穩(wěn)定性越強(qiáng)。從圖3～圖7中的(a)可以看出，在5個(gè)數(shù)據(jù)庫上，隨著迭代次數(shù)增加，PTPR算法所得到的基因排名變化幅度小于MC算法所得到的基因排名變化幅度，并快速收斂到比MC更加穩(wěn)定的水平;而且，PTPR算法在迭代次數(shù)較少的時(shí)候，基因排名的變化量遠(yuǎn)遠(yuǎn)小于 MC算法，體現(xiàn)了PTPR算法相對于MC算法，基因更早地進(jìn)入到收斂過程中。此外，MC和PTPR算法的計(jì)算量基本上是由迭代次數(shù)決定的，當(dāng)特征基因的排名趨于穩(wěn)定水平時(shí)，迭代終止。從圖3～圖7中可以看出，PTPR以較小的迭代次數(shù)，得到了和MC一樣的穩(wěn)定水平，說明PTPR算法比MC計(jì)算速度更快、計(jì)算量更小。

圖3 Leukemia—基因穩(wěn)定性。(a)基因排名的收斂性;(b)前10和前20個(gè)基因的重復(fù)率(從上至下)Fig.3 Gene stability for Leukemia.(a)convergence of gene ranking;(b)top 10 and 20 genes overlapping rate(from upper to bottom)

對于PTPR和MC等隨機(jī)算法，因隨機(jī)因素的存在，即使在其他條件完全相同的情況下，不同時(shí)刻的使用所得到的結(jié)果也不盡相同。因此，提取穩(wěn)定的特征基因成為衡量隨機(jī)算法的一項(xiàng)重要指標(biāo)。在圖3～圖7的(b)中，都是由兩幅子圖組成，分別表示基因個(gè)數(shù)為10和20的基因重復(fù)率，是兩種算法分別重復(fù)10次所得。在不同的數(shù)據(jù)集上，PTPR所得到的基因重復(fù)率大致介于60% ～80%之間，而MC最高只達(dá)到40%左右，即PTPR的基因重復(fù)率遠(yuǎn)遠(yuǎn)高于MC的結(jié)果。具體來說，對于含有w個(gè)變量的數(shù)據(jù)集，利用PTPR所提取出的10組特征基因中，每兩組的前10或20等(w?100)個(gè)基因，60%～80%是相同，而MC最高只有40%相同的基因。因此，PTPR能夠從成千上萬個(gè)基因中多次提取出60%～80%相同的基因，在穩(wěn)定性上比MC算法有顯著性的提高。除此之外，從圖3～圖7中也可以看出，隨著迭代次數(shù)的增加，雖然兩種方法的基因重復(fù)率都呈上升趨勢，但是MC算法仍然沒有超越PTPR算法。

圖4 Colon—基因穩(wěn)定性。(a)基因排名的收斂性;(b)前10和前20個(gè)基因的重復(fù)率(從上至下)Fig.4 Gene stability for Colon.(a)convergence of gene ranking;(b)top 10 and 20 genes overlapping rate(from upper to bottom)

圖5 Glioma—基因穩(wěn)定性。(a)基因排名的收斂性;(b)前10和前20個(gè)基因的重復(fù)率(從上至下)Fig.5 Gene stability for Glioma.(a)convergence of gene ranking;(b)top 10 and 20 genes overlapping rate(from upper to bottom)

圖6 Prostate—基因穩(wěn)定性。(a)基因排名的收斂性;(b)前10和前20個(gè)基因的重復(fù)率(從上至下)Fig.6 Gene stability for Prostate.(a)convergence of gene ranking;(b)top 10 and 20 genes overlapping rate(from upper to bottom)

圖7 Ovarian—基因穩(wěn)定性。(a)基因排名的收斂性;(b)前10和前20個(gè)基因的重復(fù)率(從上至下)Fig.7 Gene stability for Ovarian.(a)convergence of gene ranking;(b)top 10 and 20 genes overlapping rate(from upper to bottom)

對于圖3～圖7中的(b)，為了進(jìn)一步驗(yàn)證PTPR的基因重復(fù)率在統(tǒng)計(jì)學(xué)角度是否顯著高于MC算法，筆者進(jìn)行了相應(yīng)的permutation實(shí)驗(yàn)，具體的原理見附錄。從基因重復(fù)率的permutation實(shí)驗(yàn)的結(jié)果看，在5個(gè)數(shù)據(jù)集上，在迭代次數(shù) s從20變化到1000的過程中，P-value的最高值達(dá)到0.0055左右，遠(yuǎn)遠(yuǎn)小于 0.05，而大多數(shù)的 P-value值為 0。因此，從統(tǒng)計(jì)學(xué)角度上證明了PTPR算法的基因重復(fù)率顯著高于MC算法。

2.2 分類率比較

圖8～圖12中的橫坐標(biāo)都是迭代次數(shù)s，縱坐標(biāo)表示分類率，是5個(gè)數(shù)據(jù)集在不同分類器上的結(jié)果;各圖中的(a)和(b)分別表示在基因個(gè)數(shù)為10和20上所得到的分類率，而每幅圖又由4幅子圖組成，表示在不同分類器 NB、SVM、KNN和 RF(從左至右，從上到下)上所得到的分類率。

圖8 不同基因在NB、SVM、KNN和RF上(從左至右，從上到下)的Leukemia分類率。(a)10個(gè)基因;(b)20個(gè)基因Fig.8 The classification rate of different gene number in NB，SVM，KNN and RF(from left to right，from upper to bottom)for Leukemia.(a)10 genes，(b)top 20 genes

從圖 8～圖 12中可以看出，對于 Colon和Glioma數(shù)據(jù)集，在分類器KNN上，PTPR和MC算法所得的分類率不相上下。但是，在其他數(shù)據(jù)集和分類器上，PTPR算法所得分類率明顯高于MC算法。在Leukemia數(shù)據(jù)集上，PTPR最高分類率達(dá)到98%左右，并且隨著迭代次數(shù)s的增加，一直保持較高的分類率;而MC算法的分類率在整體上低于 PTPR算法，且動(dòng)蕩不穩(wěn)定。在Colon數(shù)據(jù)集中，對于個(gè)別分類器，PTPR和MC得到了同一水平的分類率;但是，從整體來看，PTPR比 MC仍具有一定的提高，PTPR最高達(dá)到了 90.0%左右的分類率。對于Glioma數(shù)據(jù)集，它和Colon數(shù)據(jù)集類似，所含樣本較少，在分類率上和 Colon也具有同樣的現(xiàn)象，但PTPR的部分結(jié)果仍高于 MC，且 PTPR比 MC更加快速地收斂到較高的分類率并保持穩(wěn)定，如圖10中的NB和SVM所示。在Prostate和Ovarian數(shù)據(jù)集上，除個(gè)別外，PTPR的分類率大多數(shù)超過了 MC，尤其是在 Ovarian數(shù)據(jù)集上，MC只得到65%的分類率，而PTPR卻達(dá)到了75%。

圖9 不同基因在NB、SVM、KNN和RF上(從左至右，從上到下)的Colon分類率。(a)10個(gè)基因;(b)20個(gè)基因;Fig.9 The classification rate of different gene number in NB，SVM，KNN and RF(from left to right，from upper to bottom)for Colon.(a)10 genes，(b)top 20 genes

圖10 不同基因在NB、SVM、KNN和RF上(從左至右，從上到下)的Glioma分類率。(a)10個(gè)基因;(b)20個(gè)基因;Fig.10 The classification rate of different gene number in NB，SVM，KNN and RF(from left to right，from upper to bottom)for Glioma.(a)10 genes，(b)top 20 genes

圖11 不同基因在NB、SVM、KNN和RF上(從左至右，從上到下)的Prostate分類率。(a)10個(gè)基因;(b)20個(gè)基因;Fig.11 The classification rate of different gene number in NB，SVM，KNN and RF(from left to right，from upper to bottom)for Prostate.(a)10 genes，(b)top 20 genes

圖12 不同基因在NB、SVM、KNN和RF上(從左至右，從上到下)的Ovarian分類率。(a)10個(gè)基因;(b)20個(gè)基因;Fig.12 The classification rate of different gene number in NB，SVM，KNN and RF(from left to right，from upper to bottom)for Ovarian.(a)10 genes，(b)top 20 genes

因此，從數(shù)據(jù)集Leukemia、Colon、Glioma、Prostate和Ovarian在不同分類器(NB、SVM、KNN和RF)上的分類率來看，PTPR整體的結(jié)果優(yōu)于MC，不依賴于某一固定的分類器，而且隨著迭代次數(shù)s的增加，它的分類率保持不變或者增長，動(dòng)蕩幅度小于MC算法。

2.3 其他方法的分類率比較

Leukemia、Colon、Glioma和 Prostate作為公共數(shù)據(jù)集，已經(jīng)被廣大研究者用來進(jìn)行研究和分析，并取得了一定的成果。在與其他研究者所用數(shù)據(jù)和樣本比例劃分完全一致的條件下，利用PTPR算法提取特征基因，在獨(dú)立的測試集上進(jìn)行分類率測試，結(jié)果如表2～表5所示。

表2 Leukemia-PTPR和其他方法的分類率Tab.2 Classification accuracies for PTPR and other methods on Leukemia %

表3 Colon-PTPR和其他方法的分類率Tab.3 Classification accuracies for PTPR and other methods on Colon %

表4 Glioma-PTPR和其他方法的分類率Tab.4 Classification accuracies for PTPR and other methods on Glioma %

表5 Prostate-PTPR和其他方法的分類率Tab.5 Classification accuracies for PTPR and other methods on Prostate %

由表2可以看出，用 BWSS方法提取特征基因[16]，在50個(gè)基因個(gè)數(shù)時(shí)，4個(gè)分類器都取得最高分類率97.10%;而用 PTPR算法所提取的特征基因，在SVM、KNN、RF和 ANN上的分類率最高值分別為在 10、20、30、30個(gè)基因處所對應(yīng)的 98.24%、98.24% 、98.82% 、96.47% 。也就是說，除 ANN 上PTPR所得分類率最高值略低于BWSS方法外，在其他分類器上，PTPR方法在較少基因時(shí)得到的分類率都超過 BWSS的最高值97.10%。從整體上來看，PTPR算法在 10個(gè)基因時(shí)得到 98.24%、97.94%，超過 BWSS方法在 50個(gè)基因處的97.10%，而PTPR算法在30個(gè)基因上得到了高達(dá)98.82%的分類率。因此，從不同基因個(gè)數(shù)和不同分類器角度來看，所得分類率PTPR算法整體高于BWSS方法，在不同分類器上都保持較高的分類率。

由表 3 可以看出，MPE[14]，T-test[14]和 BWSS[16]方法所得到的最高分類率88.20%是在10個(gè)基因處SVM分類器上得到，而PTPR算法同樣的在10個(gè)基因、SVM分類器上得到分類率89.00%，在30個(gè)基因上得到最高值90.50%，其他基因個(gè)數(shù)上的分類率也都在88.00%以上，整體高于88.20%。換句話而言，PTPR算法所得分類率明顯高于 T-Test方法。雖然PTPR方法在其他分類器上的結(jié)果不如在SVM上高得顯著，但是同 BWSS、MPE相比仍處于較優(yōu)水平。

由表4可以看出，ILDC_REGEC[15]的方法所得到的分類率在不同基因個(gè)數(shù)上的分類率介于67.5% ～77.8%之間，而 PTPR算法得到的分類率最高達(dá)到86.0%，明顯高于77.8%。在NB、SVM和KNN上，PTPR所得分類率基本穩(wěn)定在80.0%以上，明顯高于ILDC_REGEC方法，而 ANN上分類率的結(jié)果雖然不及其他分類器，但整體仍然較優(yōu);在5個(gè)分類器上，PTPR方法的分類率最高值全部高于ILDC_REGEC最高值。

在表 5中，ILDC_REGEC[15]方法的分類率位于78.0% ～91.2% 之間，而 PTPR 算法在 NB、SVM、KNN、RF和 ANN上的分類率最高值分別為92.86% 、94.29% 、92.14% 、97.14% 、94.29% ，全部高于ILDC_REGEC方法的91.2%。在5個(gè)不同的分類器上，PTPR的分類率整體優(yōu)于 ILDC_REGEC算法的分類率。

3 結(jié)論

PTPR算法在隨機(jī)搜索算法的基礎(chǔ)上，借鑒職業(yè)網(wǎng)球選手的排名規(guī)則，引入了種子變量、滾動(dòng)的排名機(jī)制，保留了MC算法的優(yōu)點(diǎn)，即選擇基因時(shí)，綜合利用決策樹本身的優(yōu)點(diǎn)，不是單純地依靠分類率的高低，而是從基因所含信息量的角度進(jìn)行選擇。除此之外，PTPR算法克服了MC算法搜索效率低、收斂慢的缺點(diǎn)，合理利用了當(dāng)前最優(yōu)的變量，提高了篩選效率，使得PTPR算法能夠有效地從成千上萬個(gè)變量中提取出具有顯著性差異的基因。通過在不同數(shù)據(jù)集、不同分類器上的驗(yàn)證，可知 PTPR保持了較強(qiáng)的魯棒性，所得到的結(jié)果不依賴于固定分類器，適用于高維、高噪聲、小樣本的數(shù)據(jù)類型特征選擇問題，同時(shí)能夠快速地收斂到穩(wěn)定的最優(yōu)解，而且最終得到的分類率明顯優(yōu)于MC以及其他特征提取算法。

附錄 Permutation原理及實(shí)驗(yàn)設(shè)計(jì)

為了比較MC和PTPR算法方法所挑選出的基因是否穩(wěn)定，設(shè)計(jì)了Permutation實(shí)驗(yàn)，計(jì)算P-value步驟如下：

· 根據(jù)實(shí)驗(yàn)?zāi)康模贸鰞山M真實(shí)數(shù)據(jù)集如下：

P= [p1，p2，…，pn]和 Q= [q1，q2，…，qn]

·計(jì)算真實(shí)平均值的差值Δ0=，其中

· 混合數(shù)據(jù)集 P和 Q，隨機(jī)分成數(shù)據(jù)集 k次，即

· 計(jì)算Permutation數(shù)據(jù)集平均值的差值，有

[1]Inza I，Larranaga P，Blanco R，et al.Filter versus wrapper gene selection approaches in DNA microarray domains[J].Artificial Intelligence in Medicine，2004，31：91-103.

[2]Jirapech Umpai T，Aitken S.Feature selection and classification for microarray data analysis：evolutionary methods for identifying predictive genes[J].Bmc Bioinformatics，2005，6：1-11.

[3]Yang Wenzhu，Li Dongling，Zhu Liang.An improved genetic algorithm for optimal feature subset selection from multi-character feature set[J].Expert Systems with Applications，2011，38：2733-2740.

[4]Li Xiongmin，Chan CW.Application of an enhanced decision tree learning approach for prediction of petroleum production[J].Engineering Applications of Artificial Intelligence，2010，23：102-109.

[5]Draminski M，Rada-Iglesias A，Enroth S，et al.Monte Carlo feature selection for supervised classification [J].Bioinformatics，2008，24(1)：110-117.

[6]Hamdani TM，Wob JM，Alimi AM，et al.Hierarchical genetic algorithm with new evaluation function and bi-coded representation for the selection of features considering their confidence rate[J].Applied Soft Computing，2011，11：2501-2509.

[7]Mohammadi A，Saraee MH，Salehi M.Identification of diseasecausing genes using microarray data mining and Gene Ontology[J].BMC Medical Genomics，2011，4(12)：1-9.

[8]Li Lihua，Chen Li，Goldgof D，et al.Integration of clinical information and gene expression profiles for prediction of chemoresponse for ovarian cancer[C]//Proceedings of Annual International Conference of the IEEE Engineering in Medicine and Biology Society.Shanghai：IEEE，2005：4818-4821.

[9]Guyon I，Weston J，Barnhill S，et al.Gene selection for cancer classification using support vector machines[J].Machine Learning，2002，46：389-422.

[10]Golub TR， Slonim DK， Tamayo P， et al. Molecular classification of cancer：class discovery and class prediction by gene expression monitoring[J].Science，1999，286(5439)：531-537.

[11]Alon U，Barkai N，Notterman DA，et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays[J].Proc Natl Acad Sci USA，1999，96(12)：6745-6750.

[12]Nutt CL，Mani DR，Betensky RA，et al.Gene expression-based classification of malignant gliomas correlates better with survival than histological classification[J].Cancer Research，2003，63(7)：1602-1607.

[13]Singh D，F(xiàn)ebbo PG，Ross K，et al.Gene expression correlates of clinical prostate cancer behavior[J].Cancer Cell，2002，1(2)：203-209.

[14]Mahata P，Mahata K.Selecting differentially expressed genes using minimum probability of classification error[J].Journal of Biomedical Informatics，2007，40(6)：775-786.

[15]Guarracino MR，Cuciniello S，Pardalos PM.Classification and Characterization of Gene Expression Data with Generalized Eigenvalues[J]. Journal of Optimization Theory and Applications，2009，141(3)：533-545.

[16]Chakraborty S. Simultaneous cancer classification and gene selection with Bayesian nearest neighbor method：An integrated approach[J].Computational Statistics＆ Data Analysis，2009，53(4)：1462-1474.