一種改進的組合優化決策樹算法研究

浙江工業職業技術學院 張 敏

?

一種改進的組合優化決策樹算法研究

浙江工業職業技術學院 張 敏

【摘要】本文主要基于經典的決策樹算法，引入信息熵的概念，在屬性的選取和分支策略上進行改進，對每個屬性下的樣本集，計算熵和平均值，將大于均值的樣本合并，形成新的樣本子集，最后通過實驗驗證改進后的算法在屬性選擇度量的可解釋性，減少空支，過度擬合等方面有顯著的提高。

【關鍵詞】組合優化；決策樹；度量；熵

作為分類和預測的主要技術之一的決策樹（Decision Tree），致力于從大量無序的海量數據中建立分類模型，抽象出規則集，算法采用由上而下的遞歸方法，構造出決策樹。在決策樹內部節點根據屬性值不同判斷分支路徑，最終在葉節點得到結論，形成從根節點到葉節點的完整規則，整棵樹的規則集合形成一套分類體系。

近年來，決策樹分類方法在人工智能、機器學習等領域得到廣泛應用。國內外研究人員先后提出十幾種不同的決策樹分類方法，針對不同的分類問題給出了解決方法，但并未形成統一的決策樹構建方案，不同算法在一定程度上都存在不足。

1　經典決策樹算法簡述

ID3（Iterative Dichotomizer 3）是一種經典的決策樹算法，該算法從根節點開始，賦予根節點最優選擇的屬性，然后根據屬性取值生成不同分支，對各分支又生成新的節點。屬性選擇標準上，ID3采用基于信息熵的信息增益來進行取舍。

設S是具有n個樣本的數據集，將樣本集劃分為k個不同的類Ci(i=1,2,…k)，每個類Ci含有ni個樣本，把S分成k個不同類的信息熵為：

公式中Pi是樣本集S中歸屬于第i類Ci的可能性，即：

假設屬性A的各不同值的集合組成為XA，Sv為樣本S中所有屬性為v形成的子集，可表示為：

在分支路徑選擇上，計算出樣本子集Sv的信息熵為E(Sv)，平均加權期望熵可定義成各子集Sv的加權和，權值是Sv樣本集在原有集合S中的比例值：

亦期望熵表示為：

其中，E(Sv)是把Sv劃分為k個不同類的信息熵。屬性值A較原樣本集S的信息增益可表達為：

由于ID3算法局限于屬性只能取離散值，J.R.Quinlan給出了ID3擴展算法，即C4.5算法，使決策樹分類算法可應用于連續屬性值。

2　改進的組合優化決策樹模型

經典的C4.5模型雖然得到廣泛的應用，但一直存在可解釋性低、空枝、無意義分支及過度擬合的問題。考慮到在構造決策樹過程中關鍵點在于節點屬性的選取，針對C4.5算法存在的問題，改進屬性選擇標準，在確保C4.5決策樹算法準確性的前提下，進一步提高算法效率。改進算法的基本思路如下：

（1）對各屬性（考慮離散值的情形），計算屬性值的樣本子集的熵。

（2）計算各樣本子集信息熵均值，對大于平均閾值的子集進行合并，組成臨時復合子集，同時計算出該子集的信息熵。

（3）參考臨時復合樣本子集信息熵及未合并集合的熵值計算當前節點的信息增益值。

（4）在所有計算出的信息增益值中選擇最大值的屬性作為當前節點的屬性，未合并子集及臨時子集形成其分支。

優化后的分類算法根據熵值進行分支合并，熵值越大，分類精度越高。對熵值越小的分類也進行合并，有效減少無意義分支，同時把對劃分根本不起參考作用的分支歸并，有效避免形成多值屬性問題。

3　實驗研究與分析

為了驗證改進后算法的性能，實驗中選取經典的UCI數據測試集，選取其中8個不同數據集進行，分別采用C4.5算法及改進算法進行分類。最后產生的決策樹使用10-cross-validation方法檢驗分類劃分的準確度，實驗過程中參數選擇weka默認值，最終結果如表1所示。

表1　預測準確率及葉子數比較

從表1實驗得到的結果可以看出，改進算法后的決策樹模型整體預測準確性保持原有水平，其中Soybean、German、Mushroom三個數據體的準確度有一定程度提高。同時我們發現在葉子節點有效降低的情況下，預測準確率是提高的，只有當葉子節點有較大幅度降低時，預測的準確性才開始降低，改進后模型空枝和碎片葉子節點得到大大減少，健壯性較以前有明顯提高。

4　結論

本文在研究經典決策樹算法的基礎上，提出一種改進的決策樹模型，并通過實驗驗證，改進后的算法能有效地減少決策樹的層數，提高決策樹分類效率，降低復雜性。在改進的決策樹模型中考慮如何對連續型屬性進行改進以及如何將缺失數據添加到實驗分析中，將在今后的工作中繼續關注。

參考文獻

[1]陳麗.數據挖掘中聚類算法研究[D].東北:東北大學,2007.

[2]金微.基于遺傳算法的K-means聚類算法研究[D].常州:河海大學,2007.

[3]孫秀娟.基于遺傳算法的K-means聚類算法分析研究[D].山東:山東師范大學,2009.

[4]周明孫,樹棟.遺傳算法原理及應用[M].北京:國防工業出版社.

[5]毛國君,段立娟等.挖掘原理與算法[M].北京:清華大學出版社,2007:30,165-166.

[6]David,Heikki Maxnnaa,Padhraic Smyth.數據挖掘原理[M].北京:機械工業出版社,2003:167．