一種基于隨機森林的改進特征篩選算法

劉云翔 陳斌 周子宜

摘 ?要： 肝癌是一種我國高發(fā)的消化系統(tǒng)惡性腫瘤，患者死亡率高，威脅極大。而其預后情況通常只能通過醫(yī)生的專業(yè)知識和經(jīng)驗積累來粗略判斷，準確率較差。因此文中在分析隨機森林算法的基本原理的基礎上，提出一種改進的基于隨機森林的特征篩選算法，并應用Python編程設計了一個能夠預處理數(shù)據(jù)、調(diào)用這些算法、控制各參數(shù)并展現(xiàn)測試結(jié)果的系統(tǒng)，最終將該系統(tǒng)應用于肝癌預后預測，比較分析了不同的算法、參數(shù)、內(nèi)部策略對預測精度和計算性能的影響。研究結(jié)果表明，隨機森林相比剪枝過的決策樹具備更好的泛化能力和訓練速度，改進的特征篩選算法能夠在保證預測精度的前提下顯著縮小特征集。

關鍵詞： 隨機森林算法; 特征篩選; 肝癌預后預測; 決策樹; 預測精度; 特征集

中圖分類號： TN911?34; TP3?05; TP312 ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）12?0117?05

Abstract： Liver cancer is a malignant tumor of the digestive system highly occurred in China， which causes high mortality of patients and great threat to their lives， and its prognosis conditions are often roughly judged by doctors with their professional knowledge and experience accumulation， which has poor accuracy. Therefore， on the basis of analyzing the basic principle of the random forest algorithm， an improved feature selection algorithm based on the random forest is proposed in this paper. The Python programming design is applied to design a system that can preprocess data， recall the algorithms， control various parameters and display test results. The system is applied to the prognosis prediction of the liver cancer. The influences of different algorithms， parameters and internal strategies on the prediction accuracy and computing performance are compared and analyzed. The research results show that in comparison with the pruned decision tree， the random forest has a better generalization ability and training speed， and the improved feature selection algorithm can significantly reduce the feature set on the premise of guaranteeing the prediction accuracy.

Keywords： random forest algorithm; feature selection; liver cancer prognosis prediction; decision tree; prediction accuracy; feature set

0 ?引 ?言

肝癌是一種我國高發(fā)的消化系統(tǒng)惡性腫瘤，患者死亡率在惡性腫瘤中高居第三，威脅極大。該疾病的預后情況通常只能通過醫(yī)生的專業(yè)知識和經(jīng)驗積累來粗略判斷，準確率較差，對醫(yī)生和患者都造成了不利影響。目前國內(nèi)外對該方面進行預測的系統(tǒng)性研究甚少，大多局限于某些具體指標對預后產(chǎn)生的意義，更沒有相應的模型或軟件。但是國內(nèi)尚無成熟的原發(fā)性肝癌數(shù)據(jù)庫，這可能和肝癌數(shù)據(jù)分散，難以大批量獲得有關。目前國內(nèi)將數(shù)據(jù)挖掘應用于肝癌預后預測研究主要的嘗試有申羽等人運用樸素貝葉斯算法[1]和于長春等人應用改進的神經(jīng)網(wǎng)絡算法[2]對原發(fā)性肝癌預后預測進行應用研究。隨著醫(yī)學上的數(shù)據(jù)采集設備不斷更新?lián)Q代，基于大樣本的數(shù)據(jù)挖掘技術將逐步在醫(yī)學應用中嶄露頭角，顯現(xiàn)出了重要的實用價值和廣闊的發(fā)展前景。

本文將隨機森林算法應用于原發(fā)性肝癌的數(shù)據(jù)分析，以期在臨床上能夠借助計算機進行預后預測，幫助選擇治療方案。此外，還改進并驗證了一種基于隨機森林的特征篩選算法，以降低模型訓練的開銷和數(shù)據(jù)采集的難度。本文采用Python語言實現(xiàn)了上述算法的各個細節(jié)，組織系統(tǒng)界面，最終進行大量的測試，詳細分析不同參數(shù)和內(nèi)部策略對性能、輸出造成的影響，對模型選擇提供了建議。

本文數(shù)據(jù)來自第二軍醫(yī)大學東方肝膽醫(yī)院，共有588個病例和3個類別，在專業(yè)人員的幫助下去除了很多無關指標，每例剩余39個可用指標。

1 ?隨機森林算法原理

隨機森林是以決策樹為基學習器的集成學習方法，它包含多棵隨機產(chǎn)生的決策樹并將它們的預測結(jié)合輸出[3?4]。隨機森林采取了Bagging思想和特征子空間思想，比單一決策樹有更好的抗噪性，并且不易過擬合，可以顯著提高泛化能力[3]。隨機森林在Bagging思想的樣本擾動基礎上，又加入了屬性擾動，即特征子空間思想：在各決策樹的每個節(jié)點上選取最佳劃分特征時，候選特征集都是從該節(jié)點的特征集中隨機抽取的一個子集，而不再是該處的整個特征集。特征子集的大小k決定了隨機程度，通常取[k=M]或[k=log2M+1]，其中M是當前節(jié)點的特征總數(shù)。特別地，當[k=1]時，每個特征都是隨機選取的;而當[k=M]時，建立的是普通決策樹。

由于每棵決策樹的訓練集和節(jié)點上的特征子集都是獨立抽取，所以它們的預測結(jié)果也是相互獨立的。根據(jù)Bagging思想，隨機森林在分類時用簡單投票法取各決策樹的多數(shù)預測結(jié)果。隨機森林構(gòu)造的是多棵“隨機”的決策樹，其中單棵的泛化能力通常低于在同樣訓練集上構(gòu)造的普通決策樹，然而在集成后整體的性能往往會好于只用Bagging方法建立的隨機森林，因為各基學習器之間有更大的差異性，可得隨機森林中每一棵“隨機”決策樹的構(gòu)建算法如下：

初始化每個節(jié)點抽取的特征子集大小m

由于各決策樹構(gòu)建過程的隨機性，隨機森林被證明不會過擬合[4]，故每棵樹都盡可能地生長而不需要剪枝。與此同時，各分類器同質(zhì)且相互獨立，因此隨機森林的建立可以方便地并行完成，速度較快。圖1為隨機森林的基本流程。

圖1 ?隨機森林的基本流程

2 ?基于袋外誤差的特征選擇

對于高維數(shù)據(jù)，一般要進行降維或特征選擇，目的是降低模型學習的難度[5?8]。而冗余特征的存在使得特征選擇更有必要性，去除這些不相關的特征不但能降低學習的開銷，還能給數(shù)據(jù)采集提供便利。常見的特征選擇方式有三類：過濾式、包裹式和嵌入式。過濾式方法在建立學習器之前就對數(shù)據(jù)集進行特征選擇，再用篩選后的特征訓練學習器;包裹式方法在候選特征子集上訓練學習器，用學習器的性能來評價所選的特征集;而嵌入式方法在訓練學習器的同時就能完成特征選擇。本節(jié)中隨機森林的特征選擇算法是一種基于袋外誤差的包裹式方法。

2.1 ?特征重要性

隨機森林定義了特征的重要性度量，計算某特征X重要性的步驟如下：

1） 對于隨機森林中的決策樹[Ti]，計算它在自己袋外數(shù)據(jù)上的分類錯誤數(shù)[Ei]。

2） 在該決策樹的袋外數(shù)據(jù)中對X的取值進行隨機擾動，重新計算其分類錯誤數(shù)[EXi]。

3） 令[i=1，2，…，n]，重復以上兩步，其中n是隨機森林包含的決策樹個數(shù)。

4） 特征X的重要性定義為：

這樣定義的依據(jù)是：如果對某個特征加入噪聲后模型的袋外誤差顯著提升，則說明該特征對預測結(jié)果的影響較大，從而有較高的重要性。

2.2 ?改進的特征選擇算法

2010年Genuer R等人和2014年姚登舉等人曾提出用隨機森林進行特征選擇的基本方法[5?6]，本文在此基礎上設計一種更加快捷的特征選擇算法，根據(jù)各輪篩選造成的誤差增量（相對篩選前）來判斷是否要繼續(xù)篩選，一旦它超過指定閾值就退出迭代，并將上一輪篩選所得的特征集作為結(jié)果。這樣做的依據(jù)是，對于在不斷縮減的特征集上訓練出的模型，它們的泛化性能一般呈降低趨勢，而其降低程度可以作為特征集的評價標準。該策略的實質(zhì)是在給定誤差范圍內(nèi)優(yōu)先選擇最小的特征子集，而不是測試精度最高的，從而能夠盡早停止篩選，節(jié)省大量時間。不將誤差增量閾值簡單置為0的原因是，除了剔除不相關特征之外還希望去除一些弱相關特征，而且這樣也能容許每次測試的微小偏差。試驗結(jié)果表明，篩選后的特征集其實并不會產(chǎn)生像閾值那樣大的誤差增量，在其上的測試精度可以與篩選前持平甚至更高。

由于交叉驗證的過程中會產(chǎn)生多個隨機森林，故選擇其中測試精度最高的一個來計算當前輪次的特征重要性順序。計算特征重要性的流程圖如圖2所示。

圖2 ?計算特征重要性的流程圖

3 ?在肝癌數(shù)據(jù)上的應用和分析

3.1 ?數(shù)據(jù)概覽和預處理

訓練和測試數(shù)據(jù)為肝癌病例588例，由第二軍醫(yī)大學東方肝膽醫(yī)院提供，在專業(yè)人士的幫助下去除了許多無關指標，并將所有記錄數(shù)值化。每個病例剩余39個匿名指標，類標簽有3種：

1） 惡性腫瘤，包含246例（41.8%）;

2） 正常，包含193例（32.8%）;

3） 良性病變，包含149例（25.3%）。

由于隱私保護、記錄丟失等客觀原因，樣本集缺失值較多，共693處，缺失值超過5個的樣本被程序自動丟棄，剩余519例。此外，每個樣本包含6個離散型指標，下標分別為：0，16，17，18，19，20。

本文測試過程中的操作平臺的配置為i7?3930k、16 GB內(nèi)存，開發(fā)和測試環(huán)境為WIN7 64 bit、Anaconda 5.1.0，其中Python解釋器版本3.6.5（64 bit），預處理數(shù)據(jù)結(jié)果如圖3所示。

3.2 ?模型評估方法

由于是分類問題，故模型的損失函數(shù)為0?1損失，而模型的測試誤差是其在測試集上的平均損失[9?11]。設模型f的輸入是X，Y是對應X的真實值，測試樣本容量為N，則損失函數(shù)L、測試誤差e和測試精度r的形式化定義如下：

圖3 ?讀取的文件

模型的復雜度可以直接由代碼段在同1臺計算機上的運行時間衡量，也可以通過決策樹的葉節(jié)點個數(shù)來比較。記錄的運行時間由Python計時器獲得[9]。