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

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

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

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

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

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

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