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

機(jī)器學(xué)習(xí)第3講決策樹學(xué)習(xí)機(jī)器學(xué)習(xí)第3講決策樹學(xué)習(xí)內(nèi)容簡介決策樹原理決策樹算法決策樹中的過擬合問題決策樹的其他問題屬性的其他度量內(nèi)容簡介簡介

決策樹也稱為判定樹。在決策樹方法中，首先從實(shí)例集中構(gòu)造決策樹，這是一種有指導(dǎo)學(xué)習(xí)的方法。該方法先根據(jù)訓(xùn)練集數(shù)據(jù)形成決策樹。如果該數(shù)不能對(duì)所有對(duì)象給出正確的分類，那么選擇一些例外加入到訓(xùn)練集數(shù)據(jù)中，重復(fù)該過程一直到形成正確的決策集。決策樹代表著決策集的樹性結(jié)構(gòu)。最終結(jié)果是一棵樹，其葉結(jié)點(diǎn)是類名，中間結(jié)點(diǎn)是帶有分枝的屬性，該分枝對(duì)應(yīng)屬性的某一可能值。

決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法，對(duì)噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)析取表達(dá)式。學(xué)習(xí)得到的決策樹能夠被再次表示為多個(gè)if-then的規(guī)則，提高可讀性。這種學(xué)習(xí)算法是最流行的歸納推理算法之一，被成功的應(yīng)用到從醫(yī)學(xué)醫(yī)療診斷到學(xué)習(xí)評(píng)估貸款申請(qǐng)的信用風(fēng)險(xiǎn)的廣闊領(lǐng)域。簡介決策樹也稱為判定樹。在決策樹方法中，首先決策樹原理

決策樹方法首先對(duì)數(shù)據(jù)進(jìn)行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行分析。

歸納學(xué)習(xí)

決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。歸納算法是從特殊到一般的過程。歸納推理從若干個(gè)事實(shí)中表征出的特征、特性或?qū)傩灾校ㄟ^比較、總結(jié)、概括而得出一個(gè)規(guī)律性的結(jié)論。歸納推理視圖從對(duì)象的一部分或整體的特定觀察中得到一個(gè)完備且正確的描述，即從特殊事實(shí)得出普遍規(guī)律性的結(jié)論。歸納對(duì)于認(rèn)識(shí)的發(fā)展完善具有重要的意義。

歸納學(xué)習(xí)的過程就是尋找一般化描述的過程。這種一般化描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測(cè)新的數(shù)據(jù)。歸納學(xué)習(xí)存在一個(gè)基本的假定：任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則他也能在未見樣本中很好地逼近目標(biāo)函數(shù)。這個(gè)假定是歸納學(xué)習(xí)的前提條件。

決策樹原理決策樹方法首先對(duì)數(shù)據(jù)進(jìn)行處理，利決策樹的表示

決策樹的基本組成部分：決策結(jié)點(diǎn)、分支和子葉。決策樹最上面的結(jié)點(diǎn)稱為跟結(jié)點(diǎn)，是整個(gè)決策樹的開始。每個(gè)分支是一個(gè)新的決策結(jié)點(diǎn)，或者是樹的葉子。每個(gè)決策結(jié)點(diǎn)代表一個(gè)問題或決策，通常對(duì)應(yīng)于待分類對(duì)象的屬性。每一個(gè)葉結(jié)點(diǎn)代表一種可能的分類結(jié)果。在沿著決策樹從上到下遍歷的過程中，在每個(gè)結(jié)點(diǎn)都會(huì)遇到一個(gè)測(cè)試，對(duì)每個(gè)節(jié)點(diǎn)上問題的不同測(cè)試輸出導(dǎo)致不同的分支，最后會(huì)到達(dá)一個(gè)葉子結(jié)點(diǎn)。這個(gè)過程就是利用決策樹進(jìn)行分類的過程，利用若干個(gè)變量來判斷所屬的類別。決策樹的表示決策樹表示法決策樹通過把實(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è)可能值。決策樹表示法決策樹7圖3-1Playtennis決策樹此圖為典型學(xué)習(xí)到的決策樹，這棵樹根據(jù)天氣情況分類“星期六上午是否適合打網(wǎng)球”，上面的實(shí)例沿著這棵決策樹的最左分支向下排列，因而被判定為反例（也就是這棵樹預(yù)測(cè)這個(gè)實(shí)例Playtennis=no）。7圖3-1Playtennis決策樹此圖為典型學(xué)習(xí)到的8圖3-1對(duì)應(yīng)于一下表達(dá)式?jīng)Q策樹代表實(shí)例屬性值約束的合取的析取式從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑對(duì)應(yīng)一組屬性的合取，樹本身對(duì)應(yīng)這些合取的析取。8圖3-1對(duì)應(yīng)于一下表達(dá)式?jīng)Q策樹代表實(shí)例屬性值約束的合取的析9決策樹學(xué)習(xí)的適用問題適用問題的特征實(shí)例由“屬性-值”對(duì)表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例分類問題核心任務(wù)是把樣例分類到各可能的離散值對(duì)應(yīng)的類別9決策樹學(xué)習(xí)的適用問題適用問題的特征10決策樹算法大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間貪心算法算法代表：ID310決策樹算法大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體11基本的決策樹學(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ù)上面的過程11基本的決策樹學(xué)習(xí)算法（2）ID3的思想12熵:物理學(xué)概念宏觀上：熱力學(xué)定律—體系的熵變等于可逆過程吸收或耗散的熱量除以它的絕對(duì)溫度（克勞修斯，1865）微觀上：熵是大量微觀粒子的位置和速度的分布概率的函數(shù)，是描述系統(tǒng)中大量微觀粒子的無序性的宏觀參數(shù)（波爾茲曼，1872）結(jié)論：熵是描述事物無序性的參數(shù)，熵越大則無序性越強(qiáng),在信息領(lǐng)域定義為“熵越大，不確定性越大”（香濃，1948年）12熵:物理學(xué)概念13最佳分類屬性信息增益用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為

Entropy(S)=信息論中對(duì)熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進(jìn)制位數(shù)更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為

Entropy(S)=13最佳分類屬性信息增益14假設(shè)S是關(guān)于某布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正例和5個(gè)反例，（我們采用記號(hào)[9+,5-]來概括這樣的數(shù)據(jù)樣例）。那么S相對(duì)于這個(gè)布爾分類的熵為：注：如果S的所有成員屬于一類那么S的熵為0，例：如果所有成員都是正的（p+=1），那么p-=0,于是Entropy（S）==0，集合中正反樣例相等時(shí)，熵為1，正反樣例不等時(shí)，熵介于0,1之間右圖顯示了布爾型的分類的熵函數(shù)隨著p+從0~1的變化曲線。14假設(shè)S是關(guān)于某布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正15最佳分類屬性（2）用信息增益度量期望的熵降低屬性的信息增益，由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低

Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)例子15最佳分類屬性（2）用信息增益度量期望的熵降低16S：共14個(gè)例子，其中9正、5負(fù)使用屬性Wind（取值為Weak或Strong）對(duì)S進(jìn)行分類：

Sweak（6正、2負(fù)）、Sstrong（3正、3負(fù)）16S：共14個(gè)例子，其中9正、5負(fù)17誰是最佳屬性？17誰是最佳屬性？18ID3算法一個(gè)完整的例子18ID3算法一個(gè)完整的例子2022/12/25192022/12/201920決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3的優(yōu)勢(shì)和不足假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間維護(hù)單一的當(dāng)前假設(shè)（不同于變型空間候選消除算法）不進(jìn)行回溯每一步使用所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)20決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3的優(yōu)勢(shì)和不足21決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)一個(gè)精確具有這個(gè)歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根節(jié)點(diǎn)的樹優(yōu)先21決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略22限定偏置和優(yōu)選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個(gè)完整的假設(shè)空間，但不徹底地搜索這個(gè)空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個(gè)空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對(duì)搜索空間的定義22限定偏置和優(yōu)選偏置ID3和候選消除算法的比較23限定偏置和優(yōu)選偏置優(yōu)選偏置ID3的歸納偏置是對(duì)某種假設(shè)勝過其他假設(shè)的一種優(yōu)選，對(duì)最終可列舉的假設(shè)沒有硬性限制限定偏置候選消除算法的偏置是對(duì)待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要23限定偏置和優(yōu)選偏置優(yōu)選偏置24為什么短的假設(shè)優(yōu)先思考：ID3算法中優(yōu)先選擇較短決策樹的歸納偏置，是不是從訓(xùn)練數(shù)據(jù)中泛化的一個(gè)可靠基礎(chǔ)？ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運(yùn)動(dòng)的簡單假設(shè)簡單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少，找到一個(gè)短的同時(shí)與訓(xùn)練數(shù)據(jù)擬合的假設(shè)可能性小。簡單假設(shè)對(duì)訓(xùn)練樣例的針對(duì)性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述24為什么短的假設(shè)優(yōu)先思考：ID3算法中優(yōu)先選擇較短決策樹的25為什么短的假設(shè)優(yōu)先例如：考慮決策樹假設(shè)，500個(gè)結(jié)點(diǎn)的決策樹比5個(gè)結(jié)點(diǎn)的決策樹多得多，如果給定一個(gè)20個(gè)訓(xùn)練樣例的集合，可以預(yù)期能夠找到很多500個(gè)結(jié)點(diǎn)的決策樹與訓(xùn)練數(shù)據(jù)一致，而如果一個(gè)5個(gè)結(jié)點(diǎn)的決策樹可以完美地?cái)M合這些數(shù)據(jù)則是出乎意料的。所以我們會(huì)相信5個(gè)結(jié)點(diǎn)的樹不太可能是統(tǒng)計(jì)巧合，因而優(yōu)先選擇這個(gè)假設(shè)，而不選擇500個(gè)結(jié)點(diǎn)的。25為什么短的假設(shè)優(yōu)先例如：考慮決策樹假設(shè)，500個(gè)結(jié)點(diǎn)的決26過度擬合數(shù)據(jù)過度擬合對(duì)于一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布上表現(xiàn)得卻更好時(shí)，我們說這個(gè)假設(shè)過度擬合訓(xùn)練樣例定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)hH，如果存在其他的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯(cuò)誤率比h’小，但在整個(gè)實(shí)例分布上h’的錯(cuò)誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。26過度擬合數(shù)據(jù)過度擬合27在此例中，ID3算法用來學(xué)習(xí)哪個(gè)病人患有糖尿病。橫軸表示決策樹結(jié)點(diǎn)總數(shù)，縱軸為決策樹做出的預(yù)測(cè)精度。實(shí)線顯示決策樹在訓(xùn)練樣例上的精度，虛線為一套獨(dú)立的測(cè)試樣例（沒有被包括在訓(xùn)練樣例中）上測(cè)出的精度?？梢钥闯?，隨著樹的增長，在訓(xùn)練樣例上的精度是單調(diào)上升的。然而獨(dú)立的測(cè)試樣例上測(cè)出的精度先上升后下降。當(dāng)樹超過大約25個(gè)結(jié)點(diǎn)時(shí)，對(duì)樹的進(jìn)一步精化盡管可以提高它在訓(xùn)練數(shù)據(jù)上的精度，卻降低了它在測(cè)試樣例上的精度。27在此例中，ID3算法用來學(xué)習(xí)哪個(gè)病人患有糖尿病。橫軸表示28避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因訓(xùn)練樣例含有隨機(jī)錯(cuò)誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時(shí)，過度擬合也有可能發(fā)生特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實(shí)際的目標(biāo)函數(shù)并無關(guān)系。28避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因29避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點(diǎn)第一種方法更直觀第一種方法中，精確地估計(jì)何時(shí)停止樹增長很困難第二種方法被證明在實(shí)踐中更成功29避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法30避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評(píng)估通過后修剪方法從樹上修建節(jié)點(diǎn)的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)測(cè)試來估計(jì)擴(kuò)展（或修剪）一個(gè)特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。使用一個(gè)明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個(gè)編碼的長度最小時(shí)停止樹增長。30避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵31避免過度擬合數(shù)據(jù)（5）方法評(pí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í)例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗(yàn)證集合。31避免過度擬合數(shù)據(jù)（5）方法評(píng)述32錯(cuò)誤率降低修剪將樹上的每一個(gè)節(jié)點(diǎn)作為修剪得候選對(duì)象修剪步驟刪除以此節(jié)點(diǎn)為根的子樹，使它成為葉結(jié)點(diǎn)把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點(diǎn)，每次總是選取那些刪除后可以最大提高決策樹在驗(yàn)證集合上的精度的節(jié)點(diǎn)繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止（降低了驗(yàn)證集合上的精度）32錯(cuò)誤率降低修剪將樹上的每一個(gè)節(jié)點(diǎn)作為修剪得候選對(duì)象33數(shù)據(jù)分成3個(gè)子集訓(xùn)練樣例，形成決策樹驗(yàn)證樣例，修剪決策樹測(cè)試樣例，精度的無偏估計(jì)如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪33數(shù)據(jù)分成3個(gè)子集34規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地?cái)M合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價(jià)的規(guī)則集合，方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則通過刪除任何能導(dǎo)致估計(jì)精度提高的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序，并按這樣的順序應(yīng)用這些規(guī)則來分類后來的實(shí)例34規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好35規(guī)則后修剪（2）例子最左邊一條路徑if(outlook=sunny)(Humidity=High)thenPlayTennis=No考慮刪除不會(huì)降低估計(jì)精度的先行詞(outlook=sunny)和(Humidity=High)來修剪規(guī)則選擇使估計(jì)精度有最大提升的步驟考慮修剪第二個(gè)前件35規(guī)則后修剪（2）例子36規(guī)則后修剪（3）把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點(diǎn)使用的不同上下文消除了根節(jié)點(diǎn)附近的屬性測(cè)試和葉節(jié)點(diǎn)附近的屬性測(cè)試的區(qū)別提高了可讀性36規(guī)則后修剪（3）把決策樹轉(zhuǎn)化成規(guī)則集的好處37決策樹學(xué)習(xí)的其他常見問題決策樹學(xué)習(xí)的實(shí)際問題處理連續(xù)值的屬性選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)信息增益度量存在一個(gè)內(nèi)在偏置，偏向具有較多值的屬性處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價(jià)的屬性提高計(jì)算效率針對(duì)這些問題，ID3被擴(kuò)展成C4.537決策樹學(xué)習(xí)的其他常見問題決策樹學(xué)習(xí)的實(shí)際問題38合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測(cè)的目標(biāo)屬性必須是離散的樹的決策節(jié)點(diǎn)的屬性也必須是離散的簡單刪除上面第2個(gè)限制的方法通過動(dòng)態(tài)地定義新的離散值屬性來實(shí)現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合38合并連續(xù)值屬性ID3被限制為取離散值的屬性39合并連續(xù)值屬性（2）例子，Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性選擇產(chǎn)生最大信息增益的閾值按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實(shí)例產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計(jì)算與每個(gè)候選閾值關(guān)聯(lián)的信息增益評(píng)估這些候選值方法的擴(kuò)展連續(xù)的屬性分割成多個(gè)區(qū)間，而不是單一閾值的兩個(gè)空間39合并連續(xù)值屬性（2）例子，Temperature應(yīng)該定義40屬性選擇的其他度量標(biāo)準(zhǔn)信息增益度量存在一個(gè)內(nèi)在偏置，偏向具有較多值的屬性避免方法，其他度量，比如增益比率增益比率通過加入一個(gè)被稱作分裂信息的項(xiàng)來懲罰多值屬性，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性

SplitInformation(S,A)= GainRatio(S,A)=分裂信息項(xiàng)阻礙選擇值為均勻分布的屬性問題，當(dāng)某個(gè)SiS。解決方法：采用一些啟發(fā)式規(guī)則，比如僅對(duì)增益高過平均值的屬性應(yīng)用增益比率測(cè)試40屬性選擇的其他度量標(biāo)準(zhǔn)信息增益度量存在一個(gè)內(nèi)在偏置，偏向41屬性選擇的其他度量標(biāo)準(zhǔn)（2）基于距離的度量定義了數(shù)據(jù)劃分間的一種距離尺度計(jì)算每個(gè)屬性產(chǎn)生的劃分與理想劃分間的距離選擇最接近完美劃分的屬性LopezdeMantaras定義了這個(gè)距離度量，證明了它不偏向有大量值的屬性此外Mingers實(shí)驗(yàn)，不同的屬性選擇度量對(duì)最終精度的影響小于后修剪得程度和方法的影響41屬性選擇的其他度量標(biāo)準(zhǔn)（2）基于距離的度量42缺少屬性值的訓(xùn)練樣例例子，醫(yī)學(xué)領(lǐng)域經(jīng)常需要根據(jù)此屬性值已知的實(shí)例來估計(jì)這個(gè)缺少的屬性值為了評(píng)估屬性A是否是決策節(jié)點(diǎn)n的最佳測(cè)試屬性，要計(jì)算決策樹在該節(jié)點(diǎn)的信息增益Gain(S,A)。假定<x,c(x)>是S中的一個(gè)訓(xùn)練樣例，并且其屬性A的值A(chǔ)(x)未知42缺少屬性值的訓(xùn)練樣例例子，醫(yī)學(xué)領(lǐng)域43缺少屬性值的訓(xùn)練樣例（2）處理缺少屬性值的一種策略是賦給它節(jié)點(diǎn)n的訓(xùn)練樣例中該屬性的最常見值另一種策略是賦給它節(jié)點(diǎn)n的被分類為c(x)的訓(xùn)練樣例中該屬性的最常見值更復(fù)雜的策略，為A的每個(gè)可能值賦予一個(gè)概率，而不是簡單地將最常見的值賦給A(x)

根據(jù)結(jié)點(diǎn)n的樣例上的不同值出現(xiàn)的頻率，這些概率可以被再次估計(jì)。43缺少屬性值的訓(xùn)練樣例（2）處理缺少屬性值的THANKYOUTHANKYOU機(jī)器學(xué)習(xí)第3講決策樹學(xué)習(xí)機(jī)器學(xué)習(xí)第3講決策樹學(xué)習(xí)內(nèi)容簡介決策樹原理決策樹算法決策樹中的過擬合問題決策樹的其他問題屬性的其他度量內(nèi)容簡介簡介

決策樹也稱為判定樹。在決策樹方法中，首先從實(shí)例集中構(gòu)造決策樹，這是一種有指導(dǎo)學(xué)習(xí)的方法。該方法先根據(jù)訓(xùn)練集數(shù)據(jù)形成決策樹。如果該數(shù)不能對(duì)所有對(duì)象給出正確的分類，那么選擇一些例外加入到訓(xùn)練集數(shù)據(jù)中，重復(fù)該過程一直到形成正確的決策集。決策樹代表著決策集的樹性結(jié)構(gòu)。最終結(jié)果是一棵樹，其葉結(jié)點(diǎn)是類名，中間結(jié)點(diǎn)是帶有分枝的屬性，該分枝對(duì)應(yīng)屬性的某一可能值。

決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法，對(duì)噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)析取表達(dá)式。學(xué)習(xí)得到的決策樹能夠被再次表示為多個(gè)if-then的規(guī)則，提高可讀性。這種學(xué)習(xí)算法是最流行的歸納推理算法之一，被成功的應(yīng)用到從醫(yī)學(xué)醫(yī)療診斷到學(xué)習(xí)評(píng)估貸款申請(qǐng)的信用風(fēng)險(xiǎn)的廣闊領(lǐng)域。簡介決策樹也稱為判定樹。在決策樹方法中，首先決策樹原理

決策樹方法首先對(duì)數(shù)據(jù)進(jìn)行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行分析。

歸納學(xué)習(xí)

決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。歸納算法是從特殊到一般的過程。歸納推理從若干個(gè)事實(shí)中表征出的特征、特性或?qū)傩灾?，通過比較、總結(jié)、概括而得出一個(gè)規(guī)律性的結(jié)論。歸納推理視圖從對(duì)象的一部分或整體的特定觀察中得到一個(gè)完備且正確的描述，即從特殊事實(shí)得出普遍規(guī)律性的結(jié)論。歸納對(duì)于認(rèn)識(shí)的發(fā)展完善具有重要的意義。

歸納學(xué)習(xí)的過程就是尋找一般化描述的過程。這種一般化描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測(cè)新的數(shù)據(jù)。歸納學(xué)習(xí)存在一個(gè)基本的假定：任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則他也能在未見樣本中很好地逼近目標(biāo)函數(shù)。這個(gè)假定是歸納學(xué)習(xí)的前提條件。

決策樹原理決策樹方法首先對(duì)數(shù)據(jù)進(jìn)行處理，利決策樹的表示

決策樹的基本組成部分：決策結(jié)點(diǎn)、分支和子葉。決策樹最上面的結(jié)點(diǎn)稱為跟結(jié)點(diǎn)，是整個(gè)決策樹的開始。每個(gè)分支是一個(gè)新的決策結(jié)點(diǎn)，或者是樹的葉子。每個(gè)決策結(jié)點(diǎn)代表一個(gè)問題或決策，通常對(duì)應(yīng)于待分類對(duì)象的屬性。每一個(gè)葉結(jié)點(diǎn)代表一種可能的分類結(jié)果。在沿著決策樹從上到下遍歷的過程中，在每個(gè)結(jié)點(diǎn)都會(huì)遇到一個(gè)測(cè)試，對(duì)每個(gè)節(jié)點(diǎn)上問題的不同測(cè)試輸出導(dǎo)致不同的分支，最后會(huì)到達(dá)一個(gè)葉子結(jié)點(diǎn)。這個(gè)過程就是利用決策樹進(jìn)行分類的過程，利用若干個(gè)變量來判斷所屬的類別。決策樹的表示決策樹表示法決策樹通過把實(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è)可能值。決策樹表示法決策樹51圖3-1Playtennis決策樹此圖為典型學(xué)習(xí)到的決策樹，這棵樹根據(jù)天氣情況分類“星期六上午是否適合打網(wǎng)球”，上面的實(shí)例沿著這棵決策樹的最左分支向下排列，因而被判定為反例（也就是這棵樹預(yù)測(cè)這個(gè)實(shí)例Playtennis=no）。7圖3-1Playtennis決策樹此圖為典型學(xué)習(xí)到的52圖3-1對(duì)應(yīng)于一下表達(dá)式?jīng)Q策樹代表實(shí)例屬性值約束的合取的析取式從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑對(duì)應(yīng)一組屬性的合取，樹本身對(duì)應(yīng)這些合取的析取。8圖3-1對(duì)應(yīng)于一下表達(dá)式?jīng)Q策樹代表實(shí)例屬性值約束的合取的析53決策樹學(xué)習(xí)的適用問題適用問題的特征實(shí)例由“屬性-值”對(duì)表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例分類問題核心任務(wù)是把樣例分類到各可能的離散值對(duì)應(yīng)的類別9決策樹學(xué)習(xí)的適用問題適用問題的特征54決策樹算法大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間貪心算法算法代表：ID310決策樹算法大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體55基本的決策樹學(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ù)上面的過程11基本的決策樹學(xué)習(xí)算法（2）ID3的思想56熵:物理學(xué)概念宏觀上：熱力學(xué)定律—體系的熵變等于可逆過程吸收或耗散的熱量除以它的絕對(duì)溫度（克勞修斯，1865）微觀上：熵是大量微觀粒子的位置和速度的分布概率的函數(shù)，是描述系統(tǒng)中大量微觀粒子的無序性的宏觀參數(shù)（波爾茲曼，1872）結(jié)論：熵是描述事物無序性的參數(shù)，熵越大則無序性越強(qiáng),在信息領(lǐng)域定義為“熵越大，不確定性越大”（香濃，1948年）12熵:物理學(xué)概念57最佳分類屬性信息增益用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為

Entropy(S)=信息論中對(duì)熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進(jìn)制位數(shù)更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為

Entropy(S)=13最佳分類屬性信息增益58假設(shè)S是關(guān)于某布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正例和5個(gè)反例，（我們采用記號(hào)[9+,5-]來概括這樣的數(shù)據(jù)樣例）。那么S相對(duì)于這個(gè)布爾分類的熵為：注：如果S的所有成員屬于一類那么S的熵為0，例：如果所有成員都是正的（p+=1），那么p-=0,于是Entropy（S）==0，集合中正反樣例相等時(shí)，熵為1，正反樣例不等時(shí)，熵介于0,1之間右圖顯示了布爾型的分類的熵函數(shù)隨著p+從0~1的變化曲線。14假設(shè)S是關(guān)于某布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正59最佳分類屬性（2）用信息增益度量期望的熵降低屬性的信息增益，由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低

Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)例子15最佳分類屬性（2）用信息增益度量期望的熵降低60S：共14個(gè)例子，其中9正、5負(fù)使用屬性Wind（取值為Weak或Strong）對(duì)S進(jìn)行分類：

Sweak（6正、2負(fù)）、Sstrong（3正、3負(fù)）16S：共14個(gè)例子，其中9正、5負(fù)61誰是最佳屬性？17誰是最佳屬性？62ID3算法一個(gè)完整的例子18ID3算法一個(gè)完整的例子2022/12/25632022/12/201964決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3的優(yōu)勢(shì)和不足假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間維護(hù)單一的當(dāng)前假設(shè)（不同于變型空間候選消除算法）不進(jìn)行回溯每一步使用所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)20決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3的優(yōu)勢(shì)和不足65決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)一個(gè)精確具有這個(gè)歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根節(jié)點(diǎn)的樹優(yōu)先21決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略66限定偏置和優(yōu)選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個(gè)完整的假設(shè)空間，但不徹底地搜索這個(gè)空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個(gè)空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對(duì)搜索空間的定義22限定偏置和優(yōu)選偏置ID3和候選消除算法的比較67限定偏置和優(yōu)選偏置優(yōu)選偏置ID3的歸納偏置是對(duì)某種假設(shè)勝過其他假設(shè)的一種優(yōu)選，對(duì)最終可列舉的假設(shè)沒有硬性限制限定偏置候選消除算法的偏置是對(duì)待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要23限定偏置和優(yōu)選偏置優(yōu)選偏置68為什么短的假設(shè)優(yōu)先思考：ID3算法中優(yōu)先選擇較短決策樹的歸納偏置，是不是從訓(xùn)練數(shù)據(jù)中泛化的一個(gè)可靠基礎(chǔ)？ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運(yùn)動(dòng)的簡單假設(shè)簡單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少，找到一個(gè)短的同時(shí)與訓(xùn)練數(shù)據(jù)擬合的假設(shè)可能性小。簡單假設(shè)對(duì)訓(xùn)練樣例的針對(duì)性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述24為什么短的假設(shè)優(yōu)先思考：ID3算法中優(yōu)先選擇較短決策樹的69為什么短的假設(shè)優(yōu)先例如：考慮決策樹假設(shè)，500個(gè)結(jié)點(diǎn)的決策樹比5個(gè)結(jié)點(diǎn)的決策樹多得多，如果給定一個(gè)20個(gè)訓(xùn)練樣例的集合，可以預(yù)期能夠找到很多500個(gè)結(jié)點(diǎn)的決策樹與訓(xùn)練數(shù)據(jù)一致，而如果一個(gè)5個(gè)結(jié)點(diǎn)的決策樹可以完美地?cái)M合這些數(shù)據(jù)則是出乎意料的。所以我們會(huì)相信5個(gè)結(jié)點(diǎn)的樹不太可能是統(tǒng)計(jì)巧合，因而優(yōu)先選擇這個(gè)假設(shè)，而不選擇500個(gè)結(jié)點(diǎn)的。25為什么短的假設(shè)優(yōu)先例如：考慮決策樹假設(shè)，500個(gè)結(jié)點(diǎn)的決70過度擬合數(shù)據(jù)過度擬合對(duì)于一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布上表現(xiàn)得卻更好時(shí)，我們說這個(gè)假設(shè)過度擬合訓(xùn)練樣例定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)hH，如果存在其他的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯(cuò)誤率比h’小，但在整個(gè)實(shí)例分布上h’的錯(cuò)誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。26過度擬合數(shù)據(jù)過度擬合71在此例中，ID3算法用來學(xué)習(xí)哪個(gè)病人患有糖尿病。橫軸表示決策樹結(jié)點(diǎn)總數(shù)，縱軸為決策樹做出的預(yù)測(cè)精度。實(shí)線顯示決策樹在訓(xùn)練樣例上的精度，虛線為一套獨(dú)立的測(cè)試樣例（沒有被包括在訓(xùn)練樣例中）上測(cè)出的精度?？梢钥闯?，隨著樹的增長，在訓(xùn)練樣例上的精度是單調(diào)上升的。然而獨(dú)立的測(cè)試樣例上測(cè)出的精度先上升后下降。當(dāng)樹超過大約25個(gè)結(jié)點(diǎn)時(shí)，對(duì)樹的進(jìn)一步精化盡管可以提高它在訓(xùn)練數(shù)據(jù)上的精度，卻降低了它在測(cè)試樣例上的精度。27在此例中，ID3算法用來學(xué)習(xí)哪個(gè)病人患有糖尿病。橫軸表示72避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因訓(xùn)練樣例含有隨機(jī)錯(cuò)誤或噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時(shí)，過度擬合也有可能發(fā)生特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實(shí)際的目標(biāo)函數(shù)并無關(guān)系。28避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因73避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點(diǎn)第一種方法更直觀第一種方法中，精確地估計(jì)何時(shí)停止樹增長很困難第二種方法被證明在實(shí)踐中更成功29避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法74避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評(píng)估通過后修剪方法從樹上修建節(jié)點(diǎn)的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)測(cè)試來估計(jì)擴(kuò)展（或修剪）一個(gè)特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。使用一個(gè)明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個(gè)編碼的長度最小時(shí)停止樹增長。30避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵75避免過度擬合數(shù)據(jù)（5）方法評(pí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í)例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗(yàn)證集合。31避免過度擬合數(shù)據(jù)（5）方法評(píng)述76錯(cuò)誤率降低修剪將樹上的每一個(gè)節(jié)點(diǎn)作為修剪得候選對(duì)象修剪步驟刪除以此節(jié)點(diǎn)為根的子樹，使它成為葉結(jié)點(diǎn)把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點(diǎn)，每次總是選取那些刪除后可以最大提高決策樹在驗(yàn)證集合上的精度的節(jié)點(diǎn)繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止（降低了驗(yàn)證集合上的精度）32錯(cuò)誤率降低修剪將樹上的每一個(gè)節(jié)點(diǎn)作為修剪得候選對(duì)象77數(shù)據(jù)分成3個(gè)子集訓(xùn)練樣例，形成決策樹驗(yàn)證樣例，修剪決策樹測(cè)試樣例，精度的無偏估計(jì)如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪33數(shù)據(jù)分成3個(gè)子集78規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地?cái)M合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價(jià)的規(guī)則集合，方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則通過刪除任何能導(dǎo)致估計(jì)精度提高的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序，并按這樣的順序應(yīng)用這些規(guī)則來分類后來的實(shí)例34規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好79規(guī)則后修剪（2）例子最左邊一條路徑if(outlook=sunny)(Humidity=High)thenPlayTennis=No考慮刪除不會(huì)降低估計(jì)精度的先行詞(outlook=sunny)和(Humidity=High)來修剪規(guī)則選擇使估計(jì)精度有最大提升的步驟考慮修剪第二個(gè)前件35規(guī)則后修剪（2）例子80規(guī)則后修剪（3