C4.5決策樹算法在醫(yī)療數(shù)據(jù)分類中的應(yīng)用研究

郭星晨，王青青，王 亞

（阜陽師范大學(xué)計算機與信息工程學(xué)院，安徽阜陽 236037）

分類算法旨在一群已知標(biāo)簽的數(shù)據(jù)樣本中訓(xùn)練出一種分類模型，發(fā)現(xiàn)數(shù)據(jù)之間的規(guī)則與聯(lián)系，區(qū)分?jǐn)?shù)據(jù)類別并進一步預(yù)測數(shù)據(jù)的未來發(fā)展。目前，常見的分類算法有決策樹算法、Logistics回歸算法和支持向量機算法等[1-3]，這些分類算法已廣泛應(yīng)用于互聯(lián)網(wǎng)、醫(yī)療、金融等行業(yè)[4-9]。在醫(yī)療行業(yè)里，利用決策樹算法建立模型，分析病案數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則以及疾病指標(biāo)的變化規(guī)律，能夠為醫(yī)生提供極具價值的信息，加速醫(yī)生診斷過程的同時，還能夠幫助醫(yī)生提高決策診斷的準(zhǔn)確率，優(yōu)化傳統(tǒng)的醫(yī)療方案，進一步推動智能醫(yī)療的發(fā)展。與其他常規(guī)分類算法相比，決策樹算法具有易于理解、計算復(fù)雜度較低、訓(xùn)練速度快、決策結(jié)果可視化等優(yōu)點，適用于多種數(shù)據(jù)樣本的分類。本文使用C4.5決策樹算法對乳腺癌臨床數(shù)據(jù)集進行實驗，并對部分?jǐn)?shù)據(jù)進行預(yù)測，以輔助醫(yī)療判斷。

1 決策樹相關(guān)理論

決策樹算法包含結(jié)點劃分屬性的選擇、樹的構(gòu)建、樹的剪枝3個階段。在屬性的選擇上，主要以信息增益（Information Gain）[10]、信息增益比（Gain Ratio）[11]和基尼指數(shù)（Gini Index）[12]作為選取標(biāo)準(zhǔn)。

假設(shè)當(dāng)前樣本集合為O，信息熵（Information Entropy）用于度量數(shù)據(jù)樣本中信息混亂的程度[13]，即O的純度，公式為

其中，p(xi)表示O中第i類樣本xi所占的比例（i=1,2,3,…,m）。E(O)越小，樣本集合O的純度越高。

樣本特征在其中一個屬性c上有N個可能取值，每個可能取值對應(yīng)了樣本集合中的一小群樣本Ok，k∈{1,2,3,…,N}，計算出Ok的信息熵E(Ok)，則該屬性c的信息增益可表示為

在信息增益的基礎(chǔ)上增加一項屬性c的“固定值”，由屬性c產(chǎn)生的分支結(jié)點N數(shù)目越多，該固定值就越大。屬性c的信息增益比可表示為

另一種度量數(shù)據(jù)樣本純度的指標(biāo)是基尼值，可以用單位1與每一類數(shù)據(jù)樣本概率平方和的差值表示。基尼指數(shù)是樣本集合中某一屬性各個可能取值的基尼值加權(quán)求和的結(jié)果，是用于度量一個屬性區(qū)分?jǐn)?shù)據(jù)樣本的能力，即在使用該屬性劃分?jǐn)?shù)據(jù)樣本后所獲得的純度提升。

在決策樹的構(gòu)建過程中，由于屬性的選擇依據(jù)不同，所以產(chǎn)生了ID3、C4.5和CART這三種算法，它們的特點如表1所示。

表1 ID3、C4.5和CART算法特點比較

在屬性選擇的過程中，與ID3算法不同的是，C4.5算法在最優(yōu)劃分屬性的選擇方式上，避免了選擇取值數(shù)目較多屬性的偏向，不易造成過擬合。與CART算法相比，C4.5算法所生成的決策樹規(guī)則更易被解釋，且規(guī)模相對較小。醫(yī)療數(shù)據(jù)中有關(guān)乳腺癌的數(shù)據(jù)集其屬性取值為類別較多的連續(xù)型數(shù)據(jù)，為了避免模型的過擬合，選擇C4.5算法來生成決策樹。

2 C4.5決策樹算法建樹過程

決策樹算法的核心階段是建樹過程。給定一個數(shù)據(jù)集，其所有屬性的集合用A表示，所有特征的集合用D表示，對于C4.5算法，其建樹過程如下所示。

輸入：屬性集A和特征集D。

步驟：（1）若所有數(shù)據(jù)樣本均為同一類，則直接選擇該類生成葉結(jié)點，返回一棵單結(jié)點決策樹；（2）若屬性集A為空，則直接選擇特征集D中占比最多的類作為標(biāo)記生成葉結(jié)點，返回一棵單結(jié)點決策樹；（3）若不滿足步驟（1）和（2），則將信息增益比最大的屬性作為樣本的劃分屬性；（4）將步驟（3）中所得屬性作為結(jié)點并由此生成分支結(jié)點劃分?jǐn)?shù)據(jù)；（5）在新的分支結(jié)點上的非空子集中重復(fù)步驟（1）～（4）；（6）直至每個結(jié)點的待分類樣本不可劃分，返回一棵分類決策樹。

輸出：一棵分類決策樹。

C4.5算法在建樹的過程中，排除步驟（1）的特殊情況，對特征集D中所有特征值取值進行判斷，若針對屬性集A中的多個屬性分別有多個取值，則開始選擇劃分最優(yōu)屬性，根據(jù)樣本數(shù)據(jù)在該最優(yōu)屬性上取值的不同劃分子結(jié)點。當(dāng)前結(jié)點劃分?jǐn)?shù)據(jù)完畢后，去除數(shù)據(jù)集中上一步已經(jīng)劃分過的特征，生成數(shù)據(jù)子集，繼續(xù)新一輪劃分，直至數(shù)據(jù)集不可分時，決策樹停止生長，最終返回一棵完整的分類決策樹。

3 實驗過程及分析

對數(shù)據(jù)集進行預(yù)處理，使用決策樹模型對預(yù)處理后的數(shù)據(jù)集中的訓(xùn)練集進行分類，對分類結(jié)果進行度量，計算決策樹算法的分類準(zhǔn)確率，以便與其他分類算法進行比較。以訓(xùn)練好的模型對測試集進行預(yù)測，輸出預(yù)測結(jié)果。實驗步驟按以下順序進行：數(shù)據(jù)預(yù)處理，使用決策樹算法對訓(xùn)練集進行分類，使用訓(xùn)練好的決策樹模型對測試集進行預(yù)測，輸出預(yù)測結(jié)果。

3.1 數(shù)據(jù)集及其預(yù)處理

本文的實驗是基于醫(yī)療領(lǐng)域中的乳腺癌數(shù)據(jù)集進行的，該數(shù)據(jù)集來自biendata competition中的競賽項目Breast Cancer Detection，數(shù)據(jù)集中的數(shù)據(jù)來自某醫(yī)院患者的乳腺癌數(shù)據(jù)，共有287條病歷數(shù)據(jù)，包含Id、Age、HER2、P53、molecular_subtype共6個屬性。Id是患者編號，為標(biāo)識患者的唯一屬性；Age是患者年齡；HER2是人體內(nèi)重要的乳腺癌判斷指標(biāo)，分別用0、1、2、3標(biāo)識，代表4種不同的基因高度表達程度；P53是人體內(nèi)的一種抑癌基因，用TRUE、FALSE表示，代表已突變和未突變；molecular_subtype表示最終乳腺癌的分子亞型，分為Luminal-A 型、Luminal-B 型、HER2-Enriched 型和Triple Negative 型4 種病理亞型，分別用1、2、3、4表示。

數(shù)據(jù)集中的Age和HER2屬性均為連續(xù)型數(shù)據(jù)，不能直接根據(jù)該連續(xù)屬性的取值對結(jié)點進行劃分，需先對其進行離散處理，并使用處理后的屬性值對結(jié)點進行劃分。在C4.5決策樹算法中，通常采用二分法對連續(xù)型數(shù)據(jù)進行處理。對于Age屬性，將該屬性的所有取值從小到大依次排序，兩個相鄰的年齡取其平均值作為該特征的第一個離散值，多次執(zhí)行上述步驟直到所有的Age值都離散化為止，最終Age屬性中有55個離散值。對于HER2屬性，其取值為0、1、2、3，從小到大排序后，可以轉(zhuǎn)化為3個離散值，分別為：HER2 ≤0.5、HER2 ≤1.5 以及HER2 ≤2.5。對于P53 屬性，其雖為離散屬性，但是為了使分類效果更好，分別以0代替FALSE，用1代替TRUE，兩者按照二分法將P53屬性的取值轉(zhuǎn)化為P53 ≤0.5。

3.2 實驗方法

在訓(xùn)練決策樹模型時，若不對決策樹進行剪枝操作，則預(yù)測準(zhǔn)確率較低。樹的剪枝是為了修剪掉決策樹中不可靠的分支，防止算法的過度擬合。C4.5決策樹算法所采用的剪枝策略是后剪枝法中的悲觀剪枝法，先依據(jù)訓(xùn)練集生成一棵完整的決策樹，再把決策樹上的每一個結(jié)點都當(dāng)作剪枝候選對象，在判斷是否對結(jié)點進行剪枝時，先將以此結(jié)點作為根節(jié)點的子樹刪除，讓其成為葉子結(jié)點，賦給該葉子結(jié)點所覆蓋樣本中占比最多的類，再判斷剪枝后葉結(jié)點的誤判率期望是否在剪枝前葉結(jié)點誤判率期望的標(biāo)準(zhǔn)差內(nèi)，以決定該結(jié)點是否要進行剪枝操作。依次對每一個結(jié)點重復(fù)判斷后則剪枝完成。經(jīng)過剪枝后的分類準(zhǔn)確率比未經(jīng)剪枝處理的稍低一些，但有效避免了模型的過擬合，提高了模型的預(yù)測準(zhǔn)確率。

3.3 實驗結(jié)果分析

實驗使用乳腺癌數(shù)據(jù)集，以C4.5決策樹建立分類模型，分別與Logistics回歸和支持向量機算法進行比較。為了提高分類準(zhǔn)確率，將數(shù)據(jù)集分別按照8∶2、7∶3和6∶4的比例劃分為訓(xùn)練集、測試集。對每個訓(xùn)練集進行實驗后，最終發(fā)現(xiàn)按照7∶3的比例進行劃分的數(shù)據(jù)集可以使決策樹模型達到最優(yōu)分類效果。采用7∶3的比例劃分之后，訓(xùn)練集有200條病歷數(shù)據(jù)，測試集有87條病歷數(shù)據(jù)。對于上述3種分類模型進行訓(xùn)練并分類預(yù)測，分類準(zhǔn)確率以及對測試集中預(yù)測正確的個數(shù)如表2所示。

表2 3種分類模型分類準(zhǔn)確率及預(yù)測正確個數(shù)

由表2可以看出，C4.5決策樹算法對乳腺癌數(shù)據(jù)集的分類準(zhǔn)確率最高，分類效果最好，并且對測試集中的87條病歷數(shù)據(jù)，C4.5決策樹算法的預(yù)測正確個數(shù)高達55個，高于Logistics回歸算法以及支持向量機算法。使用決策樹算法對數(shù)據(jù)集進行分類的部分可視化結(jié)果如圖1所示。

圖1 C4.5決策樹分類可視化結(jié)果

對于圖1中的可視化結(jié)果，以根結(jié)點為例來說明：

（1）根結(jié)點中的第1行HER2 ≤0.5代表第一個分類指標(biāo)，其為信息增益比最大的屬性，則基于滿足該屬性條件的TRUE和不滿足屬性條件的FALSE分別生成左右兩個子結(jié)點，其中左結(jié)點中包含81條病歷數(shù)據(jù)，右結(jié)點包含119條病歷數(shù)據(jù)；

（2）根結(jié)點中的第2行entropy代表該屬性信息熵；

（3）根結(jié)點中的第3行sample代表該訓(xùn)練集中包含200條病歷數(shù)據(jù)；

（4）根結(jié)點中的第4 行Value 代表在這200 條病歷數(shù)據(jù)中最終4 類亞型分子的個數(shù)，可以看出，其中最終結(jié)果為1型亞型分子的有51條，為2型亞型分子的有84條，為3型亞型分子的有39條，為4型亞型分子的有26條。

由根結(jié)點中第1 行判斷條件所劃分生成的左結(jié)點中共有81 條病歷數(shù)據(jù)，右結(jié)點包含119 條病歷數(shù)據(jù)。首先，對于左結(jié)點中的81條病歷數(shù)據(jù)來說，計算出各個屬性中信息增益比最大的屬性為age ≤80.0，則該81條病歷數(shù)據(jù)基于滿足該條件的TRUE和不滿足屬性條件的FALSE再次被劃分到左右兩個子結(jié)點中。其次，對于右結(jié)點中的119 條病歷數(shù)據(jù)來說，計算出各個屬性中信息增益比最大的屬性為age ≤31.0，則該119條病歷數(shù)據(jù)基于滿足條件的TRUE和不滿足屬性條件的FALSE也再次被劃分到左右兩個子結(jié)點中。新的結(jié)點依次經(jīng)過這樣的流程不斷被劃分，直至所有的子結(jié)點均為葉子結(jié)點，數(shù)據(jù)集被劃分完畢，即可得到最終完整的決策樹。拿任意一個葉子結(jié)點來說，Value的4個值分別代表著4類最終亞型分子標(biāo)簽的數(shù)量分布。

4 總結(jié)

本文介紹了C4.5決策樹算法的相關(guān)理論、分析了建樹具體流程、建立了該算法的分類模型。在乳腺癌臨床數(shù)據(jù)集上，驗證了分類模型的準(zhǔn)確率，并依據(jù)該模型對部分?jǐn)?shù)據(jù)進行了預(yù)測。實驗結(jié)果表明，相比于其他分類模型，該模型的分類準(zhǔn)確率較高，可達0.66，并且分類結(jié)果可以可視化。因此，決策樹算法在醫(yī)療行業(yè)及相關(guān)領(lǐng)域的數(shù)據(jù)分類和預(yù)測方面具有較好的輔助作用。