机器学习-决策树 -ppt

基本流程
构造过程：
决策树是以实例为基础的归纳学习算法。它从一组无次 序、无规则的元组中推理出决策树表示形式的分类规则； 采用自顶向下递归方式，在决策树的内部节点进行属性 值的比较，并根据不同的属性值从该节点向下分支，而 叶节点是要学习划分的类。从根节点到叶节点的一条路 径就对应着一条合取规则，整个决策树就对应着一组析 取表达式规则。
例如：我们要对“这是好瓜吗”这样的问题进行决策时，通常 会进行一系列的判断：我们先看“它是什么颜色”，如果是“青 绿色”再看“它的根蒂是什么形态”，如果是“蜷缩”，我们在判 断“它敲起来是什么声音”，最后，我们得出最终的决策：这是 个好瓜，这个过程如下：
决策树的基本组成部分：决策结点、分支和叶子。

ID3算法的核心是：在决策树各级节点上选择属 性时，用信息增益作为属性的选择标准，以使得 在每一个非叶节点进行测试时能获得关于被测试 记录最大的类别信息。 具体方法：检测所有的属性，选择信息增益最大 的属性产生决策树结点，由该属性的不同取值建 立分枝，再对各分支的子集递归调用该方法建立 决策树结点的分枝，直到所有子集仅包含同一类 别的数据为止，最后得到一棵决策树，它可以用 来对新的样本进行分类。
决策树
主讲人：王二
主要内容
决策树基本概念 基本流程 划分选择 剪枝处理
决策树基本概念
决策树
决策树是数据挖掘分类算法的一个重要方法。在各种分类算 法中，决策树是最直观的一种。在机器学习中也是一种常用方法。 我们希望从给定的训练集中学得一个模型用来对新示例进行 分类，这一分类过程称为“决策”过程。决策树是基于树结构进 行决策的。
由此可计算出用“色泽”划分之后的三个分支节点的信息熵为
于是可计算出属性“色泽”的信息增益为
然后，决策树学习算法将对每个分支节点作进一步 的划分。最终得到的决策树如下所示：
剪枝处理
剪枝（pruning）是决策树学习算法对付“过 合”的主要手段，为了尽可能正确的分类训练样 本，节点划分过程将不断重复，有时会造成决 策树分支太多，这时就可能因训练样本学得“太 好”了，以至于把训练集自身的一些特点当做所 有数据的特点而导致过拟合。因此，可通过主 动去掉一些分支来降低过拟合的风险。
一般而言，信息增益越大，则意味着使用属性a来进行划分所 获得的“纯度”（即分支节点所包含的样本尽可能属于同一类 别）
以下表的西瓜数据为例
以属性“色泽”为例，它有三个可能取值{青绿，乌 黑，浅白}，记为：D1==青绿，D2=乌黑，D3=浅白算 D1包含{1，4，6,10,13,17}6个样例，其中正比例 P1=3/6，反比例P2=3/6；D2包含{2,3,7,8,9，15}6个 样例，其中正比例P1=4/6，反比例P2=2/6；D3包含 {5,11,12,14,16}5个样例，其中正比例P1=1/5，反比 例P2=4/5。
剪枝分为“预剪枝”和“后剪枝”。预剪枝是在 决策树生成过程中，对每个节点在划分之前先 进行估计，若当前节点的划分不能带来决策树 的泛化性能的提升，则停止划分并将当前节点 标记为叶节点。
剪枝处理
后剪枝则是先生成一颗完整的决策树，然后 自底向上的对叶节点进行考察，若将该节点对 应的子树替换为叶节点能带来决策树泛化性能 的提升，则将该子树替换为叶节点。

Ent（D）的值越小，则D的纯度越高。
假定属性a有V个可能的取值{a1 ......av},若使用a来对样本 集D进行划分，则会产生V个分支节点，其中第V个分支节点包 含了D中所有在属性a上取值为av的样本，记为Dv。在考虑到 不同的分支节点所包含的样本不同，给分支节点赋予权重 Dv/D,即样本数越多的分支节点的影响越大，于是计算出属性 a对样本D进行划分所获得的“信息增益”（information gain）。
决策树算法
目前已有多种决策树算法：CLS、ID3、CHAID、C4.5、 CART、 SLIQ、SPRINT等。 著名的ID3（Iterative Dichotomiser3）算法是 J.R.Quinlan在1986 年提出的，该算法引入了信息论中的理论，是基于信息 熵的决策树分类算法。
ቤተ መጻሕፍቲ ባይዱ
决策树ID3算法