《机器学习》章节学习报告——决策树学习

2014年11月12日姓名：学号：专业：2014应用统计教师：《机器学习》课程章节学习报告1——决策树学习2/17目录一、决策树原理分析.......................................................................................................31．ID3算法...........................................................................................................................32．C4.5算法.........................................................................................................................43．CART算法........................................................................................................................5CART树的分支过程.........................................................................................................5CART树的剪枝过程.........................................................................................................6最优CART树的选择.......................................................................................................7CART算法的优缺点..........................................................................................................8二、优秀论文研究分析.................................................................................................81．参考文献简介..................................................................................................................82．论文的研究背景及意义..................................................................................................83．CART算法在电信业潜在客户识别模型的实证分析....................................................9三、实战演练...................................................................................................................101．数据集来源....................................................................................................................102．数据集解释....................................................................................................................113．程序演示........................................................................................................................12程序附录..............................................................................................................................173/17一、决策树原理分析决策树(DecisionTree)是一种根据提供的不同特征，以树型结构表示分类或决策集合，从而产生规则和发现发展规律的机器学习方法。决策树起源于概念学习系统CLS(ConceptLearningSystem)，其大体框架都是采用贪心方法以自顶向下递归的方式构造决策树，思路是找出最有分辨能力的属性把数据库划分为多个子集(对应树的一个分枝)，构成一个分枝过程，然后对每一个子集递归调用分枝过程，直到所有子集包含同一类型的数据,最后得到的决策树能对新的例子进行分类。根据分类准则的不同，目前决策树算法可以分为两类：基于信息论的方法和最小GINI指数方法。其中基于信息论的方法又包括ID系列算法、C4.5算法等，最小GINI指数方法包括CART、SLIQ和SPRINT算法。为更好地学习，本文在算法上分别介绍了ID3算法、C4.5算法和CART算法以进行比较分析，而在具体实例分析和程序演示部分，将以CART算法作为本文的重点介绍对象。1．ID3算法ID3算法是1986年由Quinlan提出的一种基于信息熵的决策树学习算法，他把Shannon的信息论引入到了决策树算法中，把信息熵作为选择测试属性的标准，对训练集进行分类，并构造决策树来预测如何由测试属性对整个实例空间进行划分。信息熵的概念为：设某事物具有n种相互独立的可能结果(或称状态)：12,,,nxxx，每一种结果出现的概率分别为)(),(),(21nxpxpxp，且有1)(1niixp，则Shannon信息公式为：niiinnxpxpxIxpxIxpxIxpxH122211)(log)()()()()()()()(。设训练数据集nDDDD21是n维有穷向量空间，其中jD是有穷离散符号集，D中的每个元素nttd,,1叫做例子，其中njDtjj,,2,1,。设训练数据集D一共有m个不同类),,1(miCi，每类样例数为),,2,1(misi，4/17设is是类iC中的样本数，ip是任意样本属于iC的概率，并用||Dsi估计。以属性A作为决策树的根，A具有v个值vvvv,,21，它将D分为v个子集veee,,,21，设irs是子集re中类iC的样本数，则子集re中任意元祖属于类iC的概率用irp表示，并用||rires估计，那么该子集re的期望信息是),,,(21mrrrsssI，以属性A为根分类后所需的信息期望可以用下式计算：),,,(||||)(211mrrrvrrsssIDeAE，其中miirirmrrrppsssI1221)(log),,,(，则以A为根的信息增益为：)(),,,()(21AEsssIAgainm。ID3算法即选择使)(Again最大的属性*A作为根节点，对*A的不同取值对应的v个子集递归调用上述过程生成*A的子节点vBBB,,,21。ID3算法利用了信息增益的概念，使得算法较为简单，而且建树时间是例子个数、特征个数、结点个数之积的线性函数，计算量相对较小。但它同时也存在着对信息增益的计算依赖于属性取值数目较多的特征，而属性取值较多的属性不一定最优；对特征间的相关性强调不多；对噪声较为敏感等问题。2．C4.5算法C4.5是由Quinlan自己扩充ID3算法提出来的，是ID3算法的改进，提高了算法的效率。与ID3不同，C4.5采用基于信息增益率的方法选择测试属性，信息增益率等于信息增益对分割信息量的比值，即),,,()(),,,()(2121mmsssIAEsssIAGainRatio，从而克服了用信息增益选择属性时偏向选择值多的属性的不足。同时C4.5算法在ID3的基础上增加了对连续属性，属性值空缺情况的处理，对树剪枝也有了较成熟的方法。但C4.5在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效；而且C4.5只适合于能够驻留在内部的数据集使用，当训练集大得无法在内存容纳时程序无5/17法运行。3．CART算法CART(ClassificationandRegressionTrees）算法是由几位统计学家L.Breiman，J.Friedman，R.Olshen和C.Stone在发表的刊物《分类与回归树》中提出的一种产生二叉决策树分类模型的技术。CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。分类树的两个基本思想：第一个是将训练样本进行递归地划分自变量空间进行建树的想法，第二个想法是用验证数据进行剪枝。CART算法与Quinlan提出的ID3算法和C4.5不同的是，使用的属性度量标准是Gini指标。Gini指标主要是度量数据划分或训练数据集D的不纯度为主，系数值的属性作为测试属性，Gini值越小，表明样本的“纯净度”越高（即该样本只属于同一个类的概率越高）。CART树的分支过程CART算法在对一个节点进行分支时首先要确定一个最佳的分支预测变量以及该预测变量的最佳分支阀值点。然后将性质相同的对象分在同一个节点中，并且同一个父节点的两个子节点间具有显著的差异性。CART算法选择指标的方法是使用“杂质函数”，当节点中数据都属于同一个类时，杂质函数值为0，当节点中的对象均匀分布于所有可能的类时，杂质函数值最大。节点的杂质函数定义如下：0)1,,0,0()0,,1,0()0,,0,1(max)/1,,/1,/1(1),,,,()(21121JJJppppppptEttt其中jp是节点t（包括根节点）中对象j类的概率。类似地，树T的杂质函数是树中包含的各个叶节点杂质函数的加权平均值，即)()(1inkttENNTE，这里n是树T中的叶节点个数，tN是叶节点i中的对象个数，N是所有叶节点中对象的总数或根节点中对象的数量，)(itE是叶节点i中的杂质函数值。CART算法中最常6/17使用的杂质函数是GINI系数，其公式如下：Jjjjijijpppppp122112),,,(因为对所有的j,11Jjjp，并且10jp，所以GINI系数总为正数，除非其中的一个jp为1，而其它均为0。此外，对于所有j,当Jpj/1时，这个函数达到最大值。对于一个节点，其分支前后的杂质应该减少的最多，也就是说分支后数据的纯度应该比分支前提高的很多。其中杂质的改变量为：)()()(),(rrlltEptEptEtsE这里t是父节点；)(tE是父节点t杂质函数值；)(ltE和)(rtE分别是分支后左右两个子节点的杂质函数值；而lp和rp分别是分支后左右两个子节点中包含的对象百分比。大括号中的式子是左右两个子节点的杂质函数值的加权值，也是以节点t为根节点的子树的杂质函数值。只有当子树的杂质含量少于树根的杂质含量时，进一步的分支才是有意义的。树停止分支的时候有以下几种情况：分枝后的叶节点中的样本数小于给定的阀值；分枝后的叶节