決策樹算法分析與改進

張永昭　岳晟　劉曉楠

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

關鍵詞 數據挖掘；決策樹算法；特點；改進；匯總

引言：

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

一、ID3算法優化

1.改進思路

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

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

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

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

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

2.算法步驟

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

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

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

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

（5）若子集只含有單個屬性，則分支為葉子節點，判斷其屬性值并標上相應的符號，然后返回調用處。

二、實例分析

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

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

由經驗我們假定“天氣”的優先權值為0.95，“風”的優先權值為0.35，濕度和溫度的優先權值為0。

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

由ID3算法可知：

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

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

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

通過比較，可以得到以下結論：

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

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

三、結束語

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

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