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

會(huì)計(jì)學(xué)1第機(jī)器學(xué)習(xí)決策樹上節(jié)課程內(nèi)容回顧明天太陽會(huì)升起嗎?他在一個(gè)袋子放了黑白各一個(gè)顆彈子。（太陽升起的概率？）第一天第二天太陽升起了，他加了一個(gè)白彈子在袋子里。（太陽升起的概率？）第三天太陽升起了，他又加了一個(gè)白彈子在袋子里。（太陽升起的概率？）。。。。。。。結(jié)論幾乎可以肯定，太陽總會(huì)升起。第1頁/共102頁主要內(nèi)容4.6.5決策樹的假設(shè)空間搜索4.6.4最佳分類屬性判定4.6.3決策樹的基本算法4.6.2決策樹學(xué)習(xí)的適用問題4.6.1決策樹的概念4.6.8決策樹算法的PROLOG實(shí)現(xiàn)4.6.7決策樹的優(yōu)缺點(diǎn)4.6.6決策樹的常見問題第2頁/共102頁什么是決策樹?從管理學(xué)的角度定義決策樹是指使用系統(tǒng)分析方法，把各種決策方案及出現(xiàn)結(jié)果的可能性進(jìn)行分組排列，然后確定最佳方案的決策過程。

4.6.1什么是決策樹？第3頁/共102頁舉例:漁民投資決策點(diǎn)新船舊船好魚情(0.7)壞魚情(0.3)好魚情(0.7)壞魚情(0.3)$90000-$10000$80000$200004.6.1什么是決策樹？第4頁/共102頁什么是決策樹?從機(jī)器學(xué)習(xí)的角度定義決策樹是運(yùn)用于分類的一種樹結(jié)構(gòu)。4.6.1什么是決策樹？第5頁/共102頁決策樹的表示方法每個(gè)內(nèi)部節(jié)點(diǎn)（internalnode）代表對(duì)某個(gè)屬性的一次測(cè)試。一條邊代表一個(gè)測(cè)試結(jié)果。葉子（leaf）代表某個(gè)類（class）或者類的分布（classdistribution）。最上面的節(jié)點(diǎn)是根結(jié)點(diǎn)。4.6.1什么是決策樹？第6頁/共102頁舉例假設(shè)用一個(gè)決策樹表示一個(gè)關(guān)心電子產(chǎn)品的用戶是否會(huì)購買PC的知識(shí)，然后用它來預(yù)測(cè)某條記錄（某個(gè)人）的購買意向。4.6.1什么是決策樹？第7頁/共102頁舉例年齡?學(xué)生?信用狀況?否是是是否<=3030-40>40否

是很好一般4.6.1什么是決策樹？第8頁/共102頁舉例類別：buys_computers=yes和buys_computers=no）。樣本向量為（age,student,credit_rating;buys_computers）被決策數(shù)據(jù)的格式為（age,student,credit_rating）輸入新的被決策的記錄，可以預(yù)測(cè)該記錄隸屬于哪個(gè)類。4.6.1什么是決策樹？第9頁/共102頁決策樹分類過程決策樹通過把實(shí)例從根結(jié)點(diǎn)排列（sort）到某個(gè)葉子結(jié)點(diǎn)來分類實(shí)例，葉子結(jié)點(diǎn)即為實(shí)例所屬的分類。樹上的每一個(gè)結(jié)點(diǎn)指定了對(duì)實(shí)例的某個(gè)屬性（attribute）的測(cè)試，并且該結(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值。4.6.1什么是決策樹？第10頁/共102頁決策樹分類過程（續(xù)）分類實(shí)例的方法是從這棵樹的根結(jié)點(diǎn)開始，測(cè)試這個(gè)結(jié)點(diǎn)指定的屬性，然后按照給定實(shí)例的該屬性值對(duì)應(yīng)的樹枝向下移動(dòng)。這個(gè)過程再在以新結(jié)點(diǎn)為根的子樹上重復(fù)。4.6.1什么是決策樹？問題：實(shí)例怎么表達(dá)？第11頁/共102頁決策樹與規(guī)則表達(dá)的轉(zhuǎn)換通常決策樹代表實(shí)例屬性值約束的合?。╟onjunction）的析取式（disjunction）。從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹本身對(duì)應(yīng)這些合取的析取。(Buys_computer=age<=30∧Student)∨(Buys_computer=age=30-40)∨(Buys_computer=age>40∧Credit_rating=excellent)4.6.1什么是決策樹？第12頁/共102頁決策樹學(xué)習(xí)的適用問題實(shí)例由“屬性-值”對(duì)（pair）表示

--實(shí)例是用一系列固定的屬性和它們的值來描述的。

--最簡單的決策樹學(xué)習(xí)中，每一個(gè)屬性取少數(shù)的分離的值。

--擴(kuò)展的算法允許處理值域?yàn)閷?shí)數(shù)的屬性（例如，數(shù)字表示的溫度）。4.6.2決策樹學(xué)習(xí)的適用問題第13頁/共102頁決策樹學(xué)習(xí)的適用問題目標(biāo)函數(shù)具有離散的輸出值

--上面舉例的決策樹給每個(gè)實(shí)例賦予一個(gè)布爾型的分類（例如，yes或no）。

--決策樹方法很容易擴(kuò)展到學(xué)習(xí)有兩個(gè)以上輸出值的函數(shù)。

--一種更強(qiáng)有力的擴(kuò)展算法允許學(xué)習(xí)具有實(shí)數(shù)值輸出的函數(shù)，盡管決策樹在這種情況下的應(yīng)用不太常見。4.6.2決策樹學(xué)習(xí)的適用問題第14頁/共102頁決策樹學(xué)習(xí)的適用問題可能需要析取的描述

--決策樹很自然地代表了析取表達(dá)式。

4.6.2決策樹學(xué)習(xí)的適用問題第15頁/共102頁決策樹學(xué)習(xí)的適用問題訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例

--決策樹學(xué)習(xí)對(duì)錯(cuò)誤有很好的魯棒性，無論是訓(xùn)練樣例所屬的分類錯(cuò)誤還是描述這些樣例的屬性值錯(cuò)誤。

4.6.2決策樹學(xué)習(xí)的適用問題已經(jīng)發(fā)現(xiàn)有很多實(shí)際的問題符合這些特征，所以決策樹學(xué)習(xí)已經(jīng)被應(yīng)用到很多問題中。例如：根據(jù)拖欠支付的可能性分類貸款申請(qǐng)；根據(jù)起因分類設(shè)備故障。它們的核心任務(wù)就是要把樣例分類到各可能的離散值對(duì)應(yīng)的類別中。第16頁/共102頁已有的決策樹學(xué)習(xí)算法4.6.3基本的決策樹學(xué)習(xí)算法大多數(shù)已開發(fā)的決策樹學(xué)習(xí)算法都是一種核心算法的變體。ID3(QUINLAN1986)及其后繼的C4.5第17頁/共102頁ID34.6.3基本的決策樹學(xué)習(xí)算法基本的ID3算法通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)。第18頁/共102頁ID3算法的構(gòu)造過程

（問題：哪一個(gè)屬性將在樹的根結(jié)點(diǎn)被測(cè)試？）4.6.3基本的決策樹學(xué)習(xí)算法使用統(tǒng)計(jì)測(cè)試來確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力，分類能力最好的屬性被選作樹的根結(jié)點(diǎn)的測(cè)試。為根結(jié)點(diǎn)屬性的每個(gè)可能值產(chǎn)生一個(gè)分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Вㄒ簿褪?，樣例的該屬性值?duì)應(yīng)的分支）之下。

重復(fù)整個(gè)過程，用每個(gè)分支結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例來選取在該點(diǎn)被測(cè)試的最佳屬性。第19頁/共102頁專用于學(xué)習(xí)布爾函數(shù)的ID3算法4.6.3基本的決策樹學(xué)習(xí)算法ID3是一種自頂向下增長樹的貪婪(greedy)算法，在每個(gè)結(jié)點(diǎn)選取能最好地分類樣例的屬性。繼續(xù)這個(gè)過程直到這棵樹能完美分類訓(xùn)練樣例，或者所有的屬性都使用過了。見復(fù)印資料。第20頁/共102頁專用于學(xué)習(xí)布爾函數(shù)的ID3算法4.6.3基本的決策樹學(xué)習(xí)算法什么是衡量屬性價(jià)值的定量標(biāo)準(zhǔn)？第21頁/共102頁信息熵4.6.4哪個(gè)屬性是最佳的分類屬性？信息論中廣泛使用的一個(gè)度量標(biāo)準(zhǔn)（ClaudeElwoodShannon），稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。

第22頁/共102頁信息熵4.6.4哪個(gè)屬性是最佳的分類屬性？給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為：

Entropy(S)-plog2p

-pΘlog2pΘ

其中，p是在S中正例的比例，pΘ是在S中負(fù)例的比例。在有關(guān)熵的所有計(jì)算中我們定義0log0為0。

第23頁/共102頁舉例4.6.4哪個(gè)屬性是最佳的分類屬性？假設(shè)S是一個(gè)關(guān)于某布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正例和5個(gè)反例（用記號(hào)[9+，5-]來表示）。那么S相對(duì)于這個(gè)布爾分類的熵（Entropy）為：第24頁/共102頁注意4.6.4哪個(gè)屬性是最佳的分類屬性？如果S的所有成員屬于同一類，那么S的熵為0。例如，如果所有的成員是正的（p=1），那么pΘ就是0，那么

Entropy(S)=0。第25頁/共102頁注意4.6.4哪個(gè)屬性是最佳的分類屬性？當(dāng)集合中正反樣例的數(shù)量相等時(shí)熵為1。如果集合中正反例的數(shù)量不等時(shí)，熵介于0和1之間。1.00,00.50.51.0某布爾分類的熵函數(shù)P隨著從0到1變化的曲線第26頁/共102頁信息論中熵的解釋4.6.4哪個(gè)屬性是最佳的分類屬性？熵確定了集合S中任意成員（即以均勻的概率隨機(jī)抽出的一個(gè)成員）的分類所需要的最少二進(jìn)制位數(shù)。第27頁/共102頁信息論中熵的解釋4.6.4哪個(gè)屬性是最佳的分類屬性？如果P是1，接收者知道抽出的樣例必為正，所以不必發(fā)任何消息，此時(shí)的熵為0。如果是P0.5，必須用一個(gè)二進(jìn)制位來說明抽出的樣例是正還是負(fù)。如果是P0.8，那么對(duì)所需的消息編碼方法是賦給正例集合較短的編碼，可能性較小的反例集合較長的編碼，平均每條消息的編碼少于1個(gè)二進(jìn)制位。第28頁/共102頁通用信息熵的定義4.6.4哪個(gè)屬性是最佳的分類屬性？如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)（c-wise）的分類的熵定義為： 第29頁/共102頁通用信息熵的定義4.6.4哪個(gè)屬性是最佳的分類屬性？為什么對(duì)數(shù)的底數(shù)是2?熵的最大可能值是多少?第30頁/共102頁信息增益(InformationGain)4.6.4哪個(gè)屬性是最佳的分類屬性？一個(gè)屬性的信息增益就是由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低。第31頁/共102頁信息增益(InformationGain)4.6.4哪個(gè)屬性是最佳的分類屬性？一個(gè)屬性A相對(duì)樣例集合S的信息增益Gain(S,A)被定義為:第32頁/共102頁信息增益(InformationGain)4.6.4哪個(gè)屬性是最佳的分類屬性？Gain(S,A)是由于給定屬性A的值而得到的關(guān)于目標(biāo)函數(shù)值的信息。當(dāng)對(duì)S的一個(gè)任意成員的目標(biāo)值編碼時(shí)，Gain(S,A)的值是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)。第33頁/共102頁舉例4.6.4哪個(gè)屬性是最佳的分類屬性？例如，假定S是一套有關(guān)天氣的訓(xùn)練樣例，描述它的屬性包括可能是具有Weak和Strong兩個(gè)值的Wind。假定S包含14個(gè)樣例，[9+，5-]。在這14個(gè)樣例中，假定正例中的6個(gè)和反例中的2個(gè)有Wind=Weak，其他的有Wind=Strong。由于按照屬性Wind分類14個(gè)樣例得到的信息增益可以計(jì)算如下。第34頁/共102頁舉例4.6.4哪個(gè)屬性是最佳的分類屬性？第35頁/共102頁舉例4.6.4哪個(gè)屬性是最佳的分類屬性？第36頁/共102頁信息增益與ID34.6.4哪個(gè)屬性是最佳的分類屬性？信息增益正是ID3算法增長樹的每一步中選取最佳屬性的度量標(biāo)準(zhǔn)。第37頁/共102頁舉例4.6.4哪個(gè)屬性是最佳的分類屬性？

見復(fù)印材料。課堂練習(xí):畫出該示例的決策樹。第38頁/共102頁Outlook??yesSunnyOvercastRain?舉例4.6.4哪個(gè)屬性是最佳的分類屬性？[D1,D2,D3….,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]第39頁/共102頁舉例4.6.4哪個(gè)屬性是最佳的分類屬性？Ssunny=[D1,D2,D8,D9,D11]Gain(Ssunny,Humidity)=0.97-(3/5)0.0-(2/5)0.0=0.97Gain(Ssunny,Temperature)=0.97-(2/5)0.0-(2/5)1.0

-(1/5)0.0=0.57Gain(Ssunny,Wind)=0.97-(2/5)1.0-(3/5)0.918=0.19第40頁/共102頁決策樹學(xué)習(xí)中的假設(shè)空間搜索4.6.5決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3算法可以被描述為從一個(gè)假設(shè)空間中搜索一個(gè)擬合訓(xùn)練樣例的假設(shè)。被ID3算法搜索的假設(shè)空間就是可能的決策樹的集合。ID3算法以一種從簡單到復(fù)雜的爬山算法遍歷這個(gè)假設(shè)空間，從空的樹開始，然后逐步考慮更加復(fù)雜的假設(shè)，目的是搜索到一個(gè)正確分類訓(xùn)練數(shù)據(jù)的決策樹。引導(dǎo)這種爬山搜索的評(píng)估函數(shù)是信息增益度量。第41頁/共102頁決策樹學(xué)習(xí)中的誤區(qū)4.6.5決策樹學(xué)習(xí)中的假設(shè)空間搜索樹的深度應(yīng)盡量小。但貪婪搜索可能無法找到最小樹，頂層結(jié)點(diǎn)可能不是高區(qū)分度的。第42頁/共102頁計(jì)算復(fù)雜度4.6.5決策樹學(xué)習(xí)中的假設(shè)空間搜索最壞情況是構(gòu)造出一棵完全樹，每條路徑都測(cè)試了所有特征。

第43頁/共102頁計(jì)算復(fù)雜度4.6.5決策樹學(xué)習(xí)中的假設(shè)空間搜索各層i要對(duì)剩下的|A|-i個(gè)屬性計(jì)算最佳分割。

一般來說，性能與屬性個(gè)數(shù)成線性關(guān)系。D就是樣本集第44頁/共102頁決策樹學(xué)習(xí)的歸納偏置4.6.6決策樹學(xué)習(xí)的歸納偏置歸納偏置是一系列前提，這些前提與訓(xùn)練數(shù)據(jù)一起演繹論證未來實(shí)例的分類。第45頁/共102頁決策樹學(xué)習(xí)的歸納偏置4.6.6決策樹學(xué)習(xí)的歸納偏置歸納偏置是一系列前提，這些前提與訓(xùn)練數(shù)據(jù)一起演繹論證未來實(shí)例的分類。第46頁/共102頁決策樹學(xué)習(xí)的歸納偏置4.6.6決策樹學(xué)習(xí)的歸納偏置如果給定一個(gè)訓(xùn)練樣例的集合，那么通常有很多決策樹與這些樣例一致。所以，要描述ID3算法的歸納偏置，應(yīng)找到它從所有一致的假設(shè)中選擇一個(gè)的根據(jù)。第47頁/共102頁決策樹學(xué)習(xí)的歸納偏置4.6.6決策樹學(xué)習(xí)的歸納偏置ID3從這些決策樹中選擇哪一個(gè)呢？它選擇在使用簡單到復(fù)雜的爬山算法遍歷可能的樹空間時(shí)遇到的第一個(gè)可接受的樹。第48頁/共102頁ID3的搜索策略4.6.6決策樹學(xué)習(xí)的歸納偏置優(yōu)先選擇較短的樹而不是較長的。選擇那些信息增益高的屬性離根結(jié)點(diǎn)較近的樹。第49頁/共102頁存在的問題4.6.6決策樹學(xué)習(xí)的歸納偏置在ID3中使用的選擇屬性的啟發(fā)式規(guī)則和它遇到的特定訓(xùn)練樣例之間存在著微妙的相互作用。由于這一點(diǎn)，很難準(zhǔn)確地刻劃出ID3的歸納偏置。然而我們可以近似地把它的歸納偏置描述為一種對(duì)短的決策樹的偏好。第50頁/共102頁近似的ID3算法歸納偏置

4.6.6決策樹學(xué)習(xí)的歸納偏置BFS-ID3：較短的樹比較長的優(yōu)先寬度優(yōu)先搜索？深度優(yōu)先搜索？第51頁/共102頁近似的ID3算法歸納偏置

4.6.6決策樹學(xué)習(xí)的歸納偏置BFS-ID3：原理/過程它從一個(gè)空的樹開始廣度優(yōu)先（breadthfirst）搜索逐漸復(fù)雜的樹，先考慮所有深度為1的樹，然后所有深度為2的，……。一旦它找到了一個(gè)與訓(xùn)練數(shù)據(jù)一致的決策樹，它返回搜索深度的最小的一致樹（例如，具有最少結(jié)點(diǎn)的樹）。這種廣度優(yōu)先搜索稱為BFS-ID3。BFS-ID3尋找最短的決策樹，因此精確地具有“較短的樹比較長的得到優(yōu)先”的偏置。ID3可被看作BFS-ID3的一個(gè)有效近似，它使用一種貪婪的啟發(fā)式搜索企圖發(fā)現(xiàn)最短的樹，而不用進(jìn)行完整的廣度優(yōu)先搜索來遍歷假設(shè)空間。

第52頁/共102頁近似的ID3算法歸納偏置

4.6.6決策樹學(xué)習(xí)的歸納偏置ID3歸納偏置的更貼切近似：較短的樹比較長的得到優(yōu)先。那些信息增益高的屬性更靠近根結(jié)點(diǎn)的樹得到優(yōu)先。第53頁/共102頁為什么ID3中選擇短的假設(shè)優(yōu)先？4.6.6決策樹學(xué)習(xí)的歸納偏置ID3算法中優(yōu)選較短決策樹的歸納偏置，是不是從訓(xùn)練數(shù)據(jù)中泛化的可靠基礎(chǔ)？哲學(xué)家們以及其他學(xué)者已經(jīng)對(duì)這樣的問題爭(zhēng)論幾個(gè)世紀(jì)了，而且這個(gè)爭(zhēng)論至今還未解決。威廉·奧坎姆大約在1320年提出類似的論點(diǎn)，是最早討論這個(gè)問題的人之一，所以這個(gè)偏置經(jīng)常被稱為“奧坎姆剃刀”（Occam’srazor）。第54頁/共102頁Occam’srazor4.6.6決策樹學(xué)習(xí)的歸納偏置奧卡姆剃刀（Occam'sRazor,Ockham'sRazor）是由14世紀(jì)邏輯學(xué)家、圣方濟(jì)各會(huì)修士奧卡姆的威廉（WilliamofOccam）提出的一個(gè)原理。第55頁/共102頁Occam’srazor4.6.6決策樹學(xué)習(xí)的歸納偏置Entitiesshouldnotbemultipliedunnecessarily．（“如無必要，勿增實(shí)體”。）第56頁/共102頁Occam’srazor4.6.6決策樹學(xué)習(xí)的歸納偏置威廉使用這個(gè)原理證明了許多結(jié)論，包括“通過思辨不能得出上帝存在的結(jié)論”。這使他不受羅馬教皇的歡迎。第57頁/共102頁Occam’srazor4.6.6決策樹學(xué)習(xí)的歸納偏置許多科學(xué)家接受或者（獨(dú)立的）提出了奧卡姆剃刀原理，例如萊布尼茲的“不可觀測(cè)事物的同一性原理”和牛頓提出的一個(gè)原則：如果某一原因既真又足以解釋自然事物的特性，則我們不應(yīng)當(dāng)接受比這更多的原因。第58頁/共102頁Occam’srazor4.6.6決策樹學(xué)習(xí)的歸納偏置對(duì)于科學(xué)家，這一原理最常見的形式是：當(dāng)你有兩個(gè)處于競(jìng)爭(zhēng)地位的理論能得出同樣的結(jié)論，那么簡單的那個(gè)更好。第59頁/共102頁Occam’srazor

（奧卡姆剃刀的強(qiáng)形式）4.6.6決策樹學(xué)習(xí)的歸納偏置如果你有兩個(gè)原理，它們都能解釋觀測(cè)到的事實(shí)，那么你應(yīng)該使用簡單的那個(gè)，直到發(fā)現(xiàn)更多的證據(jù)。對(duì)于現(xiàn)象最簡單的解釋往往比較復(fù)雜的解釋更正確。第60頁/共102頁Occam’srazor

（奧卡姆剃刀的強(qiáng)形式）4.6.6決策樹學(xué)習(xí)的歸納偏置如果你有兩個(gè)類似的解決方案，選擇最簡單的。需要最少假設(shè)的解釋最有可能是正確的……或者以這種自我肯定的形式出現(xiàn)：讓事情保持簡單！第61頁/共102頁Occam’srazor

（奧卡姆剃刀的強(qiáng)形式）4.6.6決策樹學(xué)習(xí)的歸納偏置嚴(yán)格的說，它們應(yīng)該被稱為吝嗇定律，或者稱為樸素原則。愛因斯坦說:“萬事萬物應(yīng)該盡量簡單，而不是更簡單。”第62頁/共102頁Occam’srazor

（奧卡姆剃刀的強(qiáng)形式）4.6.6決策樹學(xué)習(xí)的歸納偏置當(dāng)然給出一個(gè)歸納偏置的名字不等于證明了它。決策樹假設(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結(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)的。第63頁/共102頁Occam’srazor

（奧卡姆剃刀的強(qiáng)形式）4.6.7決策樹的常見問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價(jià)的屬性提高計(jì)算效率ID3擴(kuò)展為C4.5第64頁/共102頁避免過度擬合（Overfitting）4.6.7決策樹的常見問題通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)來構(gòu)造分類樹，可能無法達(dá)到最好的泛化性能。噪聲數(shù)據(jù)的影響某些決策僅基于少量數(shù)據(jù)，與客觀事實(shí)不符合第65頁/共102頁避免過度擬合（Overfitting）4.6.7決策樹的常見問題基本ID3算法描述增長樹的每一個(gè)分支的深度，直到恰好能對(duì)訓(xùn)練樣例完美地分類。數(shù)據(jù)中有噪聲。訓(xùn)練數(shù)據(jù)太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時(shí)。在以上任一種情況發(fā)生時(shí)，這個(gè)簡單的算法產(chǎn)生的樹會(huì)過度擬合訓(xùn)練樣例。第66頁/共102頁避免過度擬合（Overfitting）4.6.7決策樹的常見問題對(duì)于一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布（也就是包含訓(xùn)練集合以外的實(shí)例）上表現(xiàn)的卻更好時(shí)，我們說這個(gè)假設(shè)過度擬合（overfit）訓(xùn)練樣例。第67頁/共102頁避免過度擬合4.6.7決策樹的常見問題定義：給定一個(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ù)。第68頁/共102頁避免過度擬合4.6.7決策樹的常見問題第69頁/共102頁過度擬合與噪聲4.6.7決策樹的常見問題分類或?qū)傩栽肼暥紩?huì)導(dǎo)致過度擬合

增加噪聲實(shí)例<<medium,green,circle>,+>（實(shí)際為-）。第70頁/共102頁過度擬合與噪聲4.6.7決策樹的常見問題第71頁/共102頁過度擬合與噪聲4.6.7決策樹的常見問題噪聲也會(huì)直接導(dǎo)致樣本的沖突(相同描述，不同分類)。應(yīng)將葉結(jié)點(diǎn)標(biāo)號(hào)為主要的分類

<<big,red,circle>,->(實(shí)際上為+)。若屬性不完備且不足以判別分類時(shí)，也可能導(dǎo)致樣本的沖突。第72頁/共102頁避免過度擬合的方法—剪枝4.6.7決策樹的常見問題預(yù)修剪：支持度不夠則停止樹的增長。后修剪：置信度不夠則修剪掉該分支。第73頁/共102頁哪種方法被實(shí)踐證明更有效？原因是什么？避免過度擬合的方法—剪枝4.6.7決策樹的常見問題預(yù)修剪中精確地估計(jì)何時(shí)停止增長樹很困難。第74頁/共102頁無論是通過預(yù)修剪還是后修剪來得到正確大小的樹，一個(gè)關(guān)鍵的問題是使用什么樣的準(zhǔn)則來確定最終正確樹的大小。

避免過度擬合的方法—剪枝4.6.7決策樹的常見問題第75頁/共102頁修剪方法4.6.7決策樹的常見問題使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評(píng)估通過后修剪方法從樹上修剪結(jié)點(diǎn)的效用。第76頁/共102頁修剪方法4.6.7決策樹的常見問題使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)測(cè)試來估計(jì)擴(kuò)展（或修剪）一個(gè)特定的結(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。例如，Quinlan（1986）使用一種卡方（chi-square）測(cè)試來估計(jì)進(jìn)一步擴(kuò)展結(jié)點(diǎn)是否能改善在整個(gè)實(shí)例分布上的性能，還是僅僅改善了在當(dāng)前的訓(xùn)練數(shù)據(jù)上的性能。第77頁/共102頁修剪方法4.6.7決策樹的常見問題使用一個(gè)明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹編碼的復(fù)雜度，當(dāng)這個(gè)編碼的長度最小時(shí)停止增長樹。這個(gè)方法基于一種啟發(fā)式規(guī)則，被稱為最小描述長度（MinimumDescriptionLength）的準(zhǔn)則。第78頁/共102頁訓(xùn)練和驗(yàn)證集法4.6.7決策樹的常見問題AllavailabledataTrainingSetGrowingSetPruningSetTestSet第79頁/共102頁訓(xùn)練和驗(yàn)證集法的動(dòng)機(jī)4.6.7決策樹的常見問題即使學(xué)習(xí)器可能會(huì)被訓(xùn)練集合中的隨機(jī)錯(cuò)誤和巧合規(guī)律性所誤導(dǎo)，但驗(yàn)證集合不大可能表現(xiàn)出同樣的隨機(jī)波動(dòng)。所以，驗(yàn)證集合可以用來對(duì)過度擬合訓(xùn)練集中的虛假特征提供一個(gè)防護(hù)檢驗(yàn)。當(dāng)然，很重要的一點(diǎn)，驗(yàn)證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計(jì)意義的實(shí)例樣本。第80頁/共102頁合并連續(xù)值屬性4.6.7決策樹的常見問題如何把連續(xù)值的決策屬性加入到?jīng)Q策樹中？以通過動(dòng)態(tài)地定義新的離散值屬性來實(shí)現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合。例如，對(duì)于連續(xù)值的屬性A，算法可動(dòng)態(tài)地創(chuàng)建一個(gè)新的布爾屬性Ac，如果A<c，那么為Ac真，否則為假。唯一的問題是如何選取最佳的閾值c。第81頁/共102頁舉例4.6.7決策樹的常見問題對(duì)于與決策樹的特定結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例，進(jìn)一步假定其屬性Temperature和目標(biāo)屬性PlayTennis的值如下：Temperature: 40 48 60 72 80 90PlayTennis: No No Yes Yes Yes No對(duì)屬性Temprature，應(yīng)該定義什么樣的基于閾值的布爾屬性呢？無疑，我們會(huì)選擇產(chǎn)生最大信息增益的閾值c。第82頁/共102頁舉例4.6.7決策樹的常見問題對(duì)于與決策樹的特定結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例，進(jìn)一步假定其屬性Temperature和目標(biāo)屬性PlayTennis的值如下：Temperature: 40 48 60 72 80 90PlayTennis: No No Yes Yes Yes No第83頁/共102頁舉例4.6.7決策樹的常見問題對(duì)屬性Temprature，應(yīng)該定義什么樣的基于閾值的布爾屬性呢？第84頁/共102頁舉例4.6.7決策樹的常見問題首先按照連續(xù)屬性A排序樣例，然后確定目標(biāo)分類不同的相鄰實(shí)例，于是我們可以產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值?？梢宰C明產(chǎn)生最大信息增益的c值必定位于這樣的邊界中。第85頁/共102頁舉例4.6.7決策樹的常見問題在當(dāng)前的例子中，有兩個(gè)候選閾值，它們對(duì)應(yīng)于目標(biāo)屬性PlayTennis變化時(shí)屬性Temperature的值：（48+60）/2和（80+90）/2。然后計(jì)算每一個(gè)候選屬性——Temperature>54和Temperature>85的信息增益，并選擇最好的（Temperature>54）?，F(xiàn)在這個(gè)動(dòng)態(tài)創(chuàng)建的布爾屬性便可以和其他候選的離散值屬性一同“競(jìng)爭(zhēng)”，以用于增長決策樹。第86頁/共102頁舉例4.6.7決策樹的常見問題如何把連續(xù)的屬性分割成多個(gè)區(qū)間？第87頁/共102頁屬性選擇的其他度量標(biāo)準(zhǔn)4.6.7決策樹的常見問題信息增益度量偏袒具有較多值的屬性。舉一個(gè)極端的例子，考慮屬性Date，它有大量的可能值。它會(huì)在所有屬性中有最大的信息增益。這是因?yàn)閱为?dú)Date就可以完全預(yù)測(cè)訓(xùn)練數(shù)據(jù)的目標(biāo)屬性。第88頁/共102頁屬性選擇的其他度量標(biāo)準(zhǔn)4.6.7決策樹的常見問題于是這個(gè)屬性會(huì)被選作樹的根結(jié)點(diǎn)的決策屬性并形成一棵深度為一級(jí)但卻非常寬的樹，這棵樹可以理想地分類訓(xùn)練數(shù)據(jù)。當(dāng)然，這個(gè)決策樹對(duì)于后來數(shù)據(jù)的性能會(huì)相當(dāng)差，因?yàn)楸M管它完美地分割了訓(xùn)練數(shù)據(jù)，但它不是一個(gè)好的預(yù)測(cè)器（predicator）。第89頁/共102頁舉例4.6.7決策樹的常見問題屬性Date太多的可能值必然把訓(xùn)練樣例分割成非常小的空間。因此，相對(duì)訓(xùn)練樣例，它會(huì)有非常高的信息增益，盡管對(duì)于未見實(shí)例它是一個(gè)非常差的目標(biāo)函數(shù)預(yù)測(cè)器。第90頁/共102頁增益比率4.6.7決策樹的常見問題增益比率通過加入一個(gè)稱作分裂信息（splitinformation）的項(xiàng)來懲罰類似Date的屬性，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性：其中S1到Sc是c個(gè)值的屬性A分割S而形成的c個(gè)樣例子集。

第91頁/共102頁舉例4.6.7決策樹的常見問題分裂信息實(shí)際上就是S關(guān)于屬性A的各值的熵。

ID3中熵是S關(guān)于學(xué)習(xí)到的樹要預(yù)測(cè)的目標(biāo)屬性的值的熵。第92頁/共102頁