基于啟發(fā)式搜索的生物特征辨識算法研究.pdf

1、腫瘤是影響人類健康的主要的疾病。而基因微陣列和蛋白質質譜等生物技術的出現為疾病的診斷和治療提供了新的方法,開辟了新的途徑。但由于數據具有高維、小樣本等特性,常規(guī)的模式識別方法已不再適用。針對此類數據,如何剔除冗余特征、如何從海量的數據中挖掘出隱藏在數據背后的有用的生物信息成為研究識別和分類問題的關鍵。
　　 而目前常用的特征識別方法根據子集獲取的方式,可以分為基于隨機搜索和非隨機搜索策略的特征選擇算法;從機器學習角度,特征選擇算

2、法又可以分為:過濾法和纏繞法。過濾法獨立于分類器,分類精度無法保證;纏繞法在挑選過程中需要反復調用內嵌分類器以評估基因的分類性能,造成極高的計算量。除此之外,數據的高維、高噪聲的特點增加了過擬合的風險。近年來,Michat Draminski等人結合隨機搜索策略和決策樹,提出Monte Carlo featureselection(簡稱MC)算法,它是一種隨機搜索的特征選擇算法,不僅降低了搜索時間,而且避免結果陷入局部最優(yōu)的風險,對高維

3、數據具有較強的適應性。MC算法中所用的判別準則一決策樹,它綜合考慮了分類率及變量的重要性,避免過度依賴分類率,使得最終結果對于不同的分類器具有較強的魯棒性;決策樹中所用的判別指標不同于傳統單純的分類率,其可以減低樣本不平衡問題所造成的影響。但是,MC方法在搜索變量空間過程中沒有合理規(guī)劃,并且不同的迭代問相互獨立不相關,沒有相互的“通信”,沒有合理利用歷史成績和當前排名,造成搜索效率低,結果受隨機次數影響較大。在MC算法基礎上,結合職業(yè)網

4、球選手排名機制,提出基于職業(yè)網球選手排名的基因隨機選擇算法(Feature Selection Algorithm based onProfessional Tennis Players Ranking,PTPR)。
　　 PTPR算法保留了MC算法的精髓,即隨機選擇及決策樹判別,同時借鑒職業(yè)網球賽的排名機制,引入了“種子變量”、實時滾動更新排名,優(yōu)化了搜索過程,提高了搜索效率,保持了結果穩(wěn)定。在迭代過程中,PTPR算法不同的迭

5、代間,通過“記憶"列表,實現了“信息互通”,利用當前最優(yōu)變量更新種子變量并排名,然后在下一次迭代中對種子變量的性能進行重新的評估,重新提取當前最優(yōu)變量,如此迭代循環(huán),直至達到最終可接受范圍的最優(yōu)解。在搜索變量的同時,對已發(fā)現的變量“記憶",在下一次迭代中對其重新驗證和評價,不僅提高了搜索效率,而且最終所得的最優(yōu)變量是多次評估的結果,而非單調一次循環(huán)所得,體現了公平公正原則。
　　 通過在Leukemia、Colon、Glioma

6、、Prostate、Lung和Ovarian數據集上從四個不同的角度對PTPR的性能進行了評估,即變量排名的收斂性、變量的重復率、樣本的分類率及AUC。通過變量排名的收斂性和變量的重復的實驗中可以看出,PTPR算法相對于MC算法,變量排名變化幅度明顯低于MC,并以較少的迭代次數收斂到穩(wěn)定的變量排名,并且PTPR多次實驗所得到的結果相似性明顯高于MC,受外界因素影響較小。通過分類率和AUC實驗表明,PTPR所得到的特征變量在獨立的測試集上