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

第3章決策樹學(xué)習(xí)(Decision-TreeAlgorithm)第3章決策樹學(xué)習(xí)排名主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統(tǒng)計學(xué)習(xí)SVM581995Vapnik,V.NQiangYang4關(guān)聯(lián)分析Apriori521994RakeshAgrawalChristosFaloutsos5統(tǒng)計學(xué)習(xí)EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進(jìn)AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg共有145人參加了ICDM2006Panel(會議的專題討論),并對18種候選算法進(jìn)行投票，選出了機(jī)器學(xué)習(xí)10大算法ICDM2006會議的算法投票結(jié)果排名主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.561199概論決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一是一種逼近離散值函數(shù)的方法很好的健壯性能夠?qū)W習(xí)析取表達(dá)式ID3,Assistant,C4.5搜索一個完整表示的假設(shè)空間歸納偏置是優(yōu)先選擇較小的樹決策樹表示了多個if-then規(guī)則概論決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一提綱決策樹定義適用問題特征基本ID3算法決策樹學(xué)習(xí)的歸納偏置訓(xùn)練數(shù)據(jù)的過度擬合…提綱決策樹定義決策樹基本概念關(guān)于分類問題分類（Classification）任務(wù)就是通過學(xué)習(xí)獲得一個目標(biāo)函數(shù)（TargetFunction）f,將每個屬性集x映射到一個預(yù)先定義好的類標(biāo)號y。分類任務(wù)的輸入數(shù)據(jù)是記錄的集合，每條記錄也稱為實例或者樣例。用元組(X,y)表示，其中，X是屬性集合，y是一個特殊的屬性，指出樣例的類標(biāo)號（也稱為分類屬性或者目標(biāo)屬性）決策樹基本概念關(guān)于分類問題分類（Classifica決策樹基本概念關(guān)于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標(biāo)號人類恒溫毛發(fā)是否否是否哺乳動物海龜冷血鱗片否半否是否爬行類鴿子恒溫羽毛否否是是否鳥類鯨恒溫毛發(fā)是是否否否哺乳類Xy分類與回歸分類目標(biāo)屬性y是離散的，回歸目標(biāo)屬性y是連續(xù)的決策樹基本概念關(guān)于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動決策樹基本概念解決分類問題的一般方法

通過以上對分類問題一般方法的描述，可以看出分類問題一般包括兩個步驟：

1、模型構(gòu)建（歸納）通過對訓(xùn)練集合的歸納，建立分類模型。

2、預(yù)測應(yīng)用（推論）根據(jù)建立的分類模型，對測試集合進(jìn)行測試。決策樹基本概念解決分類問題的一般方法通過以上決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學(xué)習(xí)算法學(xué)習(xí)模型模型應(yīng)用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N415M？訓(xùn)練集（類標(biāo)號已知）檢驗集（類標(biāo)號未知）歸納推論決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y決策樹表示法內(nèi)部節(jié)點(包括根節(jié)點)指定了對實例的某個屬性的測試節(jié)點的每個后繼分支對應(yīng)于該屬性的一個可能值葉子節(jié)點即為實例所屬的分類

決策樹代表實例屬性值約束的合取的析取式圖3-1

概念PlayTennis的決策樹OutlookHumidityWindNoYesNoYesYesSunnyRainyOvercastHighNormalStrongWeak決策樹表示法內(nèi)部節(jié)點(包括根節(jié)點)指定了對實例的某個屬性的測決策樹學(xué)習(xí)的適用問題適用問題的特征實例由“屬性-值”對表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例問題舉例醫(yī)學(xué)中的應(yīng)用（如根據(jù)疾病分類患者、疾病分析與預(yù)測）根據(jù)起因分類設(shè)備故障（故障診斷）根據(jù)拖欠支付的可能性分類貸款申請分類問題核心任務(wù)是把樣例分類到各可能的離散值對應(yīng)的類別決策樹學(xué)習(xí)的適用問題適用問題的特征基本的決策樹學(xué)習(xí)算法ID3大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表該方法使用信息增益度選擇測試屬性?；镜臎Q策樹學(xué)習(xí)算法ID3大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法ID3算法通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)。構(gòu)造過程：ID3算法的核心問題是選取在樹的每個節(jié)點要測試的屬性。選擇根節(jié)點－使用統(tǒng)計測試確定每一個實例屬性單獨分類訓(xùn)練樣例的能力，分類能力最好的屬性被選作樹的根節(jié)點為根節(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過程，用每個分支節(jié)點關(guān)聯(lián)的訓(xùn)練樣例來選取在該點被測試的最佳屬性，直到滿足以下兩個條件中的任一個:1）所有的屬性已經(jīng)被這條路徑包括；

2）與這個節(jié)點關(guān)聯(lián)的所有訓(xùn)練樣例具有相同的目標(biāo)屬性值ID3算法通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)。構(gòu)造過程：表3-1用于學(xué)習(xí)布爾函數(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下加一個新的分支對應(yīng)測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節(jié)點，節(jié)點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root表3-1用于學(xué)習(xí)布爾函數(shù)的ID3算法ID3(Exampl最佳分類屬性信息增益(InformationGain)用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為

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

Entropy(S)=最佳分類屬性信息增益(InformationGain)S的所有成員屬于同一類，Entropy(S)=0；S的正反樣例數(shù)量相等，Entropy(S)=1；S的正反樣例數(shù)量不等，熵介于0，1之間S的所有成員屬于同一類，Entropy(S)=0；拋一枚均勻硬幣的信息熵是多少？解：出現(xiàn)正面與反面的概率均為0.5，信息熵是拋一枚均勻硬幣的信息熵是多少？用信息增益度量期望的熵降低屬性的信息增益，由于使用這個屬性分割樣例而導(dǎo)致的期望熵降低一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：

Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)；用信息增益度量期望的熵降低<big,red,circle>:+<small,red,circle>:+<small,red,square>:<big,blue,circle>:2+,2:E=1sizebigsmall1+,11+,1E=1E=1Gain=1(0.51+0.51)=02+,2:E=1colorredblue2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.3112+,2

:E=1shapecirclesquare2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.311計算屬性的信息增益<big,red,circle>:+DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標(biāo)概念PlayTennis的訓(xùn)練樣例DayOutlookTemperatureHumidityWHumidityS：[9+,5-]E(S)=0.940HighNormal[3+,4-]E=0.985[6+,1-]E=0.592Gain(S,Humidity)=0.940-(7/14)*0.985-(7/14)*0.592=0.151WindS：[9+,5-]E(S)=0.940WeakStrong[6+,2-]E=0.811[3+,3-]E=1Gain(S,Wind)=0.940-(8/14)*0.811-(6/14)*1=0.048計算屬性的信息增益HumidityS：[9+,5-]HighNormal[3+21考慮表3-2的訓(xùn)練數(shù)據(jù)所代表的學(xué)習(xí)任務(wù)。創(chuàng)建決策樹的根節(jié)點。計算每一個候選屬性的信息增益，然后選擇信息增益最高的一個。

Gain（S，Outlook）＝0.246

Gain（S，Humidity）＝0.151Gain（S，Wind）＝0.048Gain（S，Temperature）＝0.029

根據(jù)信息增益標(biāo)準(zhǔn)，屬性O(shè)utlook被選作根節(jié)點的決策屬性，并為它的每一個可能值（Sunny、Overcast和Rainy）在根節(jié)點下創(chuàng)建分支，得到部分決策樹顯示在圖3-4中。對非終端的后繼節(jié)點再重復(fù)前面的過程以選擇一個新的屬性來分割訓(xùn)練樣例，這一次僅使用與這個節(jié)點關(guān)聯(lián)的訓(xùn)練樣例，直到滿足結(jié)束條件。ID3算法示例21考慮表3-2的訓(xùn)練數(shù)據(jù)所代表的學(xué)習(xí)任務(wù)。創(chuàng)建決策樹的根節(jié)DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標(biāo)概念PlayTennis的訓(xùn)練樣例DayOutlookTemperatureHumidityW23ID3算法步驟1OutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.02923ID3算法步驟1OutlookSunnyRainyOveOutlook??YesSunnyOvercastRainD1,2,8,9,11D3,7,12,13D4,5,6,11,14D1~14[9+,5-][2+,3-][4+,0-][3+,2-]什么屬性？ID3算法第一步后形成的部分決策樹Outlook??YesSunnyOvercastRainD25ID3算法步驟2HumidityWindHighNormal[D1,D2,D8][0+,3-][D9,D11][2+,0-]StrongWeak[D6,D14][0+,2-][D4,D4,D10][3+,0-]NoYesNoYesYesOutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(SSunny,Humidity)=0.970Gain(SSunny,Temperature)=0.570Gain(SSunny,Wind)=0.019Gain(SRain,Humidity)=0.019Gain(SRain,Temperature)=0.019Gain(SRain,Wind)=0.97025ID3算法步驟2HumidityWindHighNorm26決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3算法搜索的假設(shè)空間就是可能的決策樹的集合。ID3以爬山算法遍歷這個假設(shè)空間，引導(dǎo)這種爬山搜索的評估函數(shù)是信息增益度量。觀察ID3的搜索空間和搜索策略，認(rèn)識到這個算法的優(yōu)勢和不足：假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間維護(hù)單一的當(dāng)前假設(shè)（不同于上章變型空間候選消除算法），不能判斷有多少個其他的決策樹也與現(xiàn)有的訓(xùn)練數(shù)據(jù)一致不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步都使用當(dāng)前所有的訓(xùn)練樣例，不同于基于單獨的訓(xùn)練樣例遞增作出決定，容錯性增強(qiáng)26決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3算法搜索的假設(shè)空間就是可決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些信息增益高的屬性離根節(jié)點較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先近似在于ID3得到局部最優(yōu)，而不一定是全局最優(yōu)一個精確具有這個歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根節(jié)點的樹優(yōu)先決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略限定偏置和優(yōu)選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個完整的假設(shè)空間，但不徹底地搜索這個空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對搜索空間的定義限定偏置和優(yōu)選偏置ID3和候選消除算法的比較限定偏置和優(yōu)選偏置優(yōu)選偏置（搜索偏置）ID3的歸納偏置是對某種假設(shè)勝過其他假設(shè)的一種優(yōu)選，對最終可列舉的假設(shè)沒有硬性限制限定偏置（語言偏置）候選消除算法的偏置是對待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要優(yōu)選偏置和限定偏置的結(jié)合考慮第1章下棋的例子（優(yōu)選偏置和限定偏置）限定偏置和優(yōu)選偏置優(yōu)選偏置（搜索偏置）為什么短的假設(shè)優(yōu)先?ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運動的簡單假設(shè)；簡單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少；簡單假設(shè)對訓(xùn)練樣例的針對性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述。為什么短的假設(shè)優(yōu)先?ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀設(shè)想你是在一條積雪的街上行走。在你前面有一個人帶著一頂黑色的高筒禮帽。街對面站著一群男孩，覺得這頂禮帽是個很好的目標(biāo)，其中一個扔雪球一下?lián)糁辛嗣弊?。讓我們舉出兩種解釋來說明這頂帽子的隨后遭遇。第一，在帽子受擊的一剎那，一隊天使疾飛而下，出其不意地把帽子從那人頭上揭走了。第二，雪球把帽子擊落了。我們將選擇？？種解釋。這就是科學(xué)上普遍適用的所謂“節(jié)儉律”的簡單說明。這條定律的意義，就在于說明，最可能的解釋就是最好的解釋，有時這條定律又被稱為奧坎姆剃刀

奧坎姆剃刀設(shè)想你是在一條積雪的街上行走。在你前面有一個人帶著為什么短的假設(shè)優(yōu)先奧坎姆剃刀的困難可以定義很多小的假設(shè)集合，根據(jù)什么相信有短描述的決策樹組成的小假設(shè)集合比其他可定義的小假設(shè)集合更適當(dāng)？假設(shè)的規(guī)模由學(xué)習(xí)器內(nèi)部使用的特定表示決定從生物進(jìn)化的觀點看內(nèi)部表示和奧坎姆剃刀原則為什么短的假設(shè)優(yōu)先奧坎姆剃刀的困難決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價的屬性提高計算效率針對這些問題，ID3被擴(kuò)展成C4.5決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題避免過度擬合數(shù)據(jù)過度擬合對于一個假設(shè)，當(dāng)存在其它的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例。定義：給定一個假設(shè)空間H，一個假設(shè)hH，如果存在其它的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。樹的規(guī)模accuracyontrainingdataontestdata避免過度擬合數(shù)據(jù)過度擬合樹的規(guī)模accuracyontra避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因（1）一種可能原因是訓(xùn)練樣例含有隨機(jī)錯誤或噪聲SunnyHotNormalStrongPlayTennis＝No避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因（1）SunnyH避免過度擬合數(shù)據(jù)（3）導(dǎo)致過度擬合的原因（2）當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點時，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標(biāo)函數(shù)并無關(guān)系。過度擬合使決策樹的精度降低（10～25）％避免過度擬合數(shù)據(jù)（3）導(dǎo)致過度擬合的原因（2）避免過度擬合數(shù)據(jù)（4）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功避免過度擬合數(shù)據(jù)（4）避免過度擬合的方法避免過度擬合數(shù)據(jù)（5）避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修剪節(jié)點的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計測試來估計擴(kuò)展（或修剪）一個特定的節(jié)點是否有可能改善在訓(xùn)練集合外的實例上的性能。使用一個明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個編碼的長度最小時停止樹增長。避免過度擬合數(shù)據(jù)（5）避免過度擬合的關(guān)鍵避免過度擬合數(shù)據(jù)（6）方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法。可用數(shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機(jī)：即使學(xué)習(xí)器可能會被訓(xùn)練集合誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機(jī)波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗證集合。避免過度擬合數(shù)據(jù)（6）方法評述錯誤率降低修剪將樹上的每一個節(jié)點作為修剪的候選對象修剪步驟刪除以此節(jié)點為根的子樹，使它成為葉結(jié)點把和該節(jié)點關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節(jié)點繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止數(shù)據(jù)分成3個子集訓(xùn)練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來引導(dǎo)修剪錯誤率降低修剪將樹上的每一個節(jié)點作為修剪的候選對象決策樹學(xué)習(xí)中錯誤率降低的修剪效果決策樹學(xué)習(xí)中錯誤率降低的修剪效果規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地擬合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價的規(guī)則集合，方法是為從根節(jié)點到葉節(jié)點的每一條路徑創(chuàng)建一條規(guī)則通過刪除不會導(dǎo)致估計精度降低的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計精度對它們進(jìn)行排序，并按這樣的順序應(yīng)用這些規(guī)則來分類后來的實例規(guī)則后修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地擬規(guī)則后修剪（2）例子if(outlook=sunny)(Humidity=High)thenPlayTennis=Noif(outlook=sunny)(Humidity=Normal)thenPlayTennis=Yes…考慮刪除先行詞(outlook=sunny)或(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第二個前件作為進(jìn)一步的修剪步驟規(guī)則后修剪（2）例子規(guī)則后修剪（3）規(guī)則精度估計方法使用與訓(xùn)練集不相交的驗證集基于訓(xùn)練集合本身被C4.5使用，使用一種保守估計來彌補(bǔ)訓(xùn)練數(shù)據(jù)有利于當(dāng)前規(guī)則的估計偏置過程先計算規(guī)則在它應(yīng)用的訓(xùn)練樣例上的精度然后假定此估計精度為二項式分布，并計算它的標(biāo)準(zhǔn)差對于一個給定的置信區(qū)間，采用下界估計作為規(guī)則性能的度量評論對于大的數(shù)據(jù)集，保守預(yù)測非常接近觀察精度，隨著數(shù)據(jù)集合的減小，離觀察精度越來越遠(yuǎn)不是統(tǒng)計有效（此概念第5章介紹），但是實踐中發(fā)現(xiàn)有效規(guī)則后修剪（3）規(guī)則精度估計方法規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點使用的不同上下文消除了根節(jié)點附近的屬性測試和葉節(jié)點附近的屬性測試的區(qū)別提高了可讀性規(guī)則后修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集的好處合并連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的樹的決策節(jié)點的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態(tài)地定義新的離散值屬性來實現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合合并連續(xù)值屬性ID3被限制為取離散值的屬性合并連續(xù)值屬性（2）例子，Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性選擇產(chǎn)生最大信息增益的閾值按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實例產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候選閾值關(guān)聯(lián)的信息增益評估這些候選值方法的擴(kuò)展連續(xù)的屬性分割成多個區(qū)間，而不是單一閾值的兩個空間合并連續(xù)值屬性（2）例子，屬性選擇的其它度量標(biāo)準(zhǔn)信息增益度量存在一個內(nèi)在偏置，偏向具有較多值的屬性避免方法，其它度量，比如增益比率增益比率通過加入一個被稱作分裂信息的項來懲罰多值屬性，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性

SplitInformation(S,A)=

GainRatio(S,A)=分裂信息項阻礙選擇值為均勻分布的屬性問題，當(dāng)某個SiS。解決方法：采用一些啟發(fā)式規(guī)則，比如僅對增益高過平均值的屬性應(yīng)用增益比率測試屬性選擇的其它度量標(biāo)準(zhǔn)信息增益度量存在一個內(nèi)在偏置，偏向具有屬性選擇的其它度量標(biāo)準(zhǔn)（2）基于距離的度量定義了數(shù)據(jù)劃分間的一種距離尺度計算每個屬性產(chǎn)生的劃分與理想劃分間的距離選擇最接近完美劃分的屬性LopezdeMantaras定義了這個距離度量，證明了它不偏向有大量值的屬性此外Mingers實驗，不同的屬性選擇度量對最終精度的影響小于后修剪的程度和方法的影響屬性選擇的其它度量標(biāo)準(zhǔn)（2）基于距離的度量缺少屬性值的訓(xùn)練樣例例子，醫(yī)學(xué)領(lǐng)域經(jīng)常需要根據(jù)此屬性值已知的實例來估計這個缺少的屬性值為了評估屬性A是否是決策節(jié)點n的最佳測試屬性，要計算決策樹在該節(jié)點的信息增益Gain(S,A)。假定<x,c(x)>是S中的一個訓(xùn)練樣例，并且其屬性A的值A(chǔ)(x)未知缺少屬性值的訓(xùn)練樣例例子，醫(yī)學(xué)領(lǐng)域缺少屬性值的訓(xùn)練樣例（2）處理缺少屬性值的策略一種策略是賦給它節(jié)點n的訓(xùn)練樣例中該屬性的最常見值另一種策略是賦給它節(jié)點n的被分類為c(x)的訓(xùn)練樣例中該屬性的最常見值更復(fù)雜的策略，為A的每個可能值賦予一個概率，而不是簡單地將最常見的值賦給A(x)缺少屬性值的訓(xùn)練樣例（2）處理缺少屬性值的策略處理不同代價的屬性實例的屬性可能與代價相關(guān)優(yōu)先選擇盡可能使用低代價屬性的決策樹，僅當(dāng)需要產(chǎn)生可靠的分類時才依賴高代價屬性通過引入一個代價項到屬性選擇度量中，可以使ID3算法考慮屬性代價Tan和Schlimmer的例子處理不同代價的屬性實例的屬性可能與代價相關(guān)C4.5改進(jìn)的具體方面用信息增益率來選擇屬性克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足?？梢蕴幚磉B續(xù)數(shù)值型屬性采用了一種后剪枝方法對于缺失值的處理C4.5改進(jìn)的具體方面用信息增益率來選擇屬性5454小結(jié)和補(bǔ)充讀物決策樹學(xué)習(xí)為概念學(xué)習(xí)和學(xué)習(xí)其他離散值的函數(shù)提供了一個實用的方法ID3算法貪婪算法從根向下推斷決策樹搜索完整的假設(shè)空間歸納偏置，較小的樹過度擬合問題ID3算法的擴(kuò)展小結(jié)和補(bǔ)充讀物決策樹學(xué)習(xí)為概念學(xué)習(xí)和學(xué)習(xí)其他離散值的函數(shù)提供參考參考演講完畢，謝謝觀看！演講完畢，謝謝觀看！第3章決策樹學(xué)習(xí)(Decision-TreeAlgorithm)第3章決策樹學(xué)習(xí)排名主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統(tǒng)計學(xué)習(xí)SVM581995Vapnik,V.NQiangYang4關(guān)聯(lián)分析Apriori521994RakeshAgrawalChristosFaloutsos5統(tǒng)計學(xué)習(xí)EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進(jìn)AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg共有145人參加了ICDM2006Panel(會議的專題討論),并對18種候選算法進(jìn)行投票，選出了機(jī)器學(xué)習(xí)10大算法ICDM2006會議的算法投票結(jié)果排名主題算法得票數(shù)發(fā)表時間作者陳述人1分類C4.561199概論決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一是一種逼近離散值函數(shù)的方法很好的健壯性能夠?qū)W習(xí)析取表達(dá)式ID3,Assistant,C4.5搜索一個完整表示的假設(shè)空間歸納偏置是優(yōu)先選擇較小的樹決策樹表示了多個if-then規(guī)則概論決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一提綱決策樹定義適用問題特征基本ID3算法決策樹學(xué)習(xí)的歸納偏置訓(xùn)練數(shù)據(jù)的過度擬合…提綱決策樹定義決策樹基本概念關(guān)于分類問題分類（Classification）任務(wù)就是通過學(xué)習(xí)獲得一個目標(biāo)函數(shù)（TargetFunction）f,將每個屬性集x映射到一個預(yù)先定義好的類標(biāo)號y。分類任務(wù)的輸入數(shù)據(jù)是記錄的集合，每條記錄也稱為實例或者樣例。用元組(X,y)表示，其中，X是屬性集合，y是一個特殊的屬性，指出樣例的類標(biāo)號（也稱為分類屬性或者目標(biāo)屬性）決策樹基本概念關(guān)于分類問題分類（Classifica決策樹基本概念關(guān)于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標(biāo)號人類恒溫毛發(fā)是否否是否哺乳動物海龜冷血鱗片否半否是否爬行類鴿子恒溫羽毛否否是是否鳥類鯨恒溫毛發(fā)是是否否否哺乳類Xy分類與回歸分類目標(biāo)屬性y是離散的，回歸目標(biāo)屬性y是連續(xù)的決策樹基本概念關(guān)于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動決策樹基本概念解決分類問題的一般方法

通過以上對分類問題一般方法的描述，可以看出分類問題一般包括兩個步驟：

1、模型構(gòu)建（歸納）通過對訓(xùn)練集合的歸納，建立分類模型。

2、預(yù)測應(yīng)用（推論）根據(jù)建立的分類模型，對測試集合進(jìn)行測試。決策樹基本概念解決分類問題的一般方法通過以上決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學(xué)習(xí)算法學(xué)習(xí)模型模型應(yīng)用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N415M？訓(xùn)練集（類標(biāo)號已知）檢驗集（類標(biāo)號未知）歸納推論決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y決策樹表示法內(nèi)部節(jié)點(包括根節(jié)點)指定了對實例的某個屬性的測試節(jié)點的每個后繼分支對應(yīng)于該屬性的一個可能值葉子節(jié)點即為實例所屬的分類

決策樹代表實例屬性值約束的合取的析取式圖3-1

概念PlayTennis的決策樹OutlookHumidityWindNoYesNoYesYesSunnyRainyOvercastHighNormalStrongWeak決策樹表示法內(nèi)部節(jié)點(包括根節(jié)點)指定了對實例的某個屬性的測決策樹學(xué)習(xí)的適用問題適用問題的特征實例由“屬性-值”對表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例問題舉例醫(yī)學(xué)中的應(yīng)用（如根據(jù)疾病分類患者、疾病分析與預(yù)測）根據(jù)起因分類設(shè)備故障（故障診斷）根據(jù)拖欠支付的可能性分類貸款申請分類問題核心任務(wù)是把樣例分類到各可能的離散值對應(yīng)的類別決策樹學(xué)習(xí)的適用問題適用問題的特征基本的決策樹學(xué)習(xí)算法ID3大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表該方法使用信息增益度選擇測試屬性?；镜臎Q策樹學(xué)習(xí)算法ID3大多數(shù)決策樹學(xué)習(xí)算法是一種核心算法ID3算法通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)。構(gòu)造過程：ID3算法的核心問題是選取在樹的每個節(jié)點要測試的屬性。選擇根節(jié)點－使用統(tǒng)計測試確定每一個實例屬性單獨分類訓(xùn)練樣例的能力，分類能力最好的屬性被選作樹的根節(jié)點為根節(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過程，用每個分支節(jié)點關(guān)聯(lián)的訓(xùn)練樣例來選取在該點被測試的最佳屬性，直到滿足以下兩個條件中的任一個:1）所有的屬性已經(jīng)被這條路徑包括；

2）與這個節(jié)點關(guān)聯(lián)的所有訓(xùn)練樣例具有相同的目標(biāo)屬性值ID3算法通過自頂向下構(gòu)造決策樹來進(jìn)行學(xué)習(xí)。構(gòu)造過程：表3-1用于學(xué)習(xí)布爾函數(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下加一個新的分支對應(yīng)測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節(jié)點，節(jié)點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root表3-1用于學(xué)習(xí)布爾函數(shù)的ID3算法ID3(Exampl最佳分類屬性信息增益(InformationGain)用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性給定包含關(guān)于某個目標(biāo)概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為

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

Entropy(S)=最佳分類屬性信息增益(InformationGain)S的所有成員屬于同一類，Entropy(S)=0；S的正反樣例數(shù)量相等，Entropy(S)=1；S的正反樣例數(shù)量不等，熵介于0，1之間S的所有成員屬于同一類，Entropy(S)=0；拋一枚均勻硬幣的信息熵是多少？解：出現(xiàn)正面與反面的概率均為0.5，信息熵是拋一枚均勻硬幣的信息熵是多少？用信息增益度量期望的熵降低屬性的信息增益，由于使用這個屬性分割樣例而導(dǎo)致的期望熵降低一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：

Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)；用信息增益度量期望的熵降低<big,red,circle>:+<small,red,circle>:+<small,red,square>:<big,blue,circle>:2+,2:E=1sizebigsmall1+,11+,1E=1E=1Gain=1(0.51+0.51)=02+,2:E=1colorredblue2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.3112+,2

:E=1shapecirclesquare2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.311計算屬性的信息增益<big,red,circle>:+DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標(biāo)概念PlayTennis的訓(xùn)練樣例DayOutlookTemperatureHumidityWHumidityS：[9+,5-]E(S)=0.940HighNormal[3+,4-]E=0.985[6+,1-]E=0.592Gain(S,Humidity)=0.940-(7/14)*0.985-(7/14)*0.592=0.151WindS：[9+,5-]E(S)=0.940WeakStrong[6+,2-]E=0.811[3+,3-]E=1Gain(S,Wind)=0.940-(8/14)*0.811-(6/14)*1=0.048計算屬性的信息增益HumidityS：[9+,5-]HighNormal[3+78考慮表3-2的訓(xùn)練數(shù)據(jù)所代表的學(xué)習(xí)任務(wù)。創(chuàng)建決策樹的根節(jié)點。計算每一個候選屬性的信息增益，然后選擇信息增益最高的一個。

Gain（S，Outlook）＝0.246

Gain（S，Humidity）＝0.151Gain（S，Wind）＝0.048Gain（S，Temperature）＝0.029

根據(jù)信息增益標(biāo)準(zhǔn)，屬性O(shè)utlook被選作根節(jié)點的決策屬性，并為它的每一個可能值（Sunny、Overcast和Rainy）在根節(jié)點下創(chuàng)建分支，得到部分決策樹顯示在圖3-4中。對非終端的后繼節(jié)點再重復(fù)前面的過程以選擇一個新的屬性來分割訓(xùn)練樣例，這一次僅使用與這個節(jié)點關(guān)聯(lián)的訓(xùn)練樣例，直到滿足結(jié)束條件。ID3算法示例21考慮表3-2的訓(xùn)練數(shù)據(jù)所代表的學(xué)習(xí)任務(wù)。創(chuàng)建決策樹的根節(jié)DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標(biāo)概念PlayTennis的訓(xùn)練樣例DayOutlookTemperatureHumidityW80ID3算法步驟1OutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.02923ID3算法步驟1OutlookSunnyRainyOveOutlook??YesSunnyOvercastRainD1,2,8,9,11D3,7,12,13D4,5,6,11,14D1~14[9+,5-][2+,3-][4+,0-][3+,2-]什么屬性？ID3算法第一步后形成的部分決策樹Outlook??YesSunnyOvercastRainD82ID3算法步驟2HumidityWindHighNormal[D1,D2,D8][0+,3-][D9,D11][2+,0-]StrongWeak[D6,D14][0+,2-][D4,D4,D10][3+,0-]NoYesNoYesYesOutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(SSunny,Humidity)=0.970Gain(SSunny,Temperature)=0.570Gain(SSunny,Wind)=0.019Gain(SRain,Humidity)=0.019Gain(SRain,Temperature)=0.019Gain(SRain,Wind)=0.97025ID3算法步驟2HumidityWindHighNorm83決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3算法搜索的假設(shè)空間就是可能的決策樹的集合。ID3以爬山算法遍歷這個假設(shè)空間，引導(dǎo)這種爬山搜索的評估函數(shù)是信息增益度量。觀察ID3的搜索空間和搜索策略，認(rèn)識到這個算法的優(yōu)勢和不足：假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個完整空間維護(hù)單一的當(dāng)前假設(shè)（不同于上章變型空間候選消除算法），不能判斷有多少個其他的決策樹也與現(xiàn)有的訓(xùn)練數(shù)據(jù)一致不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步都使用當(dāng)前所有的訓(xùn)練樣例，不同于基于單獨的訓(xùn)練樣例遞增作出決定，容錯性增強(qiáng)26決策樹學(xué)習(xí)中的假設(shè)空間搜索ID3算法搜索的假設(shè)空間就是可決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些信息增益高的屬性離根節(jié)點較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先近似在于ID3得到局部最優(yōu)，而不一定是全局最優(yōu)一個精確具有這個歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優(yōu)先，信息增益高的屬性更靠近根節(jié)點的樹優(yōu)先決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略限定偏置和優(yōu)選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個完整的假設(shè)空間，但不徹底地搜索這個空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對搜索空間的定義限定偏置和優(yōu)選偏置ID3和候選消除算法的比較限定偏置和優(yōu)選偏置優(yōu)選偏置（搜索偏置）ID3的歸納偏置是對某種假設(shè)勝過其他假設(shè)的一種優(yōu)選，對最終可列舉的假設(shè)沒有硬性限制限定偏置（語言偏置）候選消除算法的偏置是對待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要優(yōu)選偏置和限定偏置的結(jié)合考慮第1章下棋的例子（優(yōu)選偏置和限定偏置）限定偏置和優(yōu)選偏置優(yōu)選偏置（搜索偏置）為什么短的假設(shè)優(yōu)先?ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運動的簡單假設(shè)；簡單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少；簡單假設(shè)對訓(xùn)練樣例的針對性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述。為什么短的假設(shè)優(yōu)先?ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀設(shè)想你是在一條積雪的街上行走。在你前面有一個人帶著一頂黑色的高筒禮帽。街對面站著一群男孩，覺得這頂禮帽是個很好的目標(biāo)，其中一個扔雪球一下?lián)糁辛嗣弊?。讓我們舉出兩種解釋來說明這頂帽子的隨后遭遇。第一，在帽子受擊的一剎那，一隊天使疾飛而下，出其不意地把帽子從那人頭上揭走了。第二，雪球把帽子擊落了。我們將選擇？？種解釋。這就是科學(xué)上普遍適用的所謂“節(jié)儉律”的簡單說明。這條定律的意義，就在于說明，最可能的解釋就是最好的解釋，有時這條定律又被稱為奧坎姆剃刀

奧坎姆剃刀設(shè)想你是在一條積雪的街上行走。在你前面有一個人帶著為什么短的假設(shè)優(yōu)先奧坎姆剃刀的困難可以定義很多小的假設(shè)集合，根據(jù)什么相信有短描述的決策樹組成的小假設(shè)集合比其他可定義的小假設(shè)集合更適當(dāng)？假設(shè)的規(guī)模由學(xué)習(xí)器內(nèi)部使用的特定表示決定從生物進(jìn)化的觀點看內(nèi)部表示和奧坎姆剃刀原則為什么短的假設(shè)優(yōu)先奧坎姆剃刀的困難決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價的屬性提高計算效率針對這些問題，ID3被擴(kuò)展成C4.5決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實際問題避免過度擬合數(shù)據(jù)過度擬合對于一個假設(shè)，當(dāng)存在其它的假設(shè)對訓(xùn)練樣例的擬合比它差，但事實上在實例的整個分布上表現(xiàn)得卻更好時，我們說這個假設(shè)過度擬合訓(xùn)練樣例。定義：給定一個假設(shè)空間H，一個假設(shè)hH，如果存在其它的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。樹的規(guī)模accuracyontrainingdataontestdata避免過度擬合數(shù)據(jù)過度擬合樹的規(guī)模accuracyontra避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因（1）一種可能原因是訓(xùn)練樣例含有隨機(jī)錯誤或噪聲SunnyHotNormalStrongPlayTennis＝No避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因（1）SunnyH避免過度擬合數(shù)據(jù)（3）導(dǎo)致過度擬合的原因（2）當(dāng)訓(xùn)練數(shù)據(jù)沒有噪聲時，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點時，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標(biāo)函數(shù)并無關(guān)系。過度擬合使決策樹的精度降低（10～25）％避免過度擬合數(shù)據(jù)（3）導(dǎo)致過度擬合的原因（2）避免過度擬合數(shù)據(jù)（4）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功避免過度擬合數(shù)據(jù)（4）避免過度擬合的方法避免過度擬合數(shù)據(jù)（5）避免過度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修剪節(jié)點的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計測試來估計擴(kuò)展（或修剪）一個特定的節(jié)點是否有可能改善在訓(xùn)練集合外的實例上的性能。使用一個明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個編碼的長度最小時停止樹增長。避免過度擬合數(shù)據(jù)（5）避免過度擬合的關(guān)鍵避免過度擬合數(shù)據(jù)（6）方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法?？捎脭?shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機(jī)：即使學(xué)習(xí)器可能會被訓(xùn)練集合誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機(jī)波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗證集合。避免過度擬合數(shù)據(jù)（6）方法評述錯誤率降低修剪將樹上的每一個節(jié)點作為修剪的候選對象修剪步驟刪除以此節(jié)點為根的子樹，使它成為葉結(jié)點把和該節(jié)點關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節(jié)點繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止數(shù)