機器學(xué)習(xí)之決策樹學(xué)習(xí)課件

1機器學(xué)習(xí)

—決策樹學(xué)習(xí)1機器學(xué)習(xí)

—決策樹學(xué)習(xí)2決策樹學(xué)習(xí)概述決策樹學(xué)習(xí)的適用問題決策樹建樹算法決策樹學(xué)習(xí)中的假設(shè)空間搜索決策樹學(xué)習(xí)的歸納偏置決策樹學(xué)習(xí)的常見問題OUTLINE2決策樹學(xué)習(xí)概述OUTLINE3決策樹學(xué)習(xí)概述

決策樹歸納是歸納學(xué)習(xí)算法中最簡單也是最成功的算法之一——好的入門決策樹以事物的屬性描述集合作為輸入，輸出通常是一個分類(離散的輸出)——一般是二值分類(真或假)，是一種逼近離散值函數(shù)的方法3決策樹學(xué)習(xí)概述決策樹歸納是歸納學(xué)習(xí)算法中最簡單也是最成功4決策樹學(xué)習(xí)示例例子：星期六上午是否適合打網(wǎng)球?qū)傩?{outlook，Temperature,humidity，wind}屬性值={sunny,overcast,rain,hot,mild,cool,high,normal,strong,weak}4決策樹學(xué)習(xí)示例例子：星期六上午是否適合打網(wǎng)球5決策樹學(xué)習(xí)示例——訓(xùn)練樣例返回5決策樹學(xué)習(xí)示例——訓(xùn)練樣例返回6決策樹學(xué)習(xí)示例——決策樹表示

決策樹通過把實例從根節(jié)點排列到某個葉子節(jié)點來分類實例葉子節(jié)點即為實例所屬的分類樹上每個節(jié)點說明了對實例的某個屬性的測試節(jié)點的每個后繼分支對應(yīng)于該屬性的一個可能值HighNormal StrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes6決策樹學(xué)習(xí)示例——決策樹表示決策樹HighNo7OutlookWindHumiditySunnyOvercastRainHighNormal StrongWeakYesNoYesNoYes決策樹學(xué)習(xí)示例——決策樹未見實例:

<Outlook=Sunny,Temp=Warm,humidity=high,Wind=Strong>7OutlookWindHumiditySunnyOverc8決策樹學(xué)習(xí)示例——決策樹表示

決策樹代表實例屬性值約束的合取的析取式。從樹根到樹葉的每一條路徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這些合取的析取HighNormal StrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes8決策樹學(xué)習(xí)示例——決策樹表示決策樹代表實例屬性值約束的合9HighNormal StrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes決策樹學(xué)習(xí)示例——決策樹表示上面決策樹對應(yīng)于以下表達(dá)式:

（Outlook=sunny∧Humidity=normal）∨（Outlook=overcast)∨（Outlook=rain∧Wind=weak)9HighNormal Strong10決策樹學(xué)習(xí)概述決策樹學(xué)習(xí)的適用問題決策樹建樹算法決策樹學(xué)習(xí)中的假設(shè)空間搜索決策樹學(xué)習(xí)的歸納偏置決策樹學(xué)習(xí)的常見問題OUTLINE10決策樹學(xué)習(xí)概述OUTLINE11決策樹學(xué)習(xí)的適用問題決策樹適合具有以下特征的學(xué)習(xí)：實例是由“屬性-值”對表示的——固定的屬性+離散或連續(xù)的取值目標(biāo)函數(shù)具有離散的輸出值析取表達(dá)式訓(xùn)練數(shù)據(jù)可以包含錯誤——決策樹學(xué)習(xí)的魯棒性好訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例問題舉例根據(jù)疾病分類患者根據(jù)起因分類設(shè)備故障分類問題核心任務(wù)是把樣例分類到各可能的離散值對應(yīng)的類別11決策樹學(xué)習(xí)的適用問題決策樹適合具有以下特征的學(xué)習(xí)：12決策樹學(xué)習(xí)概述決策樹學(xué)習(xí)的適用問題決策樹建樹算法決策樹學(xué)習(xí)中的假設(shè)空間搜索決策樹學(xué)習(xí)的歸納偏置決策樹學(xué)習(xí)的常見問題OUTLINE12決策樹學(xué)習(xí)概述OUTLINE13決策樹建樹算法決策樹學(xué)習(xí)包括2個步驟：從實例中歸納出決策樹(建立決策樹)利用決策樹對新實例進(jìn)行分類判斷如何建立決策樹：大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表13決策樹建樹算法決策樹學(xué)習(xí)包括2個步驟：14決策樹建樹算法（1）ID3算法的基本思想：自頂向下構(gòu)造決策樹從“哪一個屬性將在樹的根節(jié)點被測試”開始使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓(xùn)練樣例的能力14決策樹建樹算法（1）ID3算法的基本思想：15決策樹建樹算法（2）ID3算法的構(gòu)造過程初始時，決策樹根節(jié)點包括所有的訓(xùn)練樣例分類能力最好的屬性被選作樹的根節(jié)點根節(jié)點的每個可能值產(chǎn)生一個分支，訓(xùn)練樣例排列到適當(dāng)?shù)姆种τ诿恳粋€分支，重復(fù)上面的過程算法的終止條件：所有的屬性已經(jīng)被這條路經(jīng)包括；與這個節(jié)點關(guān)聯(lián)的所有訓(xùn)練樣例都具有相同的目標(biāo)屬性值（即它們的熵為0）15決策樹建樹算法（2）16決策樹建樹算法（3）ID3(Examples,Target_attribute,Attributes)創(chuàng)建樹的root節(jié)點如果Examples都為正,返回label=+的單節(jié)點樹root如果Examples都為反,返回label=-的單節(jié)點樹root如果Attributes為空，那么返回單節(jié)點root，label=Examples中最普遍的Target_attribute值否則開始AAttributes中分類examples能力最好的屬性root的決策屬性A對于A的每個可能值vi在root下加一個新的分支對應(yīng)測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節(jié)點，節(jié)點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root16決策樹建樹算法（3）ID3(Examples,Targ17屬性選擇決策樹中的每個節(jié)點都代表一定的屬性，這些屬性如何在決策樹中排布是值得認(rèn)真研究的—決策樹建樹算法中的屬性選擇方案的目標(biāo)是為了最小化最終樹的深度，從而使用盡可能少的判斷步驟來分類某個實例在決策樹算法中，屬性排序以信息論中的熵概念為理論基礎(chǔ)—屬性提供的期望信息量17屬性選擇決策樹中的每個節(jié)點都代表一定的屬性，這些屬性如何18熵與不確定性信息論中用熵表示事物的不確定性，同時也是信息含量的表示——熵值越大，表示不確定性越大，同時信息量越多；反之則不確定性越小，信息量越小18熵與不確定性信息論中用熵表示事物的不確定性，同時也是信息19熵和決策樹Quinlan于1983年提出決策樹算法ID3時使用熵的概念來提高決策樹分類的效率：開始，決策樹的樹根對應(yīng)于最大的不確定狀態(tài)，表示在分類之前對被分類的對象一無所知隨著每個屬性的不斷判斷，向樹的葉子方向前進(jìn)，即相當(dāng)于選擇了其中的一棵子樹，其不確定狀態(tài)就減小了到達(dá)葉子節(jié)點，分類完成，此時不確定性為零19熵和決策樹Quinlan于1983年提出決策樹算法ID320要提高決策樹的分類效率，就相當(dāng)于要求熵值下降的更快/這樣，ID3算法的實質(zhì)就是構(gòu)造一棵熵值下降平均最快的決策樹熵值下降表明不確定性減小的思想可以應(yīng)用到許多情況，例如：自然語言中的各種歧義是一種不確定性，而從不確定性走向確定性就是歧義減小/如果不確定性消失也就是熵值為零，則說明已經(jīng)消除了歧義，選擇了某個明確的符號表示/因此可以應(yīng)用決策樹算法來消歧熵和決策樹（2）20要提高決策樹的分類效率，就相當(dāng)于要求熵值下降的更快/21熵和決策樹（3）用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為更一般地，如果目標(biāo)屬性具有c個不同的值，那么S相對于c個狀態(tài)的分類的熵定義為其中，p1是在S中正例的比例，p0是在S中反例的比例21熵和決策樹（3）用熵度量樣例的均一性其中，p1是在S中22熵和決策樹（4）熵值計算舉例：例如：“PlayTennis”中S是一個關(guān)于某布爾概念的14個樣例的集合，包括9個正例和5個反例[9+，5-]。那么S相對于這個布爾分類的熵為：訓(xùn)練數(shù)據(jù)集22熵和決策樹（4）熵值計算舉例：23熵和決策樹——熵函數(shù)變化曲線熵值分析：如果S的所有成員屬于同一類，那么S的熵為0如果S中正反樣例的數(shù)量相等時（或者：S中各類樣例等比例時），熵值為1如果S集合中正反例的數(shù)量不等時，熵介于0和1之間23熵和決策樹——熵函數(shù)變化曲線熵值分析：24信息增益用信息增益度量期望的熵降低屬性的信息增益（屬性分類訓(xùn)練數(shù)據(jù)的能力的度量標(biāo)準(zhǔn)），由于使用這個屬性分割樣例而導(dǎo)致的期望熵降低一個屬性A相對樣例集合S的信息增益Gain(S,A)為：其中，Values(A)是屬性A所有可能值得集合，Sv是S

中屬性A的值為v的子集上述等式中：第一項為原集合S的熵，第二項是用A分類S后熵的期望值即每個子集的熵的加權(quán)和。24信息增益用信息增益度量期望的熵降低其中，Values(A25上式中第二項的值應(yīng)該越小越好，因為越小說明S相對于屬性A作分解以后而造成的熵下降越快（根據(jù)前面的解釋，熵下降越快就是不確定性減少越快），換句話說Gain(S,A)越大越好決策樹建樹算法的要點是——在構(gòu)造決策樹的每一層次時，從尚未檢測的屬性中選擇信息增益Gain(S,A)大的屬性進(jìn)行分解信息增益（1）25上式中第二項的值應(yīng)該越小越好，因為越小說明S相對于屬性A26舉例——PlayTennis學(xué)習(xí)任務(wù)：星期六上午是否適合打網(wǎng)球目標(biāo)函數(shù)PlayTennis具有yes和no兩個值，我們將根據(jù)其它屬性來預(yù)測這個目標(biāo)函數(shù)值決策樹建樹算法第一步，創(chuàng)建決策樹的最頂端節(jié)點：哪個屬性在樹上第一個被測試呢？

ID3算法計算每一個候選屬性（Outlook,Temperature,

Humidity和Wind）的信息增益，然后選擇信息增益最高的一個。

26舉例——PlayTennis學(xué)習(xí)任務(wù)：星期六上午是否適合27舉例——PlayTennis（1）計算屬性Wind的信息增益Values(Wind)=Weak,Strong

S=[9+,5-]Sweak=[6+,2-]Sstrong=[3+,3-]信息增益

=Entropy(S)-(8/14)Entropy(Sweak)-(6/14)Entropy(Sstrong)=0.940-(8/14)0.811-(6/14)1.00=0.048S:[9+,5]

E=0.940

windweakstrong[6+,2][3+,3]E=0.811E=1.00Gain(S,Wind)=0.940(8/14)0.811(6/14)1.027舉例——PlayTennis（1）計算屬性Wind的信息28舉例——PlayTennis（2）同理，其它屬性的信息增益Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029根據(jù)信息增益標(biāo)準(zhǔn)，屬性O(shè)utlook在訓(xùn)練樣例上提供了對目標(biāo)函數(shù)PlayTennis的最好預(yù)測。所以，Outlook被選作根節(jié)點的決策屬性，并為它的每一個可能值在根節(jié)點下創(chuàng)建分支。28舉例——PlayTennis（2）同理，其它屬性的信息增29舉例——PlayTennis（3）{D1,D2,…,D14}S:[9+,5]

OutlookSunnyOvercastRain{D3,D7,D12,D13}[4+,0]

{D1,D2,D8,D9,D11}[2+,3]

{D4,D5,D6,D10,D14}[3+,2]

?哪一個屬性應(yīng)在這里被測試Yes?Ssunny={D1,D2,D8,D9,D11}Gain(Ssunny,Humidity)=0.970-(3/5)0.0-(2/5)0.0=0.970Gain(Ssunny,Temperature)=0.970-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.570Gain(Ssunny,Wind)=0.970-(2/5)1.0-(3/5)0.918=0.01929舉例——PlayTennis（3）{D1,D2,…,D130舉例——PlayTennis（4）上述決策樹構(gòu)建的終止條件：所有的屬性已經(jīng)被這條路經(jīng)包括；與這個節(jié)點關(guān)聯(lián)的所有訓(xùn)練樣例都具有相同的目標(biāo)屬性值（即它們的熵為0）30舉例——PlayTennis（4）上述決策樹構(gòu)建的終止條31練習(xí)著名的隱形眼鏡例子(Cendrowska給出)對于是否可配戴隱形眼鏡，可把人們分為3類：類1：適于配戴硬性隱形眼鏡；類2：適于配戴軟性隱形眼鏡；類3：不適于配戴隱形眼鏡為了判斷一個人是否適合配戴隱形眼鏡，需要檢查以下4種屬性：屬性a：配戴者年齡，取值a=<年青、早期老視、老視>屬性b：配戴者的視力缺陷，取值b=<近視、遠(yuǎn)視>屬性c：配戴者是否有散光，取值c=<是、否>屬性d：配戴者淚腺分泌情況，取值d=<少、正常>31練習(xí)著名的隱形眼鏡例子(Cendrowska給出)32隱形眼鏡例子（1）上述屬性和人群分類一律按順序用數(shù)字1,2…表示，可以假設(shè)根據(jù)屬性a、b、c、d有如下表的分類(純屬虛擬)32隱形眼鏡例子（1）上述屬性和人群分類一律按順序用數(shù)字1,33決策樹學(xué)習(xí)概述決策樹學(xué)習(xí)的適用問題決策樹建樹算法決策樹學(xué)習(xí)中的假設(shè)空間搜索決策樹學(xué)習(xí)的歸納偏置決策樹學(xué)習(xí)的常見問題OUTLINE33決策樹學(xué)習(xí)概述OUTLINE34決策樹學(xué)習(xí)中的假設(shè)空間搜索觀察ID3的搜索空間和搜索策略，認(rèn)識到這個算法的優(yōu)勢和不足假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間維護(hù)單一的當(dāng)前假設(shè)（不同于第二章的變型空間候選消除算法）不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步使用所有的訓(xùn)練樣例，不同于基于單獨的訓(xùn)練樣例遞增作出決定，容錯性增強34決策樹學(xué)習(xí)中的假設(shè)空間搜索觀察ID3的搜索空間和搜索策略35決策樹學(xué)習(xí)概述決策樹學(xué)習(xí)的適用問題決策樹建樹算法決策樹學(xué)習(xí)中的假設(shè)空間搜索決策樹學(xué)習(xí)的歸納偏置決策樹學(xué)習(xí)的常見問題OUTLINE35決策樹學(xué)習(xí)概述OUTLINE36決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些信息增益高的屬性離根節(jié)點較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根節(jié)點的樹優(yōu)先36決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略37限定偏置和優(yōu)選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個完整的假設(shè)空間，但不徹底地搜索這個空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對搜索空間的定義37限定偏置和優(yōu)選偏置ID3和候選消除算法的比較38限定偏置和優(yōu)選偏置優(yōu)選偏置ID3的歸納偏置是對某種假設(shè)勝過其他假設(shè)的一種優(yōu)選，對最終可列舉的假設(shè)沒有硬性限制限定偏置候選消除算法的偏置是對待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要優(yōu)選偏置和限定偏置的結(jié)合例如：第一章中描述的下棋程序38限定偏置和優(yōu)選偏置優(yōu)選偏置39決策樹學(xué)習(xí)概述決策樹學(xué)習(xí)的適用問題決策樹建樹算法決策樹學(xué)習(xí)中的假設(shè)空間搜索決策樹學(xué)習(xí)的歸納偏置決策樹學(xué)習(xí)的常見問題OUTLINE39決策樹學(xué)習(xí)概述OUTLINE40決策樹學(xué)習(xí)的常見問題確定決策樹增長的深度處理連續(xù)值的屬性處理屬性值不完整的訓(xùn)練數(shù)據(jù)40決策樹學(xué)習(xí)的常見問題確定決策樹增長的深度41問題1：避免過度擬和數(shù)據(jù)過度擬合對于一個假設(shè)，當(dāng)存在其他的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例定義：給定一個假設(shè)空間H，一個假設(shè)hH，如果存在其他的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。41問題1：避免過度擬和數(shù)據(jù)過度擬合42問題1：避免過度擬和數(shù)據(jù)（1）導(dǎo)致過度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機錯誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點時，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標(biāo)函數(shù)并無關(guān)系。例如：見下頁42問題1：避免過度擬和數(shù)據(jù)（1）導(dǎo)致過度擬合的原因43問題1：避免過度擬和數(shù)據(jù)（1）HighNormal StrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes訓(xùn)練樣例集中加入一條訓(xùn)練正例，但被錯誤標(biāo)示為反例:

<Outlook=Sunny,Temp=Warm,humidity=Normal,Wind=Strong，PlayTennis=no>43問題1：避免過度擬和數(shù)據(jù)（1）HighNorm44問題1：避免過度擬和數(shù)據(jù)（2）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀，但是精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功44問題1：避免過度擬和數(shù)據(jù)（2）避免過度擬合的方法45問題1：避免過度擬和數(shù)據(jù)（3）后修剪法：錯誤率降低修剪該方法考慮將樹上的每一個節(jié)點作為修剪的候選對象。修剪一個節(jié)點的步驟：1刪除此節(jié)點為根的子樹，使它成為葉子節(jié)點2把和該節(jié)點關(guān)