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

武獻(xiàn)宇 ，王建芬 ，謝金龍

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

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

1 決策樹(shù)分類過(guò)程

圖1 決策樹(shù)分類過(guò)程圖

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

2 ID3算法

2.1 ID3算法的理論基礎(chǔ)

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

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

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

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

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

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

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

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

2.2 ID3算法多值偏向性分析

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

綜上所知，把ID3算法分別作用在屬性A和屬性A′上，如果屬性選取標(biāo)準(zhǔn)在屬性A′上的取值恒大于在屬性A上的取值，則說(shuō)明該算法在建樹(shù)過(guò)程中具有多值偏向；如果屬性選取標(biāo)準(zhǔn)在屬性A′上的取值與在屬性A上的取值沒(méi)有確定的大小關(guān)系，則說(shuō)明該決策樹(shù)算法在建樹(shù)過(guò)程中不具有多值偏向性。

2.3 ID3算法的缺點(diǎn)

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

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

(3)用互信息作為選擇屬性的標(biāo)準(zhǔn)存在一個(gè)假設(shè)，即訓(xùn)練子集中的正、反例的比例應(yīng)與實(shí)際問(wèn)題領(lǐng)域中正、反例的比例一致。一般情況很難保證這兩者的比例一致，這樣計(jì)算訓(xùn)練集的互信息就會(huì)存在偏差。

(4)在建造決策樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)僅含一個(gè)屬性，是一種單變?cè)乃惴?，致使生成的決策樹(shù)結(jié)點(diǎn)之間的相關(guān)性不夠強(qiáng)。雖然在一棵樹(shù)上連在一起，但聯(lián)系還是松散的。

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

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

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

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

圖2 ID3算法所生成的決策樹(shù)

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

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

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

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

4 實(shí)例分析

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

(1)確定根結(jié)點(diǎn)

選取天氣屬性作為測(cè)試屬性，天氣為多云時(shí)，信息熵為：

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

從上面的計(jì)算可知，天氣為多云時(shí)的最小信息熵為0。

當(dāng)天氣為晴時(shí)，由于此時(shí)對(duì)應(yīng)的類別全部為適合打高爾夫球，所以信息熵都為0。

當(dāng)天氣為雨時(shí)的信息熵為：

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

從上面的計(jì)算可知，天氣為雨時(shí)的最小信息熵為0.25。

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

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

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

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

(2)確定分支結(jié)點(diǎn)

計(jì)算F1分支子集：

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

選擇H(A)值為最小的作為候選屬性，所以此時(shí)應(yīng)選擇溫度作為濕度為大的下一級(jí)結(jié)點(diǎn)。在濕度為大的12個(gè)訓(xùn)練集中對(duì)溫度的3個(gè)取值進(jìn)行分枝，3個(gè)分枝對(duì)應(yīng)3個(gè)子集，由于溫度為低的子集不存在，所以此時(shí)也只有2個(gè)子集，分別為：

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

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

同理，對(duì)于F2分支子集：

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

選擇H(A)值最小的作為候選屬性，所以此時(shí)應(yīng)選擇溫度作為濕度為正常的下一級(jí)結(jié)點(diǎn)。在濕度為正常的12個(gè)訓(xùn)練集中對(duì)溫度的3個(gè)取值進(jìn)行分枝，3個(gè)分枝對(duì)應(yīng)3個(gè)子集，分別為：

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

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

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

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

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

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

(1)從本實(shí)例所生成的決策樹(shù)的形態(tài)來(lái)看，改進(jìn)后的算法生成的是一棵二叉樹(shù)，而ID3算法生成的是多叉樹(shù)，簡(jiǎn)化了決策問(wèn)題處理的復(fù)雜度。

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

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

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

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

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

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

[6]KANTARDZIC M.Data mining concepts， models， methods，and algorithms[M].北京：清華大學(xué)出版社，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.