分類與決策樹[1]課件

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

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

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

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

5、數(shù)（ Gini Index）分類誤差（classification error)分類與決策樹1Pj 是數(shù)據(jù)集合中類別j的相對比例.entropy = 12信息熵 （ Entropy） 什么情況下，熵最小？什么情況下，熵最大？entropy = - 1 log21 - 0 log20 = 0目標變量為二元變量：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的相對比例.GINI最大=？GINI最小=？1-1/2 （目標變量為二元變量） 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 （目標變量為二元變量） 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，卡方自動交互檢測)二叉 GINI 指數(shù)二叉或多叉 信息熵二叉或多叉分類與決策樹1建立決策樹樹的生長分裂屬性及其條件的選擇 何時結(jié)束分裂樹的選擇分類與決策樹11. 裂分目標與屬性選擇裂分目標 使分裂后數(shù)據(jù)子集的純度比裂分前數(shù)據(jù)集的純度最大限度的提高；即不同類別的觀測盡量分散在不同的子集中。指標信息增益與信息增益率GINI指數(shù)的下降二分指數(shù)卡方檢驗C-SEP、分類與決策樹1信息增益Information Gain = 裂分前數(shù)據(jù)集的熵 裂分

11、后各子數(shù)據(jù)集的熵加權和其中：權重為每個子集中的觀測數(shù)在裂分前總觀測數(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信息增益率假設按照屬性S來劃分T，設S有m個值，根據(jù)該屬性的取值將數(shù)據(jù)集T劃分成m個子集T1，T2，Tm，設Tj的數(shù)據(jù)個數(shù)是tj。信息增益率可以通過如下公式計算得到：其中， 如前面所定義， 的定義為 分類與決策樹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ù)加權和 其中：權重為每個子集中的觀測數(shù)在裂分前總觀測數(shù)中所占的比例分類與決策樹1二分指數(shù)劃分對于在屬性s的劃分t，二分指數(shù)的改進量為：（j表示目標變量的取值）產(chǎn)生兩個子節(jié)點間最大差異的屬性s被選擇。分類與決策樹1卡方檢驗劃分計算每個裂分的卡方值選擇卡方檢驗最顯著的變量及其裂分分支分類與決策樹1選擇裂分屬性及其裂分條件測試每個屬性及其

20、可能的裂分條件，計算裂分指標，選擇最佳者。注意：對取值范圍比較大的類別屬性，可考慮分組泛化對有序類別屬性，劃分不能改變其順序性對數(shù)值型屬性，理論上需要測試各種可能的劃分條件，實際上可以進行優(yōu)化測試。也可以進行離散化處理。34排序類標號改變的臨界點中間值作為候選劃分閾值分類與決策樹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. 裂分停止條件每個葉子節(jié)點都屬于同一個類別； 有可能得到一個非常大的樹，某些葉子節(jié)點只包含很少的觀測。節(jié)點包含的觀測個數(shù)小于某個指定值；裂分的目標指標（例如：信息增益、信息增益率）非常小；樹的深度達到了預先指定的最大值。預剪枝38分類與決策樹13. 樹的選擇 分類模型的優(yōu)劣一般情況下可根據(jù)分類的準確度（或分類誤差）來判斷。訓練誤差：在訓練集上的誤差 泛化誤差：在非訓練集上的期望誤差在

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

24、枝訓練集：驗證集：訓練后得到的決策樹：colorx2classredsuccessbluefailurebluefailurecolorx2classredfailureredfailureredfailurebluesuccessfailure驗證集誤差：41分類與決策樹1最小誤差樹與最佳剪枝樹分類與決策樹1三、產(chǎn)生分類規(guī)則并應用對從根到葉節(jié)點的每一條路徑創(chuàng)建一條規(guī)則： 沿著給定路徑上的每個劃分 用邏輯AND形成分類規(guī)則的IF部分，對應葉節(jié)點的類別形成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ī)則的覆蓋率 準確率分類與決策樹1四、問題討論缺失值問題決策樹葉子節(jié)點的準確含義決策樹方法的特點與改進目標變量在數(shù)據(jù)集樣本與總體的分布不一致時如何處理？分類與決策樹1變量值缺失問題訓練集中的輸入變量值缺失新數(shù)據(jù)中裂分變量值缺失使用代理劃分假定X* 是節(jié)點t的最佳劃分s*的裂分變量，代理劃分s（劃分效果最接近s*）使用另