12決策樹(shù)學(xué)習(xí)

1、第1.2節(jié) 決策樹(shù)學(xué)習(xí)(Decision Tree)1內(nèi)容決策樹(shù)方法的原理決策樹(shù)中的過(guò)擬合問(wèn)題決策樹(shù)的其他問(wèn)題屬性的其他度量2決策樹(shù)學(xué)習(xí)決定是否打網(wǎng)球看看天氣看看濕度陽(yáng)光明媚下雨看看風(fēng)速高正常不去打球去打球大小不去打球去打球節(jié)點(diǎn)：每一個(gè)節(jié)點(diǎn)測(cè)試一個(gè)屬性,分支：屬性的可選數(shù)值,葉子節(jié)點(diǎn)：最終預(yù)測(cè)去打球陰天3決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)node = root 循環(huán) 1. 為當(dāng)下一個(gè)節(jié)點(diǎn)選擇一個(gè)最好的屬性 x 2. 將屬性x分配給節(jié)點(diǎn)node 3. 對(duì)于x的所有可能數(shù)值,創(chuàng)立一個(gè)降序排列的節(jié)點(diǎn)node 4. 將所有訓(xùn)練樣本在葉子節(jié)點(diǎn)排序分類(lèi) 5. 如果分類(lèi)結(jié)果到達(dá)了錯(cuò)誤率要求,跳出循

2、環(huán),否則, 在葉子節(jié)點(diǎn)開(kāi)始新循環(huán)-遞歸4決策樹(shù)表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類(lèi)實(shí)例。葉子節(jié)點(diǎn)即為實(shí)例所屬的分類(lèi)樹(shù)上每個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值決策樹(shù)代表實(shí)例屬性值約束的合取的析取式。從樹(shù)葉到樹(shù)根的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取,樹(shù)本身對(duì)應(yīng)這些合取的析取。5決策樹(shù)學(xué)習(xí)的適用問(wèn)題適用問(wèn)題的特征實(shí)例由“屬性-值對(duì)表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例問(wèn)題舉例根據(jù)天氣好壞確定是否去打球根據(jù)疾病分類(lèi)患者根據(jù)起因分類(lèi)設(shè)備故障根據(jù)拖欠支付的可能性分類(lèi)貸款申請(qǐng)分類(lèi)問(wèn)題核心任務(wù)是

3、把樣例分類(lèi)到各可能的離散值對(duì)應(yīng)的類(lèi)別6根本的決策樹(shù)學(xué)習(xí)算法大多數(shù)決策樹(shù)學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間ID3是這種算法的代表7根本的決策樹(shù)學(xué)習(xí)算法ID3的思想自頂向下構(gòu)造決策樹(shù)從“哪一個(gè)屬性將在樹(shù)的根節(jié)點(diǎn)被測(cè)試開(kāi)始使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類(lèi)訓(xùn)練樣例的能力ID3的過(guò)程分類(lèi)能力最好的屬性被選作樹(shù)的根節(jié)點(diǎn)根節(jié)點(diǎn)的每個(gè)可能值產(chǎn)生一個(gè)分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過(guò)程8決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)編號(hào)天氣溫度濕度風(fēng)是否去打球1晴天炎熱高弱不去2晴天炎熱高強(qiáng)不去3陰天炎熱高弱去4下雨適中高弱去5下雨寒冷正常弱去6下雨寒冷正常強(qiáng)不去

4、7陰天寒冷正常強(qiáng)去8晴天適中高弱不去9晴天寒冷正常弱去10下雨適中正常弱去11晴天適中正常強(qiáng)去12陰天適中高強(qiáng)去13陰天炎熱正常弱去14下雨適中高強(qiáng)不去表-1：是否去打球的數(shù)據(jù)統(tǒng)計(jì)訓(xùn)練數(shù)據(jù)9決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)濕度高正常(3+, 4-)(6+, 1-)S: (9+, 5-)風(fēng) 弱強(qiáng)(6+, 2-)(3+, 3-)S: (9+, 5-)問(wèn)題：哪一個(gè)屬性（特征）更好？10決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)熵:物理學(xué)概念宏觀上：熱力學(xué)定律體系的熵變等于可逆過(guò)程吸收或耗散的熱量除以它的絕對(duì)溫度（克勞修斯,1865）微觀上：熵是大量微觀粒子的位置和速度的分布概率的函數(shù),

5、是描述系統(tǒng)中大量微觀粒子的無(wú)序性的宏觀參數(shù)（波爾茲曼,1872）結(jié)論：熵是描述事物無(wú)序性的參數(shù),熵越大則無(wú)序性越強(qiáng),在信息領(lǐng)域定義為“熵越大,不確定性越大（香濃,1948年）11決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)隨機(jī)變量的熵 熵 比較多的用于信源編碼,數(shù)據(jù)壓縮,假設(shè)是最有效的編碼方式是使用 位編碼于是對(duì)于隨即變量的最有效編碼位之和：12決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)表示訓(xùn)練集合中的樣本表示訓(xùn)練集合中反例樣本的比例表示訓(xùn)練集合中正例樣本的比例表示訓(xùn)練集合的熵13決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)信息增益：information gain信息的增加意味著不確定性的

6、減少,也就是熵的減小,信息增益在諸多系統(tǒng)中定義為：在某一個(gè)操作之前的系統(tǒng)熵與操作之后的系統(tǒng)熵的差值,也即是不確定性的減小量14信息增益(Information Gain)原來(lái)的不確定性知道x之后的不確定性信息增益: 原來(lái)-知道x之后的原來(lái)不確定性-經(jīng)過(guò)屬性x劃分以后的不確定性15信息增益(Information Gain)選擇屬性的標(biāo)準(zhǔn)：選擇具有最高信息增益(Information Gain)的屬性假設(shè)有兩個(gè)類(lèi), + 和 -假設(shè)集合S中含有p個(gè)類(lèi)別為+的樣本,n個(gè)類(lèi)別為-的樣本將S中已知樣本進(jìn)行分類(lèi)所需要的期望信息定義為:16信息增益在決策樹(shù)中的使用假設(shè)屬性x將把集合S劃分成 K份 S1, S

7、2 , , SK 如果 Si 中包含 pi 個(gè)類(lèi)別為 “+的樣本, ni 個(gè)類(lèi)別為 “-,的樣本。那么熵就是 (entropy),在x上進(jìn)行決策分枝所獲得的信息增益為:17決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)*18決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)問(wèn)題：哪一個(gè)屬性（特征）更好？分析極端的情況溫度高正常(4+, 4-)(4+, 4-)S: (8+, 8-)心情 好壞(8+, 0-)(0+,8-)S: (8+, 8-)E=1.0E=0.0E=0.0Gain(S, 溫度）=1.0-（8/16)*1.0-（8/16）*1.0=0.0Gain(S, 心情）=1.0-(8/16)*0.0

8、-(8/16)*0.0=1.0E=1.0E=1.019決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)濕度高正常(3+, 4-)(6+, 1-)S: (9+, 5-)風(fēng) 弱強(qiáng)(6+, 2-)(3+, 3-)S: (9+, 5-)問(wèn)題：哪一個(gè)屬性（特征）更好？I=0.985I=0.592I=0.811I=1.00Gain(S, 濕度）=0.940-（7/14).985-7/14*0.592=0.151Gain(S, 風(fēng)）=0.940-(8/14).811-(6/14)1.0=0.048E=0.940E=0.94020決策樹(shù)學(xué)習(xí)原理簡(jiǎn)介(ID3, C4.5算法)決策樹(shù)的構(gòu)造過(guò)程示意x1x3x8x3x7

9、+-+-+-21決策樹(shù)學(xué)習(xí)將樹(shù)轉(zhuǎn)化為規(guī)則 將樹(shù)轉(zhuǎn)化為規(guī)則集合測(cè)試規(guī)則是否相互矛盾 將規(guī)則排序存儲(chǔ)Tree:If(陰天）-去打球If（晴天）If（風(fēng)速低）-去打球Else -不去打球22決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題決策樹(shù)學(xué)習(xí)的實(shí)際問(wèn)題確定決策樹(shù)增長(zhǎng)的深度處理連續(xù)值的屬性選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價(jià)的屬性提高計(jì)算效率針對(duì)這些問(wèn)題,ID3被擴(kuò)展成C4.523決策樹(shù)學(xué)習(xí)及over-fitting看看天氣看看濕度陽(yáng)光明媚下雨看看風(fēng)速高正常不去打球去打球大小不去打球去打球去打球陰天1晴天炎熱高強(qiáng)去打球增加一個(gè)錯(cuò)誤樣本24決策樹(shù)學(xué)習(xí)及over-fitting過(guò)度擬合對(duì)于一個(gè)假

10、設(shè),當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差,但事實(shí)上在實(shí)例的整個(gè)分布上表現(xiàn)得卻更好時(shí),我們說(shuō)這個(gè)假設(shè)過(guò)度擬合訓(xùn)練樣例定義：給定一個(gè)假設(shè)空間H,一個(gè)假設(shè)hH,如果存在其他的假設(shè)hH,使得在訓(xùn)練樣例上h的錯(cuò)誤率比h小,但在整個(gè)實(shí)例分布上h的錯(cuò)誤率比h小,那么就說(shuō)假設(shè)h過(guò)度擬合訓(xùn)練數(shù)據(jù)。25決策樹(shù)學(xué)習(xí)及over-fitting導(dǎo)致過(guò)度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機(jī)錯(cuò)誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒(méi)有噪聲時(shí),過(guò)度擬合也有可能發(fā)生,特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí),很可能出現(xiàn)巧合的規(guī)律性,使得一些屬性恰巧可以很好地分割樣例,但卻與實(shí)際的目標(biāo)函數(shù)并無(wú)關(guān)系。26決策樹(shù)學(xué)習(xí)及over-fitting假設(shè)在訓(xùn)

11、練樣本集合上的錯(cuò)誤率為樣本集合上的真實(shí)錯(cuò)誤率為訓(xùn)練結(jié)果在如下情況下即會(huì)產(chǎn)生過(guò)擬合27決策樹(shù)學(xué)習(xí)及over-fitting28決策樹(shù)學(xué)習(xí)及over-fitting防止過(guò)擬合的方法如果對(duì)數(shù)據(jù)劃分沒(méi)有明顯好處的屬性不選擇,同時(shí)不再將決策數(shù)細(xì)分構(gòu)建完成整個(gè)樹(shù)以后進(jìn)行剪枝Prune在訓(xùn)練數(shù)據(jù)上測(cè)量性能在交叉驗(yàn)證數(shù)據(jù)上測(cè)量性能MDLMinmize(Size(tree)+Size(misclassifications(tree) 29決策樹(shù)學(xué)習(xí)及over-fitting防止過(guò)擬合的方法 評(píng)估所生成的新節(jié)點(diǎn)對(duì)于Validation 數(shù)據(jù)集合的性能生成一些節(jié)點(diǎn)很少但是性能很好的“Sub-tree30決策樹(shù)學(xué)習(xí)及

12、over-fitting防止過(guò)度擬合的方法及早停止樹(shù)增長(zhǎng)后修剪法兩種方法的特點(diǎn)第一種方法更直觀第一種方法中,精確地估計(jì)何時(shí)停止樹(shù)增長(zhǎng)很困難第二種方法被證明在實(shí)踐中更成功31決策樹(shù)學(xué)習(xí)及over-fitting防止過(guò)度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來(lái)確定最終正確樹(shù)的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套別離的樣例,來(lái)評(píng)估通過(guò)后修剪方法從樹(shù)上修建節(jié)點(diǎn)的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練,但進(jìn)行統(tǒng)計(jì)測(cè)試來(lái)估計(jì)擴(kuò)展（或修剪）一個(gè)特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。使用一個(gè)明確的標(biāo)準(zhǔn)來(lái)衡量訓(xùn)練樣例和決策樹(shù)的復(fù)雜度,當(dāng)這個(gè)編碼的長(zhǎng)度最小時(shí)停止樹(shù)增長(zhǎng)。32決策樹(shù)學(xué)習(xí)及over-fitting方法評(píng)

13、述第一種方法是最普通的,常被稱(chēng)為訓(xùn)練和驗(yàn)證集法?？捎脭?shù)據(jù)分成兩個(gè)樣例集合：訓(xùn)練集合,形成學(xué)習(xí)到的假設(shè)驗(yàn)證集合,評(píng)估這個(gè)假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動(dòng)機(jī)：即使學(xué)習(xí)器可能會(huì)被訓(xùn)練集合誤導(dǎo),但驗(yàn)證集合不大可能表現(xiàn)出同樣的隨機(jī)波動(dòng)驗(yàn)證集合應(yīng)該足夠大,以便它本身可提供具有統(tǒng)計(jì)意義的實(shí)例樣本。常見(jiàn)的做法是,樣例的三分之二作訓(xùn)練集合,三分之一作驗(yàn)證集合。33訓(xùn)練誤差升高修剪將樹(shù)上的每一個(gè)節(jié)點(diǎn)作為修剪候選對(duì)象修剪步驟刪除以此節(jié)點(diǎn)為根的子樹(shù),使它成為葉結(jié)點(diǎn)把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見(jiàn)分類(lèi)賦給它反復(fù)修剪節(jié)點(diǎn),每次總是選取那些刪除后可以最大提高決策樹(shù)在驗(yàn)證集合上的精度的節(jié)點(diǎn)繼續(xù)修剪,直到進(jìn)一步的修剪是有害的為止

14、數(shù)據(jù)分成3個(gè)子集訓(xùn)練樣例,形成決策樹(shù)驗(yàn)證樣例,修剪決策樹(shù)測(cè)試樣例,精度的無(wú)偏估計(jì)如果有大量的數(shù)據(jù)可供使用,那么使用別離的數(shù)據(jù)集合來(lái)引導(dǎo)修剪34規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹(shù),增長(zhǎng)決策樹(shù)直到盡可能好地?cái)M合訓(xùn)練數(shù)據(jù),允許過(guò)度擬合發(fā)生將決策樹(shù)轉(zhuǎn)化為等價(jià)的規(guī)則集合,方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)立一條規(guī)則通過(guò)“任何能導(dǎo)致估計(jì)精度提高的前提來(lái)修剪每一條規(guī)則按照修剪過(guò)的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序,并按這樣的順序應(yīng)用這些規(guī)則來(lái)分類(lèi)后來(lái)的實(shí)例35規(guī)則后修剪規(guī)則精度估計(jì)方法使用與訓(xùn)練集不相交的驗(yàn)證集基于訓(xùn)練集合本身被C4.5使用,使用一種保守估計(jì)來(lái)彌補(bǔ)訓(xùn)練數(shù)據(jù)有利于當(dāng)前規(guī)則的估計(jì)偏置過(guò)程先計(jì)算規(guī)則在

15、它應(yīng)用的訓(xùn)練樣例上的精度然后假定此估計(jì)精度為二項(xiàng)式分布,并計(jì)算它的標(biāo)準(zhǔn)差對(duì)于一個(gè)給定的置信區(qū)間,采用下界估計(jì)作為規(guī)則性能的度量評(píng)論對(duì)于大的數(shù)據(jù)集,保守預(yù)測(cè)非常接近觀察精度,隨著數(shù)據(jù)集合的減小,離觀察精度越來(lái)越遠(yuǎn)不是統(tǒng)計(jì)有效,但是實(shí)踐中發(fā)現(xiàn)有效36規(guī)則后修剪把決策樹(shù)轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點(diǎn)使用的不同上下文消除了根節(jié)點(diǎn)附近的屬性測(cè)試和葉節(jié)點(diǎn)附近的屬性測(cè)試的區(qū)別提高了可讀性37合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹(shù)要預(yù)測(cè)的目標(biāo)屬性必須是離散的樹(shù)的決策節(jié)點(diǎn)的屬性也必須是離散的簡(jiǎn)單刪除上面第2個(gè)限制的方法通過(guò)動(dòng)態(tài)地定義新的離散值屬性來(lái)實(shí)現(xiàn),即先把連續(xù)值屬性的值域分割為離散的區(qū)

16、間集合38合并連續(xù)值屬性例,Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性選擇產(chǎn)生最大信息增益的閾值按照連續(xù)屬性排列樣例,確定目標(biāo)分類(lèi)不同的相鄰實(shí)例產(chǎn)生一組候選閾值,它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過(guò)計(jì)算與每個(gè)候選閾值關(guān)聯(lián)的信息增益評(píng)估這些候選值方法的擴(kuò)展連續(xù)的屬性分割成多個(gè)區(qū)間,而不是單一閾值的兩個(gè)空間39屬性選擇的其他度量標(biāo)準(zhǔn)信息增益度量存在一個(gè)內(nèi)在偏置,偏向具有較多值的屬性防止方法,其他度量,比方增益比率增益比率通過(guò)參加一個(gè)被稱(chēng)作分裂信息的項(xiàng)來(lái)懲罰多值屬性,分裂信息用來(lái)衡量屬性分裂數(shù)據(jù)的廣度和均勻性Spli

17、tInformation(S,A)=GainRatio(S,A)=分裂信息項(xiàng)阻礙選擇值為均勻分布的屬性問(wèn)題,當(dāng)某個(gè)SiS。解決方法：采用一些啟發(fā)式規(guī)則, 比方僅對(duì)增益高過(guò)平均值的屬性應(yīng)用增益比率測(cè)試40決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索屬性分段觀察ID3的搜索空間和搜索策略,認(rèn)識(shí)到這個(gè)算法的優(yōu)勢(shì)假設(shè)空間包含所有的決策樹(shù),它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間維護(hù)單一的當(dāng)前假設(shè),不進(jìn)行回溯,能收斂到局部最優(yōu)每一步使用所有的訓(xùn)練樣例,不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定,容錯(cuò)性增強(qiáng)41決策樹(shù)學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹(shù)選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹(shù)很難準(zhǔn)確刻畫(huà)ID3的歸

18、納偏置近似的ID3的歸納偏置較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先近似在于ID3得到局部最優(yōu),而不一定是全局最優(yōu)一個(gè)精確具有這個(gè)歸納偏置的算法,BFS-ID3更貼切近似的歸納偏置較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先,信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù)優(yōu)先42為什么短的假設(shè)優(yōu)先ID3的歸納偏置的直觀根底奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡(jiǎn)單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運(yùn)動(dòng)的簡(jiǎn)單假設(shè)簡(jiǎn)單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少簡(jiǎn)單假設(shè)對(duì)訓(xùn)練樣例的針對(duì)性更小,更像是泛化的規(guī)律,而不是訓(xùn)練樣例的另一種描述43屬性選擇的其他度量標(biāo)準(zhǔn)基于距離的度量定義了數(shù)據(jù)劃分間的一種距離尺度計(jì)算每個(gè)屬性產(chǎn)生的劃分與理想劃分間的距離Lopez de Mantaras定義了這個(gè)距離度量,證明了它不偏向有大量值的屬性Mingers實(shí)驗(yàn),不同的屬性選擇度量對(duì)最終精度的影響小于后修剪的程度和方法的影響44缺少屬性值的訓(xùn)練樣例例子,醫(yī)學(xué)領(lǐng)域,很多待測(cè)屬性無(wú)法觀測(cè)經(jīng)常需要根據(jù)此屬性值已知實(shí)例來(lái)估計(jì)這個(gè)缺少的屬性值一種策略,給它節(jié)點(diǎn)n的訓(xùn)練樣例中該屬性的最常見(jiàn)值另一種策略是賦給它節(jié)點(diǎn)n的被分類(lèi)為c(