lecture4分类基本原理与决策树.ppt
分类:基本概念与决策树,Dr.Haitao XiongBTBU,分类:定义,给定多条记录的集合(数据集)每一条记录都通过元组(x,y)来表示，其中x是属性集，y 是记录类别分类的任务:通过学习得到一个分类模型，其将属性集 x 映射到某个类别 y,分类任务示例,构建分类模型的一般方法,分类技术,基本分类算法决策树方法：Decision Tree based Methods支持向量机：Support Vector Machines基于规则的方法：Rule-based Methods最近邻法：Nearest-neighbor神经网络：Neural Networks朴素贝叶斯：Nave Bayes集成学习算法Boosting,Bagging,Random Forests,决策树方法分类任务学习,决策树方法分类任务学习,否,训练集,分类模型：决策树,决策树方法分类任务学习,是否有房,否,否,划分属性,否,是,训练集,分类模型：决策树,决策树方法分类任务学习,是否有房,婚姻状况,是,否,否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,决策树方法分类任务学习,是否有房,婚姻状况,月收入,是,否,否,否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,8000,8000,决策树方法分类任务学习,是否有房,婚姻状况,月收入,是,否,否,否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,8000,8000,决策树方法分类任务学习,训练集,分类模型：决策树,婚姻状况,是否有房,月收入,是,否,否,对于一个数据集通过学习可以得到多个决策树,已婚,未婚、离异,是,否,8000,8000,决策树方法分类任务学习,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,划分属性,否,是,未婚、离异,已婚,训练集,分类模型：决策树,8000,8000,拖欠=是,决策树方法分类任务学习,训练集,分类模型：决策树,婚姻状况,是否有房,月收入,拖欠=是,拖欠=否,拖欠=否,对于一个数据集通过学习可以得到多个决策树,已婚,未婚、离异,是,否,8000,8000,决策树方法分类任务应用,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,决策树分类模型,否,是,未婚、离异,已婚,从树的根节点开始,测试集,8000,8000,拖欠=是,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,测试集,8000,8000,拖欠=是,决策树分类模型,将分类模型应用于测试集,是否有房,婚姻状况,月收入,拖欠=否,拖欠=否,拖欠=否,否,是,未婚、离异,已婚,是否拖欠贷款预测为“否”,测试集,8000,8000,拖欠=是,决策树分类模型,决策树方法分类任务学习,决策树归纳,算法:Hunt 算法(早期算法)CARTID3,C4.5SLIQ,SPRINT,Hunt 算法结构,设 Dt 是与结点t相关联的训练集一般处理过程:如果Dt 中所有记录都属于同一类别yt,则t是叶节点，用yt标记如果Dt 中包含属于多个类的记录,则选择一个属性，将记录划分成较小的子集.然后对于每个子女结点，递归的调用该算法.,Dt,?,Hunt 算法,决策树归纳的问题,如何划分训练样本?表示属性测试条件的方法 取决于属性类型：二元属性，标称属性，序数属性如何选择最佳划分的度量何时停止划分?分裂结点，直到所有的记录都属于同一类别提前终止,表示属性测试条件的方法,依赖于属性类别二元属性 Binary标称属性 Nominal序数属性 Ordinal连续属性 Continuous依赖于划分的数目二元划分 2-way split多路划分 Multi-way split,标称属性的属性测试条件,多路划分:输出数越多越好，取决于该属性不同属性值的个数.二元划分:将该属性的所有属性值划分为两个部分需要寻找最优划分.,序数属性的属性测试条件,多路划分:输出数越多越好，取决于该属性不同属性值的个数二元划分:将该属性的所有属性值划分为两个部分需要寻找最优划分不违背序数属性值的有序性,这种方式违背了序数属性值的有序性,连续属性的属性测试条件,连续属性划分,不同的处理方法通过离散化形成一个序数分类属性 静态方法 在一开始进行离散化 动态方法范围可以通过等深分箱,等比分箱,或聚类等方法二元方式:(A v)或者(A v)考虑所有的划分方式，并从中选择一个最优的 可以处理密集型计算,如何选择最优划分,划分前:10 条记录是类 0,10 条记录是类 1,哪一种测试条件是最优的?,贪婪方法:选择纯度更高的结点来进行划分需要表明划分后子女结点不纯性的度量:,高不纯性,低不纯性,如何选择最优划分,结点不纯性度量,Gini指标值Entropy熵Classification error 分类误差,寻找最优划分,计算划分前的不纯性度量值(P)计算划分后的不纯性度量值(M)计算每个子节点的不纯性度量计算子节点的平均不纯性度量(M)选择具有最大增益的属性作为属性测试条件也就是，具有划分后具有最小不纯性度量值的属性(M),Gain=P M,寻找最优划分,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,划分前:,Gain=P M1 vs P M2,不纯性度量:GINI,结点t的 Gini 指标值的计算公式如下:(注意:p(j|t)表示给的结点t中属于类别j的记录所占的比例).最大值(1-1/nc)：当各个样本等可能的属于各个类别,意味着蕴含最少信息最小值(0.0)：当所有记录都属于同一类别,意味着蕴含最多信息,计算单个结点的Gini指标值,P(C1)=0/6=0 P(C2)=6/6=1Gini=1 P(C1)2 P(C2)2=1 0 1=0,P(C1)=1/6 P(C2)=5/6Gini=1(1/6)2(5/6)2=0.278,P(C1)=2/6 P(C2)=4/6Gini=1(2/6)2(4/6)2=0.444,计算一组结点的Gini指标值,当结点p被划分为k个划分部分时(子结点)其中,ni=子结点i中的样本记录数目,n=父节点p中的样本记录数目.选择具有最小值的子结点加权平均Gini指标值的属性进行划分CART,SLIQ,SPRINT决策树算法使用GINI指标值来进行划分,二元属性:计算GINI指标值,划分为两个部分需要进行加权平均，是因为:寻求更大、更纯的划分.,B?,Yes,No,Node N1,Node N2,Gini(N1)=1(5/6)2(1/6)2=0.278 Gini(N2)=1(2/6)2(4/6)2=0.444,Gini(Children)=6/12*0.278+6/12*0.444=0.361,标称属性:计算Gini指标值,对于每一个属性值,计算数据集中每一个类别的样本数量使用计数矩阵进行决策,多路划分,二元划分(寻找最优划分),连续属性:计算Gini指标值,进行二元决策有多个划分点可供选择可能的划分点的数目=不同的属性值的数目每一个划分点都有一个计数矩阵与之关联每一个划分中不同类别样本的数目,A v 和 A v选择最优v的简单方法对于每一个候选v,扫描数据库获得计数矩阵并计算相应的 Gini 指标值缺点：计算效率低下!重复的工作.,连续属性:计算Gini指标值,更高效的计算方式:首先对某一属性值进行排序从两个相邻的排过序的属性值中选择中间值作为候选划分点，计算其Gini指标值重复这样的计算，直到算出所有后续的Gini指标值，最佳划分点对应于最小Gini指标值的点,排序后的值,不纯性度量:熵Entropy,结点t的熵Entropy的计算公式如下:(注意:p(j|t)表示给的结点t中属于类别j的记录所占的比例).最大值(log nc)：当各个样本等可能的属于各个类别,意味着蕴含最少信息最小值(0.0)：当所有记录都属于同一类别,意味着蕴含最多信息,计算单个结点的熵Entropy,P(C1)=0/6=0 P(C2)=6/6=1Entropy=0 log 0 1 log 1=0 0=0,P(C1)=1/6 P(C2)=5/6Entropy=(1/6)log2(1/6)(5/6)log2(1/6)=0.65,P(C1)=2/6 P(C2)=4/6Entropy=(2/6)log2(2/6)(4/6)log2(4/6)=0.92,计算划分后的信息增益,信息增益 Information Gain:父节点p被划分为k个划分部分;ni 是划分部分i中的记录数目最大化增益经典决策树算法ID3和C4.5都使用信息增益来进行划分,采用信息增益进行划分带来的问题,信息增益倾向于将样本记录划分为最大数量的部分，每一个部分中的样本的类别都是小而纯的：Customer ID 具有最高的信息增益，因为它的所有子结点的熵都是0,增益率 Gain Ratio,增益率:父节点p被划分为k个划分部分;ni 是划分部分i中的记录数目通过划分的熵调整信息增益(SplitINFO).高entropy的划分往往不是一个好的划分(划分的数量过多)在C4.5算法里被使用可克服信息增益的不足,不纯性度量:分类误差,结点t的分类误差不纯性度量计算公式如下:最大值(1-1/nc)：当各个样本等可能的属于各个类别,意味着蕴含最少信息最小值(0.0)：当所有记录都属于同一类别,意味着蕴含最多信息,计算单个结点的分类误差,P(C1)=0/6=0 P(C2)=6/6=1Error=1 max(0,1)=1 1=0,P(C1)=1/6 P(C2)=5/6Error=1 max(1/6,5/6)=1 5/6=1/6,P(C1)=2/6 P(C2)=4/6Error=1 max(2/6,4/6)=1 4/6=1/3,不纯性度量之间的比较,对于二元分类问题:,分类误差 vs Gini指标值,A?,Yes,No,Node N1,Node N2,Gini(N1)=1(3/3)2(0/3)2=0 Gini(N2)=1(4/7)2(3/7)2=0.489,Gini(Children)=3/10*0+7/10*0.489=0.342Gini improves but error remains the same!,基于决策树的分类方法,优点:构建决策树技术不需要昂贵的计算代价决策树一旦建立，未知样本分类非常快决策树相对容易理解，特别是小型的决策树对一些简单数据集来说，决策树算法拥有不差于其他复杂算法的精度,Example:C4.5,简单的深度优先构造原则.使用信息增益进行划分在每一个结点对连续属性进行排序.需要一次加载所有样本记录不适合处理大型数据.你可以从下面网址下载C4.5算法:http:/www.cse.unsw.edu.au/quinlan/c4.5r8.tar.gz,
