決策樹學(xué)習(xí)培訓(xùn)講義

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

2、試l分枝l一個(gè)測(cè)試輸出l樹葉節(jié)點(diǎn)l類標(biāo)識(shí)7決策樹示例決策樹示例TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10分類型分類型分類型分類型連續(xù)型連續(xù)型類別類別RefundMarStTaxIncYESNONONOYesNoMarried Single,

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

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

5、 80K ? 10 測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)從根節(jié)點(diǎn)開始11決策樹應(yīng)用決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)12決策樹應(yīng)用決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10

6、測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)13決策樹應(yīng)用決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)14決策樹應(yīng)用決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)15決策樹應(yīng)用決

7、策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80KRefund Marital Status Taxable Income Cheat No Married 80K ? 10 測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)指定欺詐為： “No”16決策樹分類任務(wù)框架決策樹分類任務(wù)框架Decision Tree17大綱大綱l簡(jiǎn)介l決策樹學(xué)習(xí)算法l應(yīng)用實(shí)例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根據(jù)特定的性能度量選擇最好的劃分屬性l要素l哪個(gè)屬性是最佳的分類屬性？l如何確定最佳劃分點(diǎn)l如何確定停止條件22度量標(biāo)準(zhǔn)度量標(biāo)準(zhǔn)熵熵l熵(Entropy)l信息論中廣泛使用的一個(gè)度量標(biāo)準(zhǔn)l刻畫任意樣例集的純度（purity）l一般計(jì)算公式為：l對(duì)于二元分類：給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為：l Entropy(S) -plog2p-p

10、log2pl其中p是在S中正例的比例，p是在S中負(fù)例的比例。在有關(guān)熵的所有計(jì)算中我們定義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度量標(biāo)準(zhǔn)度量標(biāo)準(zhǔn)熵熵25度量標(biāo)準(zhǔn)度量標(biāo)準(zhǔn)熵熵l信息論中熵的一種解釋l熵確定了要編碼集合S中任意成員（即以均勻的概率隨機(jī)抽出的一個(gè)成員）的分類所需要的最少二進(jìn)制位數(shù)l

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

12、aluesvvvSEntropySSSEntropyASGain27例子例子l假設(shè)S是有關(guān)天氣的訓(xùn)練樣例集 9+,5-l其中：lwind=weak的樣例是 6+,2- lwind=strong的樣例+3,-3l問題:計(jì)算屬性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簡(jiǎn)介l決策樹學(xué)習(xí)算法l應(yīng)用實(shí)例30應(yīng)用實(shí)例應(yīng)用實(shí)例l問題及數(shù)據(jù)集l根據(jù)其他屬性，判斷周六是否玩網(wǎng)球playTennis=Y/N?31Step1: 確定根節(jié)點(diǎn)確定根節(jié)點(diǎn)l分別計(jì)算4個(gè)屬性的信息增益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é)點(diǎn)為Outlook32Step 2: 分枝分枝選擇哪個(gè)屬性進(jìn)行劃分？33Step 3: 循環(huán)循環(huán)選擇哪個(gè)屬性進(jìn)行劃分？34小結(jié)小結(jié)l實(shí)例是由實(shí)例是由“屬性屬性-值值”對(duì)（對(duì)（pair）表示的）表示的l目標(biāo)函數(shù)具有離散的輸出值目標(biāo)函數(shù)具有離散的輸出值l可能需要析取的描述（可能需要析取的描述（disjunctive description）l訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤l訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例35作業(yè)作業(yè)l6-1畫出表示下面布爾函數(shù)的決策樹 l（a）ABl（b）ABCl（c）A XOR Bl（d）AB CD36作業(yè)作業(yè)l6-2考慮下面的訓(xùn)練