《分类与决策树》由会员分享，可在线阅读，更多相关《分类与决策树（58页珍藏版）》请在金锄头文库上搜索。
1、分类与预测Vicky1银行个人住房行个人住房贷款款审批批银行个人客行个人客户提出住房提出住房贷款申款申请，根据，根据历史数史数据据发现：部分：部分贷款客款客户不能按不能按时还款。款。为尽量降尽量降低低这种种现象，需要象，需要发现不能按不能按时还款客款客户的特征，的特征，以便以便对以后住房以后住房贷款申款申请的的审批提供依据。批提供依据。 2006年年底，由年年底，由SAS机构与招商机构与招商银行启行启动了全了全行个人住房行个人住房贷款款评分卡开分卡开发与推广与推广项目。目。 该项目利用客目利用客户的的历史数据构建史数据构建评分卡模型，分卡模型，然后将然后将该模型模型应用到新客用到新客户上，最后
2、决定是否接上，最后决定是否接受新客受新客户的的贷款申款申请。分析数据集应该包括哪些客户？分析数据集应该包括哪些客户？2银行贷款申请IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcell
3、entYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo3分类与预测分分类：目目标变量量为非数非数值型型预测：目目标变量量为数数值型型根据根据历史数据集（已知目史数据集（已知目标变量），构建模型描述目量），构建模型描述目标变量量与与输入入变量之量之间的关系，并依的关系，并依据模型来分据模型来分类或或预测新数据新数据（目（目标变量量值未知未知)。 分分类模型也称模型也称为分分类器。器。模模型型应应用用建模建模规则规则1：Ifrefund=noandmarst=marriedthencheat=no模
4、型评估模型评估4分类的过程数据集分区数据集分区训练集集：建立模型：建立模型验证集集：调整和整和选择模型模型测试集集：评估模型的估模型的预测能力能力建立模型建立模型评估并估并选择模型模型运用模型运用模型 新数据（打分集）新数据（打分集）思考：分类模型在什么情况下不适合用于新数据？思考：分类模型在什么情况下不适合用于新数据？5分类方法决策决策树方法方法贝叶斯分叶斯分类法法LOGISTIC回回归神神经网网络方法方法K近近邻分分类法法SVM分分类法法.6RootLeafNode7决策树(decision tree)规则规则1：Ifrefund=noand(marst=singleormarst=div
5、orced)andtaxincome80kthencheat=yes7决策树是一棵二叉或多叉树结构每个内部节点代表一个属性，该节点的分支表示根据该属性的不同测试条件的输出叶子节点表示一个类标决策决策树一般是自上而下生成的一般是自上而下生成的8l决策树基本思想决策树基本思想l建立决策树建立决策树l将决策树转换为决策规则并应用将决策树转换为决策规则并应用l相关问题讨论相关问题讨论内容9一、决策树思想将数据集根据某将数据集根据某种种测试条件分条件分为2个或多个个或多个子集，使分裂后的子集子集，使分裂后的子集在目在目标变量上量上具有更具有更纯的分的分类纯度与混度与混杂度度10混混杂度的常用度的常用测度
6、指度指标信息信息熵 （ Entropy）基尼指数（基尼指数（ Gini Index）分分类误差（差（classification error)11Pj 是数据集合中类别是数据集合中类别j的相对比例的相对比例.entropy = 12信息信息熵 （ Entropy） 什么情况下，熵最小？什么情况下，熵最小？什么情况下，熵最大？什么情况下，熵最大？lentropy = - 1 log21 - 0 log20 = 0目标变量为二元变量：lentropy = -0.5 log20.5 0.5 log20.5 =112IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFa
7、irNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款数据集银行贷款案例数据集的熵：银行贷款案例数据集的熵：
8、Entropy(T)=6/15*log2(6/15)9/15*log2(9/15)=0.97113Gini 指数Pj 是数据集合中类别是数据集合中类别j的相对比例的相对比例.GINI最大最大=？GINI最小最小=？1-1/2（目标变量为二元变量）（目标变量为二元变量）014IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYes
9、GoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款数据集银行贷款案例数据集银行贷款案例数据集的基尼指数：的基尼指数：gini=1-(6/15)2-(9/15)2=0.4815分分类误差（差（classification error)CE最大最大=？CE最小最小=？1-1/2（目标变量为二元变量）（目标变量为二元变量）016IDAgeHas_j
10、obOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFair
11、No银行贷款数据集银行贷款案例数据集银行贷款案例数据集的分类误差：的分类误差：CE=1- 9/15=6/15=0.417二、建立二、建立决策决策树常用算法常用算法ID3-ID5,C4,C4.5,C5.0CART（Classification and Regression Trees分分类与回与回归树) （C&RT）CHAID(chi-squared automatic interaction detection，卡方自，卡方自动交互交互检测)二叉二叉GINI指数指数二叉或多叉二叉或多叉信息熵信息熵二叉或多叉二叉或多叉18建立建立决策决策树树的生的生长分裂属性及其条件的分裂属性及其条件的选择 何
12、何时结束分裂束分裂树的的选择191. 裂分目标与属性选择裂分目裂分目标 使分裂后数据子集的使分裂后数据子集的纯度度比裂分前数据集的比裂分前数据集的纯度度最大限度的提高最大限度的提高；即不同；即不同类别的的观测尽量分散在不尽量分散在不同的子集中。同的子集中。指指标信息增益与信息增益率信息增益与信息增益率GINI指数的下降指数的下降二分指数二分指数卡方卡方检验C-SEP、20信息增益Information Gain = 裂分前数据集的裂分前数据集的熵 裂分后各子数据集的裂分后各子数据集的熵加加权和和其中：其中：权重重为每个子集中的每个子集中的观测数在裂分前数在裂分前总观测数中所占的比例数中所占的比
13、例21案例数据集基于own_home属性划分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14O
14、ldYesNoExcellentYes15OldNoNoFairNo22案例数据集基于ownhome属性划分划分后数据集的划分后数据集的熵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:6No:0No:6Yes:3裂分前数据集的熵：裂分前数据集的熵：Entrop
15、y(T0)=6/15*log2(6/15)9/15*log2(9/15)=0.97123案例数据集基于age属性划分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes1
16、2OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo24案例数据集基于age属性划分裂分后数据集的裂分后数据集的熵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/5) 4/5*log2(4/5) )=0.888 信息增益信息增益
17、Gain(age)=0.971-0.888=0.083AgeYoungMiddleOldYes:2No:3Yes：3No:2No:1Yes:425案例数据集基于其它属性划分根据根据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:5No:0No:6Yes:4creditfair
18、goodexcellentYes:1No:4Yes：4No:2No:0Yes:4Own_homeYesNoYes:6No:0No:6Yes:326IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNoOwn_homeYesNoNo:6Yes:3Yes:6No:0has_jobYesN
19、oYes:3No:0No:6Yes:027IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14Ol
20、dYesNoExcellentYes15OldNoNoFairNo信息增益方法偏向选择具有大量取值的属性信息增益方法偏向选择具有大量取值的属性28信息增益率信息增益率假设按照属性假设按照属性S来划分来划分T，设，设S有有m个值，根据该属性的取值个值，根据该属性的取值将数据集将数据集T划分成划分成m个子集个子集T1，T2，Tm，设，设Tj的数据个数的数据个数是是tj。信息增益率可以通过如下公式计算得到：。信息增益率可以通过如下公式计算得到：其中，其中， 如前面所定义，如前面所定义， 的定义为的定义为 29信息增益率：案例数据集基于ownhome属性划分信息增益信息增益Gain(ownhome)=
21、0.971-0.551=0.42SPLITI(ownhome)=-6/15*log2(6/15) 9/15*log2(9/15) =0.971信息增益率信息增益率GR(ownhome)=0.42/0.971=0.433Own_homeYesNoYes:6No:0No:6Yes:330GINI指数的下降 GINI指数的下降指数的下降 = 裂分前数据集的裂分前数据集的GINI指数指数 裂分后各子裂分后各子数据集的数据集的GINI指数加指数加权和和 其中：其中：权重重为每个子集中的每个子集中的观测数在裂数在裂分前分前总观测数中所占的比例数中所占的比例31二分指数划分二分指数划分对于在属性于在属性s的
22、划分的划分t，二分指数的改，二分指数的改进量量为：（j表示目表示目标变量的取量的取值）产生两个子生两个子节点点间最大差异的属性最大差异的属性s被被选择。32卡方检验划分计算每个裂分的卡方算每个裂分的卡方值选择卡方卡方检验最最显著的著的变量及其裂分分支量及其裂分分支33选择裂分属性及其裂分条件裂分属性及其裂分条件测试每个属性及其可能的裂分条件，每个属性及其可能的裂分条件，计算裂分指算裂分指标，选择最佳者。最佳者。注意：注意：对取取值范范围比比较大的大的类别属性，可考属性，可考虑分分组泛化泛化对有序有序类别属性，划分不能改属性，划分不能改变其其顺序性序性对数数值型属性，理型属性，理论上需要上需要测
23、试各种可能的划分条件，各种可能的划分条件，实际上可以上可以进行行优化化测试。也可以。也可以进行离散化行离散化处理。理。341.排序排序2.类标号改变的临界点中间值作为候选划分阈值类标号改变的临界点中间值作为候选划分阈值34PersonHair LengthWeightAgeClass Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”20045M3535PersonHair LengthWeightAgeClassMaggie4”201
24、FLisa6”788FBart2”9010MMarge10”15034FSelma8”16041FAbe1”17070MOtto10”18038MKrusty6”20045M Homer0”25036M36Weight = 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) = -(0/4)log2(0/4) - (4/4)log2(4/4) = 0Ga
25、in(Weight = 165) = 0.9911 (5/9 * 0.7219 + 4/9 * 0 ) = 0.590037372. 裂分停止条件裂分停止条件每个叶子节点都属于同一个类别；每个叶子节点都属于同一个类别；有可能得到一个非常大的树，某些叶子节点只有可能得到一个非常大的树，某些叶子节点只包含很少的观测。包含很少的观测。节点包含的观测个数小于某个指定值；节点包含的观测个数小于某个指定值；裂分的目标指标（例如：信息增益、信息增益率）裂分的目标指标（例如：信息增益、信息增益率）非常小；非常小；树的深度达到了预先指定的最大值。树的深度达到了预先指定的最大值。预剪枝预剪枝38383. 树的的选
26、择 分分类模型的模型的优劣一般情况下可根据分劣一般情况下可根据分类的准的准确度（或分确度（或分类误差）来判断。差）来判断。训练误差：在差：在训练集上的集上的误差差 泛化泛化误差：在非差：在非训练集上的期望集上的期望误差差在在验证数据集上的数据集上的预测误差是泛化差是泛化误差的无偏估差的无偏估计。39过拟合合好的分好的分类模型：模型：低低训练误差差低泛化低泛化误差差拟合不足：合不足：较高高训练误差差较高泛化高泛化误差差过拟合：合：低低训练误差差较高泛化高泛化误差差40过拟合41过拟合合处理策略理策略-剪枝剪枝 给树剪枝就是剪掉剪枝就是剪掉“弱枝弱枝”（指的是在（指的是在验证数据上数据上误分分类率
27、高的率高的树枝）。枝）。 为树剪枝会增加剪枝会增加训练数据上的数据上的错误分分类率，但精率，但精简的的树会提高新数据上的会提高新数据上的预测能力。能力。 42决策决策树剪枝剪枝预剪枝（提前剪枝（提前终止裂分）止裂分）在在树没有完全没有完全扩张之前就停止之前就停止树的生的生长，即不要求，即不要求每个叶子每个叶子节点内的每一个属性点内的每一个属性值都相同，或者属都相同，或者属于同一于同一类别。后剪枝后剪枝用新的叶子用新的叶子节点（点（类标号号为多数多数类）代替子）代替子树；用子用子树中最常用的分枝代替子中最常用的分枝代替子树；43后剪枝训练集：验证集：训练后得到的决策树：colorcolorx2x
28、2classclassredredsuccesssuccessbluebluefailurefailurebluebluefailurefailurecolorcolorx2x2classclassredredfailurefailureredredfailurefailureredredfailurefailurebluebluesuccesssuccessfailure验证集误差：验证集误差：4144最小最小误差差树与最佳剪枝与最佳剪枝树45三、三、产生分生分类规则并并应用用对从根到叶从根到叶节点的每一条路径点的每一条路径创建一条建一条规则： 沿着沿着给定路径上的每个划分定路径上的每个划分
29、 用用逻辑AND形成分形成分类规则的的IF部分，部分，对应叶叶节点的点的类别形成形成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规则的覆盖率规则的覆盖率准确率准确率46四、四、问题讨论缺失缺失值问题决策决策树叶子叶子节点的准确含点的准确
30、含义决策决策树方法的特点与改方法的特点与改进目目标变量在数据集量在数据集样本与本与总体的分布不一体的分布不一致致时如何如何处理？理？47变量量值缺失缺失问题训练集中的集中的输入入变量量值缺失缺失新数据中裂分新数据中裂分变量量值缺失缺失使用代理划分使用代理划分假定假定X* 是是节点点t的最佳划分的最佳划分s*的裂分的裂分变量，代理量，代理划分划分s（划分效果最接近（划分效果最接近s*）使用另外一个）使用另外一个输入入变量量X。如果要如果要预测的新的新记录在在X*上有缺失上有缺失值而在而在X变量量上没有缺失上没有缺失值，则预测将使用代理划分将使用代理划分s。48问题讨论缺失缺失值问题决策决策树叶子
31、叶子节点的准确含点的准确含义决策决策树方法的特点与改方法的特点与改进目目标变量在数据集量在数据集样本与本与总体的分布不一体的分布不一致致时如何如何处理？理？49决策树叶子节点的准确含义PersonHair LengthWeightAgeClass Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”20045MP(class=M)=100%P(class=F)=80%Weight = 165?yesno50问题讨论缺失缺失值问题决策决策树
32、叶子叶子节点的准确含点的准确含义决策决策树方法的特点与改方法的特点与改进目目标变量在数据集量在数据集样本与本与总体的分布不一体的分布不一致致时如何如何处理？理？51决策决策树分分类方法的特点方法的特点优点：优点：1)可以生成容易理解的规则；可以生成容易理解的规则；2)计算量相对来说不是很大；计算量相对来说不是很大；3)可以处理连续和离散变量；可以处理连续和离散变量；4)可以清晰的显示哪些变量比较重要。可以清晰的显示哪些变量比较重要。5）对输入变量的缺失值、噪声、冗余属性不敏感对输入变量的缺失值、噪声、冗余属性不敏感缺点：缺点：1)对数值型变量需要进行离散化或候选划分较多；对数值型变量需要进行离
33、散化或候选划分较多；2)模型稳定性受数据影响较大；模型稳定性受数据影响较大；3)一般的算法一次只能根据一个变量来裂分一般的算法一次只能根据一个变量来裂分52单属性裂分VS多属性裂分53决策决策树方法改方法改进提高算法可伸提高算法可伸缩性性RainForest（雨林）算法（雨林）算法在每个在每个节点，点，对每个属性每个属性维护一个一个AVC（属性（属性-值，类标号及其号及其计数）集，将其存于内存中。数）集，将其存于内存中。54决策决策树方法改方法改进自助自助乐观算法算法可可视化挖掘化挖掘基于感知的分基于感知的分类(PBC)法法55问题讨论缺失缺失值问题决策决策树叶子叶子节点的准确含点的准确含义决
34、策决策树方法的特点与改方法的特点与改进目目标变量在数据集量在数据集样本与本与总体的分布不一体的分布不一致致时如何如何处理？理？56后验概率的调整-设置先验概率条件下57练习Customer IDStudentCredit RatingClass: Buy PDA1No FairNo2No ExcellentNo3No FairYes4No Fair Yes5Yes Fair Yes6Yes ExcellentNo7Yes ExcellentYes8NoExcellentNo以信息增益最大作为裂分目标，以信息增益最大作为裂分目标，哪个变量将是决策树的根节点？哪个变量将是决策树的根节点？log2(2/3)=-0.585,log2(1/3)=-1.585,log2(1/2)=-1,log2(3/5)=-0.737,Log2(2/5)=-1.322,log2(1/4)=-2,log2(3/4)=-0.4155858
