決策樹學(xué)習(xí)-機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)第3章決策樹學(xué)習(xí)1概論決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一是一種逼近離散值函數(shù)的方法很好的健壯性能夠?qū)W習(xí)析取表達(dá)式ID3,Assistant,C4.5搜索一個(gè)完整表示的假設(shè)空間歸納偏置是優(yōu)先選擇較小的樹決策樹表示了多個(gè)if-then規(guī)則2提綱決策樹定義適用問題特征基本ID3算法決策樹學(xué)習(xí)的歸納偏置訓(xùn)練數(shù)據(jù)的過度擬合更深入的話題3決策樹表示法決策樹通過把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來分類實(shí)例。葉子節(jié)點(diǎn)即為實(shí)例所屬的分類樹上每個(gè)節(jié)點(diǎn)說明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值圖3-1決策樹代表實(shí)例屬性值約束的合取的析取式。從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹本身對(duì)應(yīng)這些合取的析取。4決策樹學(xué)習(xí)的適用問題適用問題的特征實(shí)例由“屬性-值”對(duì)表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例問題舉例根據(jù)疾病分類患者根據(jù)起因分類設(shè)備故障根據(jù)拖欠支付的可能性分類貸款申請(qǐng)分類問題核心任務(wù)是把樣例分類到各可能的離散值對(duì)應(yīng)的類別5基本的決策樹學(xué)習(xí)算法大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表6基本的決策樹學(xué)習(xí)算法（2）ID3的思想自頂向下構(gòu)造決策樹從“哪一個(gè)屬性將在樹的根節(jié)點(diǎn)被測(cè)試”開始使用統(tǒng)計(jì)測(cè)試來確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力ID3的過程分類能力最好的屬性被選作樹的根節(jié)點(diǎn)根節(jié)點(diǎn)的每個(gè)可能值產(chǎn)生一個(gè)分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過程7表3-1用于學(xué)習(xí)布爾函數(shù)的ID3算法概要ID3(Examples,Target_attribute,Attributes)創(chuàng)建樹的root節(jié)點(diǎn)如果Examples都為正,返回label=+的單節(jié)點(diǎn)樹root如果Examples都為反,返回label=-的單節(jié)點(diǎn)樹root如果Attributes為空，那么返回單節(jié)點(diǎn)root，label=Examples中最普遍的Target_attribute值否則開始AAttributes中分類examples能力最好的屬性root的決策屬性A對(duì)于A的每個(gè)可能值vi在root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個(gè)新分支下加一個(gè)葉子節(jié)點(diǎn)，節(jié)點(diǎn)的label=Examples中最普遍的Target_attribute值否則在新分支下加一個(gè)子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root8最佳分類屬性信息增益用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為 Entropy(S)=-p+log2p+-p-log2p-信息論中對(duì)熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進(jìn)制位數(shù)更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為 Entropy(S)=9最佳分類屬性（2）用信息增益度量期望的熵降低屬性的信息增益，由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低

Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)例子10ID3算算法法舉舉例例表3-2…繼續(xù)這個(gè)個(gè)過程，，直到滿滿足以下下兩個(gè)條條件中的的一個(gè)所有的屬屬性已經(jīng)經(jīng)被這條條路經(jīng)包包括與這個(gè)節(jié)節(jié)點(diǎn)關(guān)聯(lián)聯(lián)的所有有訓(xùn)練樣樣例都具具有相同同的目標(biāo)標(biāo)屬性值值11決策樹學(xué)學(xué)習(xí)中的的假設(shè)空空間搜索索觀察ID3的搜搜索空間間和搜索索策略，，認(rèn)識(shí)到到這個(gè)算算法的優(yōu)優(yōu)勢(shì)和不不足假設(shè)空間間包含所所有的決決策樹，，它是關(guān)關(guān)于現(xiàn)有有屬性的的有限離離散值函函數(shù)的一一個(gè)完整整空間維護(hù)單一一的當(dāng)前前假設(shè)（（不同于于第二章章的變型型空間候候選消除除算法））不進(jìn)行回回溯，可可能收斂斂到局部部最優(yōu)每一步使使用所有有的訓(xùn)練練樣例，，不同于于基于單單獨(dú)的訓(xùn)訓(xùn)練樣例例遞增作作出決定定，容錯(cuò)錯(cuò)性增強(qiáng)強(qiáng)12決策樹學(xué)學(xué)習(xí)的歸歸納偏置置ID3的的搜索策策略優(yōu)先選擇擇較短的的樹選擇那些些信息增增益高的的屬性離離根節(jié)點(diǎn)點(diǎn)較近的的樹很難準(zhǔn)確確刻畫ID3的的歸納偏偏置近似的ID3的的歸納偏偏置較短的樹樹比較長長的樹優(yōu)優(yōu)先近似在于于ID3得到局局部最優(yōu)優(yōu)，而不不一定是是全局最最優(yōu)一個(gè)精確確具有這這個(gè)歸納納偏置的的算法，，BFS-ID3更貼切近近似的歸歸納偏置置較短的樹樹比較長長的樹優(yōu)優(yōu)先，信信息增益益高的屬屬性更靠靠近根節(jié)節(jié)點(diǎn)的樹樹優(yōu)先13限定偏置置和優(yōu)選選偏置ID3和和候選消消除算法法的比較較ID3的的搜索范范圍是一一個(gè)完整整的假設(shè)設(shè)空間，，但不徹徹底地搜搜索這個(gè)個(gè)空間候選消除除算法的的搜索范范圍是不不完整的的假設(shè)空空間，但但徹底地地搜索這這個(gè)空間間ID3的的歸納偏偏置完全全是搜索索策略排排序假設(shè)設(shè)的結(jié)果果，來自自搜索策策略候選消除除算法完完全是假假設(shè)表示示的表達(dá)達(dá)能力的的結(jié)果，，來自對(duì)對(duì)搜索空空間的定定義14限定偏置置和優(yōu)選選偏置優(yōu)選偏置置ID3的的歸納偏偏置是對(duì)對(duì)某種假假設(shè)勝過過其他假假設(shè)的一一種優(yōu)選選，對(duì)最最終可列列舉的假假設(shè)沒有有硬性限限制限定偏置置候選消除除算法的的偏置是是對(duì)待考考慮假設(shè)設(shè)的一種種限定通常優(yōu)選選偏置比比限定偏偏置更符符合歸納納學(xué)習(xí)的的需要優(yōu)選偏置置和限定定偏置的的結(jié)合考慮第1章的例例子15為什么短短的假設(shè)設(shè)優(yōu)先ID3的的歸納偏偏置的哲哲學(xué)基礎(chǔ)礎(chǔ)奧坎姆剃剃刀優(yōu)先選擇擇擬合數(shù)數(shù)據(jù)的最最簡(jiǎn)單的的假設(shè)科學(xué)上的的例子物理學(xué)家家優(yōu)先選選擇行星星運(yùn)動(dòng)的的簡(jiǎn)單假假設(shè)簡(jiǎn)單假設(shè)設(shè)的數(shù)量量遠(yuǎn)比復(fù)復(fù)雜假設(shè)設(shè)的數(shù)量量少簡(jiǎn)單假設(shè)設(shè)對(duì)訓(xùn)練練樣例的的針對(duì)性性更小，，更像是是泛化的的規(guī)律，，而不是是訓(xùn)練樣樣例的另另一種描描述16為什么短短的假設(shè)設(shè)優(yōu)先奧坎姆剃剃刀的困困難我們反問問，使用用上頁的的推理，，應(yīng)該優(yōu)優(yōu)先選擇擇包含恰恰好17個(gè)葉子子節(jié)點(diǎn)和和11個(gè)個(gè)非葉子子節(jié)點(diǎn)的的決策樹樹？假設(shè)的規(guī)規(guī)模由學(xué)學(xué)習(xí)器內(nèi)內(nèi)部使用用的特定定表示決決定從生物進(jìn)進(jìn)化的觀觀點(diǎn)看內(nèi)內(nèi)部表示示和奧坎坎姆剃刀刀原則17決策樹學(xué)學(xué)習(xí)的常常見問題題決策樹學(xué)學(xué)習(xí)的實(shí)實(shí)際問題題確定決策策樹增長長的深度度處理連續(xù)續(xù)值的屬屬性選擇一個(gè)個(gè)適當(dāng)?shù)牡膶傩院Y篩選度量量標(biāo)準(zhǔn)處理屬性性值不完完整的訓(xùn)訓(xùn)練數(shù)據(jù)據(jù)處理不同同代價(jià)的的屬性提高計(jì)算算效率針對(duì)這些些問題，，ID3被擴(kuò)展展成C4.518避免過度度擬合數(shù)數(shù)據(jù)過度擬合合對(duì)于一個(gè)個(gè)假設(shè)，，當(dāng)存在在其他的的假設(shè)對(duì)對(duì)訓(xùn)練樣樣例的擬擬合比它它差，但但事實(shí)上上在實(shí)例例的整個(gè)個(gè)分布上上表現(xiàn)得得卻更好好時(shí)，我我們說這這個(gè)假設(shè)設(shè)過度擬擬合訓(xùn)練練樣例定義：給給定一個(gè)個(gè)假設(shè)空空間H，，一個(gè)假假設(shè)hH，如果果存在其其他的假假設(shè)h’’H，使得得在訓(xùn)練練樣例上上h的錯(cuò)錯(cuò)誤率比比h’小小，但在在整個(gè)實(shí)實(shí)例分布布上h’’的錯(cuò)誤誤率比h小，那那么就說說假設(shè)h過度擬擬合訓(xùn)練練數(shù)據(jù)。。圖3-6的例子子19避免過度度擬合數(shù)數(shù)據(jù)（2）導(dǎo)致過度度擬合的的原因一種可能能原因是是訓(xùn)練樣樣例含有有隨機(jī)錯(cuò)錯(cuò)誤或噪噪聲當(dāng)訓(xùn)練數(shù)數(shù)據(jù)沒有有噪聲時(shí)時(shí)，過度度擬合也也有可能能發(fā)生，，特別是是當(dāng)少量量的樣例例被關(guān)聯(lián)聯(lián)到葉子子節(jié)點(diǎn)時(shí)時(shí)，很可可能出現(xiàn)現(xiàn)巧合的的規(guī)律性性，使得得一些屬屬性恰巧巧可以很很好地分分割樣例例，但卻卻與實(shí)際際的目標(biāo)標(biāo)函數(shù)并并無關(guān)系系。20避免過度度擬合數(shù)數(shù)據(jù)（3）避免過度度擬合的的方法及早停止止樹增長長后修剪法法兩種方法法的特點(diǎn)點(diǎn)第一種方方法更直直觀第一種方方法中，，精確地地估計(jì)何何時(shí)停止止樹增長長很困難難第二種方方法被證證明在實(shí)實(shí)踐中更更成功21避免過度度擬合數(shù)數(shù)據(jù)（4）避免過度度擬合的的關(guān)鍵使用什么么樣的準(zhǔn)準(zhǔn)則來確確定最終終正確樹樹的規(guī)模模解決方法法使用與訓(xùn)訓(xùn)練樣例例截然不不同的一一套分離離的樣例例，來評(píng)評(píng)估通過過后修剪剪方法從從樹上修修建節(jié)點(diǎn)點(diǎn)的效用用。使用所有有可用數(shù)數(shù)據(jù)進(jìn)行行訓(xùn)練，，但進(jìn)行行統(tǒng)計(jì)測(cè)測(cè)試來估估計(jì)擴(kuò)展展（或修修剪）一一個(gè)特定定的節(jié)點(diǎn)點(diǎn)是否有有可能改改善在訓(xùn)訓(xùn)練集合合外的實(shí)實(shí)例上的的性能。。使用一個(gè)個(gè)明確的的標(biāo)準(zhǔn)來來衡量訓(xùn)訓(xùn)練樣例例和決策策樹的復(fù)復(fù)雜度，，當(dāng)這個(gè)個(gè)編碼的的長度最最小時(shí)停停止樹增增長。22避免過度度擬合數(shù)數(shù)據(jù)（5）方法評(píng)述述第一種方方法是最最普通的的，常被被稱為訓(xùn)訓(xùn)練和驗(yàn)驗(yàn)證集法法?？捎脭?shù)據(jù)據(jù)分成兩兩個(gè)樣例例集合：：訓(xùn)練集合合，形成成學(xué)習(xí)到到的假設(shè)設(shè)驗(yàn)證集合合，評(píng)估估這個(gè)假假設(shè)在后后續(xù)數(shù)據(jù)據(jù)上的精精度方法的動(dòng)動(dòng)機(jī)：即即使學(xué)習(xí)習(xí)器可能能會(huì)被訓(xùn)訓(xùn)練集合合誤導(dǎo)，，但驗(yàn)證證集合不不大可能能表現(xiàn)出出同樣的的隨機(jī)波波動(dòng)驗(yàn)證集合合應(yīng)該足足夠大，，以便它它本身可可提供具具有統(tǒng)計(jì)計(jì)意義的的實(shí)例樣樣本。常見的做做法是，，樣例的的三分之之二作訓(xùn)訓(xùn)練集合合，三分分之一作作驗(yàn)證集集合。23錯(cuò)誤率降降低修剪剪將樹上的的每一個(gè)個(gè)節(jié)點(diǎn)作作為修剪剪得候選選對(duì)象修剪步驟驟刪除以此此節(jié)點(diǎn)為為根的子子樹，使使它成為為葉結(jié)點(diǎn)點(diǎn)把和該節(jié)節(jié)點(diǎn)關(guān)聯(lián)聯(lián)的訓(xùn)練練樣例的的最常見見分類賦賦給它反復(fù)修剪剪節(jié)點(diǎn)，，每次總總是選取取那些刪刪除后可可以最大大提高決決策樹在在驗(yàn)證集集合上的的精度的的節(jié)點(diǎn)繼續(xù)修剪剪，直到到進(jìn)一步步的修剪剪是有害害的為止止數(shù)據(jù)分成成3個(gè)子子集訓(xùn)練樣例例，形成成決策樹樹驗(yàn)證樣例例，修剪剪決策樹樹測(cè)試樣例例，精度度的無偏偏估計(jì)如果有大大量的數(shù)數(shù)據(jù)可供供使用，，那么使使用分離離的數(shù)據(jù)據(jù)集合來來引導(dǎo)修修剪24規(guī)則后后修剪剪從訓(xùn)練練集合合推導(dǎo)導(dǎo)出決決策樹樹，增增長決決策樹樹直到到盡可可能好好地?cái)M擬合訓(xùn)訓(xùn)練數(shù)數(shù)據(jù)，，允許許過度度擬合合發(fā)生生將決策策樹轉(zhuǎn)轉(zhuǎn)化為為等價(jià)價(jià)的規(guī)規(guī)則集集合，，方法法是為為從根根節(jié)點(diǎn)點(diǎn)到葉葉節(jié)點(diǎn)點(diǎn)的每每一條條路徑徑創(chuàng)建建一條條規(guī)則則通過刪刪除任任何能能導(dǎo)致致估計(jì)計(jì)精度度提高高的前前件來來修剪剪每一一條規(guī)規(guī)則按照修修剪過過的規(guī)規(guī)則的的估計(jì)計(jì)精度度對(duì)它它們進(jìn)進(jìn)行排排序，，并按按這樣樣的順順序應(yīng)應(yīng)用這這些規(guī)規(guī)則來來分類類后來來的實(shí)實(shí)例25規(guī)則后后修剪剪（2）例子圖3-1的的最左左一條條路徑徑if(outlook=sunny)(Humidity=High)thenPlayTennis=No考慮刪刪除先先行詞詞(outlook=sunny)和(Humidity=High)選擇使使估計(jì)計(jì)精度度有最最大提提升的的步驟驟考慮修修剪第第二個(gè)個(gè)前件件26規(guī)則后后修剪剪（3）規(guī)則精精度估估計(jì)方方法使用與與訓(xùn)練練集不不相交交的驗(yàn)驗(yàn)證集集基于訓(xùn)訓(xùn)練集集合本本身被C4.5使用用，使使用一一種保保守估估計(jì)來來彌補(bǔ)補(bǔ)訓(xùn)練練數(shù)據(jù)據(jù)有利利于當(dāng)當(dāng)前規(guī)規(guī)則的的估計(jì)計(jì)偏置置過程先計(jì)算算規(guī)則則在它它應(yīng)用用的訓(xùn)訓(xùn)練樣樣例上上的精精度然后假假定此此估計(jì)計(jì)精度度為二二項(xiàng)式式分布布，并并計(jì)算算它的的標(biāo)準(zhǔn)準(zhǔn)差對(duì)于一一個(gè)給給定的的置信信區(qū)間間，采采用下下界估估計(jì)作作為規(guī)規(guī)則性性能的的度量量評(píng)論對(duì)于大大的數(shù)數(shù)據(jù)集集，保保守預(yù)預(yù)測(cè)非非常接接近觀觀察精精度，，隨著著數(shù)據(jù)據(jù)集合合的減減小，，離觀觀察精精度越越來越越遠(yuǎn)不是統(tǒng)統(tǒng)計(jì)有有效（（此概概念第第5章章介紹紹），，但是是實(shí)踐踐中發(fā)發(fā)現(xiàn)有有效27規(guī)則后后修剪剪（4）把決策策樹轉(zhuǎn)轉(zhuǎn)化成成規(guī)則則集的的好處處可以區(qū)區(qū)分決決策節(jié)節(jié)點(diǎn)使使用的的不同同上下下文消除了了根節(jié)節(jié)點(diǎn)附附近的的屬性性測(cè)試試和葉葉節(jié)點(diǎn)點(diǎn)附近近的屬屬性測(cè)測(cè)試的的區(qū)別別提高了了可讀讀性28合并連連續(xù)值值屬性性ID3被限限制為為取離離散值值的屬屬性學(xué)習(xí)到到的決決策樹樹要預(yù)預(yù)測(cè)的的目標(biāo)標(biāo)屬性性必須須是離離散的的樹的決決策節(jié)節(jié)點(diǎn)的的屬性性也必必須是是離散散的簡(jiǎn)單刪刪除上上面第第2個(gè)個(gè)限制制的方方法通過動(dòng)態(tài)地地定義新的的離散值屬屬性來實(shí)現(xiàn)現(xiàn)，即先把把連續(xù)值屬屬性的值域域分割為離離散的區(qū)間間集合29合并連續(xù)值值屬性（2）例子，Temperature應(yīng)該定定義什么樣樣的基于閾閾值的布爾爾屬性選擇產(chǎn)生最最大信息增增益的閾值值按照連續(xù)屬屬性排列樣樣例，確定定目標(biāo)分類類不同的相相鄰實(shí)例產(chǎn)生一組候候選閾值，，它們的值值是相應(yīng)的的A值之間間的中間值值可以證明產(chǎn)產(chǎn)生最大信信息增益的的c值位于于這樣的邊邊界中（Fayyad1991）通過計(jì)算與與每個(gè)候選選閾值關(guān)聯(lián)聯(lián)的信息增增益評(píng)估這這些候選值值方法的擴(kuò)展展連續(xù)的屬性性分割成多多個(gè)區(qū)間，，而不是單單一閾值的的兩個(gè)空間間30屬性選擇的的其他度量量標(biāo)準(zhǔn)信息增益度度量存在一一個(gè)內(nèi)在偏偏置，偏向向具有較多多值的屬性性避免方法，，其他度量量，比如增增益比率增益比率通通過加入一一個(gè)被稱作作分裂信息息的項(xiàng)來懲懲罰多值屬屬性，分裂裂信息用來來衡量屬性性分裂數(shù)據(jù)據(jù)的廣度和和均勻性SplitInformation(S,A)=GainRatio(S,A)=分裂信息項(xiàng)項(xiàng)阻礙選擇擇值為均勻勻分布的屬屬性問題，當(dāng)某某個(gè)SiS。解決方方法：采用用一些啟發(fā)發(fā)式規(guī)則，，比如僅僅對(duì)增益高高過平均值值的屬性應(yīng)應(yīng)用增益比比率測(cè)試31屬性選擇的的其他度量量標(biāo)準(zhǔn)（2）基于距離的的度量定義了數(shù)據(jù)據(jù)劃分間的的一種距離離尺度計(jì)算每個(gè)屬屬性產(chǎn)生的的劃分與理理想劃分間間的距離選擇最接近近完美劃分分的屬性LopezdeMantaras定義了這這個(gè)距離度度量，證明明了它不偏偏向有大量量值的屬性性此外Mingers實(shí)驗(yàn)驗(yàn)，不同的的屬性選擇擇度量對(duì)最最終精度的的影響小于于后修剪得得程度和方方法的影響響32缺少屬性值值的訓(xùn)練樣樣例例子，醫(yī)學(xué)學(xué)領(lǐng)域經(jīng)常需要根根據(jù)此屬性性值已知的的實(shí)例來估估計(jì)這個(gè)缺缺少的屬性性值為了評(píng)估屬屬性A是否否是決策節(jié)節(jié)點(diǎn)n的最最佳測(cè)試屬屬性，要計(jì)計(jì)算決策樹樹在該節(jié)點(diǎn)點(diǎn)的信息增增益Gain(S,A)。假假定<x,c(x)>是S中中的一個(gè)訓(xùn)訓(xùn)練樣例，，并且其屬屬性A的值值A(chǔ)(x)未知33缺少屬性值值的訓(xùn)練樣樣例（2））處理缺少屬屬性值的一種策略是是賦給它節(jié)節(jié)點(diǎn)n的訓(xùn)訓(xùn)練樣例中中該屬性的的最常見值值另一種策略略是賦給它它節(jié)點(diǎn)n的的被分類為為c(x)的訓(xùn)練樣樣例中該屬屬性的最常常見值更復(fù)雜的策策略，為A的每