決策樹模型詳解演示文稿課件

1、決策樹模型詳解演示文稿（優(yōu)選）決策樹模型分類的技術(shù)監(jiān)督式(supervised learning)的機器學習法-決策樹(Decision Tree)數(shù)據(jù)庫分類標記性別年齡婚姻否是否是FemaleMale3535未婚已婚分類的過程1.模型建立(Model Building)2.模型評估(Model Evaluation)3.使用模型(Use Model)性別年齡婚姻否是否是FemaleMale3535未婚已婚分類規(guī)則IF 性別=Female AND 年齡35 THEN 購買RV房車=否IF 性別=Female AND 年齡35 THEN 購買RV房車=是IF 性別=Male AND 婚姻=未婚

2、THEN 購買RV房車=否IF 性別=Male AND 婚姻=已婚 THEN 購買RV房車=是數(shù)據(jù)庫訓練樣本(training samples)建立模型測試樣本(testing samples)評估模型資料Example訓練樣本婚姻年齡家庭 所得否是否是未婚已婚3535低高否小康1.建立模型測試樣本2. 模型評估X錯誤率為 66.67%修改模型3.使用模型決策樹(Decision Tree)介紹根部節(jié)點(root node)中間節(jié)點(non-leaf node)(代表測試的條件)分支(branches)(代表測試的結(jié)果)葉節(jié)點(leaf node)(代表分類后所獲得的分類標記)決策樹的形成根部

3、節(jié)點中間節(jié)點停止分支？7.1 信息論原理7.2 決策樹方法7.1 信息論原理 信息論是C.E.Shannon為解決信息傳遞（通信）過程問題而建立的理論，也稱為統(tǒng)計通信理論。1. 信道模型一個傳遞信息的系統(tǒng)是由發(fā)送端（信源）和接收端（信宿）以及連接兩者的通道（信道）三者組成。信道u1,u2.ur信源Uv1,v2.vrP(V|U)信宿V在進行實際的通信之前，收信者（信宿）不可能確切了解信源究竟會發(fā)出什么樣的具體信息，不可能判斷信源會處于什么樣的狀態(tài)。這種情形就稱為信宿對于信源狀態(tài)具有不確定性。而且這種不確定性是存在于通信之前的。因而又叫做先驗不確定性，表示成 信息熵 H（U）在進行了通信之后，信宿

4、收到了信源發(fā)來的信息，這種先驗不確定性才會被消除或者被減少。如果干擾很小，不會對傳遞的信息產(chǎn)生任何可察覺的影響，信源發(fā)出的信息能夠被信宿全部收到，在這種情況下，信宿的先驗不確定性就會被完全消除。在一般情況下，干擾總會對信源發(fā)出的信息造成某種破壞，使信宿收到的信息不完全。先驗不確定性不能全部被消除，只能部分地消除。通信結(jié)束之后，信宿仍然具有一定程度的不確定性。這就是后驗不確定性，用條件熵表示H（U/V）。后驗不確定性總要小于先驗不確定性:H（U/V）H（X） 故信源Y比信源X的平均不確定性要大。 信息熵H（U）是信源輸出前的平均不確定性，也稱先驗熵。 H（U）的性質(zhì): （1）H（U）=0時，說明

5、只存在著唯一的可能性，不存在不確定性。 （2）如果n種可能的發(fā)生都有相同的概率，即所有的Ui有P（Ui）=1/n，H（U）達到最大值log n，系統(tǒng)的不確定性最大。 P（Ui）互相接近，H（U）就大。P（Ui）相差大，則H（U）就小。 7互信息(1)后驗熵和條件熵當沒有接收到輸出符號V時，已知輸入符號U的概率分布為P（U），而當接收到輸出符號V=Vj 后，輸入符號的概率分布發(fā)生了變化,變成后驗概率分布P（U|Vj）。其后驗熵為：那么接收到輸出符號V=Vj后，關(guān)于U的平均不確定性為： 這是接收到輸出符號Vj后關(guān)于U的條件熵 這個條件熵稱為信道疑義度。它表示在輸出端收到全部輸出符號V后，對于輸入端

6、的符號集U尚存在的不確定性（存在疑義）。 從上面分析可知：條件熵小于無條件熵，即H（U|V）H（U）。說明接收到符號集V的所有符號后，關(guān)于輸入符號U的平均不確定性減少了。即總能消除一些關(guān)于輸入端X的不確定性，從而獲得了一些信息。（2）平均互信息定義: I（U,V） = H（U） H（U|V） （3.10） I（U,V）稱為U和V之間的平均互信息.它代表接收到符號集V后獲得的關(guān)于U的信息量。 可見，熵（H（U）、H（U|V）只是平均不確定性的描述。熵差（H（U） H（U|V）是不確定性的消除，即互信息才是接收端所獲得的信息量。 對輸入端U只有U1，U2兩類，互信息的計算公式為: 7.2 決策樹方

7、法7.2.1決策樹概念決策樹是用樣本的屬性作為結(jié)點，用屬性的取值作為分支的樹結(jié)構(gòu)。 決策樹的根結(jié)點是所有樣本中信息量最大的屬性。樹的中間結(jié)點是該結(jié)點為根的子樹所包含的樣本子集中信息量最大的屬性。決策樹的葉結(jié)點是樣本的類別值。決策樹是一種知識表示形式，它是對所有樣本數(shù)據(jù)的高度概括。決策樹能準確地識別所有樣本的類別，也能有效地識別新樣本的類別。 7.2.2 ID3方法基本思想當前國際上最有影響的示例學習方法首推J.R.Quinlan的ID3（Interative Dicmiser versions3）. 原理：首先找出最有判別力的特征，把數(shù)據(jù)分成多個子集，每個子集又選擇最有判別力的特征進行劃分，一

8、直進行到所有子集僅包含同一類型的數(shù)據(jù)為止。最后得到一棵決策樹。J.R.Quinlan的工作主要是引進了信息論中的互信息，他將其稱為信息增益（information gain），作為特征判別能力的度量，并且將建樹的方法嵌在一個迭代的外殼之中。一、ID3基本思想 例如：關(guān)于氣候的類型，特征為: 天氣 取值為： 晴，多云，雨 氣溫 取值為： 冷 ，適中，熱 濕度 取值為： 高 ，正常 風 取值為： 有風， 無風 每個實體在世界中屬于不同的類別，為簡單起見，假定僅有兩個類別，分別為P，N。在這種兩個類別的歸納任務(wù)中，P類和N類的實體分別稱為概念的正例和反例。將一些已知的正例和反例放在一起便得到訓練集。

9、表3.1給出一個訓練集。由ID3算法得出一棵正確分類訓練集中每個實體的決策樹，見下圖。NO.屬性類別天氣氣溫濕度風1晴熱高無風N2晴熱高有風N3多云熱高無風P4雨適中高無風P5雨冷正常無風P6雨冷正常有風N7多云冷正常有風P8晴適中高無風N9晴冷正常無風P10雨適中正常無風P11晴適中正常有風P12多云適中高有風P13多云熱正常無風P14雨適中高有風N天 氣濕 度風晴雨多云高正常有風無風PNNPPID3決策樹決策樹葉子為類別名，即P 或者N。其它結(jié)點由實體的特征組成，每個特征的不同取值對應一分枝。若要對一實體分類，從樹根開始進行測試，按特征的取值分枝向下進入下層結(jié)點，對該結(jié)點進行測試，過程一直

10、進行到葉結(jié)點，實體被判為屬于該葉結(jié)點所標記的類別?，F(xiàn)用圖來判一個具體例子， 某天早晨氣候描述為: 天氣：多云 氣溫：冷 濕度：正常 風： 無風 它屬于哪類氣候呢?從圖中可判別該實體的類別為P類。ID3就是要從表的訓練集構(gòu)造圖這樣的決策樹。實際上，能正確分類訓練集的決策樹不止一棵。Quinlan的ID3算法能得出結(jié)點最少的決策樹。二、ID3算法（一）主算法 從訓練集中隨機選擇一個既含正例又含反例的子集（稱為窗口）； 用“建樹算法”對當前窗口形成一棵決策樹； 對訓練集（窗口除外）中例子用所得決策樹進行類別判定，找出錯判的例子； 若存在錯判的例子，把它們插入窗口，轉(zhuǎn)2，否則結(jié)束。主算法流程用下圖表示

11、。其中PE、NE分別表示正例集和反例集，它們共同組成訓練集。PE，PE和NE，NE分別表示正例集和反例集的子集。主算法中每迭代循環(huán)一次，生成的決策樹將會不相同。訓練集PE、NE取子集建窗口窗口PE、NE生成決策樹測試PE、NE擴展窗口PE=PE+PENE=NE+NE此決策樹為最后結(jié)果存在錯判的PE，NE嗎是否ID3主算法流程（二）建樹算法 對當前例子集合，計算各特征的互信息； 選擇互信息最大的特征Ak； 把在Ak處取值相同的例子歸于同一子集，Ak取幾個值就得幾個子集； 對既含正例又含反例的子集，遞歸調(diào)用建樹算法； 若子集僅含正例或反例，對應分枝標上P或N，返回調(diào)用處。實例計算 對于氣候分類問題

12、進行具體計算有： 信息熵的計算信息熵：類別出現(xiàn)概率：|S|表示例子集S的總數(shù)，|ui|表示類別ui的例子數(shù)。 對9個正例和5個反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit 條件熵計算條件熵：屬性A1取值vj時，類別ui的條件概率：A1=天氣 取值 v1=晴，v2=多云，v3=雨在A1處取值晴的例子5個，取值多云的例子4 個，取值雨的例子5 個，故： P（v1）=5/14 P（v2）=4/14 P（v3）=5/14取值為晴的5 個例子中有2 個正例、3個反例，故： P（u1/v1）=2/5， P（u2/

13、v1）=3/5同理有：P（u1/v2）=4/4， P（u2/v2）=0 P（u1/v3）=2/5， P（u2/v3）=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4) +0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3) = 0.694bit 互信息計算 對 A1=天氣 處有： I（天氣）=H（U）- H（U|V）= 0.94 - 0.694 = 0.246 bit 類似可得： I（氣溫）=0.029 bit I（濕度）=0.151 bit I（風）=0.048 bit 建決策樹的樹根和分枝 I

14、D3算法將選擇互信息最大的特征天氣作為樹根，在14個例子中對天氣的3個取值進行分枝，3 個分枝對應3 個子集，分別是: F1=1，2，8，9，11，F(xiàn)2=3，7，12，13，F(xiàn)3=4，5，6，10，14 其中F2中的例子全屬于P類，因此對應分枝標記為P，其余兩個子集既含有正例又含有反例，將遞歸調(diào)用建樹算法。 遞歸建樹 分別對F1和F3子集利用ID3算法，在每個子集中對各特征（仍為四個特征）求互信息. （1）F1中的天氣全取晴值，則H（U）=H（U|V），有I（U|V）=0，在余下三個特征中求出濕度互信息最大，以它為該分枝的根結(jié)點，再向下分枝。濕度取高的例子全為N類，該分枝標記N。取值正常的例子

15、全為P類，該分枝標記P。 （2）在F3中，對四個特征求互信息，得到風特征互信息最大，則以它為該分枝根結(jié)點。再向下分枝，風取有風時全為N類，該分枝標記N。取無風時全為P類，該分枝標記P。 這樣就得到下圖的決策樹。 天 氣濕 度風晴雨多云高正常有風無風PNNPPID3決策樹對ID3的討論 優(yōu)點 ID3在選擇重要特征時利用了互信息的概念，算法的基礎(chǔ)理論清晰，使得算法較簡單，是一個很有實用價值的示例學習算法。 該算法的計算時間是例子個數(shù)、特征個數(shù)、結(jié)點個數(shù)之積的線性函數(shù)。用4761個關(guān)于苯的質(zhì)譜例子作了試驗。其中正例2361個，反例2400個，每個例子由500個特征描述，每個特征取值數(shù)目為6，得到一棵

16、1514個結(jié)點的決策樹。對正、反例各100個測試例作了測試，正例判對82個，反例判對80個，總預測正確率81%，效果是令人滿意的。 缺點 （1）互信息的計算依賴于特征取值的數(shù)目較多的特征，這樣不太合理。一種簡單的辦法是對特征進行分解，如上節(jié)例中，特征取值數(shù)目不一樣，可以把它們統(tǒng)統(tǒng)化為二值特征，如天氣取值晴，多云，雨，可以分解為三個特征；天氣晴，天氣多云，天氣雨。取值都為“是”或“否”，對氣溫也可做類似的工作。這樣就不存在偏向問題了。 （2）用互信息作為特征選擇量存在一個假設(shè)，即訓練例子集中的正，反例的比例應與實際問題領(lǐng)域里正、反例比例相同。一般情況不能保證相同，這樣計算訓練集的互信息就有偏差。

17、 （3）ID3在建樹時，每個節(jié)點僅含一個特征，是一種單變元的算法，特征間的相關(guān)性強調(diào)不夠。雖然它將多個特征用一棵樹連在一起，但聯(lián)系還是松散的。 （4）ID3對噪聲較為敏感。關(guān)于什么是噪聲，Quinlan的定義是訓練例子中的錯誤就是噪聲。它包含兩方面，一是特征值取錯，二是類別給錯。 （5）當訓練集增加時，ID3的決策樹會隨之變化。在建樹過程中，各特征的互信息會隨例子的增加而改變，從而使決策樹也變化。這對漸近學習（即訓練例子不斷增加）是不方便的。 總的來說，ID3由于其理論的清晰，方法簡單，學習能力較強，適于處理大規(guī)模的學習問題 ，在世界上廣為流傳，得到極大的關(guān)注，是數(shù)據(jù)挖掘和機器學習領(lǐng)域中的一個極好范例，也不失為一種知識獲取的有用工具。C4.5算法 ID3算法在數(shù)據(jù)挖掘中占有非常重要的地位。但是，在應用中，ID3算法不能夠處理連續(xù)屬性、計算信息增益時偏向于選擇取值較多的屬性等不足。