C4.5決策樹算法在醫療數據分類中的應用研究

郭星晨，王青青，王 亞

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

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

1 決策樹相關理論

決策樹算法包含結點劃分屬性的選擇、樹的構建、樹的剪枝3個階段。在屬性的選擇上，主要以信息增益（Information Gain）[10]、信息增益比（Gain Ratio）[11]和基尼指數（Gini Index）[12]作為選取標準。

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

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

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

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

另一種度量數據樣本純度的指標是基尼值，可以用單位1與每一類數據樣本概率平方和的差值表示。基尼指數是樣本集合中某一屬性各個可能取值的基尼值加權求和的結果，是用于度量一個屬性區分數據樣本的能力，即在使用該屬性劃分數據樣本后所獲得的純度提升。

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

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

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

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

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

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

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

輸出：一棵分類決策樹。

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

3 實驗過程及分析

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

3.1 數據集及其預處理

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

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

3.2 實驗方法

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

3.3 實驗結果分析

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

表2 3種分類模型分類準確率及預測正確個數

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

圖1 C4.5決策樹分類可視化結果

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

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

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

（3）根結點中的第3行sample代表該訓練集中包含200條病歷數據；

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

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

4 總結

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