分類與決策樹[1]課件

1、分類與決策樹2022/7/24分類與決策樹1銀行個(gè)人住房貸款審批銀行個(gè)人客戶提出住房貸款申請(qǐng)，根據(jù)歷史數(shù)據(jù)發(fā)現(xiàn)：部分貸款客戶不能按時(shí)還款。為盡量降低這種現(xiàn)象，需要發(fā)現(xiàn)不能按時(shí)還款客戶的特征，以便對(duì)以后住房貸款申請(qǐng)的審批提供依據(jù)。 2006年年底，由SAS機(jī)構(gòu)與招商銀行啟動(dòng)了全行個(gè)人住房貸款評(píng)分卡開發(fā)與推廣項(xiàng)目。 該項(xiàng)目利用客戶的歷史數(shù)據(jù)構(gòu)建評(píng)分卡模型，然后將該模型應(yīng)用到新客戶上，最后決定是否接受新客戶的貸款申請(qǐng)。分析數(shù)據(jù)集應(yīng)該包括哪些客戶？分類與決策樹1銀行貸款申請(qǐng) IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3

2、YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo分類與決策樹1分類與預(yù)測(cè)分類：目標(biāo)變量為非數(shù)值型預(yù)測(cè)：目標(biāo)變量為數(shù)值型根據(jù)歷史數(shù)據(jù)集（已知目標(biāo)變量），構(gòu)

3、建模型描述目標(biāo)變量與輸入變量之間的關(guān)系，并依據(jù)模型來(lái)分類或預(yù)測(cè)新數(shù)據(jù)（目標(biāo)變量值未知)。 分類模型也稱為分類器。模型應(yīng)用建模規(guī)則1：If refund=no and marst=married then cheat=no模型評(píng)估分類與決策樹1分類的過(guò)程數(shù)據(jù)集分區(qū)訓(xùn)練集：建立模型驗(yàn)證集：調(diào)整和選擇模型測(cè)試集：評(píng)估模型的預(yù)測(cè)能力建立模型評(píng)估并選擇模型運(yùn)用模型 新數(shù)據(jù)（打分集）思考：分類模型在什么情況下不適合用于新數(shù)據(jù)？分類與決策樹1分類方法決策樹方法貝葉斯分類法LOGISTIC回歸神經(jīng)網(wǎng)絡(luò)方法K近鄰分類法SVM分類法.分類與決策樹1RootLeafNode7決策樹(decision tree)規(guī)則

4、1：If refund=no and (marst=single or marst=divorced) and taxincome80k then cheat=yes分類與決策樹1決策樹是一棵二叉或多叉樹結(jié)構(gòu)每個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)屬性，該節(jié)點(diǎn)的分支表示根據(jù)該屬性的不同測(cè)試條件的輸出葉子節(jié)點(diǎn)表示一個(gè)類標(biāo)決策樹一般是自上而下生成的分類與決策樹1決策樹基本思想建立決策樹將決策樹轉(zhuǎn)換為決策規(guī)則并應(yīng)用相關(guān)問(wèn)題討論內(nèi)容分類與決策樹1一、決策樹思想將數(shù)據(jù)集根據(jù)某種測(cè)試條件分為2個(gè)或多個(gè)子集，使分裂后的子集在目標(biāo)變量上具有更純的分類純度與混雜度分類與決策樹1混雜度的常用測(cè)度指標(biāo)信息熵 （ Entropy）基尼指

5、數(shù)（ Gini Index）分類誤差（classification error)分類與決策樹1Pj 是數(shù)據(jù)集合中類別j的相對(duì)比例.entropy = 12信息熵 （ Entropy） 什么情況下，熵最小？什么情況下，熵最大？entropy = - 1 log21 - 0 log20 = 0目標(biāo)變量為二元變量：entropy = -0.5 log20.5 0.5 log20.5 =1分類與決策樹1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5

6、YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo銀行貸款數(shù)據(jù)集銀行貸款案例數(shù)據(jù)集的熵： Entropy(T)=6/15*log2(6/15) 9/15*log2(9/15)=0.971分類與決策樹1Gini 指數(shù)Pj 是數(shù)據(jù)集

7、合中類別j的相對(duì)比例.GINI最大=？GINI最小=？1-1/2 （目標(biāo)變量為二元變量） 0分類與決策樹1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldN

8、oYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo銀行貸款數(shù)據(jù)集銀行貸款案例數(shù)據(jù)集的基尼指數(shù)：gini=1-(6/15)2-(9/15)2=0.48分類與決策樹1分類誤差（classification error)CE最大=？CE最小=？1-1/2 （目標(biāo)變量為二元變量） 0分類與決策樹1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairN

9、o6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo銀行貸款數(shù)據(jù)集銀行貸款案例數(shù)據(jù)集的分類誤差：CE=1- 9/15=6/15=0.4分類與決策樹1二、建立決策樹常用算法ID3-ID5,C4,C4.5,C5.0CART（Classification and

10、Regression Trees分類與回歸樹) （C&RT）CHAID(chi-squared automatic interaction detection，卡方自動(dòng)交互檢測(cè))二叉 GINI 指數(shù)二叉或多叉 信息熵二叉或多叉分類與決策樹1建立決策樹樹的生長(zhǎng)分裂屬性及其條件的選擇 何時(shí)結(jié)束分裂樹的選擇分類與決策樹11. 裂分目標(biāo)與屬性選擇裂分目標(biāo) 使分裂后數(shù)據(jù)子集的純度比裂分前數(shù)據(jù)集的純度最大限度的提高；即不同類別的觀測(cè)盡量分散在不同的子集中。指標(biāo)信息增益與信息增益率GINI指數(shù)的下降二分指數(shù)卡方檢驗(yàn)C-SEP、分類與決策樹1信息增益Information Gain = 裂分前數(shù)據(jù)集的熵 裂分

11、后各子數(shù)據(jù)集的熵加權(quán)和其中：權(quán)重為每個(gè)子集中的觀測(cè)數(shù)在裂分前總觀測(cè)數(shù)中所占的比例分類與決策樹1案例數(shù)據(jù)集基于own_home屬性劃分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcel

12、lentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo分類與決策樹1案例數(shù)據(jù)集基于ownhome屬性劃分劃分后數(shù)據(jù)集的熵EntropyOwn_home(T)= 6/15* Entropy(T1)+ 9/15* Entropy(T2)= 6/15*( 6/6*log2(6/6) 0/0*log2(0/6) )+ 9/15*( 3/9*log2(3/9) 6/9*log2(6/9) =0.551 信息增益Gain(ownhome)=0.971-0.551=0.42Own_homeYesNoYes:

13、6No:0No:6Yes:3 裂分前數(shù)據(jù)集的熵：Entropy(T0)=6/15*log2(6/15) 9/15*log2(9/15)=0.971分類與決策樹1案例數(shù)據(jù)集基于age屬性劃分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYe

14、sExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo分類與決策樹1案例數(shù)據(jù)集基于age屬性劃分裂分后數(shù)據(jù)集的熵EntropyAge(T)= 5/15* Entropy(T1)+ 5/15* Entropy(T2)+ 5/15* Entropy(T3)= 5/15*( 3/5*log2(3/5) 2/5*log2(2/5) )+ 5/15*( 3/5*log2(3/5) 2/5*log2(2/5) )+ 5/15*( 1/5*log2(1

15、/5) 4/5*log2(4/5) )=0.888 信息增益Gain(age)=0.971-0.888=0.083AgeYoungMiddleOldYes:2No:3Yes：3No:2No:1Yes:4分類與決策樹1案例數(shù)據(jù)集基于其它屬性劃分根據(jù)hasjob 和credit劃分后的熵分別為EntropyHas_job(T)= 0.647 EntropyCredit(T)=0.608信息增益分別為：Gain(hasjob)=0.324 Gain(credit)=0.363Gain(ownhome)=0.42Gain(age)=0.971-0.888=0.083has_jobYesNoYes:5N

16、o:0No:6Yes:4creditfairgoodexcellentYes:1No:4Yes：4No:2No:0Yes:4Own_homeYesNoYes:6No:0No:6Yes:3分類與決策樹1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNoOwn_homeYesNoNo

17、:6Yes:3Yes:6No:0has_jobYesNoYes:3No:0No:6Yes:0分類與決策樹1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldN

18、oYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo信息增益方法偏向選擇具有大量取值的屬性分類與決策樹1信息增益率假設(shè)按照屬性S來(lái)劃分T，設(shè)S有m個(gè)值，根據(jù)該屬性的取值將數(shù)據(jù)集T劃分成m個(gè)子集T1，T2，Tm，設(shè)Tj的數(shù)據(jù)個(gè)數(shù)是tj。信息增益率可以通過(guò)如下公式計(jì)算得到：其中， 如前面所定義， 的定義為 分類與決策樹1信息增益率：案例數(shù)據(jù)集基于ownhome屬性劃分信息增益Gain(ownhome)=0.971-0.551=0.42SPLITI(ownhome)=-6/15*log2(6/15) 9/15*log2(9

19、/15) =0.971信息增益率GR(ownhome)=0.42/0.971=0.433Own_homeYesNoYes:6No:0No:6Yes:3分類與決策樹1GINI指數(shù)的下降 GINI指數(shù)的下降 = 裂分前數(shù)據(jù)集的GINI指數(shù) 裂分后各子數(shù)據(jù)集的GINI指數(shù)加權(quán)和 其中：權(quán)重為每個(gè)子集中的觀測(cè)數(shù)在裂分前總觀測(cè)數(shù)中所占的比例分類與決策樹1二分指數(shù)劃分對(duì)于在屬性s的劃分t，二分指數(shù)的改進(jìn)量為：（j表示目標(biāo)變量的取值）產(chǎn)生兩個(gè)子節(jié)點(diǎn)間最大差異的屬性s被選擇。分類與決策樹1卡方檢驗(yàn)劃分計(jì)算每個(gè)裂分的卡方值選擇卡方檢驗(yàn)最顯著的變量及其裂分分支分類與決策樹1選擇裂分屬性及其裂分條件測(cè)試每個(gè)屬性及其

20、可能的裂分條件，計(jì)算裂分指標(biāo)，選擇最佳者。注意：對(duì)取值范圍比較大的類別屬性，可考慮分組泛化對(duì)有序類別屬性，劃分不能改變其順序性對(duì)數(shù)值型屬性，理論上需要測(cè)試各種可能的劃分條件，實(shí)際上可以進(jìn)行優(yōu)化測(cè)試。也可以進(jìn)行離散化處理。34排序類標(biāo)號(hào)改變的臨界點(diǎn)中間值作為候選劃分閾值分類與決策樹1PersonHair LengthWeightAgeClass Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”20045M35分類與決策樹1PersonH

21、air LengthWeightAgeClassMaggie4”201FLisa6”788FBart2”9010MMarge10”15034FSelma8”16041FAbe1”17070MOtto10”18038MKrusty6”20045M Homer0”25036M分類與決策樹1Weight = 165?yesno劃分前：Entropy(4F,5M) = -(4/9)log2(4/9) - (5/9)log2(5/9) = 0.9911Entropy(4F,1M) = -(4/5)log2(4/5) - (1/5)log2(1/5) = 0.7219Entropy(0F,4M) = -(

22、0/4)log2(0/4) - (4/4)log2(4/4) = 0Gain(Weight = 165) = 0.9911 (5/9 * 0.7219 + 4/9 * 0 ) = 0.590037分類與決策樹12. 裂分停止條件每個(gè)葉子節(jié)點(diǎn)都屬于同一個(gè)類別； 有可能得到一個(gè)非常大的樹，某些葉子節(jié)點(diǎn)只包含很少的觀測(cè)。節(jié)點(diǎn)包含的觀測(cè)個(gè)數(shù)小于某個(gè)指定值；裂分的目標(biāo)指標(biāo)（例如：信息增益、信息增益率）非常小；樹的深度達(dá)到了預(yù)先指定的最大值。預(yù)剪枝38分類與決策樹13. 樹的選擇 分類模型的優(yōu)劣一般情況下可根據(jù)分類的準(zhǔn)確度（或分類誤差）來(lái)判斷。訓(xùn)練誤差：在訓(xùn)練集上的誤差 泛化誤差：在非訓(xùn)練集上的期望誤差在

23、驗(yàn)證數(shù)據(jù)集上的預(yù)測(cè)誤差是泛化誤差的無(wú)偏估計(jì)。分類與決策樹1過(guò)擬合好的分類模型：低訓(xùn)練誤差低泛化誤差擬合不足：較高訓(xùn)練誤差較高泛化誤差過(guò)擬合：低訓(xùn)練誤差較高泛化誤差分類與決策樹1過(guò)擬合分類與決策樹1過(guò)擬合處理策略-剪枝 給樹剪枝就是剪掉“弱枝”（指的是在驗(yàn)證數(shù)據(jù)上誤分類率高的樹枝）。 為樹剪枝會(huì)增加訓(xùn)練數(shù)據(jù)上的錯(cuò)誤分類率，但精簡(jiǎn)的樹會(huì)提高新數(shù)據(jù)上的預(yù)測(cè)能力。 分類與決策樹1決策樹剪枝預(yù)剪枝（提前終止裂分）在樹沒(méi)有完全擴(kuò)張之前就停止樹的生長(zhǎng)，即不要求每個(gè)葉子節(jié)點(diǎn)內(nèi)的每一個(gè)屬性值都相同，或者屬于同一類別。后剪枝用新的葉子節(jié)點(diǎn)（類標(biāo)號(hào)為多數(shù)類）代替子樹；用子樹中最常用的分枝代替子樹；分類與決策樹1后剪

24、枝訓(xùn)練集：驗(yàn)證集：訓(xùn)練后得到的決策樹：colorx2classredsuccessbluefailurebluefailurecolorx2classredfailureredfailureredfailurebluesuccessfailure驗(yàn)證集誤差：41分類與決策樹1最小誤差樹與最佳剪枝樹分類與決策樹1三、產(chǎn)生分類規(guī)則并應(yīng)用對(duì)從根到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則： 沿著給定路徑上的每個(gè)劃分 用邏輯AND形成分類規(guī)則的IF部分，對(duì)應(yīng)葉節(jié)點(diǎn)的類別形成THEN部分。例如：R1：IF Own_home=yes THEN Class=yesR2：IF Own_home=No AND Has_job=Yes THEN Class=YesR3：IF Own_home=No AND Has_job=No THEN Class=NoOwn_homeYesNoNo:6Yes:3Yes:6No:0has_jobYesNoYes:3No:0No:6Yes:0規(guī)則的覆蓋率 準(zhǔn)確率分類與決策樹1四、問(wèn)題討論缺失值問(wèn)題決策樹葉子節(jié)點(diǎn)的準(zhǔn)確含義決策樹方法的特點(diǎn)與改進(jìn)目標(biāo)變量在數(shù)據(jù)集樣本與總體的分布不一致時(shí)如何處理？分類與決策樹1變量值缺失問(wèn)題訓(xùn)練集中的輸入變量值缺失新數(shù)據(jù)中裂分變量值缺失使用代理劃分假定X* 是節(jié)點(diǎn)t的最佳劃分s*的裂分變量，代理劃分s（劃分效果最接近s*）使用另