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

1、上節(jié)課程內(nèi)容回顧什么是機(jī)器學(xué)習(xí)？機(jī)器學(xué)習(xí)的產(chǎn)生與發(fā)展貝葉斯定理貝葉斯分類算法上節(jié)課程內(nèi)容回顧明天太陽會(huì)升起嗎?他在一個(gè)袋子放了黑白各一個(gè)顆彈子。（太陽升起的概率？）第一天第二天太陽升起了，他加了一個(gè)白彈子在袋子里。（太陽升起的概率？）第三天太陽升起了，他又加了一個(gè)白彈子在袋子里。（太陽升起的概率？）。結(jié)論幾乎可以肯定，太陽總會(huì)升起。主要內(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、理學(xué)的角度定義決策樹是指使用系統(tǒng)分析方法，把各種決策方案及出現(xiàn)結(jié)果的可能性進(jìn)行分組排列，然后確定最佳方案的決策過程。 4.6.1 什么是決策樹？舉例:漁民投資決策點(diǎn)新船舊船好魚情(0.7)壞魚情(0.3)好魚情(0.7)壞魚情(0.3)$90000-$10000$80000$200004.6.1 什么是決策樹？什么是決策樹? 從機(jī)器學(xué)習(xí)的角度定義決策樹是運(yùn)用于分類的一種樹結(jié)構(gòu)。 4.6.1 什么是決策樹？決策樹的表示方法每個(gè)內(nèi)部節(jié)點(diǎn)（internal node）代表對(duì)某個(gè)屬性的一次測(cè)試。一條邊代表一個(gè)測(cè)試結(jié)果。葉子（leaf）代表某個(gè)類（class）或者類的分布（class distribut

3、ion）。最上面的節(jié)點(diǎn)是根結(jié)點(diǎn)。 4.6.1 什么是決策樹？舉例假設(shè)用一個(gè)決策樹表示一個(gè)關(guān)心電子產(chǎn)品的用戶是否會(huì)購買PC的知識(shí)，然后用它來預(yù)測(cè)某條記錄（某個(gè)人）的購買意向。4.6.1 什么是決策樹？舉例年齡?學(xué)生?信用狀況?否是是是否40否 是很好一般4.6.1 什么是決策樹？舉例類別：buys_computers=yes和buys_computers=no）。樣本向量為（age, student, credit_rating; buys_computers）被決策數(shù)據(jù)的格式為（age, student, credit_rating）輸入新的被決策的記錄，可以預(yù)測(cè)該記錄隸屬于哪個(gè)類。4.6.1

4、 什么是決策樹？決策樹分類過程決策樹通過把實(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 什么是決策樹？決策樹分類過程（續(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á)？決策樹與規(guī)則表達(dá)的轉(zhuǎn)換通常決策樹代表實(shí)例屬性值約束的合?。╟onjunction）的析取式（disjunction）。

5、從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹本身對(duì)應(yīng)這些合取的析取。(Buys_computer=age40 Credit_rating=excellent)4.6.1 什么是決策樹？決策樹學(xué)習(xí)的適用問題實(shí)例由“屬性-值”對(duì)（pair）表示 -實(shí)例是用一系列固定的屬性和它們的值來描述的。 -最簡(jiǎn)單的決策樹學(xué)習(xí)中，每一個(gè)屬性取少數(shù)的分離的值。 -擴(kuò)展的算法允許處理值域?yàn)閷?shí)數(shù)的屬性（例如，數(shù)字表示的溫度）。4.6.2 決策樹學(xué)習(xí)的適用問題決策樹學(xué)習(xí)的適用問題目標(biāo)函數(shù)具有離散的輸出值 -上面舉例的決策樹給每個(gè)實(shí)例賦予一個(gè)布爾型的分類（例如，yes或no）。 -決策樹方法很容易擴(kuò)展到學(xué)習(xí)有兩個(gè)以

6、上輸出值的函數(shù)。 -一種更強(qiáng)有力的擴(kuò)展算法允許學(xué)習(xí)具有實(shí)數(shù)值輸出的函數(shù)，盡管決策樹在這種情況下的應(yīng)用不太常見。4.6.2 決策樹學(xué)習(xí)的適用問題決策樹學(xué)習(xí)的適用問題可能需要析取的描述 -決策樹很自然地代表了析取表達(dá)式。 4.6.2 決策樹學(xué)習(xí)的適用問題決策樹學(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ù)就是要把樣例分類到

7、各可能的離散值對(duì)應(yīng)的類別中。已有的決策樹學(xué)習(xí)算法4.6.3 基本的決策樹學(xué)習(xí)算法大多數(shù)已開發(fā)的決策樹學(xué)習(xí)算法都是一種核心算法的變體。ID3(QUINLAN 1986)及其后繼的C4.5ID34.6.3 基本的決策樹學(xué)習(xí)算法基本的ID3算法通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)。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è)分支

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

9、佳的分類屬性？給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為： Entropy(S) -plog2p -plog2p 其中，p是在S中正例的比例，p是在S中負(fù)例的比例。在有關(guān)熵的所有計(jì)算中我們定義0log0為0。 舉例4.6.4 哪個(gè)屬性是最佳的分類屬性？假設(shè)S是一個(gè)關(guān)于某布爾概念的有14個(gè)樣例的集合，它包括9個(gè)正例和5個(gè)反例（用記號(hào)9+，5-來表示）。那么S相對(duì)于這個(gè)布爾分類的熵（Entropy）為：注意4.6.4 哪個(gè)屬性是最佳的分類屬性？如果S的所有成員屬于同一類，那么S的熵為0。例如，如果所有的成員是正的（p=1），那么p就是0，那么 Entropy(S)

10、 = 0。注意4.6.4 哪個(gè)屬性是最佳的分類屬性？當(dāng)集合中正反樣例的數(shù)量相等時(shí)熵為1。如果集合中正反例的數(shù)量不等時(shí)，熵介于0和1之間。 1.00,00.50.51.0某布爾分類的熵函數(shù)P隨著從0到1變化的曲線信息論中熵的解釋4.6.4 哪個(gè)屬性是最佳的分類屬性？熵確定了集合S中任意成員（即以均勻的概率隨機(jī)抽出的一個(gè)成員）的分類所需要的最少二進(jìn)制位數(shù)。信息論中熵的解釋4.6.4 哪個(gè)屬性是最佳的分類屬性？如果P是1，接收者知道抽出的樣例必為正，所以不必發(fā)任何消息，此時(shí)的熵為0。如果是P 0.5，必須用一個(gè)二進(jìn)制位來說明抽出的樣例是正還是負(fù)。如果是P 0.8，那么對(duì)所需的消息編碼方法是賦給正例集

11、合較短的編碼，可能性較小的反例集合較長(zhǎng)的編碼，平均每條消息的編碼少于1個(gè)二進(jìn)制位。 通用信息熵的定義4.6.4 哪個(gè)屬性是最佳的分類屬性？如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)（c-wise）的分類的熵定義為： 通用信息熵的定義4.6.4 哪個(gè)屬性是最佳的分類屬性？為什么對(duì)數(shù)的底數(shù)是2?熵的最大可能值是多少?信息增益(Information Gain)4.6.4 哪個(gè)屬性是最佳的分類屬性？一個(gè)屬性的信息增益就是由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低。信息增益(Information Gain)4.6.4 哪個(gè)屬性是最佳的分類屬性？一個(gè)屬性A相對(duì)樣例集合S的信息增益Gain(S,

12、A)被定義為:信息增益(Information Gain)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ù)。 舉例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è)樣例得到的信息增益可

13、以計(jì)算如下。舉例4.6.4 哪個(gè)屬性是最佳的分類屬性？舉例4.6.4 哪個(gè)屬性是最佳的分類屬性？信息增益與ID34.6.4 哪個(gè)屬性是最佳的分類屬性？信息增益正是ID3算法增長(zhǎng)樹的每一步中選取最佳屬性的度量標(biāo)準(zhǔn)。 舉例4.6.4 哪個(gè)屬性是最佳的分類屬性？ 見復(fù)印材料。課堂練習(xí): 畫出該示例的決策樹。Outlook?yesSunnyOvercastRain?舉例4.6.4 哪個(gè)屬性是最佳的分類屬性？D1,D2,D3.,D149+,5-D1,D2,D8,D9,D112+,3-D3,D7,D12,D134+,0-D4,D5,D6,D10,D143+,2-舉例4.6.4 哪個(gè)屬性是最佳的分類屬性？S

14、sunny=D1,D2,D8,D9,D11Gain(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決策樹學(xué)習(xí)中的假設(shè)空間搜索4.6.5 決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3算法可以被描述為從一個(gè)假設(shè)空間中搜索一個(gè)擬合訓(xùn)練樣例的假設(shè)。被ID3算法搜索的假設(shè)空間就是可能的決策樹的集合。ID3算法以一種從簡(jiǎn)單到復(fù)雜的爬山算法遍歷這個(gè)假設(shè)空間，從空的

15、樹開始，然后逐步考慮更加復(fù)雜的假設(shè)，目的是搜索到一個(gè)正確分類訓(xùn)練數(shù)據(jù)的決策樹。引導(dǎo)這種爬山搜索的評(píng)估函數(shù)是信息增益度量。 決策樹學(xué)習(xí)中的誤區(qū)4.6.5 決策樹學(xué)習(xí)中的假設(shè)空間搜索樹的深度應(yīng)盡量小。但貪婪搜索可能無法找到最小樹，頂層結(jié)點(diǎn)可能不是高區(qū)分度的。 計(jì)算復(fù)雜度4.6.5 決策樹學(xué)習(xí)中的假設(shè)空間搜索最壞情況是構(gòu)造出一棵完全樹，每條路徑都測(cè)試了所有特征。計(jì)算復(fù)雜度4.6.5 決策樹學(xué)習(xí)中的假設(shè)空間搜索各層i要對(duì)剩下的|A|-i個(gè)屬性計(jì)算最佳分割。一般來說，性能與屬性個(gè)數(shù)成線性關(guān)系。D就是樣本集決策樹學(xué)習(xí)的歸納偏置4.6.6 決策樹學(xué)習(xí)的歸納偏置歸納偏置是一系列前提，這些前提與訓(xùn)練數(shù)據(jù)一起演繹

16、論證未來實(shí)例的分類。決策樹學(xué)習(xí)的歸納偏置4.6.6 決策樹學(xué)習(xí)的歸納偏置歸納偏置是一系列前提，這些前提與訓(xùn)練數(shù)據(jù)一起演繹論證未來實(shí)例的分類。決策樹學(xué)習(xí)的歸納偏置4.6.6 決策樹學(xué)習(xí)的歸納偏置如果給定一個(gè)訓(xùn)練樣例的集合，那么通常有很多決策樹與這些樣例一致。所以，要描述ID3算法的歸納偏置，應(yīng)找到它從所有一致的假設(shè)中選擇一個(gè)的根據(jù)。 決策樹學(xué)習(xí)的歸納偏置4.6.6 決策樹學(xué)習(xí)的歸納偏置ID3從這些決策樹中選擇哪一個(gè)呢？它選擇在使用簡(jiǎn)單到復(fù)雜的爬山算法遍歷可能的樹空間時(shí)遇到的第一個(gè)可接受的樹。 ID3的搜索策略4.6.6 決策樹學(xué)習(xí)的歸納偏置優(yōu)先選擇較短的樹而不是較長(zhǎng)的。選擇那些信息增益高的屬性離

17、根結(jié)點(diǎn)較近的樹。存在的問題4.6.6 決策樹學(xué)習(xí)的歸納偏置在ID3中使用的選擇屬性的啟發(fā)式規(guī)則和它遇到的特定訓(xùn)練樣例之間存在著微妙的相互作用。由于這一點(diǎn)，很難準(zhǔn)確地刻劃出ID3的歸納偏置。然而我們可以近似地把它的歸納偏置描述為一種對(duì)短的決策樹的偏好。近似的ID3算法歸納偏置 4.6.6 決策樹學(xué)習(xí)的歸納偏置BFS-ID3：較短的樹比較長(zhǎng)的優(yōu)先寬度優(yōu)先搜索？深度優(yōu)先搜索？近似的ID3算法歸納偏置 4.6.6 決策樹學(xué)習(xí)的歸納偏置BFS-ID3：原理/過程它從一個(gè)空的樹開始廣度優(yōu)先（breadth first）搜索逐漸復(fù)雜的樹，先考慮所有深度為1的樹，然后所有深度為2的，。一旦它找到了一個(gè)與訓(xùn)練數(shù)

18、據(jù)一致的決策樹，它返回搜索深度的最小的一致樹（例如，具有最少結(jié)點(diǎn)的樹）。這種廣度優(yōu)先搜索稱為BFS-ID3。BFS-ID3尋找最短的決策樹，因此精確地具有“較短的樹比較長(zhǎng)的得到優(yōu)先”的偏置。ID3可被看作BFS-ID3的一個(gè)有效近似，它使用一種貪婪的啟發(fā)式搜索企圖發(fā)現(xiàn)最短的樹，而不用進(jìn)行完整的廣度優(yōu)先搜索來遍歷假設(shè)空間。 近似的ID3算法歸納偏置 4.6.6 決策樹學(xué)習(xí)的歸納偏置ID3歸納偏置的更貼切近似：較短的樹比較長(zhǎng)的得到優(yōu)先。那些信息增益高的屬性更靠近根結(jié)點(diǎn)的樹得到優(yōu)先。為什么ID3中選擇短的假設(shè)優(yōu)先？4.6.6 決策樹學(xué)習(xí)的歸納偏置ID3算法中優(yōu)選較短決策樹的歸納偏置，是不是從訓(xùn)練數(shù)據(jù)

19、中泛化的可靠基礎(chǔ)？哲學(xué)家們以及其他學(xué)者已經(jīng)對(duì)這樣的問題爭(zhēng)論幾個(gè)世紀(jì)了，而且這個(gè)爭(zhēng)論至今還未解決。威廉奧坎姆大約在1320年提出類似的論點(diǎn)，是最早討論這個(gè)問題的人之一，所以這個(gè)偏置經(jīng)常被稱為“奧坎姆剃刀”（Occams razor）。Occams razor4.6.6 決策樹學(xué)習(xí)的歸納偏置奧卡姆剃刀（Occams Razor, Ockhams Razor）是由14世紀(jì)邏輯學(xué)家、圣方濟(jì)各會(huì)修士奧卡姆的威廉（William of Occam）提出的一個(gè)原理。 Occams razor4.6.6 決策樹學(xué)習(xí)的歸納偏置Entities should not be multiplied unnecessa

20、rily （“如無必要，勿增實(shí)體”。）Occams razor4.6.6 決策樹學(xué)習(xí)的歸納偏置威廉使用這個(gè)原理證明了許多結(jié)論，包括“通過思辨不能得出上帝存在的結(jié)論”。這使他不受羅馬教皇的歡迎。 Occams razor4.6.6 決策樹學(xué)習(xí)的歸納偏置許多科學(xué)家接受或者（獨(dú)立的）提出了奧卡姆剃刀原理，例如萊布尼茲的“不可觀測(cè)事物的同一性原理”和牛頓提出的一個(gè)原則：如果某一原因既真又足以解釋自然事物的特性，則我們不應(yīng)當(dāng)接受比這更多的原因。 Occams razor4.6.6 決策樹學(xué)習(xí)的歸納偏置對(duì)于科學(xué)家，這一原理最常見的形式是： 當(dāng)你有兩個(gè)處于競(jìng)爭(zhēng)地位的理論能得出同樣的結(jié)論，那么簡(jiǎn)單的那個(gè)更好。

21、 Occams razor（奧卡姆剃刀的強(qiáng)形式）4.6.6 決策樹學(xué)習(xí)的歸納偏置如果你有兩個(gè)原理，它們都能解釋觀測(cè)到的事實(shí)，那么你應(yīng)該使用簡(jiǎn)單的那個(gè)，直到發(fā)現(xiàn)更多的證據(jù)。 對(duì)于現(xiàn)象最簡(jiǎn)單的解釋往往比較復(fù)雜的解釋更正確。Occams razor（奧卡姆剃刀的強(qiáng)形式）4.6.6 決策樹學(xué)習(xí)的歸納偏置如果你有兩個(gè)類似的解決方案，選擇最簡(jiǎn)單的。需要最少假設(shè)的解釋最有可能是正確的或者以這種自我肯定的形式出現(xiàn)：讓事情保持簡(jiǎn)單！ Occams razor（奧卡姆剃刀的強(qiáng)形式）4.6.6 決策樹學(xué)習(xí)的歸納偏置嚴(yán)格的說，它們應(yīng)該被稱為吝嗇定律，或者稱為樸素原則。 愛因斯坦說: “萬事萬物應(yīng)該盡量簡(jiǎn)單，而不是更簡(jiǎn)

22、單。”O(jiān)ccams razor（奧卡姆剃刀的強(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)的。 Occams razor（奧卡姆剃刀的強(qiáng)形式）4.6.7 決策樹的常見問題確定決策樹增長(zhǎng)的深度處理連續(xù)值的屬性選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理

23、不同代價(jià)的屬性提高計(jì)算效率 ID3擴(kuò)展為C4.5避免過度擬合（Overfitting）4.6.7 決策樹的常見問題通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)來構(gòu)造分類樹，可能無法達(dá)到最好的泛化性能。噪聲數(shù)據(jù)的影響某些決策僅基于少量數(shù)據(jù)，與客觀事實(shí)不符合避免過度擬合（Overfitting）4.6.7 決策樹的常見問題基本ID3算法描述增長(zhǎng)樹的每一個(gè)分支的深度，直到恰好能對(duì)訓(xùn)練樣例完美地分類。數(shù)據(jù)中有噪聲。訓(xùn)練數(shù)據(jù)太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時(shí)。在以上任一種情況發(fā)生時(shí)，這個(gè)簡(jiǎn)單的算法產(chǎn)生的樹會(huì)過度擬合訓(xùn)練樣例。避免過度擬合（Overfitting）4.6.7 決策樹的常見問題對(duì)于一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)

24、訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布（也就是包含訓(xùn)練集合以外的實(shí)例）上表現(xiàn)的卻更好時(shí)，我們說這個(gè)假設(shè)過度擬合（overfit）訓(xùn)練樣例。避免過度擬合4.6.7 決策樹的常見問題定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)hH，如果存在其他的假設(shè)hH，使得在訓(xùn)練樣例上h的錯(cuò)誤率比h小，但在整個(gè)實(shí)例分布上h的錯(cuò)誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。 避免過度擬合4.6.7 決策樹的常見問題過度擬合與噪聲4.6.7 決策樹的常見問題分類或?qū)傩栽肼暥紩?huì)導(dǎo)致過度擬合增加噪聲實(shí)例, +（實(shí)際為-）。過度擬合與噪聲4.6.7 決策樹的常見問題過度擬合與噪聲4.6.7 決策樹的常見問題噪聲也會(huì)直接導(dǎo)致樣

25、本的沖突(相同描述，不同分類)。應(yīng)將葉結(jié)點(diǎn)標(biāo)號(hào)為主要的分類, - (實(shí)際上為+)。若屬性不完備且不足以判別分類時(shí)，也可能導(dǎo)致樣本的沖突。避免過度擬合的方法剪枝4.6.7 決策樹的常見問題預(yù)修剪：支持度不夠則停止樹的增長(zhǎng)。后修剪：置信度不夠則修剪掉該分支。哪種方法被實(shí)踐證明更有效？原因是什么？避免過度擬合的方法剪枝4.6.7 決策樹的常見問題預(yù)修剪中精確地估計(jì)何時(shí)停止增長(zhǎng)樹很困難。 無論是通過預(yù)修剪還是后修剪來得到正確大小的樹，一個(gè)關(guān)鍵的問題是使用什么樣的準(zhǔn)則來確定最終正確樹的大小。 避免過度擬合的方法剪枝4.6.7 決策樹的常見問題修剪方法4.6.7 決策樹的常見問題使用與訓(xùn)練樣例截然不同的一

26、套分離的樣例，來評(píng)估通過后修剪方法從樹上修剪結(jié)點(diǎn)的效用。 修剪方法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ù)上的性能。 修剪方法4.6.7 決策樹的常見問題使用一個(gè)明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹編碼的復(fù)雜度，當(dāng)這個(gè)編碼的長(zhǎng)度最小時(shí)停止增長(zhǎng)樹。這個(gè)方法基于一種啟發(fā)式規(guī)則，被稱為最小描述長(zhǎng)度（Minimum Description Leng

27、th）的準(zhǔn)則 。訓(xùn)練和驗(yàn)證集法4.6.7 決策樹的常見問題All available dataTraining SetGrowing SetPruning SetTest Set訓(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í)例樣本。 合并連續(xù)值屬性 4.6.7 決策樹的常見問題如何把連續(xù)值的決策屬性加入到?jīng)Q策樹中？以通過動(dòng)態(tài)地定義新的離散值屬性來實(shí)現(xiàn)，即先把

28、連續(xù)值屬性的值域分割為離散的區(qū)間集合。例如，對(duì)于連續(xù)值的屬性A，算法可動(dòng)態(tài)地創(chuàng)建一個(gè)新的布爾屬性Ac，如果A54 和Temperature85的信息增益，并選擇最好的（Temperature54）?，F(xiàn)在這個(gè)動(dòng)態(tài)創(chuàng)建的布爾屬性便可以和其他候選的離散值屬性一同“競(jìng)爭(zhēng)”，以用于增長(zhǎng)決策樹。 舉例 4.6.7 決策樹的常見問題如何把連續(xù)的屬性分割成多個(gè)區(qū)間？屬性選擇的其他度量標(biāo)準(zhǔn) 4.6.7 決策樹的常見問題信息增益度量偏袒具有較多值的屬性。舉一個(gè)極端的例子，考慮屬性Date，它有大量的可能值。它會(huì)在所有屬性中有最大的信息增益。這是因?yàn)閱为?dú)Date就可以完全預(yù)測(cè)訓(xùn)練數(shù)據(jù)的目標(biāo)屬性。屬性選擇的其他度量標(biāo)

29、準(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）。舉例 4.6.7 決策樹的常見問題屬性Date太多的可能值必然把訓(xùn)練樣例分割成非常小的空間。因此，相對(duì)訓(xùn)練樣例，它會(huì)有非常高的信息增益，盡管對(duì)于未見實(shí)例它是一個(gè)非常差的目標(biāo)函數(shù)預(yù)測(cè)器。 增益比率4.6.7 決策樹的常見問題增益比率通過加入一個(gè)稱作分裂信息（split information）的項(xiàng)來懲罰類似Date的屬性，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性： 其中S1到Sc是c個(gè)值的屬性A分割S而形成的c個(gè)樣例子集。 舉例 4.6.7 決策樹的常見問題分裂信息實(shí)際上就是S關(guān)于屬性A的各值的熵。 ID3中熵是S關(guān)于學(xué)習(xí)到的樹要預(yù)測(cè)的目標(biāo)屬性的值的熵。 增益比率4.6.7 決策樹的常見問題增益比率度量是用前面的增益度量和這里的分裂信息度量來共同定義的，即：處理缺少屬性值的訓(xùn)練樣例 4.6.7