机器学习决策树ppt

1、决策树决策树主讲人：王二主讲人：王二主要内容主要内容决策树基本概念决策树基本概念基本流程基本流程划分选择划分选择剪枝处理剪枝处理决策树基本概念决策树基本概念决策树决策树 决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中，决策树是最直观的一种。在机器学习中也是一种常用方法。 我们希望从给定的训练集中学得一个模型用来对新示例进行分类，这一分类过程称为“决策”过程。决策树是基于树结构进行决策的。基本流程基本流程构造过程： 决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则；采用自顶向下递归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性

2、值从该节点向下分支，而叶节点是要学习划分的类。从根节点到叶节点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。 例如：我们要对例如：我们要对“这是好瓜吗这是好瓜吗”这样的问题进行决策时，通常这样的问题进行决策时，通常会进行一系列的判断：我们先看会进行一系列的判断：我们先看“它是什么颜色它是什么颜色”，如果是，如果是“青青绿色绿色”再看再看“它的根蒂是什么形态它的根蒂是什么形态”，如果是，如果是“蜷缩蜷缩”，我们在判，我们在判断断“它敲起来是什么声音它敲起来是什么声音”，最后，我们得出最终的决策：这是，最后，我们得出最终的决策：这是个好瓜，这个过程如下：个好瓜，这个过程如下

3、：决策树的基本组成部分：决策结点、分支和叶子。决策树的基本组成部分：决策结点、分支和叶子。 决策树算法决策树算法目前已有多种决策树算法：目前已有多种决策树算法：clscls、id3id3、chaidchaid、c4.5c4.5、cartcart、sliqsliq、sprintsprint等。等。著名的著名的id3id3（iterative dichotomiser3iterative dichotomiser3）算法是）算法是j.r.quinlanj.r.quinlan在在19861986年提出的，该算法引入了信息论中的理论，年提出的，该算法引入了信息论中的理论，是基于信息是基于信息熵的决策树

4、分类算法熵的决策树分类算法。决策树决策树id3算法算法v id3算法的核心是：在决策树各级节点上选择属性时，用信息增益信息增益作为属性的选择标准，以使得在每一个非叶节点进行测试时能获得关于被测试记录最大的类别信息。v具体方法：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分枝，再对各分支的子集递归调用该方法建立决策树结点的分枝，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。 ent（d）的值越小，则d的纯度越高。 假定属性a有v个可能的取值a1 .av,若使用a来对样本集d进行划分，则会产生v个分支节点，其中第v个分支节点

5、包含了d中所有在属性a上取值为av的样本，记为dv。在考虑到不同的分支节点所包含的样本不同，给分支节点赋予权重dv/d,即样本数越多的分支节点的影响越大，于是计算出属性a对样本d进行划分所获得的“信息增益”（information gain）。一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度”（即分支节点所包含的样本尽可能属于同一类别）以下表的西瓜数据为例以下表的西瓜数据为例以属性“色泽”为例，它有三个可能取值青绿，乌黑，浅白，记为：d1=青绿，d2=乌黑，d3=浅白算算d1包含1，4，6,10,13,176个样例，其中正比例p1=3/6，反比例p2=3/6；d2包含2,3,

6、7,8,9，156个样例，其中正比例p1=4/6，反比例p2=2/6；d3包含5,11,12,14,165个样例，其中正比例p1=1/5，反比例p2=4/5。由此可计算出用“色泽”划分之后的三个分支节点的信息熵为于是可计算出属性“色泽”的信息增益为然后，决策树学习算法将对每个分支节点作进一步的划分。最终得到的决策树如下所示： 剪枝处理剪枝处理 剪枝（pruning）是决策树学习算法对付“过合”的主要手段，为了尽可能正确的分类训练样本，节点划分过程将不断重复，有时会造成决策树分支太多，这时就可能因训练样本学得“太好”了，以至于把训练集自身的一些特点当做所有数据的特点而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。 剪枝分为“预剪枝”和“后剪枝”。预剪枝是在决策树生成过程中，对每个节点在划分之前先进行估计，若当前节点的划分不能带来决策树的泛化性能的提升，则停止划