(完整版)ID3算法課件

1、1決策樹算法2InputID3 AlgorithmData Mining AlgorithmOutputData setDT3決策樹是用樣本的屬性作為結(jié)點，用屬性的取值作為分支的樹結(jié)構(gòu)。 決策樹的根結(jié)點是所有樣本中信息量最大的屬性。樹的中間結(jié)點是該結(jié)點為根的子樹所包含的樣本子集中信息量最大的屬性。決策樹的葉結(jié)點是樣本的類別值。決策樹概念4決策樹是一種知識表示形式，它是對所有樣本數(shù)據(jù)的高度概括。決策樹能準(zhǔn)確地識別所有樣本的類別，也能有效地識別新樣本的類別。 5ID3方法基本思想首先找出最有判別力的屬性，把樣例分成多個子集，每個子集又選擇最有判別力的屬性進(jìn)行劃分，一直進(jìn)行到所有子集僅包含同一類型的

2、數(shù)據(jù)為止。最后得到一棵決策樹。J.R.Quinlan的工作主要是引進(jìn)了信息論中的信息增益，他將其稱為信息增益（information gain），作為屬性判別能力的度量，設(shè)計了構(gòu)造決策樹的遞歸算法。下面通過一個例子，說明ID3算法的基本思想。6 對于氣候分類問題，屬性為: 天氣(A1) 取值為： 晴，多云，雨 氣溫(A2) 取值為： 冷 ，適中，熱 濕度(A3) 取值為： 高 ，正常 風(fēng) (A4) 取值為： 有風(fēng)， 無風(fēng) 一、ID3基本思想7每個樣例屬于不同的類別，此例僅有兩個類別，分別為P，N。P類和N類的樣例分別稱為正例和反例。將一些已知的正例和反例放在一起便得到訓(xùn)練集。表6.4.1給出一

3、個訓(xùn)練集。由ID3算法得出一棵正確分類訓(xùn)練集中每個樣例的決策樹，見下圖。8天 氣濕 度風(fēng)晴雨多云高正常有風(fēng)無風(fēng)PNNPPBACKGO9決策樹葉子為類別名，即P 或者N。其它結(jié)點由樣例的屬性組成，每個屬性的不同取值對應(yīng)一分枝。若要對一樣例分類，從樹根開始進(jìn)行測試，按屬性的取值分枝向下進(jìn)入下層結(jié)點，對該結(jié)點進(jìn)行測試，過程一直進(jìn)行到葉結(jié)點，樣例被判為屬于該葉結(jié)點所標(biāo)記的類別。10現(xiàn)用圖來判一個具體例子， 某天早晨氣候描述為: 天氣：多云 氣溫：冷 濕度：正常 風(fēng)： 無風(fēng) 它屬于哪類氣候呢?從圖中可判別該樣例的類別為P類。11ID3就是要從表的訓(xùn)練集構(gòu)造圖這樣的決策樹。實際上，能正確分類訓(xùn)練集的決策樹

4、不止一棵。Quinlan的ID3算法能得出結(jié)點最少的決策樹。12二、ID3算法 對當(dāng)前例子集合，計算各屬性的信息增益； 選擇信息增益最大的屬性Ak； 把在Ak處取值相同的例子歸于同一子集，Ak取幾個值就得幾個子集； 對既含正例又含反例的子集，遞歸調(diào)用建樹算法； 若子集僅含正例或反例，對應(yīng)分枝標(biāo)上P或N，返回調(diào)用處。13實例計算 對于氣候分類問題進(jìn)行具體計算有： 信息熵的計算 信息熵： 其中S是樣例的集合， P(ui)是類別i出現(xiàn)概率：14|S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù)。對9個正例和5個反例有：P（u1）=9/14P（u2）=5/14H（S）=（9/14）log（14/9

5、）+（5/14）log（14/5）=0.94bit15信息增益的計算公式：其中A是屬性，Value(A)是屬性A取值的集合，v是A的某一屬性值，Sv是S中A的值為v的樣例集合，| Sv |為Sv中所含樣例數(shù)。 信息增益的計算16屬性Ai的信息增益以屬性A1為例，根據(jù)信息增益的計算公式，屬性A1的信息增益為S=9+,5- /原樣例集中共有14個樣例，9個正例，5個反例S晴=2+,3-/屬性A1取值晴的樣例共5個，2正，3反S多云=4+,0- /屬性A1取值多云的樣例共4個，4正，0反S雨=3+,2- /屬性A1取值晴的樣例共5個，3正，2反故1718計算結(jié)果屬性A1的信息增益最大，所以被選為根結(jié)

6、點19 ID3算法將選擇信息增益最大的屬性天氣作為樹根，在14個例子中對天氣的3個取值進(jìn)行分枝，3 個分枝對應(yīng)3 個子集，分別是: S1=1，2，8，9，11; S2=3，7，12，13; S3=4，5，6，10，14 其中S2中的例子全屬于P類，因此對應(yīng)分枝標(biāo)記為P，其余兩個子集既含有正例又含有反例，將遞歸調(diào)用建樹算法。 建決策樹的根和分枝20天氣S=D1,D2,D3,D14晴多云雨S1=D1,D2,D8,D9,D11S2=D3,D7,D12, D13S3=D4,D5,D6,D10,D14全為正例21 分別對S1和S3子集遞歸調(diào)用ID3算法，在每個子集中對各屬性求信息增益. （1）對S1，濕

7、度屬性信息增益最大，以它為該分枝的根結(jié)點，再向下分枝。濕度取高的例子全為N類，該分枝標(biāo)記N。取值正常的例子全為P類，該分枝標(biāo)記P。 （2）對S3，風(fēng)屬性信息增益最大，則以它為該分枝根結(jié)點。再向下分枝，風(fēng)取有風(fēng)時全為N類，該分枝標(biāo)記N。取無風(fēng)時全為P類，該分枝標(biāo)記P。 這樣就得到如圖所示的決策樹 遞歸建樹22對ID3的討論 優(yōu)點 ID3在選擇重要屬性時利用了信息增益的概念，算法的基礎(chǔ)理論清晰，使得算法較簡單，是一個很有實用價值的示例學(xué)習(xí)算法。 該算法的計算時間是例子個數(shù)、屬性個數(shù)、結(jié)點個數(shù)之積的線性函數(shù)。對有4761個關(guān)于苯的質(zhì)譜例子作了試驗。其中正例2361個，反例2400個，每個例子由500

8、個屬性描述，每個屬性取值數(shù)目為6，得到一棵1514個結(jié)點的決策樹。對正、反例各100個測試?yán)髁藴y試，正例判對82個，反例判對80個，總預(yù)測正確率81%，效果是令人滿意的。23 缺點 （1）信息增益的計算依賴于屬性取值的數(shù)目較多的屬性，這樣不太合理。一種簡單的辦法是對屬性進(jìn)行分解，如上節(jié)例中，屬性取值數(shù)目不一樣，可以把它們統(tǒng)統(tǒng)化為二值屬性，如天氣取值晴，多云，雨，可以分解為三個屬性；天氣晴，天氣多云，天氣雨。取值都為“是”或“否”，對氣溫也可做類似的工作。這樣就不存在偏向問題了。24 （2）用信息增益作為屬性選擇量存在一個假設(shè)，即訓(xùn)練例子集中的正，反例的比例應(yīng)與實際問題領(lǐng)域里正、反例比例相同。

9、一般情況不能保證相同，這樣計算訓(xùn)練集的信息增益就有偏差。 （3）ID3在建樹時，每個節(jié)點僅含一個屬性，是一種單變元的算法，屬性間的相關(guān)性強調(diào)不夠。雖然它將多個屬性用一棵樹連在一起，但聯(lián)系還是松散的。25 （4）ID3對噪聲較為敏感。關(guān)于什么是噪聲，Quinlan的定義是訓(xùn)練例子中的錯誤就是噪聲。它包含兩方面，一是屬性值取錯，二是類別給錯。 （5）當(dāng)訓(xùn)練集增加時，ID3的決策樹會隨之變化。在建樹過程中，各屬性的信息增益會隨例子的增加而改變，從而使決策樹也變化。這對漸近學(xué)習(xí)（即訓(xùn)練例子不斷增加）是不方便的。 26 總的來說，ID3由于其理論的清晰，方法簡單，學(xué)習(xí)能力較強，適于處理大規(guī)模的學(xué)習(xí)問題 ，在世界上廣為流傳，得到極大的關(guān)注，是數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域中的一個極好范例，也不失為一種知識獲取的有用工具。NO.屬性類別天氣氣溫濕度風(fēng)D1晴熱高無