3.机器学习之决策树详解(2)|python教程|python入门|python教程

当前位置:

首页 > 编程开发 > python入门 >

python入门教程之3.机器学习之决策树详解(2)

本站最新发布 Python从入门到精通|Python基础教程
试听地址 https://www.xin3721.com/eschool/pythonxin3721/

2). 将节点2删掉替换成8、9和5，测试在验证集上的表现

3). 将节点3删掉替换成6和7，测试在验证集上的表现

REP剪枝方法决定是否修剪这个结点步骤如下：

1：删除以此结点为根的子树

2：使其成为叶子结点

3：赋予该结点关联的训练数据的最常见分类

4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点

REP是最简单的后剪枝方法之一，不过在数据量比较少的情况下，REP方法趋于过拟合而较少使用。这是因为训练数据集合中的特性在剪枝过程中被忽略，所以在验证数据集合比训练数据集合小的多时，要注意这个问题。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

2). Pessimistic Error Pruning(PEP，悲观剪枝）：

上文的REP方法思想简单且易于使用，不过最大的问题在于它需要一个新的验证集来修正我们的决策树。PEP方法也是根据剪枝前后的错误率来决定是否剪枝，和REP不同之处在于：PEP不需要新的验证集，而是完全使用训练数据来生成决策树，又用这些训练数据来完成剪枝，并且PEP是自上而下剪枝的。将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。由于我们还是用生成决策树时相同的训练样本，那么对于每个节点剪枝后的错分率一定是会上升的，因此在计算错分率时需要加一个惩罚因子0.5。PEP后剪枝技术是由大师Quinlan提出的。它不需要像REP(错误率降低修剪)样，需要用部分样本作为测试数据，。决策树生成和剪枝都使用训练集, 所以会产生错分。

PEP剪枝算法是在C4.5决策树算法中提出的，把一颗子树（具有多个叶子节点）用一个叶子节点来替代，比起REP剪枝法，它不需要一个单独的测试数据集。PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度,。两外PEP方法不需要分离训练集合和验证机和，对于数据量比较少的情况比较有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程中，树中的每颗子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。

# 详细原理待总结。

3). Cost-Complexity Pruning(CCP、代价复杂度)：

代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。CART就是采用CCP（代价复杂度）剪枝方法，CART剪枝分为剪枝成子树序列，并通过交叉验证选取最优子树。也就是说，CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二步是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

CCP算法为子树Tt定义了代价和复杂度，以及一个衡量代价与复杂度之间关系的参数α。代价指的是在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，α则表示剪枝后树的复杂度降低程度与代价间的关系，表面误差率增益值定义为：

其中，R(t)表示节点t的错误代价，R(t)=r(t)∗p(t)；r(t)表示节点t的错分样本率，p(t)表示节点t中样本占全部样本的比例，|N|表示子树Tt中的叶节点数。

从原始决策树生成各种剪枝效果的决策树的具体步骤：

1). 令决策树的非叶子节点为{T1，T2，T3，......，Tn}

2). 计算所有非叶子节点的表面误差率增益值α={α1，α2，α3，......，αn}

3). 选择表面误差率增益值αi最小的非叶子节点Ti（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）

4). 对Ti进行剪枝

实例：

假设数据有100条，从下往上，首先计算T5：

同理，T6 的α为0.03，由于0 < 0.03，此时将T5 剪枝而得到一颗新树。

CCP算法的实现步骤：

1）按照上述公式从下到上计算每一个非叶节点的α值，然后每一次都剪掉具有最小α值的子树。从而得到一个集合{T0，T1，T2，......，TM}，其中，T0 表示完整的决策树，TM 表示根节点

2）根据真实的错误率在集合{T0,T1,T2,...,TM}选出一个最好的决策树（交叉验证）

剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够保留最重要的属性划分，差别不大。反而是剪枝方法对于最优树的生成更为关键。C4.5使用了PEP剪枝方法，本文的CART使用了CCP的剪枝方法。

决策树算法总结：

决策树学习的关键就是如何选择最优划分属性。三种算法主要区别:CART构建的一定是二叉树,ID3,C4.5构建的不一定是二叉树。分类树是基于概率来构建的,采用信息增益、信息增益率、基尼系数来作为树的评价指标。回归数是基于平均值来构建的,采用均方差作为树的评价指标。

算法	支持模型	树结构	特征选择	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益比	支持	支持	支持
CART	分类，回归	二叉树	基尼系数，均方差	支持	支持	支持