龐泰吾 胡春燕 尹鐘

摘? 要： 快速地建立預(yù)測模型并且完成準(zhǔn)確的分類在某些特殊的醫(yī)療診斷場合下具有重要的意義。從連續(xù)特征離散化入手，本文提出了一種改進的隨機森林算法。之后使用改進的算法建立了分類模型，并在三個常用的醫(yī)療數(shù)據(jù)集上進行了實驗。實驗結(jié)果表明改進的隨機森林算法不僅運行時間顯著縮減，同時預(yù)測精度也得到了提升。更進一步的，初始的連續(xù)特征經(jīng)過離散化之后變得簡潔明了，這可以方便研究人員的理解。

關(guān)鍵詞： 隨機森林;連續(xù)特征離散化;決策樹;算法改進;醫(yī)療診斷;分類算法

中圖分類號： TP301.6 ???文獻標(biāo)識碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.032

本文著錄格式：龐泰吾，胡春燕，尹鐘. 一種改進的隨機森林在醫(yī)療診斷中的應(yīng)用[J]. 軟件，2020，41（07）：159-163

An Improved Random Forest for Medical Diagnosis

PANG Tai-wu， HU Chun-yan， YIN Zhong

（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China）

【Abstract】： The rapid building of predictive models and accurate classification is of great significance in some special medical diagnosis situations. Based on the discretization of continuous features， an improved random forest algorithm was proposed in this paper. Then the classification model was built by using the improved algorithm and experiments were carried out on three widely used medical data sets. Experimental results show that the improved random forest algorithm not only reduces the running time significantly， but also improves the prediction accuracy. Furthermore， discretization makes the initial continuous feature concise， which is convenient for researchers to understand.

【Key words】： Random forest; Discretization of continuous features; Decision tree; Algorithm improvement; Medical diagnosis; Classification algorithm

0? 引言

機器學(xué)習(xí)可謂當(dāng)下最炙手可熱的人工智能技術(shù)。如何將它與傳統(tǒng)行業(yè)相結(jié)合成為了許多企業(yè)所面臨的新課題。機器學(xué)習(xí)可以看作一個通過挖掘數(shù)據(jù)中存在的潛在規(guī)律來構(gòu)建學(xué)習(xí)器的過程。學(xué)習(xí)器通?？梢苑譃闇\層網(wǎng)絡(luò)與深層網(wǎng)絡(luò)兩種。前者是由一些傳統(tǒng)的機器學(xué)習(xí)方法構(gòu)建的，如邏輯回歸、支持向量機等。它們雖然結(jié)構(gòu)簡單，訓(xùn)練省時，且針對小樣本數(shù)據(jù)也有不錯的預(yù)測精度，但卻普遍存在著過擬合的問題^[1]。深層網(wǎng)絡(luò)包括結(jié)構(gòu)各異的人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN），如卷積神經(jīng)網(wǎng)絡(luò)、循環(huán)神經(jīng)網(wǎng)絡(luò)等。ANN相較于傳統(tǒng)學(xué)習(xí)器更能挖掘出數(shù)據(jù)背后的本質(zhì)規(guī)律，從而達到更好的學(xué)習(xí)效果。但是ANN具有眾多的超參數(shù)。實現(xiàn)對這些參數(shù)的精確調(diào)控需要大量的數(shù)據(jù)作為支撐。而獲得大量的標(biāo)記樣本往往并不是一件容易的事。

為了解決數(shù)據(jù)樣本較少和淺層網(wǎng)絡(luò)存在的過擬合問題，集成學(xué)習(xí)是一個不錯的選擇。它是一種將多個弱學(xué)習(xí)器進行整合從而得到更好預(yù)測效果的方法^[2]。其主要包括三種構(gòu)造思想：bagging^[3]、boosting^[4]和stacking^[5]。隨機森林（Random Forest，RF）作為bagging方法的代表，已經(jīng)在軟件工程^[6]、機械設(shè)計制造^[7]、模式識別^[8]、金融科技^[9]等諸多領(lǐng)域取得了廣泛的應(yīng)用。因為醫(yī)療數(shù)據(jù)采集比較困難且涉及患者隱私，所以樣本規(guī)模通常不大。這便給RF提供了廣泛的應(yīng)用前景^[10-11]。但RF構(gòu)建了多個學(xué)習(xí)器，所以它的運行效率顯著低于單個淺層網(wǎng)絡(luò)。而在一些特殊的情況下，時間是最重要的評估因素。同時，RF的預(yù)測精度還有進一步提升的空間。據(jù)此，本文提出一種基于連續(xù)屬性離散化的改進方法，力求在保證模型預(yù)測精度的同時，使模型的訓(xùn)練時間盡可能地縮短。更進一步的，離散化也可以為連續(xù)數(shù)據(jù)提供一個簡明的概括，從而方便研究人員的理解。

1? 算法研究

隨機森林是多個決策樹集成的產(chǎn)物。因為每棵樹的特性各不相同，即針對測試集的表現(xiàn)各有千秋。所以將它們進行結(jié)合可以顯著地降低結(jié)果方差，從使模型的整體預(yù)測精度得到提升。據(jù)此，本文首先對決策樹的有關(guān)概念進行闡述。

1.1? 決策樹

決策樹是一種經(jīng)典的學(xué)習(xí)器，它由根節(jié)點、葉子節(jié)點、中間節(jié)點及各節(jié)點之間的路徑組成。其中節(jié)點表示若干樣本的集合，而路徑表示某種分類的規(guī)則。根據(jù)節(jié)點分裂方法的不同，現(xiàn)在廣泛使用的決策樹包括C4.5和CART（Classification And Regression Tree）兩種。本文中的隨機森林是使用CART構(gòu)建的。該種樹采取Gini系數(shù)作為節(jié)點分裂的指標(biāo)。CART的生成過程如下。

計算當(dāng)前節(jié)點中樣本的Gini系數(shù)可表示為。

式中S_r表示節(jié)點的樣本集，n表示類標(biāo)的種數(shù)，P_i表示類標(biāo)為i的樣本占總樣本的比例。之后分別計算每種劃分情況下的Gini系數(shù)，下式以一個二元屬性x為例。

式中|S_x1|表示x屬性值為1的樣本個數(shù)。接著選擇Gini系數(shù)最小的屬性作為節(jié)點劃分的依據(jù)。需要說明的是，針對連續(xù)屬性，CART會先將其離散化之后再按照離散變量處理。最終以遞歸的形式重復(fù)上述步驟直到?jīng)Q策樹的完全構(gòu)建。

觀察上述過程不難看出，決策樹每一步的分裂都依據(jù)了貪婪的思想，這便使其很容易陷入到局部最優(yōu)中。同時從根節(jié)點到葉子節(jié)點的路徑往往非常復(fù)雜，這使得決策樹對噪聲很敏感，且容易出現(xiàn)過擬合現(xiàn)象。為了解決這一問題，隨機森林應(yīng)運而生。

1.2? 隨機森林

1.2.1? 隨機森林簡述

隨機森林是一種基于決策樹的集成學(xué)習(xí)方法。它的具體工作流程如下圖所示。

現(xiàn)有大量實驗證明，相較于決策樹，隨機森林的泛化誤差得到了顯著的降低^[12-13]。這與它的隨機特性是密切相關(guān)的。隨機森林的隨機性主要表現(xiàn)在兩個方面：①訓(xùn)練集的隨機性，即采用一種有放回的抽樣法獲取多個不盡相同的樣本集;②屬性的隨機性，即僅使用樣本集中部分的特征變量來訓(xùn)練決策樹。有了上述隨機性的保證，隨機森林便不會像單個決策樹那樣產(chǎn)生嚴重的過擬合現(xiàn)象了。下文中的定理2充分說明了這一點。

1.2.2? 隨機森林的數(shù)學(xué)描述^[14]

定義1? 隨機森林的本質(zhì)為一個集成分類器，為了對其置信度進行度量，引入邊緣函數(shù)（Marginal Function）的定義是十分必要的。設(shè)隨機森林是由N_t棵決策樹構(gòu)成的，且基分類器表示為h（X，θ_k），其中X表示輸入向量，θ_k是一個用來刻畫第k棵決策樹構(gòu)造過程的隨機向量。

式中：Y為正確的預(yù)測類標(biāo);avg為求平均的函數(shù);I為示性函數(shù);k為從1～N_t的整數(shù);j為某一個不正確的類標(biāo)。根據(jù)上式可以看出，函數(shù)mf表示了正確分類的平均得票數(shù)超過最大的錯誤分類平均得票數(shù)的程度。顯然，mf函數(shù)的輸出值越大，分類器的置信度便越高。

定義2? 根據(jù)邊緣函數(shù)的定義，隨機森林的泛化誤差可以表示為。

式中：P表示錯誤分類的概率，其下標(biāo)刻畫了該式中的概率空間。根據(jù)上述兩個定義和大數(shù)定理，可以得到定理1。

定理1? 當(dāng)隨機森林中基分類器的個數(shù)增加時，其泛化誤差均收斂于。

定理1? 說明了隨著樹數(shù)目的增加，森林的泛化誤差會趨向某一個上界。這表明了隨機森林相較于決策樹具有很好的抗過擬合能力。

定理2? 泛化誤差的上界可表示為。

式中：表示森林中決策樹的平均相關(guān)度;s²表示決策樹強度的平均值。根據(jù)式（6）可以看出，降低隨機森林的泛化誤差主要有兩種方法：增加單棵樹的預(yù)測能力;降低森林中各棵樹之間的相關(guān)性。在前文中已經(jīng)提到，上述的兩點正是由隨機森林的隨機性保證的。

1.2.3? 隨機森林的缺陷

縱使隨機森林在很大程度上解決了決策樹面臨的過擬合問題，但它所使用的bagging算法也增加了計算成本。而使RF運行效率降低的另一個主要因素便是CART對連續(xù)特征的處理方法，即逐一針對每個分裂點進行二分處理，之后根據(jù)GINI系數(shù)選擇劃分方案。顯然，這樣的處理方法具有一定的盲目性。同時，隨機森林模型的預(yù)測精度也有進一步提升的空間。

1.3? 算法改進

如前文所介紹的，本文主要通過引入一種連續(xù)特征離散化的方法來改進隨機森林的算法的性能^[15]。當(dāng)前，連續(xù)特征離散化存在著眾多方法。依據(jù)劃分起點的不同，它們可以分為自底向上的和自頂向下的兩種。當(dāng)連續(xù)屬性的取值個數(shù)遠大于目標(biāo)劃分區(qū)間的種數(shù)時，后者的運行效率顯然會高于前者。所以本文決定選擇CACC（Class-Attribute Contingency Coe?cient）算法作為連續(xù)屬性離散化的方法^[16]。不同于CART以GINI系數(shù)作為劃分的依據(jù)，CACC算法引入了一個新的指標(biāo)cacc。其計算過程如下。

式中：M表示數(shù)據(jù)集中樣本的總個數(shù);q_ir表示類標(biāo)為i且在第r個特征劃分（d_r-1，d_r]內(nèi)的樣本的個數(shù);S表示類標(biāo)的種數(shù);n表示特征劃分的種數(shù);M_i+為類標(biāo)為i的樣本的總個數(shù);M_+r為在特征劃分（d_r-1，d_r]內(nèi)的樣本的總個數(shù);log表示求自然對數(shù)的函數(shù)。之后CACC算法以分治和貪心的思想^[17]逐步遞歸便可以完成連續(xù)屬性的離散化了。

2? 實驗

2.1? 數(shù)據(jù)集及實驗環(huán)境

本文實驗中所使用的數(shù)據(jù)集均源于UCI機器學(xué)習(xí)數(shù)據(jù)庫。它們分別是關(guān)于如下三種疾病的數(shù)據(jù)：糖尿病、心臟病和癌癥。數(shù)據(jù)集的具體信息如表1所示。

在對數(shù)據(jù)進行了預(yù)處理之后，實驗在一臺6核16G的計算機上進行。其操作系統(tǒng)為Windows 10;程序設(shè)計語言為Python 3.7。

2.2? 參數(shù)配置

不同于神經(jīng)網(wǎng)絡(luò)，隨機森林算法僅涉及兩個超參數(shù)的配置^[18]。它們是森林中樹的棵數(shù)N_t和構(gòu)造單個決策樹時選用特征的個數(shù)N_f。由定理1可以看出，N_t的增加并不會導(dǎo)致森林出現(xiàn)嚴重的過擬合。但是隨著樹數(shù)目的增多，模型所花費的時間成本與空間成本都會上升。而且邊際效用遞減法則同樣適用于此^[14]。N_f如果取值過小，則單棵決策樹的強度無法得到保證;但隨著N_f的增大，森林中樹間的相關(guān)度有可能也會增大。經(jīng)過上述分析我們不難發(fā)現(xiàn)N_t和N_f的設(shè)置對于模型性能的影響是很大的。經(jīng)過大量實驗，本文對隨機森林的兩個超參數(shù)的設(shè)置如表2所示。

2.3? 評估指標(biāo)

對于類標(biāo)為兩種的醫(yī)療診斷問題，結(jié)果通?？煞譃橐韵滤姆N：患者本身沒病但被診斷為有?。‵alse Positive，F(xiàn)P）;患者本身有病但被診斷為沒病（False Negative，F(xiàn)P）;患者有病且被診斷為有?。═rue Positive，TP）;患者沒病且被診斷為沒?。═rue Negative，TN）。本文選用醫(yī)學(xué)中最常用的三個指標(biāo)作為模型評估的依據(jù)。它們是：特異性（Specificity）、靈敏度（Sensitivity）和準(zhǔn)確性（Accuracy）。其可通過如下的公式計算得出。

2.4? 結(jié)果及分析

考慮到一次實驗可能存在著偶然性，本文將每組實驗重復(fù)50次，之后取各個評估指標(biāo)的平均值作為最終的結(jié)果。需要說明的是，實驗中訓(xùn)練集與測試集的比例為4∶1。同時，本文將引入CACC算法的RF記為IRF（Improved Random Forest）。

2.4.1? 模型訓(xùn)練速度

為了測試改進的隨機森林算法的運行效率，本文使用傳統(tǒng)的隨機森林算法建立了模型以與其形成對比。上述兩種算法運行的具體時間如下表所示。

通過上表我們可以看出，IRF在三個數(shù)據(jù)集上的表現(xiàn)均要優(yōu)于RF。其中運行時間縮短幅度最大可以達到24.48%;平均的縮減幅度可以達到12.11%。這說明IRF的運行效率相較于RF得到了提升，而隨著數(shù)據(jù)集規(guī)模的增大，前者的優(yōu)勢也將得到擴大。

2.4.2? 模型預(yù)測精度

為了檢測CACC對IRF算法性能所造成的影響，實驗使用RF與IRF構(gòu)建了分類模型，之后將三個數(shù)據(jù)集分別代入其中完成了模型的訓(xùn)練與預(yù)測。RF和IRF模型的診斷結(jié)果如表4、表5所示。

從表4、表5可以看出，相較于RF模型，IRF模型的預(yù)測準(zhǔn)確性在糖尿病樣本集上保持穩(wěn)定，而在另兩個數(shù)據(jù)集上均略有提升。同時特異性和靈敏度也均穩(wěn)步提升。這一結(jié)果與引入的連續(xù)特征離散化的方法是密切相關(guān)的。CACC算法對相依系數(shù)的概念進行拓展^[16]，從而使得生成的規(guī)則更加符合樣本間的內(nèi)在聯(lián)系。這與預(yù)期的結(jié)果是相符的。

3? 結(jié)束語

本文從連續(xù)變量離散化入手，對隨機森林算法進行了改進。通過實驗證明，改進的隨機森林算法在運行時間上顯著縮短，且預(yù)測精度也有所提升。更進一步的，連續(xù)特征離散化后變得更加簡潔明了，這無疑可以方便研究人員的理解?？v使IRF相較于RF展現(xiàn)出了一定的優(yōu)越性，但仍存在著很大的改進空間。本文提出的算法僅是針對處理連續(xù)特征的方法進行了優(yōu)化，如若對特殊的數(shù)據(jù)集采取相應(yīng)的預(yù)處理，抑或?qū)?jié)點的分裂算法進行改進，想必都可以使算法的性能得到提升。當(dāng)下知識更新迅速，新的技術(shù)與算法層出不窮，只有不斷地學(xué)習(xí)，完善自身才是正道。

參考文獻

1. Larasati A， DeYong C， Slevitch L. The Application of Neural Network and Logistics Regression Models on Predicting Customer Satisfaction in a Student-Operated Restaurant[J]. Procedia-Social and Behavioral Sciences， 2012， （65）： 94-99.

2. Nath A， Sahu G K. Exploiting ensemble learning to improve prediction of phospholipidosis inducing potential[J]. Journal of Theoretical Biology， 2019， （479）： 37-47.

3. 張春霞，郭高. Out-of-bag樣本的應(yīng)用研究[J]. 軟件， 2011， 32（3）： 1-4.

4. Pooja S B， Balan S R V， Anisha M， et al. Techniques Tanimoto correlated feature selection system and hybridization of clustering and boosting ensemble classification of remote se?n?sed big data for weather forecasting[J]. Computer Commun?i?c?ations， 2020， （151）： 266-274.

5. 李昆明， 厲文婕. 基于利用BP神經(jīng)網(wǎng)絡(luò)進行Stacking模型融合算法的電力非節(jié)假日負荷預(yù)測研究[J]. 軟件， 2019， 40（9）： 176-181.

6. 張洋. 一種基于Logicboost的軟件缺陷預(yù)測方法[J]. 軟件， 2019， 40（8）： 79-83.

7. Tao Hongfei， Chen Ran， Xuan Jianping， et al. Prioritization analysis and compensation of geometric errors for ultra-? pre?cision lathe based on the random forest methodology[J]. Precision Engineering， 2020， （61）： 23-40.

8. 全雪峰. 基于奇異熵和隨機森林的人臉識別[J]. 軟件， 2016， 37（2）： 35-38.

9. Gupta D， Pierdzioch C， Vivian A J， et al. The predictive value of inequality measures for stock returns： An analysis of long- span UK data using quantile random[J]. Finance Research Letters， 2019， （29）： 315-322.

10. 張雨琦， 林勇. 基于機器學(xué)習(xí)的腫瘤免疫治療應(yīng)答預(yù)測研究[J]. 軟件， 2019， 40（1）： 97-102.

11. 全雪峰. 基于隨機森林的乳腺癌計算機輔助診斷[J]. 軟件， 2017， 38（3）： 57-59.

12. Fratello M， Tagliaferri R. Decision Trees and Random For?ests[J]. Encyclopedia of Bioinformatics and Computational Biology， 2019， （1）： 374-383.

13. Akhoondzadeh M. Decision Tree， Bagging and Random For?est methods detect TEC seismo-ionospheric anomalies around the time of the Chile， （Mw=8.8） earthquake of 27 February 2010[J]. Advances in Space Research， 2016， 57（12）： 374-383.

14. Breiman L. Random Forests[J]. Machine Learning， 2001， 45（1）： 44-51.

15. 沈?qū)W華， 周志華， 吳建鑫， 等. Boosting和Bagging綜述[J]. 計算機工程與應(yīng)用， 2000， 36（12）： 31-32， 40.

16. Tsai C J， Lee C I， Yang Weipang. A discretization algorithm based on Class-Attribute Contingency Coefficient[J]. Neuro?biology of Aging， 2008， 178（3）： 180-191.

17. Cormen T H， Leiserson C E， Rivest R L， et al. Introduction to Algorithms[M]. Beijing： China Machine Press， 2012： 16-19， 242-244 （in Chinese）.

18. 方匡南， 吳見彬， 朱建平， 等. 隨機森林方法研究綜述[J]. 統(tǒng)計與信息論壇， 2011， 26（3）： 32-38.