基于ID3算法實(shí)現(xiàn)的離散決策樹生成。

ID3算法的基本思想是貪心算法，采用自上而下的分而治之的方法構(gòu)造決策樹。首先檢測(cè)訓(xùn)練數(shù)據(jù)集的所有特征，選擇信息增益最大的特征A建立決策樹根節(jié)點(diǎn)，由該特征的不同取值建立分枝，對(duì)各分枝的實(shí)例子集遞歸，用該方法建立樹的節(jié)點(diǎn)和分枝，直到某一子集中的數(shù)據(jù)都屬于同一類別，或者沒有特征可以在用于對(duì)數(shù)據(jù)進(jìn)行分割。ID3算法總是選擇具有最高信息增益(或最大熵壓縮)的屬性作為當(dāng)前結(jié)點(diǎn)的測(cè)試屬性。該屬性使得結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或“不純性”。這種信息理論方法使得對(duì)一個(gè)對(duì)象分類所需的期望測(cè)試數(shù)目達(dá)到最小，并盡量確保一棵簡(jiǎn)單的(但不必是最簡(jiǎn)單的)樹來刻畫相關(guān)的信息。

在ID3算法中，計(jì)算信息增益時(shí)，由于信息增益存在一個(gè)內(nèi)在偏置，它偏袒具有較多值的屬性，太多的屬性值把訓(xùn)練樣例分割成非常小的空間。因此，這個(gè)屬性可能會(huì)有非常高的信息增益，而且被選作樹的根結(jié)點(diǎn)的決策屬性，并形成一棵深度只為一級(jí)但卻非常寬的樹，這棵樹可以理想地分類訓(xùn)練數(shù)據(jù)。但是這個(gè)決策樹對(duì)于測(cè)試數(shù)據(jù)的分類性能可能會(huì)相當(dāng)差，因?yàn)樗^分地完美地分割了訓(xùn)練數(shù)據(jù)，不是一個(gè)好的分類器。

在J.Mingers關(guān)于ID3算法的研究中，通過對(duì)五種包含噪音的學(xué)習(xí)樣例的實(shí)驗(yàn)發(fā)現(xiàn)，多數(shù)情況下過度擬合導(dǎo)致決策樹的精度降低了10%一25%。過度擬合不僅影響決策樹對(duì)未知實(shí)例的分類精度，而且還會(huì)導(dǎo)致決策樹的規(guī)模增大。一方面，葉子節(jié)點(diǎn)隨分割不斷增多。在極端的情況下，在一棵完成分割的決策樹中，每個(gè)葉子節(jié)點(diǎn)中只包含一個(gè)實(shí)例。此時(shí)決策樹在學(xué)習(xí)樣例上的分類精度達(dá)到100%，而其葉子節(jié)點(diǎn)的數(shù)目等于學(xué)習(xí)樣例中實(shí)例的數(shù)目。但是顯然這棵決策樹對(duì)任何未見的實(shí)例都是毫無意義的。另一方面，決策樹不斷向下生長(zhǎng)，導(dǎo)致樹的深度增加。因?yàn)槊恳粭l自根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑都對(duì)應(yīng)一條規(guī)則，所以樹的深度越大，其對(duì)應(yīng)的規(guī)則越長(zhǎng)。作為一種蘊(yùn)含于學(xué)習(xí)樣例中的知識(shí)，這樣一組過長(zhǎng)的規(guī)則集合是很難被人理解的。過度擬合現(xiàn)象的存在，無論是對(duì)決策樹的分類精度，還是對(duì)其規(guī)模以及可理解性都產(chǎn)生了不利的影響。因此對(duì)與決策樹的剪枝是非常有必要的。