建立模型之決策樹講義

2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)1/344.建立模型之決策樹分類預(yù)測的概念什么是決策樹決策樹的核心問題決策樹的生長，模型建立決策樹的修剪C5.0算法及其應(yīng)用實例信息熵和信息增益修剪算法當(dāng)前第1頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)2/344.1分類預(yù)測概念目的（通用）學(xué)習(xí)模型建立的算法了解該算法在相應(yīng)數(shù)據(jù)挖掘問題中的應(yīng)用分類預(yù)測的含義分類預(yù)測算法的類型當(dāng)前第2頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)3/344.1分類預(yù)測概念目的（通用）分類預(yù)測的含義通過對現(xiàn)有數(shù)據(jù)的學(xué)習(xí)建立起擬合數(shù)據(jù)的模型利用該模型對未來新數(shù)據(jù)進行分類，具備預(yù)測能力分類預(yù)測算法的類型當(dāng)前第3頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)4/344.1分類預(yù)測概念目的（通用）分類預(yù)測的含義分類預(yù)測算法的類型分析新數(shù)據(jù)在離散型輸出變量上的取值分類決策樹分析新數(shù)據(jù)在數(shù)值型（連續(xù)）輸出變量上的取值

回歸決策樹當(dāng)前第4頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)5/34聚類、分類和模式識別聚類子集劃分，把一個集合分割為無交集的子集；模式分類標識出樣本歸屬的子集（標簽）模式識別標識出樣本對應(yīng)的個體（樣例）本身，或標識出樣本所屬子集本身（如考古、物種鑒別等）【注】樣本，只需是個體或集合的特征表示當(dāng)前第5頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)6/34從二分類問題開始很多問題可以歸結(jié)為上課、習(xí)題，以及考試都不是目的，只是為一個結(jié)果：及格？通過？優(yōu)秀看電影：這是好人還是壞人求職：多項測試之后，決定

喜歡還是不喜歡？滿意還是不滿意？研究方向：Majorinorout在上述選擇過程中，涉及到多個因素，如何比較不同因素重要性的差別？當(dāng)前第6頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)7/34在“虛度的日子”的判別中

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

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

離散值（布爾）函數(shù)；Node,testattributesBranches,valuesRootNode,firstattributeLeafNodes,discretevalues決策樹的表示？當(dāng)前第9頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)10/34兩類問題,右圖IF(Outlook=Sunny)^(Humidity=High)THEN

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

(Outlook=Sunny∧Humidity=High)

∨(Outlook=Sunny∧Humidity=Normal)

∨(Outlook=Overcast)

∨(Outlook=Rain∧Wind=Weak)

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

可能的決策樹空間ID3IterativeDichotomiser3是這種算法的代表,ID3C4.5C5.0如何安排節(jié)點在樹中的順序樹（堆）結(jié)構(gòu)排序，需要樹中節(jié)點具有相同屬性，比較其屬性值大?。欢笠苿庸?jié)點如何定義這個可以在決策樹中進行比較的屬性？

換言之，該屬性測度如何計算以便于比較？當(dāng)前第18頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)19/344.1ID3算法算法思想：如何安排節(jié)點在樹中的順序自頂向下構(gòu)造決策樹從“哪一個屬性將在樹的根節(jié)點被測試”開始？使用統(tǒng)計測試來確定每一個實例屬性單獨分類

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

當(dāng)前第20頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)21/344.1.1最佳分類屬性信息增益用熵度量樣例的均一性熵刻畫了任意樣例集合S的純度給定包含關(guān)于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類（函數(shù)）的熵為

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

當(dāng)前第21頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)22/344.1.1最佳分類屬性（2）用信息增益度量熵的降低程度屬性A的信息增益，使用屬性A分割樣例集合S而導(dǎo)致的熵的降低程度

Gain(S,A)是

在知道屬性A的值后可以節(jié)省的二進制位數(shù)例子，注意是對當(dāng)前樣例集合計算上式當(dāng)前第22頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)23/34PlayTennis的14個訓(xùn)練樣例DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo當(dāng)前第23頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)24/34當(dāng)前樣例集合中的最佳分類屬性Gain(S,Outlook)=0.246Gain(S,Temperature)=0.029當(dāng)前第24頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)25/34然后呢？類別值較多的輸入變量更容易成為當(dāng)前最佳GainsR(U,V)=Gains(U,V)/Entropy(V)是不是再比較剩余的幾個信息增益值？應(yīng)該怎么辦？注意決策樹每個分支上屬性間的關(guān)系當(dāng)前第25頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)26/34根節(jié)點的左右孩子順序全正例、全負例當(dāng)前第26頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)27/34用于學(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（當(dāng)前子樹，根節(jié)點的每一個孩子節(jié)點）在root下加一個新的分支對應(yīng)測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節(jié)點，節(jié)點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root當(dāng)前第27頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)28/34ID3算法舉例…繼續(xù)這個過程，

直到滿足以下兩個條件中的任一個所有的屬性已經(jīng)被這條路經(jīng)包括與這個節(jié)點關(guān)聯(lián)的所有訓(xùn)練樣例都具有相同的目標屬性值當(dāng)前第28頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)29/34EntropyandInformationGain這個信息增益到底怎么來的？在信息論中信息增益是什么含義？二者存在確定的關(guān)系嗎？譬如：等價；提示：

不是從Y到X的信息增益

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

Patternrecognitionandmachinelearning

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

精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功當(dāng)前第37頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)38/34避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵使用什么樣的準則來計算最終決策樹的尺寸解決方法使用與訓(xùn)練樣例不同的一套分離的樣例來評估

通過后修剪方法從樹上修剪節(jié)點的效用。使用所有可用數(shù)據(jù)進行訓(xùn)練，但進行統(tǒng)計測試來估計擴展（或修剪）一個特定的節(jié)點是否有可能改善在訓(xùn)練集合外的實例上的性能。使用一個顯式的標準來測度訓(xùn)練樣例和決策樹的編碼復(fù)雜度，當(dāng)這個測度最小時停止樹增長。當(dāng)前第38頁\共有46頁\編于星期四\23點2023/6/16數(shù)據(jù)庫新技術(shù)(數(shù)據(jù)挖掘)39/34避免過度擬合數(shù)據(jù)（5）方法評述第一種方法是最普通的，常被稱為訓(xùn)練和驗證集法可用的數(shù)據(jù)分成兩個樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗證集合，評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度方法的動機：即使學(xué)習(xí)器可能會被訓(xùn)練集合誤導(dǎo)，但驗證集合不大可能表現(xiàn)出同樣的隨機波動驗證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計意義的實例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，

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