分類預(yù)測(cè)決策樹(shù)方法

分類預(yù)測(cè)決策樹(shù)方法第1頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)2/344.1分類預(yù)測(cè)概念目的（通用）學(xué)習(xí)模型建立的算法了解該算法在相應(yīng)數(shù)據(jù)挖掘問(wèn)題中的應(yīng)用分類預(yù)測(cè)的含義分類預(yù)測(cè)算法的類型第2頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)3/344.1分類預(yù)測(cè)概念目的（通用）分類預(yù)測(cè)的含義通過(guò)對(duì)現(xiàn)有數(shù)據(jù)的學(xué)習(xí)建立起擬合數(shù)據(jù)的模型利用該模型對(duì)未來(lái)新數(shù)據(jù)進(jìn)行分類，具備預(yù)測(cè)能力分類預(yù)測(cè)算法的類型第3頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)4/344.1分類預(yù)測(cè)概念目的（通用）分類預(yù)測(cè)的含義分類預(yù)測(cè)算法的類型分析新數(shù)據(jù)在離散型輸出變量上的取值分類決策樹(shù)分析新數(shù)據(jù)在數(shù)值型（連續(xù)）輸出變量上的取值

回歸決策樹(shù)第4頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)5/34聚類、分類和模式識(shí)別聚類子集劃分，把一個(gè)集合分割為無(wú)交集的子集；模式分類標(biāo)識(shí)出樣本歸屬的子集（標(biāo)簽）模式識(shí)別標(biāo)識(shí)出樣本對(duì)應(yīng)的個(gè)體（樣例）本身，或標(biāo)識(shí)出樣本所屬子集本身（如考古、物種鑒別等）【注】樣本，只需是個(gè)體或集合的特征表示第5頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)6/34從二分類問(wèn)題開(kāi)始很多問(wèn)題可以歸結(jié)為上課、習(xí)題，以及考試都不是目的，只是為一個(gè)結(jié)果：及格？通過(guò)？?jī)?yōu)秀看電影：這是好人還是壞人求職：多項(xiàng)測(cè)試之后，決定

喜歡還是不喜歡？滿意還是不滿意？研究方向：Majorinorout在上述選擇過(guò)程中，涉及到多個(gè)因素，如何比較不同因素重要性的差別？第6頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)7/34在“虛度的日子”的判別中

最關(guān)鍵的是哪一個(gè)因素？睡眠時(shí)間：6/7/8/9/10成功事例數(shù)目：1/2/3開(kāi)心指數(shù)：快樂(lè)、憂傷、憤怒、平淡、無(wú)聊人際交往：有成效、封閉健康指數(shù)：生病、恢復(fù)、亞健康、正常學(xué)思比數(shù)：10：1，3：1，2：1，1：2第7頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)8/34基于樹(shù)型結(jié)構(gòu)的排序算法樹(shù)中節(jié)點(diǎn)的位置的確定和調(diào)整是通過(guò)對(duì)每一個(gè)節(jié)點(diǎn)中某個(gè)特定域的屬性值排序決定，通常，樹(shù)中節(jié)點(diǎn)都具有該屬性二叉排序樹(shù)堆排序如果樹(shù)中節(jié)點(diǎn)沒(méi)有現(xiàn)成的公共屬性，無(wú)法據(jù)以比較節(jié)點(diǎn)以安排其在生成樹(shù)中位置，怎么辦？第8頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)9/342.什么是決策樹(shù)決策樹(shù)來(lái)自決策論,由多個(gè)決策分支和可能的結(jié)果（包括資源成本和風(fēng)險(xiǎn)）組成，用來(lái)創(chuàng)建到達(dá)目標(biāo)的規(guī)劃；ADecisiontreeisatreewithbranchingnodeswithachoicebetweentwoormorechoices.也可以用來(lái)表示算法。分類預(yù)測(cè)：決策樹(shù)表示

決策樹(shù)學(xué)習(xí)結(jié)果：表示為決策樹(shù)形式的

離散值（布爾）函數(shù)；Node,testattributesBranches,valuesRootNode,firstattributeLeafNodes,discretevalues決策樹(shù)的表示？第9頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)10/34兩類問(wèn)題,右圖IF(Outlook=Sunny)^(Humidity=High)THEN

PlayTennis=?IF(Outlook=Sunny)^(Humidity=Normal)THENPlayTennis=?兩步驟求解過(guò)程：Trainingexamples:DayOutlookTemp.HumidityWindPlayTennisD1SunnyHotHighWeakNoD2OvercastHotHighStrongYes1.歸納推理求得一般性結(jié)論（決策樹(shù)生成學(xué)習(xí)）2.由決策樹(shù)演繹推理得到新樣例對(duì)應(yīng)的結(jié)果；OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo2.1決策樹(shù)學(xué)習(xí)和分類預(yù)測(cè)第10頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)11/34決策樹(shù)生成算法——有指導(dǎo)學(xué)習(xí)樣本數(shù)據(jù)中既包含輸入字段、也包含輸出字段學(xué)習(xí)階段，生成決策樹(shù)模型基于特定屬性值比較，放置樣本在生成樹(shù)上修剪生成樹(shù)的特定算法分類預(yù)測(cè)階段，判斷分類結(jié)果基于邏輯，即通過(guò)對(duì)輸入字段取值的布爾邏輯比較實(shí)現(xiàn)對(duì)輸出變量的(分類)值的預(yù)測(cè)第11頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)12/34決策樹(shù)分類算法——基于邏輯樣本數(shù)據(jù)中既包含輸入字段、也包含輸出字段學(xué)習(xí)階段，生成決策樹(shù)模型分類預(yù)測(cè)階段，判斷分類結(jié)果基于邏輯，即通過(guò)對(duì)輸入字段取值的布爾邏輯比較實(shí)現(xiàn)對(duì)輸出變量的(分類)值的預(yù)測(cè)每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一條推理規(guī)則，作為對(duì)新的數(shù)據(jù)對(duì)象進(jìn)行分類預(yù)測(cè)的依據(jù)。第12頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)13/343.決策樹(shù)的核心問(wèn)題決策樹(shù)的生成對(duì)訓(xùn)練樣本進(jìn)行分組關(guān)鍵，確定樹(shù)根節(jié)點(diǎn)和分支準(zhǔn)則停止生長(zhǎng)時(shí)機(jī)決策樹(shù)的修剪解決過(guò)度擬合問(wèn)題預(yù)先修剪，限值決策樹(shù)的充分生長(zhǎng)，如：限制樹(shù)的高度滯后修剪，待決策樹(shù)充分生長(zhǎng)完畢后再進(jìn)行修剪當(dāng)節(jié)點(diǎn)和分支數(shù)較多時(shí)，顯然不合適第13頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)14/343.1決策樹(shù)表示法決策樹(shù)通過(guò)把樣本從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類樣本葉子節(jié)點(diǎn)即為樣本所屬的分類樹(shù)上每個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)樣本的某個(gè)屬性的測(cè)試,如：濕度節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值，High決策樹(shù)代表樣本的屬性值約束的合取的析取式OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo第14頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)15/34OutlookSunnyOvercastRainHumidityYesWindHighNormalYesNoStrongWeakYesNo決策樹(shù)例圖的邏輯表達(dá)式?jīng)Q策樹(shù)代表實(shí)例屬性值約束的合取的析取式。從樹(shù)根到樹(shù)葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取樹(shù)本身對(duì)應(yīng)這些合取的析取。

(Outlook=Sunny∧Humidity=High)

∨(Outlook=Sunny∧Humidity=Normal)

∨(Outlook=Overcast)

∨(Outlook=Rain∧Wind=Weak)

∨(Outlook=Rain∧Wind=Strong)注意：右面的決策樹(shù)中沒(méi)有Temperature（溫度）屬性；而Outlook的屬性值有三個(gè)。第15頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)16/343.2決策樹(shù)學(xué)習(xí)的適用問(wèn)題適用問(wèn)題的特征實(shí)例由“屬性-值”對(duì)表示（傳統(tǒng)的數(shù)據(jù)庫(kù)記錄屬性）目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤/訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例問(wèn)題舉例分類問(wèn)題核心任務(wù)是把新(舊)樣例分派到各可能的離散值對(duì)應(yīng)的類別第16頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)17/343.2決策樹(shù)方法的適用問(wèn)題適用問(wèn)題的特征問(wèn)題舉例根據(jù)疾病分類患者/根據(jù)起因分類設(shè)備故障根據(jù)拖欠支付的可能性分類貸款申請(qǐng)(是否拒絕)根據(jù)人員分類情形更新數(shù)據(jù)庫(kù)記錄數(shù)據(jù)創(chuàng)新點(diǎn)？大型稀疏庫(kù)分類問(wèn)題核心任務(wù)是把新(舊)樣例分派到各可能的離散值對(duì)應(yīng)的類別第17頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)18/344.C5.0算法大多數(shù)決策樹(shù)學(xué)習(xí)算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷

可能的決策樹(shù)空間ID3IterativeDichotomiser3是這種算法的代表,ID3C4.5C5.0如何安排節(jié)點(diǎn)在樹(shù)中的順序樹(shù)（堆）結(jié)構(gòu)排序，需要樹(shù)中節(jié)點(diǎn)具有相同屬性，比較其屬性值大小；而后移動(dòng)節(jié)點(diǎn)如何定義這個(gè)可以在決策樹(shù)中進(jìn)行比較的屬性？

換言之，該屬性測(cè)度如何計(jì)算以便于比較？第18頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)19/344.1ID3算法算法思想：如何安排節(jié)點(diǎn)在樹(shù)中的順序自頂向下構(gòu)造決策樹(shù)從“哪一個(gè)屬性將在樹(shù)的根節(jié)點(diǎn)被測(cè)試”開(kāi)始？使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類

訓(xùn)練樣例的能力ID3的算法執(zhí)行過(guò)程對(duì)樣例集合S分類能力最好的屬性被選作樹(shù)的根節(jié)點(diǎn)根節(jié)點(diǎn)的每個(gè)可能值產(chǎn)生一個(gè)分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е貜?fù)上面的過(guò)程，直到訓(xùn)練樣例被安排到適當(dāng)?shù)娜~子上確定對(duì)應(yīng)的分類第19頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)20/344.1.1最佳分類屬性信息增益用來(lái)衡量給定的屬性區(qū)分訓(xùn)練樣例的能力，中間（間接）表示屬性ID3算法在生成樹(shù)的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性

第20頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)21/344.1.1最佳分類屬性信息增益用熵度量樣例的均一性熵刻畫了任意樣例集合S的純度給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類（函數(shù)）的熵為

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

第21頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)22/344.1.1最佳分類屬性（2）用信息增益度量熵的降低程度屬性A的信息增益，使用屬性A分割樣例集合S而導(dǎo)致的熵的降低程度

Gain(S,A)是

在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)例子，注意是對(duì)當(dāng)前樣例集合計(jì)算上式第22頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)23/34PlayTennis的14個(gè)訓(xùn)練樣例DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo第23頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)24/34當(dāng)前樣例集合中的最佳分類屬性Gain(S,Outlook)=0.246Gain(S,Temperature)=0.029第24頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)25/34然后呢？類別值較多的輸入變量更容易成為當(dāng)前最佳GainsR(U,V)=Gains(U,V)/Entropy(V)是不是再比較剩余的幾個(gè)信息增益值？應(yīng)該怎么辦？注意決策樹(shù)每個(gè)分支上屬性間的關(guān)系第25頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)26/34根節(jié)點(diǎn)的左右孩子順序全正例、全負(fù)例第26頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)27/34用于學(xué)習(xí)布爾函數(shù)的ID3算法概要ID3(Examples,Target_attribute,Attributes)創(chuàng)建樹(shù)的root節(jié)點(diǎn)，整棵樹(shù)的指針如果Examples都為正,返回label=+的單節(jié)點(diǎn)樹(shù)root;%原因在例子中說(shuō)明如果Examples都為反,返回label=-的單節(jié)點(diǎn)樹(shù)root如果Attributes為空，那么返回單節(jié)點(diǎn)root，label=Examples中最普遍的Target_attribute值否則開(kāi)始AAttributes中分類examples能力最好的屬性root的決策屬性A對(duì)于A的每個(gè)可能值vi（當(dāng)前子樹(shù)，根節(jié)點(diǎn)的每一個(gè)孩子節(jié)點(diǎn)）在root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個(gè)新分支下加一個(gè)葉子節(jié)點(diǎn)，節(jié)點(diǎn)的label=Examples中最普遍的Target_attribute值否則在新分支下加一個(gè)子樹(shù)ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root第27頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)28/34ID3算法舉例…繼續(xù)這個(gè)過(guò)程，

直到滿足以下兩個(gè)條件中的任一個(gè)所有的屬性已經(jīng)被這條路經(jīng)包括與這個(gè)節(jié)點(diǎn)關(guān)聯(lián)的所有訓(xùn)練樣例都具有相同的目標(biāo)屬性值第28頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)29/34EntropyandInformationGain這個(gè)信息增益到底怎么來(lái)的？在信息論中信息增益是什么含義？二者存在確定的關(guān)系嗎？譬如：等價(jià)；提示：

不是從Y到X的信息增益

而是從p(x)p(y)到p(x,y)的信息增益

Patternrecognitionandmachinelearning

pp:48~58第29頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)30/34決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索觀察ID3的搜索空間和搜索策略，認(rèn)識(shí)到這個(gè)算法的優(yōu)勢(shì)和不足在假設(shè)空間中搜索一個(gè)擬合訓(xùn)練樣例的最優(yōu)假設(shè)假設(shè)空間包含所有的決策樹(shù)，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間，避免（有偏的）不完備假設(shè)空間不含目標(biāo)假設(shè)的問(wèn)題維護(hù)單一的當(dāng)前假設(shè)，不顧其它假設(shè)，前向策略不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步使用所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)第30頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)31/34決策樹(shù)學(xué)習(xí)的深入話題決策樹(shù)學(xué)習(xí)的實(shí)際問(wèn)題確定決策樹(shù)增長(zhǎng)的深（高）度處理連續(xù)值的屬性選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價(jià)的屬性提高計(jì)算效率/download.html為解決這些問(wèn)題，ID3被擴(kuò)展成C4.5第31頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)32/344.2C4.5的修剪算法滯后修剪將生成樹(shù)轉(zhuǎn)換成規(guī)則再修剪，自己閱讀從葉子節(jié)點(diǎn)向上逐層修剪誤差估計(jì)，在訓(xùn)練樣本集上估計(jì)誤差通常，估計(jì)生成的決策樹(shù)在測(cè)試集上的預(yù)測(cè)誤差修剪標(biāo)準(zhǔn)修剪示例第32頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)33/344.2.1避免過(guò)度擬合數(shù)據(jù)過(guò)度擬合對(duì)于一個(gè)假設(shè)h，如果存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但在實(shí)例的整個(gè)分布上卻表現(xiàn)得更好時(shí)，我們說(shuō)這個(gè)假設(shè)h過(guò)度擬合訓(xùn)練樣例定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)hH，如果存在其他的假設(shè)h’H，使得在訓(xùn)練樣例上h的錯(cuò)誤率比h’小，但在整個(gè)實(shí)例分布上h’的錯(cuò)誤率比h小，那么就說(shuō)假設(shè)h過(guò)度擬合訓(xùn)練數(shù)據(jù)。圖3-6的例子，說(shuō)明樹(shù)的尺寸(節(jié)點(diǎn)數(shù))對(duì)測(cè)試精度和訓(xùn)練精度的影響——避免過(guò)度擬合必須控制樹(shù)尺寸!第33頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)34/34Overfitting第34頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)35/34避免過(guò)度擬合必須控制樹(shù)尺寸Highaccuracy,smallerrorLowaccuracy,bigerror第35頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)36/34避免過(guò)度擬合數(shù)據(jù)（2）導(dǎo)致過(guò)度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機(jī)噪聲當(dāng)訓(xùn)練數(shù)據(jù)沒(méi)有噪聲時(shí)，過(guò)度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實(shí)際的目標(biāo)函數(shù)并無(wú)關(guān)系。第36頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)37/34避免過(guò)度擬合數(shù)據(jù)（3）避免過(guò)度擬合的方法及早停止樹(shù)增長(zhǎng)后修剪法兩種方法的特點(diǎn)第一種方法更直觀，但是

精確地估計(jì)何時(shí)停止樹(shù)增長(zhǎng)很困難第二種方法被證明在實(shí)踐中更成功第37頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)38/34避免過(guò)度擬合數(shù)據(jù)（4）避免過(guò)度擬合的關(guān)鍵使用什么樣的準(zhǔn)則來(lái)計(jì)算最終決策樹(shù)的尺寸解決方法使用與訓(xùn)練樣例不同的一套分離的樣例來(lái)評(píng)估

通過(guò)后修剪方法從樹(shù)上修剪節(jié)點(diǎn)的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)測(cè)試來(lái)估計(jì)擴(kuò)展（或修剪）一個(gè)特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。使用一個(gè)顯式的標(biāo)準(zhǔn)來(lái)測(cè)度訓(xùn)練樣例和決策樹(shù)的編碼復(fù)雜度，當(dāng)這個(gè)測(cè)度最小時(shí)停止樹(shù)增長(zhǎng)。第38頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)39/34避免過(guò)度擬合數(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í)例樣本。常見(jiàn)的做法是，樣例的三分之二作訓(xùn)練集合，

三分之一作驗(yàn)證集合。第39頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)40/344.2.1C5.0決策樹(shù)的誤差估計(jì)針對(duì)決策樹(shù)的每個(gè)節(jié)點(diǎn)，以輸出變量的眾數(shù)類別為預(yù)測(cè)類別；設(shè)第i個(gè)節(jié)點(diǎn)包含Ni個(gè)觀測(cè)樣本值，有Ei個(gè)預(yù)測(cè)錯(cuò)誤的觀測(cè)，錯(cuò)誤率，即誤差在誤差近似正態(tài)分布的假設(shè)下，對(duì)第i個(gè)節(jié)點(diǎn)的真實(shí)誤差進(jìn)行區(qū)間估計(jì)，置信度定位1-，有悲觀估計(jì)：第40頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)41/344.2.2C5.0決策樹(shù)的修剪標(biāo)準(zhǔn)在誤差估計(jì)的基礎(chǔ)上，依據(jù)“減少誤差”法判斷是否修剪節(jié)點(diǎn)；計(jì)算待剪子樹(shù)中葉子節(jié)點(diǎn)的加權(quán)誤差與父節(jié)點(diǎn)的誤差進(jìn)行比較父節(jié)點(diǎn)的誤差較小，則剪掉該子樹(shù)父節(jié)點(diǎn)的誤差較大，保留該子樹(shù)第41頁(yè)，課件共46頁(yè)，創(chuàng)作于2023年2月2023/7/30數(shù)據(jù)庫(kù)新技術(shù)(數(shù)據(jù)挖掘)42/34修剪節(jié)點(diǎn)、降低錯(cuò)誤率將