決策樹學習-機器學習

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

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