消除屬性間依賴的C4.5決策樹改進算法

唐耀先　余青松

(華東師范大學計算中心　上海 200062)

0　引　言

近年來，先進的數據存儲技術使人們能快速地搜集和存儲海量的數據信息，促進了數據挖掘技術的飛速發展。分類是數據挖掘中的重要研究方向之一，主要的分類算法有決策樹、貝葉斯、人工神經網絡、K-近鄰、支持向量機等[1]。其中，決策樹以其預測準確率高、穩定性好、直觀易懂等特點得到廣泛應用和研究[2]。應用如文獻[3]利用決策樹進行水質建模測試；文獻[4]利用決策樹處理流量分類問題；文獻[5]利用決策樹探究人體測量。研究上如文獻[6]在1993年提出的C4.5算法解決了連續屬性值的處理問題和多值偏向問題；文獻[7]把線性分類器和決策樹結合在一起減少決策樹的層數提高了決策樹效率；文獻[8]通過控制高維數據噪聲來優化C4.5算法。但上述算法在構造決策樹模型的過程中，選擇分裂屬性時僅僅只是考慮了屬性對類的影響，卻忽視了屬性之間的相互影響。

在數據集的屬性中，并非所有的屬性都包含相同的信息量，有些屬性包含較多會影響分類的信息量，而另外一些屬性包含較少會影響分類的信息量[9]。同樣，在數據集中選擇一個待分裂屬性后，剩下的屬性集中，有的屬性包含較多會影響待分裂屬性取值的信息量，而另外一些屬性包含較少會影響待分裂屬性取值的信息量。例如學生有“年齡”和“年級”兩個屬性，年齡“大小”會影響到學生的年級“高低”，所以這兩個屬性之間有一定的影響，即它們有一定的依賴關系。上述例子只是一個極端的例子，本文認為任何兩個屬性或多或少都具有一定的依賴關系，并且定義這種依賴關系為依賴度，而依賴度會成為選擇分裂屬性的影響因素之一，忽視這種影響因素會對構造決策樹模型產生不良影響。

本文針對上述問題，提出一種消除屬性依賴的C4.5決策樹改進算法，稱之為DTEAT算法。DTEAT算法通過計算屬性間的信息增益率來量化屬性間的依賴度，在構造決策樹的過程中把待分裂屬性與其他屬性間的依賴度均值作為選擇分裂屬性時的主要度量標準之一，從而消除屬性間依賴關系對選擇分裂屬性時產生的影響，以達到提高最終模型分類準確率的目的。

1　C4.5決策樹算法

1.1　決策樹介紹[10]

決策樹是一種類似流程圖的樹結構，其中每個內部節點(非樹葉節點)表示在一個屬性上的測試，每個分支代表一個測試輸出，而每個葉子節點存放一個類標號。一旦建立好了決策樹，對于一組未給定類標號的數據，跟蹤一條由根節點到葉子節點的路徑，該葉子節點就存放著該數據分類的預測。決策樹的優勢在于不需要任何領域知識或參數設置，適合于探測性的知識發現。圖1就是一棵典型的C4.5算法對數據集產生的決策樹。

圖1　決策樹模型圖

1.2　C4.5決策樹生成

設有數據集D，|D|為D的樣本總數。設類別C有m個不同的取值{C1,C2,…,Ci,…,Cm}，|Ci|為D中屬于類Ci的樣本總數。設有n個不同的屬性{Aj1,Aj2,…,Ajk,…,Ajt}，屬性Aj有t個不同的取值{aj1,aj2,…,ajk,…,ajt}，|Djk|為D中屬性Aj取值為ajk的子集Djk的樣本總數，|Dijk|為在Djk中屬于類Ci的樣本總數。

一個數據集本身有很多屬性，我們需要考慮屬性進行判斷的順序，ID3算法引進了信息增益來量化屬性對類別的影響程度，并將信息增益作為屬性選擇的度量標準[11]。在給定Aj的條件下，C在D中的信息增益計算公式為：

Gain(C,D|Aj)=Info(C,D)-Info(C,D|Aj)

(1)

式中：Info(C,D)為C在D中的信息熵，Info(C,D|Aj)為給定屬性Aj的條件下，C在D中的信息熵：

(2)

(3)

則信息增益最終的計算公式為：

(4)

C4.5使用信息增益率來量化屬性對類別的影響程度，并將信息增益率作為屬性選擇的度量標準，計算公式為：

(5)

式中：Info(Aj,D)為屬性Aj在D中的信息熵：

(6)

2　DTEAT算法

2.1　最優屬性選擇

屬性選擇使用BFS(Best First Search)算法對屬性集進行搜索，在搜索的過程中使用CFS(Correlation-base Feature Selector)算法對屬性進行評估選擇。

BFS是寬度優先搜索的擴展，基本思想是將節點表按據目標的距離進行排序，再以節點的估計距離為標準選擇待擴展的節點[12]。在搜索的過程中使用CFS評估算法，評估從初始節點到達目的節點的最佳路徑代價。

CFS評估算法評估每個屬性的預測能力以及相互之間的依賴度，傾向于選擇與類別依賴度高，但是相互之間依賴度低的屬性。

通過屬性選擇，先剔除掉與類別依賴度低或者相互之間依賴度高的屬性，提高算法的效率，并且完成一次屬性依賴的消除。

2.2　DTEAT的改進思想

信息增益率表示的是在給定一個屬性條件下，類不確定性相對于沒有屬性限定條件時的減少量，即類對該屬性的依賴度。同理在給定屬性Ax的條件下，另一個屬性Aj在D中的信息增益率即可表示屬性Aj對屬性Ax依賴度。

根據式(5)，屬性Aj對屬性Ax依賴度公式為：

(7)

則屬性Ax與其他所有屬性的平均依賴度公式為：

(8)

式中：E為不包含Aj的屬性子集，|E|為集合E的屬性總數。

在選擇分裂屬性的時候不僅要考慮該屬性給類帶來最大的信息增益率，也必須考慮該屬性和其他屬性有最小的信息增益率，即該屬性與其他屬性有最小的平均依賴度。本文提出新的選擇分裂屬性的信息增益率公式：

(9)

2.3　DTEAT的算法流程

假設D代表當前樣本集，當前候選屬性集用A表示，則DTEAT算法見算法1。

算法1使用訓練數據集構建決策樹

輸入：訓練樣本D；候選屬性的集合A。

輸出：一棵決策樹T。

步驟1創建節點N。

步驟2如果D中的所有實例都屬于同一類別Ci，則將N標記為Ci類葉節點，構建T為只包含N的單節點樹，返回決策樹T。

步驟3如果A為空，或者D中所有實例在A上取值相同，則將N標記葉節點，其類別標記D中實例數最大的類，置T為只包含N的單節點樹，返回決策樹T。

步驟4對于A中的每一個屬性，利用式(9)計算屬性對類產生的信息增益率GainRatioNew(C,D|Aj)，選擇具有最高信息增益率的屬性Aj作為節點N的待分裂屬性。

步驟5如果待分裂屬性Aj為連續型，則找到Aj的分割閾值。

步驟6對于屬性Aj的每一個屬性值ajk，從節點N生成對應的子節點，并從D中劃分出對應的子集Dk。如果Dk非空，構建子節點Nk，將其標記為Dk中實例數最大的類別，由節點及其子節點構建決策樹T，返回T。

步驟7對節點Nk,以Dk作為訓練集，A-Aj為特征集，遞歸調用步驟1-步驟6，得到子樹Tk,返回Tk。

步驟8對T進行剪枝處理。

3　實驗結果及分析

3.1　實驗環境及數據集介紹

實驗使用Weka分類平臺和UCI數據集。Weka是新西蘭大學提出的基于Java的開源開發平臺，集合了包括數據預處理、分類、回歸、聚類、關聯規則等大量的機器學習算法，并實現了交互式界面上的可視化[13]。UCI是加州大學歐文分校提出的用于機器學習的數據庫，種類涉及生活、工程、科學各個領域。它已被學生、教育工作者和其他研究機器學習的研究者作為數據來源廣泛使用。本文的實驗環境如表1所示。

表1　實驗環境

本文使用UCI官方提供的Audiology、Heart-c、heart-h、Labor、Soybean、Splice、Vehicle等7組數據集進行實驗，各個數據的樣本總數和屬性總數如表2所示。

表2　數據集樣本數和屬性總數

3.2　實驗結果及分析

實驗一：對上述7組數據集進行屬性選擇。首先使用BFS算法進行屬性搜索，然后使用CFS算法進行屬性評估，選擇最優的訓練屬性集。各組數據集剩余的最優屬性總數如表3所示。屬性選擇是直接剔除掉一部分與類別依賴度低，但是相互之間依賴度高的屬性，而剩下的屬性之間依舊會有一定依賴度，因此在分類算法中消除屬性間依賴度的影響還是很有必要。

表3　屬性選擇之后的數據集

實驗二：數據集Labor具有57個樣本，屬性選擇后具有7個最優屬性，是一個二分類的經典數據集，只包含good和bad兩種類別。本實驗分別使用C4.5算法和DTEAT算法對屬性選擇后的該數據集進行分類，通過設置不同的閾值得到真正例率TP Rate和假正例率FP Rate，分別繪制C4.5和DTEAT兩種分類模型的ROC平滑曲線圖，如圖2所示。

圖2　ROC曲線圖

ROC曲線即接受者操作特征曲線，表明了假正例率與真正例率之間的關系。ROC曲線可以用來判斷分類方法的性能，ROC曲線下方包圍的面積(AUC)越大，分類效果越好。本次實驗計算出利用C4.5算法模型進行分類時，AUC的值為0.733 1，而利用DTEAT算法模型進行分類，AUC的值為0.812 9。DTEAT算法模型的AUC值明顯大于C4.5算法模型的AUC值，由此可知DTEAT算法的分類效果比C4.5算法的分類效果好。

實驗三：分別使用傳統C4.5決策樹算法和消除屬性依賴的DTEAT算法在進行屬性選擇后的7組數據集上進行分類實驗，然后通過十字交叉驗證法計算分類準確率，最后對比兩種算法的分類準確率，如表4所示。

表4　C4.5算法改進前后的準確率　　　%

兩種算法在7組數據集上的分類準確率對比如圖3所示。

圖3　C4.5算法改進前后準確率對比

根據圖3的實驗結果，可以看出DTEAT算法相對于C4.5算法準確率有了明顯的提升，準確率最高提升了7.15個百分點，最少也提升了3.02個百分點，平均提升了4.43個百分點，即使是對于原算法準確率高達94.49%的數據集Splice仍然有3個百分點的提升。由此可知DTEAT算法通過計算屬性間的信息增益率來量化屬性間的依賴度。在構造決策樹的過程中把待分裂屬性與其他屬性間的依賴度均值作為選擇分裂屬性時的主要度量標準之一。將屬性間依賴關系對選擇

分裂屬性時產生的影響進行消除之后，有效地提升了分類的準確率。

4　結　語

本文是基于C4.5算法在選擇分裂屬性時忽視屬性間的相互影響這一不足，提出了消除屬性依賴的DTEAT算法。在構造決策樹的過程中，通過計算待分裂屬性與其他屬性間的信息增益率量化屬性間的依賴度，并且將屬性間依賴度均值作為選擇分裂屬性時的主要度量標準之一。在Weka實驗平臺上對7組UCI官方數據集進行了實驗，實驗表明DTEAT算法在消除屬性依賴后的分類準確率有了明顯提升，即DTEAT算法減少了屬性間依賴對分裂屬性的選擇產生的影響，從而提高了最終的分類準確率。目前，本文提出的消除屬性依賴的改進算法每一次選擇分裂屬性時，都要多計算一次屬性間的增益率，算法效率有所降低。如何在消除屬性依賴提高分類準確率的同時兼顧算法的效率是需要進一步研究的問題。

[1] 周美琴.單位代價收益敏感決策樹分類算法及其剪枝算法的研究[D].桂林:廣西師范大學,2016.

[2] 姚亞夫,邢留濤.決策樹C4.5連續屬性分割閾值算法改進及其應用[J].中南大學學報(自然科學版),2011,42(12):3772-3776.

[3] Everaert G,Bennetsen E,Goethals P L M.An applicability index for reliable and applicable decision trees in water quality modelling[J].Ecological Informatics,2016,32:1-6.

[4] 徐鵬,林森.基于C4.5決策樹的流量分類方法[J].軟件學報,2009,20(10):2692-2704.

[5] Savall F,Faruch-Bilfeld M,Dedouit F,et al.Metric sex determination of the human coxal bone on a virtual sample using decision trees[J].Journal of Forensic Sciences,2015,60(6):1395-1400.

[6] Quinlan J R.C4.5:programs for machine learning[M].Morgan Kaufmann Publishers Inc.1993.

[7] 馮少榮.決策樹算法的研究與改進[J].廈門大學學報(自然版),2007,46(4):496-500.

[8] 王偉,李磊,張志鴻.具有容噪特性的C4.5算法改進[J].計算機科學,2015,42(12):268-271.

[9] 王培,金聰,葛賀賀.面向軟件缺陷預測的互信息屬性選擇方法[J].計算機應用,2012,32(6):1738-1740.

[10] 王凱華,蔣逸恒,李迪.基于WEKA平臺的C4.5基因分類方法[J].信息化建設,2016(5):30-32.

[11] 董躍華,劉力.結合矯正函數的決策樹優化算法[J].計算機應用與軟件,2016,33(1):300-306.

[12] 楊青松.爬蟲技術在互聯網領域的應用探索[J].電腦知識與技術:學術交流,2016,12(15):62-64.

[13] 劉彩霞,方建軍,劉艷霞,等.Weka平臺上距離指數自動尋優的模糊C-均值聚類算法[J].北京聯合大學學報,2016(4):53-57.