基于K—S檢驗的Relief特征基因選擇方法

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

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

關鍵詞：基因數據；K-S檢驗；Relief基因特征選擇算法；分類精度

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

1 相關知識1.1K-S檢驗算法

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

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

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

是在顯著性水平下樣本統計量的臨界值，當得到的樣本統計量r大于或等于^寸，認為在置信水平下，該基因在正類與負類中存在顯著性差異；反之，沒有顯著性差異。

1.2 Relief特征選擇算法

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

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

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

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

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

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

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

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

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

3 實驗結果與分析3.1實驗數據

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

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

利用3個數據集：Prostate，Leukemia和Lung進行實驗，

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

3.3 特征選擇算法的對比

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

4 結語

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

[參考文獻]

[1]李萍.基于基因表達數據的胃癌特征基因選取研究[D].北京：北京工業大學，2009.

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

[3]楊昆.基因表達數據分析和處理關鍵技術[D].哈爾濱：哈爾濱工業大學，2008.

[4]李萍.基于基因表達數據的胃癌特征基因選取研究[D].北京：北京工業大學，2009.endprint