浙江工業(yè)職業(yè)技術(shù)學院 張 敏

?

一種改進的組合優(yōu)化決策樹算法研究

浙江工業(yè)職業(yè)技術(shù)學院 張 敏

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

【關鍵詞】組合優(yōu)化；決策樹；度量；熵

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

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

1　經(jīng)典決策樹算法簡述

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

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

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

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

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

亦期望熵表示為：

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

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

2　改進的組合優(yōu)化決策樹模型

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

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

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

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

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

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

3　實驗研究與分析

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

表1　預測準確率及葉子數(shù)比較

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

4　結(jié)論

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

參考文獻

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

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

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

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

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

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