分类与决策树.ppt

分类与预测,Vicky,银行个人住房贷款审批,银行个人客户提出住房贷款申请，根据历史数据发现：部分贷款客户不能按时还款。为尽量降低这种现象，需要发现不能按时还款客户的特征，以便对以后住房贷款申请的审批提供依据。2006年年底，由SAS机构与招商银行启动了全行个人住房贷款评分卡开发与推广项目。该项目利用客户的历史数据构建评分卡模型，然后将该模型应用到新客户上，最后决定是否接受新客户的贷款申请。,分析数据集应该包括哪些客户？,银行贷款申请,分类与预测,分类：目标变量为非数值型预测：目标变量为数值型根据历史数据集（已知目标变量），构建模型描述目标变量与输入变量之间的关系，并依据模型来分类或预测新数据（目标变量值未知)。分类模型也称为分类器。,模型评估,分类的过程,数据集分区训练集：建立模型验证集：调整和选择模型测试集：评估模型的预测能力建立模型评估并选择模型运用模型新数据（打分集）,思考：分类模型在什么情况下不适合用于新数据？,分类方法,决策树方法贝叶斯分类法LOGISTIC回归神经网络方法K近邻分类法SVM分类法.,Root,Leaf,Node,7,决策树(decisiontree),规则1：Ifrefund=noand(marst=singleormarst=divorced)andtaxincome80kthencheat=yes,决策树,是一棵二叉或多叉树结构每个内部节点代表一个属性，该节点的分支表示根据该属性的不同测试条件的输出叶子节点表示一个类标决策树一般是自上而下生成的,决策树基本思想建立决策树将决策树转换为决策规则并应用相关问题讨论,内容,一、决策树思想,将数据集根据某种测试条件分为2个或多个子集，使分裂后的子集在目标变量上具有更纯的分类纯度与混杂度,混杂度的常用测度指标,信息熵（Entropy）基尼指数（GiniIndex）分类误差（classificationerror),Pj是数据集合中类别j的相对比例.entropy=,12,信息熵（Entropy）,什么情况下，熵最小？什么情况下，熵最大？,entropy=-1log21-0log20=0目标变量为二元变量：entropy=-0.5log20.50.5log20.5=1,银行贷款数据集,银行贷款案例数据集的熵：Entropy(T)=6/15*log2(6/15)9/15*log2(9/15)=0.971,Gini指数,Pj是数据集合中类别j的相对比例.,GINI最大=？GINI最小=？,1-1/2（目标变量为二元变量）0,银行贷款数据集,银行贷款案例数据集的基尼指数：gini=1-(6/15)2-(9/15)2=0.48,分类误差（classificationerror),银行贷款数据集,银行贷款案例数据集的分类误差：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属性划分,案例数据集基于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.42,裂分前数据集的熵：Entropy(T0)=6/15*log2(6/15)9/15*log2(9/15)=0.971,案例数据集基于age属性划分,案例数据集基于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.083,案例数据集基于其它属性划分,根据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.083,信息增益方法偏向选择具有大量取值的属性,信息增益率,假设按照属性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.433,GINI指数的下降,GINI指数的下降=裂分前数据集的GINI指数裂分后各子数据集的GINI指数加权和其中：权重为每个子集中的观测数在裂分前总观测数中所占的比例,二分指数划分,对于在属性s的划分t，二分指数的改进量为：（j表示目标变量的取值）产生两个子节点间最大差异的属性s被选择。,卡方检验划分,计算每个裂分的卡方值选择卡方检验最显著的变量及其裂分分支,选择裂分属性及其裂分条件,测试每个属性及其可能的裂分条件，计算裂分指标，选择最佳者。注意：对取值范围比较大的类别属性，可考虑分组泛化对有序类别属性，划分不能改变其顺序性对数值型属性，理论上需要测试各种可能的划分条件，实际上可以进行优化测试。也可以进行离散化处理。,34,排序类标号改变的临界点中间值作为候选划分阈值,35,划分前：Entropy(4F,5M)=-(4/9)log2(4/9)-(5/9)log2(5/9)=0.9911,Entropy(4F,1M)=-(4/5)log2(4/5)-(1/5)log2(1/5)=0.7219,Entropy(0F,4M)=-(0/4)log2(0/4)-(4/4)log2(4/4)=0,Gain(Weight=165)=0.9911(5/9*0.7219+4/9*0)=0.5900,37,2.裂分停止条件,每个叶子节点都属于同一个类别；有可能得到一个非常大的树，某些叶子节点只包含很少的观测。节点包含的观测个数小于某个指定值；裂分的目标指标（例如：信息增益、信息增益率）非常小；树的深度达到了预先指定的最大值。预剪枝,38,3.树的选择,分类模型的优劣一般情况下可根据分类的准确度（或分类误差）来判断。训练误差：在训练集上的误差泛化误差：在非训练集上的期望误差在验证数据集上的预测误差是泛化误差的无偏估计。,过拟合,好的分类模型：低训练误差低泛化误差拟合不足：较高训练误差较高泛化误差过拟合：低训练误差较高泛化误差,过拟合,过拟合处理策略-剪枝,给树剪枝就是剪掉“弱枝”（指的是在验证数据上误分类率高的树枝）。为树剪枝会增加训练数据上的错误分类率，但精简的树会提高新数据上的预测能力。,决策树剪枝,预剪枝（提前终止裂分）在树没有完全扩张之前就停止树的生长，即不要求每个叶子节点内的每一个属性值都相同，或者属于同一类别。后剪枝用新的叶子节点（类标号为多数类）代替子树；用子树中最常用的分枝代替子树；,后剪枝,训练集：验证集：训练后得到的决策树：,验证集误差：41,最小误差树与最佳剪枝树,三、产生分类规则并应用,对从根到叶节点的每一条路径创建一条规则：沿着给定路径上的每个划分用逻辑AND形成分类规则的IF部分，对应叶节点的类别形成THEN部分。例如：R1：IFOwn_home=yesTHENClass=yesR2：IFOwn_home=NoANDHas_job=YesTHENClass=YesR3：IFOwn_home=NoANDHas_job=NoTHENClass=No,规则的覆盖率准确率,四、问题讨论,缺失值问题决策树叶子节点的准确含义决策树方法的特点与改进目标变量在数据集样本与总体的分布不一致时如何处理？,变量值缺失问题,训练集中的输入变量值缺失新数据中裂分变量值缺失使用代理划分假定X*是节点t的最佳划分s*的裂分变量，代理划分s（划分效果最接近s*）使用另外一个输入变量X。如果要预测的新记录在X*上有缺失值而在X变量上没有缺失值，则预测将使用代理划分s。,问题讨论,缺失值问题决策树叶子节点的准确含义决策树方法的特点与改进目标变量在数据集样本与总体的分布不一致时如何处理？,决策树叶子节点的准确含义,P(class=M)=100%,P(class=F)=80%,问题讨论,缺失值问题决策树叶子节点的准确含义决策树方法的特点与改进目标变量在数据集样本与总体的分布不一致时如何处理？,决策树分类方法的特点,优点：1)可以生成容易理解的规则；2)计算量相对来说不是很大；3)可以处理连续和离散变量；4)可以清晰的显示哪些变量比较重要。5）对输入变量的缺失值、噪声、冗余属性不敏感缺点：1)对数值型变量需要进行离散化或候选划分较多；2)模型稳定性受数据影响较大；3)一般的算法一次只能根据一个变量来裂分,单属性裂分VS多属性裂分,决策树方法改进,提高算法可伸缩性RainForest（雨林）算法在每个节点，对每个属性维护一个AVC（属性-值，类标号及其计数）集，将其存于内存中。,决策树方法改进,自助乐观算法可视化挖掘基于感知的分类(