通用的决策树算法CART课件.ppt

《通用的决策树算法CART课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ch10.决策树特征类型数值数据（numericaldata）例：{1.2,4.5,3.3}模式间可以计算距离度量基于度量的模式分类方法标称数据（nominaldata）例：{红色，有光泽，甜，小}模式间没有距离的概念非度量方法决策树什么是决策树？决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别决策树的构成根节点（root）分支（branch）叶节点（leaf）决策树决策树决策树分类过程从根节点开始，首先对某一属性的取值提问Color?与根节点相连的不同分支，对应这个属性的不同取值gree

2、n;yellow;red;根据不同的回答，转向相应的分支green在新到达的节点处做同样的分支判断Size?–big.这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记Watermelon决策树决策树的判决面决策树决策树的优势语义可表示性从根节点到叶节点表示为合取式（颜色=黄）AND（形状=细长）香蕉利用合取式和析取式获得某个类别的明确描述苹果=（绿色AND中等大小）OR（红色AND中等大小）分类速度快只需一系列简单查询即可对模式的类别做出判断可以很自然的嵌入专家的先验知识决策树学习算法决策树研究历史第一个决策树算法称为CLS(ConceptLearningSy

3、stem)[E.B.Hunt,J.Marin,andP.T.Stone’sbook“ExperimentsinInduction”publishedbyAcademicPressin1966]真正引发决策树研究热潮的算法是ID3[J.R.Quinlan’spaperinabook“ExpertSystemsintheMicroElectronicAge”editedbyD.Michie,publishedbyEdinburghUniversityPressin1979]最流行的决策树算法C4.5[J.R.Quinlan’sbook“C4.5:ProgramsforMa

4、chineLearning”publishedbyMorganKaufmannin1993]决策树学习算法决策树研究历史通用的决策树算法CART(ClassificationandRegressionTree)[L.Breiman,J.H.Friedman,R.A.Olshen,andC.J.Stone’sbook“ClassificationandRegressionTrees”publishedbyWadsworthin1984]基于决策树的集成学习算法：随机森林(RandomForests)[L.Breiman’sMLJ’01paper“RandomForest

5、s”]构造决策树基本过程从上到下，分而治之（divide-and-conquer），递归生长最初，所有的样本都在根节点所有属性都是标称型的（如果是连续数值型的，则需要预先离散化）所有样本根据每次选择出的属性递归的逐渐划分开来选择出来的属性称为一个划分（split）或测试（test）或查询（query）查询的选择基于启发式或者统计特征构造决策树基本过程满足如下条件之一时，划分操作停止所有落入某一节点的样本均属于同一类别该节点成为叶节点，标记为该类别没有特征能够进一步用于划分样本集该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别没有任何样本落入某一节点该节点成

6、为叶节点，类别标签为落入父节点的多数样本所属的类别CART分类和回归树（ClassificationAndRegressionTree,CART)CART为通用的树生长算法框架，涉及如下问题：属性的值是二值的还是多值的？即节点可以有几个分支？如何确定某节点处应该测试哪个属性？何时令某个节点为叶节点？如果树生长的过大，如何使其变小变简单，即如何剪枝？如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别标记？分支数目同一个节点分出去的分支的数目称为分支系数或分支率（branchingratio）任意决策树都可以用分支系数为2的决策树（即二叉树）来表示二叉树是最常用的决

7、策树形式分支数目分支数目测试的选取决策树设计的核心问题之一基本思想：使后继结点的数据尽可能的“纯粹”节点N的不纯度（impurity）i(N)当N节点上的所有模式都来自同一类时，i(N)=0；当N节点上的模式类别分布均匀时，i(N)应很大测试的选取常用不纯度度量熵不纯度（entropyimpurity）Gini不纯度误分类不纯度测试的选取常用不纯度度量测试的选取对N节点如何选择查询？使不纯度下降最快的那个查询！和分别为左、右子节点和分别为左、右子节点的不纯度是N节点的模式划分到的比例如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的信息增益（in