決策樹學習培訓講義

1、1人工智能人工智能第第6章章學習智能體學習智能體-決策樹學習決策樹學習巢文涵 G1001/G931北航計算機學院智能信息研究所2022-2-142大綱大綱l簡介l決策樹學習算法l應用實例3決策樹決策樹(Decision Tree)l決策樹學習是應用最廣的歸納推理算法之一l它是一種逼近離散離散函數的方法l學習到的函數以決策樹的形式表示l主要用于分類l對噪聲數據有很好的魯棒性l能夠學習析取表達 4分類任務基本框架分類任務基本框架5分類應用實例分類應用實例l垃圾郵件過濾l信貸分析l新聞分類l人臉識別、手寫體識別等6決策樹的結構決策樹的結構l圖結構l內部節(jié)點（非樹葉節(jié)點，包括根節(jié)點）l在一個屬性上的測

2、試l分枝l一個測試輸出l樹葉節(jié)點l類標識7決策樹示例決策樹示例TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10分類型分類型分類型分類型連續(xù)型連續(xù)型類別類別RefundMarStTaxIncYESNONONOYesNoMarried Single,

3、 Divorced 80K測試屬性測試屬性訓練數據訓練數據模型：決策樹模型：決策樹(Refund=YES)? (Refund=NO ? MarSt=Single,Divorced ? TaxInc 80K) ? (Refund=NO ? Married=NO)8另一棵決策樹另一棵決策樹MarStRefundTaxIncYESNONONOYesNoMarried Single, Divorced 80K相同的數據可產生多棵決策樹相同的數據可產生多棵決策樹TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo

4、3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10分類型分類型分類型分類型連續(xù)型連續(xù)型類別類別9決策樹分類任務框架決策樹分類任務框架決策樹決策樹10決策樹應用決策樹應用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married

5、 80K ? 10 測試數據測試數據從根節(jié)點開始11決策樹應用決策樹應用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測試數據測試數據12決策樹應用決策樹應用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10

6、測試數據測試數據13決策樹應用決策樹應用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測試數據測試數據14決策樹應用決策樹應用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測試數據測試數據15決策樹應用決

7、策樹應用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測試數據測試數據指定欺詐為： “No”16決策樹分類任務框架決策樹分類任務框架Decision Tree17大綱大綱l簡介l決策樹學習算法l應用實例18決策樹算法決策樹算法lHunts AlgorithmlCARTlID3, C4.5lSLIQ,SPRINT19基本的基本的ID3算法算法20基本算法基本算法Dont CheatRefundDont

8、 CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarriedTidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDiv

9、orced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes1021決策樹歸納決策樹歸納l貪婪策略l根據特定的性能度量選擇最好的劃分屬性l要素l哪個屬性是最佳的分類屬性？l如何確定最佳劃分點l如何確定停止條件22度量標準度量標準熵熵l熵(Entropy)l信息論中廣泛使用的一個度量標準l刻畫任意樣例集的純度（purity）l一般計算公式為：l對于二元分類：給定包含關于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為：l Entropy(S) -plog2p-p

10、log2pl其中p是在S中正例的比例，p是在S中負例的比例。在有關熵的所有計算中我們定義0log0為0。ciiippSEntropy12log)(23例子例子C1 0 C2 6 Entropy = -(0/6)log(0/6)-(6/6)log(6/6)=0Entropy = 1-(1/6)log(1/6)-(5/6)log(5/6)=0.650Entropy = 1-(3/6)log(3/6)-(3/6)log(3/6)=124度量標準度量標準熵熵25度量標準度量標準熵熵l信息論中熵的一種解釋l熵確定了要編碼集合S中任意成員（即以均勻的概率隨機抽出的一個成員）的分類所需要的最少二進制位數l

11、= 1接收者知道抽出的樣例必為正，所以不必發(fā)任何消息，熵為0l = 0.5必須用一個二進制位來說明抽出的樣例是正還是負，熵為1l = 0.8 那么對所需的消息編碼方法是賦給正例集合較短的編碼，可能性較小的反例集合較長的編碼，平均每條消息的編碼少于1個二進制位ppp26性能度量性能度量信息增益信息增益l屬性的信息增益l使用這個屬性分割樣例而導致的期望熵降低的數量 lValues(A)是屬性A所有可能值的集合l Sv 是S中屬性A的值為v的子集 ，即Sv=sS|A(s)=vl當對S的一個任意成員的目標值編碼時，Gain(S,A)的值是在知道屬性A的值后可以節(jié)省的二進制位數 )(|)(),()(AV

12、aluesvvvSEntropySSSEntropyASGain27例子例子l假設S是有關天氣的訓練樣例集 9+,5-l其中：lwind=weak的樣例是 6+,2- lwind=strong的樣例+3,-3l問題:計算屬性wind的信息增益lS的熵： E(S)= -(9/14)log(9/14) (5/14)log(9/14)=0.940048. 000. 1 )14/6(811. 0)14/8 (940. 0)()14/6()()14/8 ()()(|)(),(,StrongWeakStrongWeakvvvSEntropySEntropySEntropySEntropySSSEntrop

13、yWindSGain28選擇最好的分類屬性選擇最好的分類屬性29大綱大綱l簡介l決策樹學習算法l應用實例30應用實例應用實例l問題及數據集l根據其他屬性，判斷周六是否玩網球playTennis=Y/N?31Step1: 確定根節(jié)點確定根節(jié)點l分別計算4個屬性的信息增益lOutlook: 0.246l=Sunny 2+,3-l=Overcast 4+,0-l=Rain 3+,2-lWind: 0.048l=weak的樣例是 6+,2- l=strong的樣例+3,-3lHumidity : 0.151lTemperature : 0.029l因此：根節(jié)點為Outlook32Step 2: 分枝分枝選擇哪個屬性進行劃分？33Step 3: 循環(huán)循環(huán)選擇哪個屬性進行劃分？34小結小結l實例是由實例是由“屬性屬性-值值”對（對（pair）表示的）表示的l目標函數具有離散的輸出值目標函數具有離散的輸出值l可能需要析取的描述（可能需要析取的描述（disjunctive description）l訓練數據可以包含錯誤訓練數據可以包含錯誤l訓練數據可以包含缺少屬性值的實例訓練數據可以包含缺少屬性值的實例35作業(yè)作業(yè)l6-1畫出表示下面布爾函數的決策樹 l（a）ABl（b）ABCl（c）A XOR Bl（d）AB CD36作業(yè)作業(yè)l6-2考慮下面的訓練