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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

亦期望熵表示為：

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

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

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

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

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

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

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

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

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

3　實驗研究與分析

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

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

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

4　結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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