分类与决策树

1、分类与预测Vicky银行个人住房贷款审批银行个人住房贷款审批银行个人客户提出银行个人客户提出住房住房贷款申请，根据历史贷款申请，根据历史数据发现：部分贷款客户不能按时还款。为尽量数据发现：部分贷款客户不能按时还款。为尽量降低这种现象，需要发现不能按时还款客户的降低这种现象，需要发现不能按时还款客户的特特征，以便对以后住房贷款申请的审批提供依据。征，以便对以后住房贷款申请的审批提供依据。 2006年年底，由年年底，由SAS机构与招商银行启动了全机构与招商银行启动了全行个人住房贷款评分卡开发与推广项目。行个人住房贷款评分卡开发与推广项目。 该项目利用客户的历史数据构建评分卡模型，该项目利用客户的历

2、史数据构建评分卡模型，然后将该模型应用到新客户然后将该模型应用到新客户上，上，最后决定是否接最后决定是否接受新客户受新客户的贷款申请。的贷款申请。银行贷款申请 IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes1

3、1OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo分类与预测 分类：分类： 目标变量为非数值型目标变量为非数值型 预测：预测： 目标变量目标变量为为数值型数值型 根据历史数据集（已知目标变根据历史数据集（已知目标变量），构建模型描述目标变量量），构建模型描述目标变量与输入变量之间的关系，并依与输入变量之间的关系，并依据模型来分类或预测新数据（据模型来分类或预测新数据（目标变量值未知目标变量值未知)。 分类模型也称为分类器。分类模型也称为分类器。模型模型应用应用建

4、模建模规则规则1：If refund=no and marst=married then cheat=no模型评估模型评估分类的过程 数据集分区数据集分区 训练集训练集：建立模型：建立模型 验证集验证集：调整和选择模型：调整和选择模型 测试集测试集：评估模型的预测能力：评估模型的预测能力 建立模型建立模型 评估并选择模型评估并选择模型 运用模型运用模型 新数据新数据思考：分类模型在什么情况下不思考：分类模型在什么情况下不适合适合用于新数据？用于新数据？分类方法决策树方法决策树方法贝叶斯分类法贝叶斯分类法LOGISTIC回归回归神经网络方法神经网络方法K近邻分类法近邻分类法SVM分类法分类法.R

5、ootLeafNode7决策树(decision tree)规则规则1：If refund=no and (marst=single or marst=divorced) and taxincome80k then cheat=yes决策树 是一棵二叉或多叉树结构 每个内部节点代表一个属性，该节点的分支表示根据该属性的不同测试条件的输出 叶子节点表示一个类标 决策树决策树一般是自上而下生成一般是自上而下生成的的l决策树基本思想决策树基本思想l建立决策树建立决策树l将决策树转换为决策规则并应用将决策树转换为决策规则并应用l相关问题讨论相关问题讨论内容一、决策树思想 将数据集根据某将数据集根据某中

6、中测试条件分为测试条件分为2个或多个个或多个子集，使分裂后的子集子集，使分裂后的子集在目标变量上在目标变量上具有具有更纯的分类更纯的分类纯度与混杂度纯度与混杂度混杂度的常用测度指标混杂度的常用测度指标 信息熵信息熵 （ Entropy） 基尼基尼指数（指数（ Gini Index） 分类误差（分类误差（classification error)Pj 是数据集合中类别是数据集合中类别j的相对比例的相对比例.entropy = iiipp2log12信息熵信息熵 （ Entropy） 什么情况下，熵最小？什么情况下，熵最小？什么情况下，熵什么情况下，熵最大？最大？lentropy = - 1 lo

7、g21 - 0 log20 = 0目标变量为二元变量：lentropy = -0.5 log20.5 0.5 log20.5 =1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcell

8、entYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款数据集银行贷款案例数据银行贷款案例数据集的集的熵：熵： Entropy(T)=6/15*log2(6/15) 9/15*log2(9/15)=0.971Gini 指数Pj 是数据集合中类别是数据集合中类别j的相对的相对比例比例.GINI最大最大=？GINI最小最小=？1-1/2 （目标变量为二元变量）（目标变量为二元变量） 0IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNo

9、NoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款数据集银行贷款案例数据集银行贷款案例数据集的基尼指数：的基尼指数：gini=1

10、-(6/15)2-(9/15)2=0.48分类误差（分类误差（classification error)CE最大最大=？CE最小最小=？1-1/2 （目标变量为二元变量）（目标变量为二元变量） 0IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10Middle

11、NoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款数据集银行贷款案例数据集银行贷款案例数据集的分类误差：的分类误差：CE=1- 9/15=6/15=0.4二、建立二、建立决策树决策树常用常用算法算法 ID3-ID5,C4,C4.5,C5.0 CART（Classification and Regression Trees分分类与回归树类与回归树) （C&RT） CHAID(chi-squared automatic i

12、nteraction detection，卡方自动交互检测，卡方自动交互检测)二二叉叉 GINI 指数指数二叉或多叉二叉或多叉 信息熵信息熵二叉或多叉二叉或多叉建立建立决策树决策树 树的生长树的生长 分裂属性及其条件的选择分裂属性及其条件的选择 何时结束分裂何时结束分裂 树的选择树的选择1. 裂分目标与属性选择 裂分裂分目标目标 使分裂后数据子集的使分裂后数据子集的纯度纯度比裂分前数据集的纯度比裂分前数据集的纯度最大限度的提高最大限度的提高；即不同类别的观测尽量分散在不；即不同类别的观测尽量分散在不同的子集中。同的子集中。 指标指标 信息增益与信息增益率信息增益与信息增益率 GINI指数的下降

13、指数的下降 二分指数二分指数 卡方检验卡方检验 C-SEP、信息增益Information Gain = 裂分前数据集的熵裂分前数据集的熵 裂分后各子数据裂分后各子数据集集的熵的熵加权和加权和其中：权重为每个其中：权重为每个子集中的观测数在裂分前总观测子集中的观测数在裂分前总观测数中所占的比例数中所占的比例案例数据集基于own_home属性划分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNo

14、FairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo案例数据集基于ownhome属性划分划分后数据集的熵划分后数据集的熵EntropyOwn_home(T)= 6/15* Entropy(T1)+ 9/15* Entropy(T2)= 6/15*( 6/6*log2(6/6) 0/

15、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 裂分前数据集的熵：裂分前数据集的熵：Entropy(T0)=6/15*log2(6/15) 9/15*log2(9/15)=0.971案例数据集基于age属性划分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYe

16、sFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo案例数据集基于age属性划分裂裂分后数据集的熵分后数据集的熵EntropyAge(T)= 5/15* Entropy(T1)+ 5/15* Entropy(T2

17、)+ 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 信息增益信息增益Gain(age)=0.971-0.888=0.083AgeYoungMiddleOldYes:2No:3Yes：3No:2No:1Yes:4案例数据集基于其它属性划分根据根据hasjob 和和credit划分后的熵分别为划分后的熵分别为EntropyHas_job(T)= 0.647 Entropy

18、Credit(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:4creditfairgoodexcellentYes:1No:4Yes：4No:2No:0Yes:4Own_homeYesNoYes:6No:0No:6Yes:3IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGo

19、odYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNoOwn_homeYesNoNo:6Yes:3Yes:6No:0has_jobYesNoYes:3No:0No:6Yes:0IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFai

20、rNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo信息增益方法偏向选择具有大量取值的信息增益方法偏向选择具有大量取值的属性属性信息增益率信息增益率 假设按照属性假设按照属性S来划分来划分T，设，设S有有m个值，根据该属性的取值个值，根据该属性的取值将将数据数据集集T划分成划分成m个子集

21、个子集T1，T2，Tm，设，设Tj的数据个数的数据个数是是tj。信息增益率可以通过如下公式计算得到：。信息增益率可以通过如下公式计算得到： 其中，其中， 如前面所定义，如前面所定义， 的定义为的定义为 )()()(TSplitISGainSGainRatioSmjjjSttttTSplitI12)(log)()(SGain)(TSplitIS信息增益率：案例数据集基于ownhome属性划分信息增益信息增益Gain(ownhome)=0.971-0.551=0.42SPLITI(ownhome)=-6/15*log2(6/15) 9/15*log2(9/15) =0.971信息增益率信息增益率G

22、R(ownhome)=0.42/0.971=0.433Own_homeYesNoYes:6No:0No:6Yes:3GINI指数的下降 GINI指数指数的下降的下降 = 裂裂分前数据集分前数据集的的GINI指数指数 裂分后各子裂分后各子数据集数据集的的GINI指数指数加权和加权和 其中其中：权重为每个子集中的观测数在裂：权重为每个子集中的观测数在裂分前总观测数中所占的比例分前总观测数中所占的比例二分指数划分二分指数划分 对于在属性对于在属性s的划分的划分t，二分指数的改进量，二分指数的改进量为：（为：（j表示目标变量的取值）表示目标变量的取值） 产生两个子节点间最大差异的产生两个子节点间最大差

23、异的属性属性s被选择。被选择。卡方检验划分 计算每个裂分的卡方值计算每个裂分的卡方值 选择卡方检验最显著的变量及其裂分分支选择卡方检验最显著的变量及其裂分分支选择裂分属性及其裂分条件选择裂分属性及其裂分条件 测试每个属性及其可能的裂分条件，计算裂分测试每个属性及其可能的裂分条件，计算裂分指标，选择最佳者。指标，选择最佳者。 注意：注意： 对取值范围比较大的类别属性，对取值范围比较大的类别属性，可考虑分组泛化可考虑分组泛化 对有序类别属性，划分不能改变其顺序性对有序类别属性，划分不能改变其顺序性 对数值型属性，理论上需要测试各种可能的划分条件，对数值型属性，理论上需要测试各种可能的划分条件，实际

24、上可以进行实际上可以进行优化测试优化测试。也可以进行离散化处理。也可以进行离散化处理。341.排序排序2.类标号改变的类标号改变的临界点中间值作为临界点中间值作为候选候选划分阈值划分阈值PersonHair LengthWeightAgeClass Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”20045M35PersonHair LengthWeightAgeClassMaggie4”201FLisa6”788FBart2”901

25、0MMarge10”15034FSelma8”16041FAbe1”17070MOtto10”18038MKrusty6”20045M Homer0”25036MWeight = 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) = 0Gain(Weight = 165) = 0.9

26、911 (5/9 * 0.7219 + 4/9 * 0 ) = 0.5900372. 裂分停止条件裂分停止条件每个叶子节点都属于同一个类别；每个叶子节点都属于同一个类别； 有可能得到一个非常大的树，某些叶子节点只有可能得到一个非常大的树，某些叶子节点只包含很少的观测。包含很少的观测。节点包含的观测个数小于某个指定值；节点包含的观测个数小于某个指定值；裂分的目标指标（例如：信息增益、信息增益率）裂分的目标指标（例如：信息增益、信息增益率）非常小；非常小；树树的深度达到了预先指定的最大的深度达到了预先指定的最大值。值。预剪枝预剪枝383. 树的选择树的选择 分类模型的优劣一般情况下可根据分类的准分

27、类模型的优劣一般情况下可根据分类的准确度（或分类误差）来判断。确度（或分类误差）来判断。训练误差：在训练集上的误差训练误差：在训练集上的误差 泛化误差：在非训练集上的期望误差泛化误差：在非训练集上的期望误差在验证数据集上的预测误差是泛化误差的无偏估计。在验证数据集上的预测误差是泛化误差的无偏估计。过拟合过拟合 好的分类模型：好的分类模型： 低训练误差低训练误差 低泛化误差低泛化误差 拟合不足：拟合不足： 较高训练误差较高训练误差 较高泛化误差较高泛化误差 过拟合：过拟合： 低训练误差低训练误差 较高泛化误差较高泛化误差过拟合过拟合处理策略过拟合处理策略-剪枝剪枝 给树剪枝就是剪掉给树剪枝就是剪

28、掉“弱枝弱枝”（指的是（指的是在验证数据上误分类率高的树枝）。在验证数据上误分类率高的树枝）。 为树剪枝会增加训练数据上的错误分为树剪枝会增加训练数据上的错误分类率，但精简的树会提高新数据上的预类率，但精简的树会提高新数据上的预测能力。测能力。 决策树剪枝决策树剪枝 预剪枝（提前终止裂分）预剪枝（提前终止裂分）在树没有完全扩张之前就停止树的生长，即不要求在树没有完全扩张之前就停止树的生长，即不要求每个叶子节点内的每一个属性值都相同，或者属每个叶子节点内的每一个属性值都相同，或者属于同一类别。于同一类别。 后剪枝后剪枝 用新的叶子节点（类标号为多数类）代替子树；用新的叶子节点（类标号为多数类）代

29、替子树； 用子树中最常用的分枝代替子树；用子树中最常用的分枝代替子树；后剪枝训练集：验证集：训练后得到的决策树：colorcolorx2x2classclassredredsuccesssuccessbluebluefailurefailurebluebluefailurefailurecolorcolorx2x2classclassredredfailurefailureredredfailurefailureredredfailurefailurebluebluesuccesssuccessfailure验证集验证集误差误差：41最小误差树与最佳剪枝树最小误差树与最佳剪枝树三、产生分类规则

30、并应用三、产生分类规则并应用 对从根到叶节点的每一条路径创建一条规则：对从根到叶节点的每一条路径创建一条规则： 沿着给定路径上的每个划分沿着给定路径上的每个划分 用逻辑用逻辑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

31、:6No:0has_jobYesNoYes:3No:0No:6Yes:0规则的覆盖率规则的覆盖率 准确率准确率四、问题讨论四、问题讨论 缺失值问题缺失值问题 决策决策树叶子节点的准确含义树叶子节点的准确含义 决策树方法的特点与改进决策树方法的特点与改进 目标变量在目标变量在数据集数据集样本与总体的分布不一样本与总体的分布不一致时如何处理？致时如何处理？变量值变量值缺失问题缺失问题 训练集中的输入变量值缺失训练集中的输入变量值缺失 新新数据中裂分数据中裂分变量变量值值缺失缺失使用代理划分使用代理划分 假定假定X* 是节点是节点t的最佳划分的最佳划分s*的裂分的裂分变量变量，代，代理划分理划分s（

32、划分（划分效果最接近效果最接近s*）使用另外一个输）使用另外一个输入变量入变量X。 如果要预测的新记录在如果要预测的新记录在X*上有缺失值而在上有缺失值而在X变变量上没有缺失值量上没有缺失值，则预测将使用代理划分，则预测将使用代理划分s。问题讨论问题讨论 缺失值问题缺失值问题 决策决策树叶子节点的准确含义树叶子节点的准确含义 决策树方法的决策树方法的特点与特点与改进改进 目标变量在目标变量在数据集数据集样本与总体的分布不一样本与总体的分布不一致时如何处理？致时如何处理？决策树叶子节点的准确含义PersonHair LengthWeightAgeClass Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”20045MP(class=M)=100%P(class=F)=80%Weight = 165?yesno问题讨论问题讨论 缺失值问题缺失值问题 决策决策树叶子节点的准确含义树叶子节点的准确含义 决策树方法的特点决策树方法的特点与与改进改进 目标变量在目标变量在数据集数据集样本与总体的分布不一样本与总体的分布不一致时如何处理？致时如何处理？