AI_決策樹學(xué)習(xí)_Chap6

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

2、e, Divorced 80K測(cè)試屬性訓(xùn)練數(shù)據(jù)模型：決策樹(Refund=YES) (Refund=NO MarSt=Single,Divorced TaxInc 80K) (Refund=NO Married=NO)7另一棵決策樹MarStRefundTaxIncYESNONONOYesNoMarried Single, Divorced 80K相同的數(shù)據(jù)可產(chǎn)生多棵決策樹分類型分類型連續(xù)型類別8決策樹分類任務(wù)框架決策樹9決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)從根節(jié)點(diǎn)開始10決策樹應(yīng)用Refund

3、MarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)11決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)12決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)13決策樹應(yīng)用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)14決策樹應(yīng)用RefundMarStTaxIncYESNONONO

4、YesNoMarried Single, Divorced 80K測(cè)試數(shù)據(jù)指定欺詐為： “No15決策樹分類任務(wù)框架Decision Tree16大綱簡(jiǎn)介決策樹學(xué)習(xí)算法應(yīng)用實(shí)例17決策樹算法Hunts AlgorithmCARTID3, C4.5SLIQ,SPRINT18根本的ID3算法19根本算法Dont CheatRefundDont CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont

5、 CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarried20決策樹歸納貪婪策略根據(jù)特定的性能度量選擇最好的劃分屬性要素哪個(gè)屬性是最正確的分類屬性？如何確定最正確劃分點(diǎn)如何確定停止條件21度量標(biāo)準(zhǔn)熵熵(Entropy)信息論中廣泛使用的一個(gè)度量標(biāo)準(zhǔn)刻畫任意樣例集的純度（purity）一般計(jì)算公式為：對(duì)于二元分類：給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為： Entropy(S) -plog2p-plog2p其中p是在S中正例的比例，p是在S中負(fù)例的比例。在有關(guān)熵的所有計(jì)算中我們定義0log0為0。

6、22例子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)=123度量標(biāo)準(zhǔn)熵24度量標(biāo)準(zhǔn)熵信息論中熵的一種解釋熵確定了要編碼集合S中任意成員（即以均勻的概率隨機(jī)抽出的一個(gè)成員）的分類所需要的最少二進(jìn)制位數(shù) = 1接收者知道抽出的樣例必為正，所以不必發(fā)任何消息，熵為0 = 0.5必須用一個(gè)二進(jìn)制位來說明抽出的樣例是正還是負(fù)，熵為1 = 0.8 那么對(duì)所需的消息編碼方法是賦給正例集合較短的編碼，可能性較

7、小的反例集合較長(zhǎng)的編碼，平均每條消息的編碼少于1個(gè)二進(jìn)制位25性能度量信息增益屬性的信息增益使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低的數(shù)量 Values(A)是屬性A所有可能值的集合 Sv 是S中屬性A的值為v的子集 ，即Sv=sS|A(s)=v當(dāng)對(duì)S的一個(gè)任意成員的目標(biāo)值編碼時(shí)，Gain(S,A)的值是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù) 26例子假設(shè)S是有關(guān)天氣的訓(xùn)練樣例集 9+,5-其中：wind=weak的樣例是 6+,2- wind=strong的樣例+3,-3問題:計(jì)算屬性wind的信息增益S的熵： E(S)= -(9/14)log(9/14) (5/14)log(9/14)=0.

8、94027選擇最好的分類屬性28大綱簡(jiǎn)介決策樹學(xué)習(xí)算法應(yīng)用實(shí)例29應(yīng)用實(shí)例問題及數(shù)據(jù)集根據(jù)其他屬性，判斷周六是否玩網(wǎng)球playTennis=Y/N?30Step1: 確定根節(jié)點(diǎn)分別計(jì)算4個(gè)屬性的信息增益Outlook: 0.246=Sunny 2+,3-=Overcast 4+,0-=Rain 3+,2-Wind: 0.048=weak的樣例是 6+,2- =strong的樣例+3,-3Humidity : 0.151Temperature : 0.029因此：根節(jié)點(diǎn)為Outlook31Step 2: 分枝選擇哪個(gè)屬性進(jìn)行劃分？32Step 3: 循環(huán)選擇哪個(gè)屬性進(jìn)行劃分？33小結(jié)實(shí)例是由“屬性-值對(duì)（pair）表示的目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述（disjunctive description）訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例34作業(yè)6-1畫出表示下面布爾函數(shù)的決策樹 （a）AB（b）ABC（c）A XOR B（d）AB CD35作業(yè)6-2考慮下面的訓(xùn)練樣例集合 手動(dòng)給出決策樹的構(gòu)造過程36作業(yè)6-3 ID3僅尋找一個(gè)一致的假設(shè)，而候選消除算法尋找所有一致的假設(shè)。考慮這兩種學(xué)習(xí)算法間的對(duì)應(yīng)關(guān)系 （a