搜索
决策树主讲人：王二主要内容决策树基本概念基本流程划分选择剪枝处理决策树基本概念决策树决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中，决策树是最直观的一种。在机器学习中也是一种常用方法。我们希望从给定的训练集中学得一个模型用来对新示例进行分类，这一分类过程称为“决策”过程。决策树是基于树结构进行决策的。基本流程构造过程：决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则；采用自顶向下递归方式，在决策树的内部节点进行属性值的比较，并根据不同的属性值从该节点向下分支，而叶节点是要学习划分的类。从根节点到叶节点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。例如：我们要对“这是好瓜吗”这样的问题进行决策时，通常会进行一系列的判断：我们先看“它是什么颜色”，如果是“青绿色”再看“它的根蒂是什么形态”，如果是“蜷缩”，我们在判断“它敲起来是什么声音”，最后，我们得出最终的决策：这是个好瓜，这个过程如下：决策树的基本组成部分：决策结点、分支和叶子。决策树算法目前已有多种决策树算法：CLS、ID3、CHAID、C4.5、CART、SLIQ、SPRINT等。著名的ID3（IterativeDichotomiser3）算法是J.R.Quinlan在1986年提出的，该算法引入了信息论中的理论，是基于信息熵的决策树分类算法。决策树ID3算法，最后得到一棵决策树，它可以用来对新的样本进行分类。ID3算法的核心是：在决策树各级节点上选择属性时，用信息增益作为属性的选择标准，以使得在每一个非叶节点进行测试时能获得关于被测试记录最大的类别信息。具体方法：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分枝，再对各分支的子集递归调用该方法建立决策树结点的分枝，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。Ent（D）的值越小，则D的纯度越高。假定属性a有V个可能的取值{a1......av},若使用a来对样本集D进行划分，则会产生V个分支节点，其中第V个分支节点包含了D中所有在属性a上取值为av的样本，记为Dv。在考虑到不同的分支节点所包含的样本不同，给分支节点赋予权重Dv/D,即样本数越多的分支节点的影响越大，于是计算出属性a对样本D进行划分所获得的“信息增益”（informationgain）。一般而言，信息增益越大，则意味着使用属性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。由此可计算出用“色泽”划分之后的三个分支节点的信息熵为于是可计算出属性“色泽”的信息增益为然后，决策树学习算法将对每个分支节点作进一步的划分。最终得到的决策树如下所示：剪枝处理剪枝（pruning）是决策树学习算法对付“过合”的主要手段，为了尽可能正确的分类训练样本，节点划分过程将不断重复，有时会造成决策树分支太多，这时就可能因训练样本学得“太好”了，以至于把训练集自身的一些特点当做所有数据的特点而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。剪枝分为“预剪枝”和“后剪枝”。预剪枝是在决策树生成过程中，对每个节点在划分之前先进行估计，若当前节点的划分不能带来决策树的泛化性能的提升，则停止划分并将当前节点标记为叶节点。剪枝处理后剪枝则是先生成一颗完整的决策树，然后自底向上的对叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。