分类与决策树

分类与预测Vicky银行个人住房贷款审批

银行个人客户提出住房贷款申请，根据历史数据发现：部分贷款客户不能按时还款。为尽量降低这种现象，需要发现不能按时还款客户的特征，以便对以后住房贷款申请的审批提供依据。2006年年底，由SAS机构与招商银行启动了全行个人住房贷款评分卡开发与推广项目。该项目利用客户的历史数据构建评分卡模型，然后将该模型应用到新客户上，最后决定是否接受新客户的贷款申请。分析数据集应该包括哪些客户？银行贷款申请

IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo分类与预测分类：目标变量为非数值型预测：目标变量为数值型根据历史数据集（已知目标变量），构建模型描述目标变量与输入变量之间的关系，并依据模型来分类或预测新数据（目标变量值未知)。分类模型也称为分类器。模型应用建模规则1：Ifrefund=noandmarst=marriedthencheat=no……模型评估分类的过程数据集分区训练集：建立模型验证集：调整和选择模型测试集：评估模型的预测能力建立模型评估并选择模型运用模型

新数据（打分集）思考：分类模型在什么情况下不适合用于新数据？分类方法决策树方法贝叶斯分类法LOGISTIC回归神经网络方法K近邻分类法SVM分类法……….RootLeafNode7决策树(decisiontree)规则1：Ifrefund=noand(marst=singleormarst=divorced)andtaxincome>80kthencheat=yes……决策树是一棵二叉或多叉树结构每个内部节点代表一个属性，该节点的分支表示根据该属性的不同测试条件的输出叶子节点表示一个类标决策树一般是自上而下生成的决策树基本思想建立决策树将决策树转换为决策规则并应用相关问题讨论内容一、决策树思想将数据集根据某种测试条件分为2个或多个子集，使分裂后的子集在目标变量上具有更纯的分类纯度与混杂度混杂度的的常用测测度指标标信息熵（Entropy）基尼指数数（GiniIndex）分类误差差（classificationerror)Pj是数据集集合中类类别j的相对比比例.entropy=12信息熵（Entropy）什么情况况下，熵熵最小？？什么情况况下，熵熵最大？？entropy=-1log21-0log20=0目标变量量为二元元变量：：entropy=-0.5log20.5––0.5log20.5=1IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款款数据集集银行贷款款案例数数据集的的熵：Entropy(T)=−6/15*log2(6/15)−−9/15*log2(9/15)=0.971Gini指数Pj是数据集集合中类类别j的相对比比例.GINI最大=？GINI最小=？1-1/2（目标变变量为二二元变量量）0IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款款数据集集银行贷款款案例数数据集的基尼指数数：gini=1-(6/15)2-(9/15)2=0.48分类误差（（classificationerror)CE最大=？CE最小=？1-1/2（目标变量为二元变量）

0IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo银行贷款数数据集银行贷款案案例数据集集的分类误差差：CE=1-9/15=6/15=0.4二、建立决策树常用算法ID3-ID5,C4,C4.5,C5.0CART（ClassificationandRegressionTrees分类与回归归树)（C&RT）CHAID(chi-squaredautomaticinteractiondetection，卡方自动动交互检测测)二叉GINI指数二叉或多叉叉信息息熵二叉或多叉叉建立决策树树的生长分裂属性及及其条件的的选择何时结束分分裂树的选择1.裂分目标与与属性选择择裂分目标使分裂后数数据子集的的纯度比裂分前数数据集的纯纯度最大限度的的提高；即不同类类别的观测测尽量分散散在不同的的子集中。。指标信息增益与与信息增益益率GINI指数的下降降二分指数卡方检验C-SEP、…信息增益InformationGain=裂分前数据据集的熵–裂分后各子子数据集的的熵加权和和其中：权重为每个个子集中的的观测数在在裂分前总总观测数中中所占的比比例案例数据集集基于own_home属性划分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo案例数据集集基于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裂分前数据据集的熵：：Entropy(T0)=−−6/15*log2(6/15)−9/15*log2(9/15)=0.971案例数据集集基于age属性划分IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo案例数据集集基于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信息增益Gain(age)=0.971-0.888=0.083AgeYoungMiddleOldYes:2No:3Yes：3No:2No:1Yes:4案例数据集集基于其它它属性划分分根据hasjob和credit划分后的熵熵分别为EntropyHas_job(T)=0.647EntropyCredit(T)=0.608信息增益分分别为：Gain(hasjob)=0.324Gain(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_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNoOwn_homeYesNoNo:6Yes:3Yes:6No:0has_jobYesNoYes:3No:0No:6Yes:0IDAgeHas_jobOwn_homeCreditClass1YoungNoNoFairNo2YoungNoNoGoodNo3YoungYesNoGoodYes4YoungYesYesFairYes5YoungNoNoFairNo6MiddleNoNoFairNo7MiddleNoNoGoodNo8MiddleYesYesGoodYes9MiddleNoYesExcellentYes10MiddleNoYesExcellentYes11OldNoYesExcellentYes12OldNoYesGoodYes13OldYesNoGoodYes14OldYesNoExcellentYes15OldNoNoFairNo信息增益方方法偏向选选择具有大大量取值的的属性信息增益率率假设按照属属性S来划分T，设S有m个值，根据据该属性的的取值将数数据集T划分成m个子集{T1，T2，…Tm}，设Tj的数据个数数是tj。信息增益益率可以通通过如下公公式计算得得到：其中，如如前前面所定义义，的的定义为为信息增益率率：案例数数据集基于于ownhome属性划分信息增益Gain(ownhome)=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:3GINI指数的下降降GINI指数的下降=裂分前数据集集的GINI指数–裂分后各子子数据集的GINI指数加权和其中：权重为每每个子集中中的观测数数在裂分前前总观测数数中所占的的比例二分指数划划分对于在属性性s的划分t，二分指数数的改进量量为：（j表示目标变变量的取值值）产生两个子子节点间最最大差异的的属性s被选择。卡方检验划划分计算每个裂裂分的卡方方值选择卡方检检验最显著著的变量及及其裂分分分支选择裂分属属性及其裂裂分条件测试每个属属性及其可可能的裂分分条件，计计算裂分指指标，选择择最佳者。。注意：对取值范围围比较大的的类别属性性，可考虑虑分组泛化化对有序类别别属性，划划分不能改改变其顺序序性对数值型属属性，理论论上需要测测试各种可可能的划分分条件，实实际上可以以进行优化测试。也可以进进行离散化化处理。34排序类标号改变变的临界点点中间值作作为候选划划分阈值PersonHairLengthWeightAgeClass

Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”20045M35PersonHairLengthWeightAgeClassMaggie4”201FLisa6”788FBart2”9010MMarge10”15034FSelma8”16041FAbe1”17070MOtto10”18038MKrusty6”20045MHomer0”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.9911–(5/9*0.7219+4/9*0)=0.5900372.裂分停止条条件每个叶子节节点都属于于同一个类类别；有可能得到到一个非常常大的树，，某些叶子子节点只包包含很少的的观测。节点包含的的观测个数数小于某个个指定值；；裂分的目标标指标（例例如：信息息增益、信信息增益率率）非常小小；树的深度达达到了预先先指定的最最大值。预剪枝383.树的选择分类模型的的优劣一般般情况下可可根据分类类的准确度度（或分类类误差）来来判断。训练误差：：在训练集集上的误差差泛化误差：：在非训练练集上的期期望误差在验证数据据集上的预预测误差是是泛化误差差的无偏估估计。过拟合好的分类模模型：低训练误差差低泛化误差差拟合不足：：较高训练误误差较高泛化误误差过拟合：低训练误差差较高泛化误误差过拟合过拟合处理理策略--剪枝–给树剪枝就就是剪掉““弱枝”（（指的是在在验证数据据上误分类类率高的树树枝）。–为树剪枝会会增加训练练数据上的的错误分类类率，但精精简的树会会提高新数数据上的预预测能力。。决策树剪枝枝预剪枝（提提前终止裂裂分）在树没有完完全扩张之之前就停止止树的生长长，即不要要求每个叶叶子节点内内的每一个个属性值都都相同，或或者属于同同一类别。。后剪枝用新的叶子子节点（类类标号为多多数类）代代替子树；；用子树中最最常用的分分枝代替子子树；后剪枝训练集：验证集：训练后得到到的决策树树：colorx2…classred……successblue……failureblue……failurecolorx2…classred……failurered……failurered……failureblue……successfailure验证集误差差：41最小误差树树与最佳剪剪枝树三、产生分分类规则并并应用对从根到叶叶节点的每每一条路径径创建一条条规则：沿着给定路路径上的每每个划分用用逻辑AND形成分类规规则的IF部分，对应应叶节点的的类别形成成THEN部分。例如：R1：IFOwn_home=yesTHENClass=yesR2：IFOwn_home=NoANDHas_job=YesTHENClass=YesR3：IFOwn_home=NoANDHas_job=NoTHENClass=NoOwn_homeYesNoNo:6Yes:3Yes:6No:0has_jobYesNoYes:3No:0No:6Yes:0规则的覆盖盖率准确率四、问题讨讨论缺失值问题题决策树叶子子节点的准准确含义决策树方法法的特点与与改进目标变量在在数据集样样本与总体体的分布不不一致时如如何处理？？变量值缺失失问题训练集中的的输入变量量值缺失新数据中裂分分变量值缺失使用代理划划分假定X*是节点t的最佳划分分s*的裂分变量，代理划分分s（划分效果最接近近s*）使用另外外一个输入入变量X。如果要预测测的新记录录在X*上有缺失值值而在X变量上没有有缺失值，则预测将将使用代理理划分s。问题讨论缺失值问题题决策树叶子子节点的准准确含义决策树方法法的特点与与改进目标变量在在数据集样样本与总体体的分布不不一致时如如何处理？？决策树叶子子节点的准准确含义PersonHairLengthWeightAgeClass

Homer0”25036MMarge10”15034FBart2”9010MLisa6”788FMaggie4”201FAbe1”17070MSelma8”16041FOtto10”18038MKrusty6”2004