程璐+李欣+王薇+鄧佳穎+邢陽陽

摘要：文章在分析兩種基因數(shù)據(jù)分析技術(shù)的基礎(chǔ)上，提出一種基于K-S檢驗與Relief特征選擇算法相結(jié)合的基因識別方法。首先采用K-S檢驗選擇出具有一定區(qū)分能力的基因，然后利用Relief算法對篩選出來的基因子集進行特征選擇，將該方法分別與K-S檢驗、Relief算法進行對比，以驗證該算法的可行性。

關(guān)鍵詞：基因數(shù)據(jù)；K-S檢驗；Relief基因特征選擇算法；分類精度

適合度檢驗法（Kolmogorov-Smirnov，K-S）是一種常用的非參數(shù)統(tǒng)計方法，對兩類樣本的分布形狀差異很敏感，主要用于比較兩類樣本是否同分布。Relief根據(jù)特征評估近距離樣本的區(qū)分能力特征，簡單易用并能取得良好的特征選擇效果，但是該特征選擇方法在搜索時不能處理冗余特征的問題，本文將K-S檢驗與Relief算法相結(jié)合，提出一種基于K-S檢驗的Relief基因特征選擇方法，通過K-S檢驗過濾掉大部分冗余和噪聲基因，保留具有顯著區(qū)分能力的基因，有效增強了種群基因的多樣性；再通過Relief算法對這些基因進行特征選擇，避免粒子搜索時不考慮特征之間的相關(guān)性而陷入局部最優(yōu)，從而獲得較高的分類準(zhǔn)確度，快速獲得最優(yōu)特征子集，最后將該方法分別與K-S檢驗、Relief算法進行對比。

1 相關(guān)知識1.1K-S檢驗算法

K-S檢驗基于累積分布函數(shù)，是一種典型的非參數(shù)檢驗方法，用以檢驗一個累積分布是否符合某種理論分布，或者比較兩個累積分布是否存在顯著性差異。本文利用K-S檢驗判斷腫瘤患者與正常人的各基因是否存在顯著差異。

數(shù)據(jù)中包含正類和負類兩組獨立的樣本，對基因數(shù)據(jù)集的特征值進行降序排列，取其中某個正類基因X，其觀測值為基因數(shù)據(jù)集的樣本數(shù)，從而得到次序觀測值…，則基因的累積分布函數(shù)定義見式⑴。

根據(jù)公式（1）計算出正類樣本的累積分布函數(shù)巧w與負類樣本的累積分布函數(shù)，則K-S檢驗統(tǒng)計量T見式（2）。

是在顯著性水平下樣本統(tǒng)計量的臨界值，當(dāng)?shù)玫降臉颖窘y(tǒng)計量r大于或等于^寸，認為在置信水平下，該基因在正類與負類中存在顯著性差異；反之，沒有顯著性差異。

1.2 Relief特征選擇算法

Relief是由Kira和Rendell年提出的一種著名的多變量過濾式特征選擇算法，它也是一種基于樣本學(xué)習(xí)的特征權(quán)重計算算法。Relief算法作為目前應(yīng)用廣泛的特征評估算法之一，是一種經(jīng)典的過濾式特征選擇算法，基于實例的非線性特征，為特征空間中的每維特征賦予一個權(quán)值，以權(quán)值表征特征與類別的相關(guān)程度。

從待選擇的基因數(shù)據(jù)集中隨機選擇〖個基因樣本，根據(jù)歐氏距離找出每個所選擇的樣本在其同類基因樣本中的最近鄰點和在其非同類基因樣本中的最近鄰點。

設(shè)基因樣本空間中兩個輸入樣本向量分別為'和；則其歐氏距離為：

假設(shè)候選特征變量有//個，待選擇的基因樣本有其中第w個特征的權(quán)值%通過多次迭代得到，通過公式（4）計算每個屬性的權(quán)值，最后，篩選出權(quán)值較大的特征作為最終結(jié)果。

2 基于K-S檢驗的Relief基因特征選擇算法

針對上述算法中存在的部分缺點，本文結(jié)合K-S檢驗算法和ReUe償法提出了一種新的基因特征選擇算法，假設(shè)基因數(shù)據(jù)集的樣本數(shù)為凡特征數(shù)為&本文算法的具體實現(xiàn)步驟如下。

（1）將待檢測的正類樣本和負類樣本的y個特征值代入累積分布函數(shù)中，分別得出正類與負類的累積分布函數(shù)值和懇W（2）根據(jù)式（2）計算出基因Z的K-S檢驗統(tǒng)計

量，并與alpha對應(yīng)的基因臨界值rei.it進行對比，篩選出大于該臨界值且具有顯著區(qū)分能力的基因構(gòu)成預(yù)選擇基因子集A；（3）對基因子集A進行表達譜數(shù)據(jù)歸一化；⑷依據(jù)公式

（4）求出每個基因的權(quán)重向量，并利用MATLAB作出基因分類權(quán)重散點圖和基因分類權(quán)重的柱圖；（5）設(shè)定基因權(quán)重閾值和相關(guān)系數(shù)閾值；（6）對選出的權(quán)重較大基因進行兩兩冗余分析，去掉冗余基因。

3 實驗結(jié)果與分析3.1實驗數(shù)據(jù)

為了闡明本文提出的算法是有效的，在前列腺癌（Prostate）、白血?。↙eukemia）和肺癌（Lung）數(shù)據(jù)集上進行試驗，該數(shù)據(jù)集來自于http：//bioinformatics.rutgers.ed/Static/Supplemens/CompCancer/datasets.htm上的公開數(shù)據(jù)集。實驗中使用的計算機系統(tǒng)為WindowslO，64位操作系統(tǒng)、內(nèi)存為8GB、處理器為；。所有實驗都是在MatlabR2016b和weka3.9.0中實現(xiàn)的。

3.2 K-S算法、Relief算法與基于K-S檢驗的Relief基因特征選擇算法對比

利用3個數(shù)據(jù)集：Prostate，Leukemia和Lung進行實驗，

基于K-S檢驗的Relief基因特征選擇算法對基因數(shù)據(jù)集的特征選擇能力明顯優(yōu)于K-S算法。在Prostate基因數(shù)據(jù)中，首先使用K-S檢驗算法剔除無關(guān)基因進行粗提取，再利用Relief算法進行特征選擇，對比只使用K-S算法的結(jié)果發(fā)現(xiàn)，基因數(shù)據(jù)集Prostate中，共有54個樣本、12600基因特征值，通過K-S檢驗進行粗提取，從中篩選12437個特征值，只剔除了原來基因總數(shù)的1.293%，沒有考慮到基因的相關(guān)性；而通過基于K-S的Relief算法對K-S檢驗過后的基因進行特征選擇，從中篩選出了5個特征值，其基因權(quán)重閾值設(shè)為4000，相關(guān)系數(shù)閾值設(shè)為0.9，篩選率高達99.96%，并在懷卡托智能分析環(huán)境下對分類結(jié)果進行檢測，發(fā)現(xiàn)其分類準(zhǔn)確率達到98.5714%。以此類比，分別得出Leukemia和Lung的篩選結(jié)果，再結(jié)合圖像對比3組數(shù)據(jù)的分類精度值得出實驗結(jié)論：K-SReliefX寸基因的特征提取效果優(yōu)于K-S檢驗。

3.3 特征選擇算法的對比

為了進一步驗證基于K-S檢驗的Relief特征選擇算法的適用性，實驗分別采用了以F-sore作為評價準(zhǔn)則的Filter操作，與SVM-RFE方法進行了分類準(zhǔn)確度對比，通過分類精度來評價選擇方法的優(yōu)劣，Leukemia在F+SVMRFE方法下分類精度為81.8%，而在基于K-S檢驗的Relief特征選擇算法下分類精度為87.024%，選擇結(jié)果更優(yōu)。

4 結(jié)語

本文提出了一種基于K-S檢驗的Relief基因特征選擇算法，重新構(gòu)造了基因識別的方法。將粗提取與特征選擇相結(jié)合，使得在面對大量基因數(shù)據(jù)集時的處理方法更加簡便，得出的分類結(jié)果更加精確。利用Lung，Prostate，Leukemia3個基因數(shù)據(jù)集進行實驗，將該實驗結(jié)果與只進行K-S檢驗和Rdief基因特征選擇算法的兩個實驗結(jié)果進行對比，實驗結(jié)果均表明改進算法優(yōu)于原算法，從而驗證了改進算法的有效性。

[參考文獻]

[1]李萍.基于基因表達數(shù)據(jù)的胃癌特征基因選取研究[D].北京：北京工業(yè)大學(xué)，2009.

[2]謝娟英，胡秋鋒，董亞非.K-S檢驗與mRMR相結(jié)合的基因選擇算法[J].計算機應(yīng)用研究，2016（4）：1001-3695.

[3]楊昆.基因表達數(shù)據(jù)分析和處理關(guān)鍵技術(shù)[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2008.

[4]李萍.基于基因表達數(shù)據(jù)的胃癌特征基因選取研究[D].北京：北京工業(yè)大學(xué)，2009.endprint