決策樹ID3算法研究及其優(yōu)化

武獻宇 ，王建芬 ，謝金龍

(1.湖南現(xiàn)代物流職業(yè)技術(shù)學院，湖南 長沙 410131；2.長沙醫(yī)學院，湖南 長沙 410131)

分類是一種非常重要的數(shù)據(jù)挖掘方法，也是數(shù)據(jù)挖掘領域中被廣泛研究的課題。決策樹分類方法是一種重要的分類方法，它是以信息論為基礎對數(shù)據(jù)進行分類的一種數(shù)據(jù)挖掘方法。決策樹生成后成為一個類似流程圖的樹形結(jié)構(gòu)，其中樹的每個內(nèi)部結(jié)點代表一個屬性的測試，分枝代表測試結(jié)果，葉結(jié)點則代表一個類或類的分布，最終可生成一組規(guī)則。相對其他數(shù)據(jù)挖掘方法而言，決策樹分類方法因簡單、直觀、準確率高且應用價值高等優(yōu)點在數(shù)據(jù)挖掘及數(shù)據(jù)分析中得到了廣泛應用。

1 決策樹分類過程

圖1 決策樹分類過程圖

決策樹的分類過程也就是決策樹分類模型(簡稱決策樹)的生成過程，如圖1所示。從圖中可知決策樹分類的建立過程與用決策樹分類模型進行預測的過程實際上是一種歸納-演繹過程。其中，由已分類數(shù)據(jù)得到?jīng)Q策樹分類模型的過程稱歸納過程，用決策樹分類模型對未分類數(shù)據(jù)進行分類的過程稱為演繹過程。需要強調(diào)的是：由訓練集得到分類模型必須經(jīng)過測試集測試達到一定要求才能用于預測。

2 ID3算法

2.1 ID3算法的理論基礎

ID3算法的理論依據(jù)為：

設 E=F1×F2×…×Fn是 n 維有窮向量空間，F(xiàn)j是有窮離散符號集，E 中的元素 e=＜V1，V2， …，Vn＞稱為例子，其中 Vj∈Fj，j=1，2，…，n。設 PE 和 NE 是 E 的兩個例子集，分別叫正例集和反例集。

假設向量空間E中的正例集PE和反例集NE的大小分別為p和n。ID3算法是基于如下兩種假設：

(1)向量空間E上的一棵正確決策樹對任意例子的分類概率同E中的正反例的概率一致。

(2)一棵決策樹對一例子做出正確類別判斷所需的信息量為:

如果以屬性A作為決策樹的根，A具有V個值{V1，V2，V3，…，Vv}，它們將 E 分成 V 個子集{E1，E2，…，Ev}，假設 Ei中含有 pi個正例和 ni個反例，則子集Ei所需的期望信息是 E(pi，ni)，以屬性 A為根的期望熵為：

因此，以A為根的信息增益是：

信息增益是不確定性的消除，也就是接收端所獲得的信息量。

2.2 ID3算法多值偏向性分析

首先，設A是某訓練樣本集的一個屬性，它的取值為 A1，A2，…，An，創(chuàng)建另外一個新屬性 A′，它與屬性 A唯一的區(qū)別：其中一個已知值 An分解為兩個值 A′n和A′n+1，其余值和A中的完全一樣，假設原來 n個值已經(jīng)提供足夠的信息使分類正確進行，很明顯，則屬性A′相對于A沒有任何作用。但如果按照Qulnina的標準，屬性A′應當優(yōu)先于屬性A選取。

綜上所知，把ID3算法分別作用在屬性A和屬性A′上，如果屬性選取標準在屬性A′上的取值恒大于在屬性A上的取值，則說明該算法在建樹過程中具有多值偏向；如果屬性選取標準在屬性A′上的取值與在屬性A上的取值沒有確定的大小關系，則說明該決策樹算法在建樹過程中不具有多值偏向性。

2.3 ID3算法的缺點

(1)ID3算法往往偏向于選擇取值較多的屬性，而在很多情況下取值較多的屬性并不總是最重要的屬性，即按照使熵值最小的原則被ID3算法列為應該首先判斷的屬性在現(xiàn)實情況中卻并不一定非常重要。例如:在銀行客戶分析中，姓名屬性取值多，卻不能從中得到任何信息。

(2)ID3算法不能處理具有連續(xù)值的屬性，也不能處理具有缺失數(shù)據(jù)的屬性。

(3)用互信息作為選擇屬性的標準存在一個假設，即訓練子集中的正、反例的比例應與實際問題領域中正、反例的比例一致。一般情況很難保證這兩者的比例一致，這樣計算訓練集的互信息就會存在偏差。

(4)在建造決策樹時，每個結(jié)點僅含一個屬性，是一種單變元的算法，致使生成的決策樹結(jié)點之間的相關性不夠強。雖然在一棵樹上連在一起，但聯(lián)系還是松散的。

(5)ID3算法雖然理論清晰，但計算比較復雜，在學習和訓練數(shù)據(jù)集的過程中機器內(nèi)存占用率比較大，耗費資源。

決策樹ID3算法是一個很有實用價值的示例學習算法，它的基礎理論清晰，算法比較簡單，學習能力較強，適于處理大規(guī)模的學習問題，是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)領域中的一個很好的范例，為后來各學者提出優(yōu)化算法奠定了理論基礎。表1是一個經(jīng)典的訓練集。

表1 天氣數(shù)據(jù)庫訓練數(shù)據(jù)集

由ID3算法遞歸建樹得到一棵決策樹如圖2所示。

圖2 ID3算法所生成的決策樹

3 ID3算法優(yōu)化的探討

ID3算法在選擇分裂屬性時，往往偏向于選擇取值較多的屬性，然而在很多情況下取值較多的屬性并不總是最重要的屬性，這會造成生成的決策樹的預測結(jié)果與實際偏離較大，針對這一弊端，本文提出以下改進思路：

(1)引入分支信息熵的概念。對于所有屬性，任取屬性A，計算A屬性的各分支子集的信息熵，在每個分支子集中找出最小信息熵，并計算其和，比較大小，選擇其最小值作為待選擇的最優(yōu)屬性。

(2)引入屬性優(yōu)先的概念。不同的屬性對于分類或決策有著不同的重要程度，這種重要程度可在輔助知識的基礎上事先加以假設，給每個屬性都賦予一個權(quán)值，其大小為(0，1)中的某個值。通過屬性優(yōu)先法，降低非重要屬性的標注，提高重要屬性的標注。

4 實例分析

仍以表1為例，分別計算其H(A)的值。在此通過反復測試，天氣的屬性優(yōu)先權(quán)值為0.95，風的屬性優(yōu)先權(quán)值為0.35，其余兩個的屬性優(yōu)先權(quán)值都為0。

(1)確定根結(jié)點

選取天氣屬性作為測試屬性，天氣為多云時，信息熵為：

同理 E(天氣(多云)/濕度)=0，E(天氣(多云)/風)=0.972 77

從上面的計算可知，天氣為多云時的最小信息熵為0。

當天氣為晴時，由于此時對應的類別全部為適合打高爾夫球，所以信息熵都為0。

當天氣為雨時的信息熵為：

同 理 E(天 氣(雨)/濕 度)=0.451 21，E(天 氣(雨)/風 )=0.344 36

從上面的計算可知，天氣為雨時的最小信息熵為0.25。

同 理 H(溫 度)=1.083 83，H(濕 度)=1.068 7，H(風)=2.775 54

根據(jù)算法步驟(6)，選擇值H(A)為最小的作為候選屬性，所以此時應選擇濕度作為根結(jié)點。在24個訓練集中對濕度的2個取值進行分枝，2個分枝對應2個子集，分別為：

F1={1，2，3，4，5，6，7，13，14，21，22，24}(濕度為高對應)

F2={8，9，10，11，12，15，16，17，18，19，20，23}(濕度為正常對應)

(2)確定分支結(jié)點

計算F1分支子集：

H(溫度)=0.908 05，H(天氣)=0.95，H(風)=1.554 56

選擇H(A)值為最小的作為候選屬性，所以此時應選擇溫度作為濕度為大的下一級結(jié)點。在濕度為大的12個訓練集中對溫度的3個取值進行分枝，3個分枝對應3個子集，由于溫度為低的子集不存在，所以此時也只有2個子集，分別為：

F11={1，2，3，4，5}(濕度為大且溫度為高對應)

F12={6，7，13，14，21，22，24}(濕度為大且溫度為適中對應)

同理，對于F2分支子集：

H(溫度)=0.863 71，H(天氣)=1.250 8，H(風)=1.554 6

選擇H(A)值最小的作為候選屬性，所以此時應選擇溫度作為濕度為正常的下一級結(jié)點。在濕度為正常的12個訓練集中對溫度的3個取值進行分枝，3個分枝對應3個子集，分別為：

F21={8，10，23}(濕度為正常且溫度為高對應)

F22={17，18，19，20}(濕度為正常且溫度為適中對應)

F23={9，11，12，15，16}(濕度為正常且溫度為低對應)

繼續(xù)對 F11，F(xiàn)12，F(xiàn)21，F(xiàn)22，F(xiàn)23等分支子集采用此優(yōu)化算法遞歸建樹，經(jīng)過合并和簡化后得到的決策樹如圖3所示。

圖3 優(yōu)化算法所生成的決策樹

通過比較ID3算法和本文所提出的組合優(yōu)化算法所生成的決策樹可知，組合優(yōu)化算法的改進為：

(1)從本實例所生成的決策樹的形態(tài)來看，改進后的算法生成的是一棵二叉樹，而ID3算法生成的是多叉樹，簡化了決策問題處理的復雜度。

(2)引入了分支信息熵和屬性優(yōu)先的概念，用條件熵、分支信息熵與屬性優(yōu)先三者相結(jié)合來選擇分裂屬性。從本實例來看，根結(jié)點選擇濕度而未選擇屬性值最多的天氣，所以本優(yōu)化算法確實能克服傳統(tǒng)ID3算法的多值偏向性。

[1]安淑芝.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].北京：清華大學出版社，2005：104-107.

[2]史忠植.知識發(fā)現(xiàn)[M].北京：清華大學出版社，2002：23-37.

[3]徐潔磐.數(shù)據(jù)倉庫與決策支持系統(tǒng)[M].北京：科學出版社，2005：77-86.

[4]路紅梅.基于決策樹的經(jīng)典算法綜述[J].宿州學院學報，2007(4)：91-95.

[5]韓慧.數(shù)據(jù)挖掘中決策樹算法的最新進展[J].計算機應用研究，2004(12)：5-8.

[6]KANTARDZIC M.Data mining concepts， models， methods，and algorithms[M].北京：清華大學出版社，2003：120-136.

[7]OLARU C，WEHENKEL L.A complete fuzzy decision tree technique[J].Fuzzy Sets and Systems， 2003，138(2)：221-254.

[8]AITKENHEAD M J.Aco-evolving decision tree classification method[J].Expert System with Application， 2008(34)：18-25.

[9]Norio Takeoka.Subjective probability over a subjective decision tree[J].Journal of Economic Theory，2007(136):536-571.