基于C4.5決策樹分類算法的改進與應用

李春生，焦海濤，劉 澎，劉小剛

(東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318)

0 引 言

數據挖掘的過程是根據預警目標選擇合適的數據挖掘算法，利用該數據挖掘算法挖掘出預警目標潛在的特征規律，根據規律特征進行目標預警。

原始數據的純度直接關系到相關數據挖掘技術的選取，也會影響整個數據挖掘的效果。若在挖掘前的數據格式或數據類型差異很大，容易造成數據挖掘結果產生偏差，影響數據挖掘結果的準確率，無法實現科學有效的預警。同樣，如果采用的數據挖掘技術不適用當前的數據特點和預警目標，容易導致算法無法發揮應有的效果，挖掘出的規律也無法用于預警。

數據挖掘算法的確立必須要以大量的歷史數據和目標為依據，針對不同的數據類型和數據特點，采用不同的數據挖掘算法。不同挖掘預警目標需要與不同分析模式進行匹配，不同預警目標需要的規則表達方法也有差異。因此，有必要選擇與預警目的相關的、合適度較高的數據挖掘算法。

決策樹算法是數據挖掘中常用的分類與預測算法之一，其中包括ID3算法、C4.5算法、CART算法三種。文中主要針對C4.5算法，分析傳統C4.5算法存在的缺點，并對其進行改進。

1 決策樹方法的選定與改進

1.1 ID3算法

ID3算法是傳統經典的決策樹算法[1-3]，其在構造決策樹時，各節點代表非類屬性，邊表示此時非類屬性的取值情況。根據信息熵的下降速度進行屬性劃分，按照從根到當前節點進行路徑選擇測試屬性，不以最大信息增益作為條件屬性。ID3算法具有理論清晰易懂、使用價值強等優點，同時也存在多值偏向等問題，其運算過程通常偏重于選擇屬性取值較多的條件屬性作為決策屬性，但在大多數運算情況下，屬性值取值最多的屬性并非是最優屬性，由于在構建決策樹的過程中各個節點僅包含一個特征，也就是單變元算法，屬性間不存在強相關性。也可以看成，最終生成的決策樹連在一起依舊呈現分散現象。

1.2 C4.5算法

C4.5算法是基于ID3基礎上的改進算法[4-7]，在一定程度上彌補了ID3算法的缺陷。C4.5算法具有可處理數據范圍包含連續性數值、數據的自適用性較強、可處理不完整數據、屬性選擇的標準較精確以及建樹完成后具有剪枝操作等優點，可避免決策樹的不完整性，同時也存在生成決策樹時計算效率較慢等缺點，因此最終生成決策樹所表示的知識通?？刹捎肐F-THEN形式的分類規則來表示。

1.3 CART算法

CART算法是在決策樹方法基礎上采用的交叉決策樹算法[8-11]，具體在算法執行的過程中，首先需要選取具有最小基尼系數的屬性，通過對當前決策樹的節點進行分裂，選取的基尼系數越小，則表示目前擁有的訓練樣本集的純度越高，采用決策樹進行分類效果也就越好。CART算法主要是針對高度傾斜和多態的數值數據、有序或無序的類別型屬性數據進行快速處理。該算法存在對每個節點進行多次布爾測試的詬病，按照最終的測試結果進行規則劃分，當判定條件為真時判定為左分支，否則判定為右分支[12-16]。

2 C4.5決策樹算法的改進

文中以C4.5算法思想在經濟犯罪數據中的應用為例進行概述。運用C4.5算法的主要思想是：以訓練數據集S作為樣本集，當樣本集S不斷分裂生成經濟犯罪特征決策樹的同時，通過對各經濟犯罪屬性信息增益率的計算，選取當前數值最大的屬性作為分裂節點。重復按照此標準，可將樣本集S散列成n個樣本子集。若在樣本集分裂過程中，第i個樣本子集Si內包含的元組類別相同時，當前節點可看作此時分裂決策樹的葉子節點，分裂終止。若在決策樹分裂過程中生成不滿足上述條件的經濟犯罪屬性子集Si，則繼續使用上述方法依次遞歸生成決策樹，直到所有經濟犯罪屬性子集包含的元組均屬同一個類別為止。它主要基于以下原理：

定義1：類別信息熵：假設訓練樣本集為S，S中有s個子樣本，將此訓練集劃分為m個類別，第i類的實例個數可看作為Si，Pi為Si/S的概率，INFO(S)為類別信息熵，基于信息熵的計算公式為：

定義2：條件信息熵：假設A作為屬性劃分訓練樣本集S，訓練樣本集S被劃分成k個子集{S1，S2，…，Sk}，即將A的取值分為k個{a1，a2，…，ak}，定義Si中屬于第i類的訓練實例個數為Sij，INFOA(S)為屬性A的條件信息熵，由A劃分成子集的信息熵計算公式如下：

定義3：屬性A的信息增益計算公式為：

Gain(A,S)=INFO(S)-INFOA(S)

定義4：分裂信息熵：設劃分訓練集的屬性A有k個不同的值，則將屬性A樣本集劃分為k個不同的子集。其中，樣本子集Sj包含樣本集S中的部分樣本，ai為它們在屬性A上的值。若以屬性A的值為基準，對樣本集進行分割，則INFO(A)表示屬性A的分裂信息熵，其計算公式為：

定義5：劃分屬性A的信息增益率的計算公式為：

在C4.5算法構建特征決策樹的過程中，選擇適合分裂經濟犯罪特征屬性時，需要計算每個經濟犯罪條件屬性的信息增益率，選定信息增益率最大的條件屬性作為分裂屬性。由于經濟犯罪涉案人特征數據量較大，需要不斷計算屬性的信息增益率，涉及到多次的對數運算，需要頻繁調用庫函數，因此增加了經濟犯罪特征模式挖掘的計算量，容易產生建樹效率過慢的問題。

針對上述問題，文中通過對信息增益率的計算公式進行改進，深入了解數學統計思想的泰勒公式和麥克勞林公式[17]，將二者的公式思想融入到C4.5算法的信息增益率公式計算中，從而實現信息增益率計算速度下降的目的。

由于lnx在x=0時導數無意義，且在信息增益率計算公式中常定義的概率取值范圍為[0,1]，因此，選用ln(x+1)的麥克勞林公式改進傳統C4.5中信息增益率的計算公式，如下所示：

于是有：

通過對以上公式進行近似簡化，完全能夠將對數運算轉換成非對數運算，同時利用上述轉化特點實現消除信息增益率公式中復雜的對數運算，從而達到簡化計算過程、提升建樹效率的目的。

類別信息熵的轉化過程如下：

INFO(S)=

同理，條件信息熵和分裂信息熵的轉化可表示為：

INFO(S)=

INFO(A)=

因此，轉化后的信息增益率計算公式為：

對上述改進后的計算公式分析可得出結論，利用類別信息熵來計算條件屬性信息增益率時每次的時間值相似度較高，由于上述公式在簡化的過程中各部分均可省去-1/ln2S。為了有效地保證算法的分類精度，文中在計算類條件熵時采用改進的計算公式，實現不改變各個條件屬性的信息增益率的排列順序，同時又不影響分類精度。

改進后的C4.5算法與常規C4.5算法通過調用函數來進行大量的對數函數運算的不同之處在于，改進算法只需利用簡單的四則混合運算，便能實現信息增益率計算公式的運算，無需多次對數運算，從而大幅提高了系統的運算速度。因此，簡化后的計算公式以信息熵理論和知識為依據，在一定程度上可保留分類的精準度。

算法的主要步驟如下所示：

輸入：經濟犯罪數據訓練樣本集S，經濟犯罪涉案特征屬性集合list，決策屬性d；

輸出：決策樹。

(1)以經濟犯罪數據訓練樣本集合S作為根節點N，創建特征決策樹；

(2)如果經濟犯罪數據訓練樣本集S中的所有樣本屬于同一類別，則記節點N為葉子節點，并標記為類別C，否則轉入步驟(3)；

(3)如果經濟犯罪涉案特征屬性集合list為空，記節點N為訓練樣本集合S中含樣本數量最多的類C，否則轉入步驟(4)；

(4)計算經濟犯罪涉案特征屬性集合list里每個條件屬性的信息增益率，將具有最大的信息增益率的節點屬性作為當前節點的分割屬性，標記節點N為A；

(5)根據分割屬性的值確定訓練樣本子集，并建立相應的分支；

(6)對劃分出的訓練樣本子集重復步驟(2)～(5)，生成新的經濟犯罪涉案特征決策分支，直到將所有的樣本子集劃分完為止。

算法流程如圖1所示。

3 實驗結果分析

以知識產權類經濟犯罪案件作為預警目標對預警模型進行實例分析。文中采用的是數據庫中的13個知識產權類經濟犯罪數據集來進行數據分析，將各實驗數據集分成兩組，驗證實驗結果。將數據集分成兩類，即訓練樣本集和測試樣本集，將數據中的90%作為訓練樣本，10%作為測試樣本。將改進后的C4.5算法命名為K-C4.5算法，文中在實驗數據相同的情況下，分別對傳統的C4.5算法和改進的K-C4.5算法進行對比分析，驗證了改進后算法的真實有效性。在實驗分析過程中，分別對傳統的C4.5算法和改進后的K-C4.5算法進行準確率和時間的記錄，如表1所示。

圖1 算法流程

表1 算法效率統計

續表1

為了直觀地展示算法實驗結果，采用圖表表示法對部分數據測試結果進行直觀顯示，對比分析原始的C4.5算法和改進后的K-C4.5算法的準確率和執行速度。圖2是傳統的C4.5算法和改進后的K-C4.5算法在分類精度上的對比，圖3傳統的C4.5算法和改進后的K-C4.5算法在運行時間上的對比。

圖2 算法分類精度對比

圖3 算法執行時間對比

根據圖2、圖3的實驗結果分析可得，相對于傳統的C4.5算法，改進后的K-C4.5算法在進行分類時花費時間較少，同時算法時間效率提高沒有影響分類的準確度，準確度與原始的C4.5算法一致性強。通過對實驗結果的分析，驗證了改進后的K-C4.5算法能夠提升算法的執行效率，縮短算法執行時間，同時算法執行效率的提升保證了算法的準確率。

4 結束語

主要介紹了決策樹算法中的C4.5算法的改進方法。在研究和比較了多種常見的決策樹方法的基礎上，分析C4.5算法在執行過程中可能存在的問題，對C4.5算法信息增益率的計算公式進行改進，通過實驗結果進行了對比分析，驗證了算法的準確性和效率性。