一種基于隨機(jī)森林的改進(jìn)特征篩選算法

劉云翔 陳斌 周子宜

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

關(guān)鍵詞： 隨機(jī)森林算法; 特征篩選; 肝癌預(yù)后預(yù)測; 決策樹; 預(yù)測精度; 特征集

中圖分類號(hào)： TN911?34; TP3?05; TP312 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ?文章編號(hào)： 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ī)生的專業(yè)知識(shí)和經(jīng)驗(yàn)積累來粗略判斷，準(zhǔn)確率較差，對(duì)醫(yī)生和患者都造成了不利影響。目前國內(nèi)外對(duì)該方面進(jìn)行預(yù)測的系統(tǒng)性研究甚少，大多局限于某些具體指標(biāo)對(duì)預(yù)后產(chǎn)生的意義，更沒有相應(yīng)的模型或軟件。但是國內(nèi)尚無成熟的原發(fā)性肝癌數(shù)據(jù)庫，這可能和肝癌數(shù)據(jù)分散，難以大批量獲得有關(guān)。目前國內(nèi)將數(shù)據(jù)挖掘應(yīng)用于肝癌預(yù)后預(yù)測研究主要的嘗試有申羽等人運(yùn)用樸素貝葉斯算法[1]和于長春等人應(yīng)用改進(jìn)的神經(jīng)網(wǎng)絡(luò)算法[2]對(duì)原發(fā)性肝癌預(yù)后預(yù)測進(jìn)行應(yīng)用研究。隨著醫(yī)學(xué)上的數(shù)據(jù)采集設(shè)備不斷更新?lián)Q代，基于大樣本的數(shù)據(jù)挖掘技術(shù)將逐步在醫(yī)學(xué)應(yīng)用中嶄露頭角，顯現(xiàn)出了重要的實(shí)用價(jià)值和廣闊的發(fā)展前景。

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

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

1 ?隨機(jī)森林算法原理

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

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

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

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

圖1 ?隨機(jī)森林的基本流程

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

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

2.1 ?特征重要性

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

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

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

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

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

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

2.2 ?改進(jìn)的特征選擇算法

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

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

圖2 ?計(jì)算特征重要性的流程圖

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

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

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

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

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

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

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

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

3.2 ?模型評(píng)估方法

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

圖3 ?讀取的文件

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