決策樹ID3算法的一種改進

趙 靜

沈陽市服裝藝術學校，遼寧沈陽 110032

1 ID3算法簡介

ID3算法由Quinlan于1979年提出。其基本思想是：在對訓練集進行分類時，以信息熵為度量，用于決策樹節點的屬性選擇，每次優先選取信息量最多的屬性對數據進行劃分，以構造一顆熵值下降最快的決策樹，每個葉子節點對應的實例集中的實例屬于同一類。

2 ID3算法的優點和不足

優點：運用信息論知識選擇屬性，理論清晰；容易生成IF-THEN語句；對于離散型樣本數據處理功能強；ID3自頂向下搜索，節省系統資源，計算時間與樣本大小。

不足：ID3算法在選擇分類屬性時往往選擇了取值較多的屬性；ID3算法只能處理離散型數據，若分析必須先進行離散化；用ID3算法創建決策樹時必須知道所有內部節點。

3 ID3算法的改進

定理1：若函數f(x)在[a，b]上連續，在（a，b）內有一階、二階導數，并且在（a，b）上，若f'(x)＜0，則f(x)在[a，b]上是凸函數；

3.1 算法改進的實現

pi表示數據屬于類Ci的概率，在（0，1）上任取p1，p2有p1+p2=1，p1-p2=△p→0，因為log2p函數在（0，1]上連續，由定理1可知log2p函數在其連續區間上是凸函數。

由凸函數性質計算得：

3.2 改進算法的應用

表一為某公司調查的顧客數據統計表.通過數據挖掘旨在回答“誰在買電腦”這一問題。

表1 顧客調查表

第2步：計算條件屬性的熵

1）年齡分三組:老、中、青。 青年384人，正例128人，反例256人；中年256人，正例256人，反例0人；老年252人，正例125，反例127人。

老年 ： I(125，127)=0.9157 所以 ，E（年齡）=0.6877 ； G（年齡）=0.9537-0.6877 =0.2660 ；

2）E（收入）=0.9361 G（收入信息增益）=0.9537-0.9361=0.0176；

3）E（學生）=0.7811 G（年齡信息增益）=0.9537-0.7811=0.1726；

4）E（信譽）=0.9048 G(信譽信息增益）=0.9537-0.9048=0.0453。

第3步：計算選擇節點。由上可知“年齡”具有最高的信息增益，選擇“年齡”為測試屬性 。

第4步：遞歸建樹算法，分別對各個子集分析，計算選擇分支的測試屬性。

1）年齡=“青年”的子集有：選擇學生為測試屬性對子集進行再劃分；

2）對于年齡=“中年”，數據都屬于同一類，自然形成樹葉；

3）對于年齡=“老年”的子集有：選擇信譽為測試屬性。由此生成決策樹如下圖所示：