決策樹算法分析與改進(jìn)

張永昭　岳晟　劉曉楠

摘 要 ID3、C4.5、CART是三種已經(jīng)研究發(fā)展很多年的經(jīng)典算法，是從事數(shù)據(jù)挖掘研究工作基礎(chǔ)模板。三種決策樹模型應(yīng)用廣泛，原理簡明，各有所長，但缺點同樣明顯。經(jīng)過深入的學(xué)習(xí)研究，團(tuán)隊對三種算法的特點及改進(jìn)進(jìn)行了匯總，為進(jìn)一步的研究做了總結(jié)性分析；并運用分析成果對ID3算法進(jìn)行了改進(jìn)。

關(guān)鍵詞 數(shù)據(jù)挖掘；決策樹算法；特點；改進(jìn)；匯總

引言：

近年來，決策樹方法在機(jī)器學(xué)習(xí)、知識發(fā)現(xiàn)等領(lǐng)域得到了廣泛應(yīng)用。數(shù)據(jù)挖掘作為一種發(fā)現(xiàn)大量數(shù)據(jù)中潛在信息的數(shù)據(jù)分析方法和技術(shù)，已經(jīng)成為各界關(guān)注的熱點。其中，決策樹以其出色的數(shù)據(jù)分析效率、直觀易懂等特點，倍受青睞。構(gòu)造決策樹有多種算法，國際上最早的、具有影響力的決策樹是由Quinlan于1986年提出的ID3算法[1]，是基于信息熵的決策樹分類算法。ID3算法采用信息熵作為屬性選擇標(biāo)準(zhǔn)，可這個標(biāo)準(zhǔn)易偏向于取值較多的候選屬性。

一、ID3算法優(yōu)化

1.改進(jìn)思路

針對ID3算法的缺點④，即信息增益的計算依賴于特征數(shù)目較多的特征，而屬性取值最多的屬性并不一定最優(yōu)，這會導(dǎo)致結(jié)果與實際誤差較大。基于上述對ID3算法改進(jìn)方案的分析，本文提出以下改進(jìn)思路：

（1）提出子屬性信息熵的概念。假設(shè)所有屬性集合為{A1，A2，…，An}，對于屬性Ai有子屬性{Ai1，Ai2， …， Aim}。定義Aij的子屬性信息熵為。

（2）引入屬性優(yōu)先[18]的概念。不同的屬性對決策的影響程度不同，這種影響程度可以在輔助知識的的基礎(chǔ)上事先加以假設(shè)，給每個屬性賦予一個權(quán)值{w1，w2，…，wn}，通過權(quán)值，弱化非重要屬性，強(qiáng)化重要屬性。

（3）引入屬性修正信息熵的概念，目的是弱化非重要多值屬性對信息增益的影響。假設(shè)所有屬性集合為{A1，A2，…，An}，每個屬性發(fā)生概率分別是{P1，P2，…，Pn}，對于屬性Ai每個子屬性發(fā)生的概率為{Pi1，Pi2，…，Pim}。定義屬性Ai的屬性修正信息熵為。

而entropy（Ai）采用ID3中的算法計算。

2.算法步驟

（1）對當(dāng)前例子集合，計算各個屬性的修正信息熵。

（2）選擇修正信息熵最小的屬性Ai作為根節(jié)點。

（3）把在Ai處取值相同的例子歸于同一子集，Ai取幾個值就得幾個子集。

（4）依次對每種取值情況下的子集，遞歸調(diào)用建樹算法，即返回（1）。

（5）若子集只含有單個屬性，則分支為葉子節(jié)點，判斷其屬性值并標(biāo)上相應(yīng)的符號，然后返回調(diào)用處。

二、實例分析

針對表1中的數(shù)據(jù)，用ID3算法求解得圖1所示決策樹。

由表一，對于該例子集合的屬性集合為{天氣，溫度，濕度，風(fēng)} 。對于“天氣”屬性有子屬性{多云，雨，晴}，對于“溫度”屬性有子屬性{高，低，適中}，對于“濕度”屬性有子屬性{正常，大}，對于“風(fēng)”屬性有子屬性{無風(fēng)，中風(fēng)，大風(fēng)}。

由經(jīng)驗我們假定“天氣”的優(yōu)先權(quán)值為0.95，“風(fēng)”的優(yōu)先權(quán)值為0.35，濕度和溫度的優(yōu)先權(quán)值為0。

計算“天氣”的子屬性的子屬性信息熵：

由ID3算法可知：

由5.1中屬性修正信息熵的定義可得：

同理，，。所以選取“濕度”為根節(jié)點。接下來將例子集分成兩個子集：

接下來重復(fù)上面步驟，可得決策樹如圖2所示。

通過比較，可以得到以下結(jié)論：

（1）優(yōu)化算法所生成是二叉樹，而ID3算法所生成的是多叉樹，簡化了決策問題處理的復(fù)雜度。

（2）引入子屬性信息熵、優(yōu)先權(quán)、屬性修正信息熵的概念，從本例來看，根節(jié)點選擇了濕度而沒有選擇屬性值最多的天氣，所以本優(yōu)化算法確實能克服傳統(tǒng)ID3算法的多值偏向性。

三、結(jié)束語

數(shù)據(jù)挖掘技術(shù)是當(dāng)前數(shù)據(jù)庫和人工智能領(lǐng)域研究的熱點課題，分類是數(shù)據(jù)挖掘的一種非常重要的任務(wù)。決而策樹算法是一種非常重要的數(shù)據(jù)挖掘分類算法。本文主要對三種算法的特點及改進(jìn)進(jìn)行了匯總。對于ID3算法，目前的改進(jìn)方向主要集中在解決ID3偏向于選擇取值較多的屬性的不足、解決不能處理連續(xù)值的屬性、解決易受噪聲干擾和優(yōu)化儲存這四個方面。

本文對這三種決策樹算法當(dāng)前研究情況進(jìn)行了總結(jié)分析，并運用分析結(jié)果對經(jīng)典ID3算法提出了改進(jìn)方法。通過進(jìn)行實例分析，了解和熟悉實際應(yīng)用上的差別，為對決策樹算法進(jìn)一步的研究作準(zhǔn)備。