题目5.1
题目描述: 根据表(5.1)所给的训练数据集, 利用信息增益比 (C4.5算法)生成决策树
解答:
信息增益率的公式是:
首先回顾一下表(5.1)的结构：
表(5.1)
根据书上已经计算提供的数据, 我们有:
, ,
, ,
, ,
, ,
所以根据信息增益比的原则, 我们选择特征"有自己的房子"为切分点.
在左结点里, 所有"有自己的房子==是"的实例数据的类别均为"是", 所以左结点为叶结点, 结点类别为"是".
在右结点里, 我们首先整理出子数据集
:右结点 数据子集
所以在右结点选择特征"有工作", 以此切分后, 左右结点的实例数据子集都是单一类别的.
由此, 我们完成了根据信息增益比的C4.5决策树构造, 见下图.
C4.5算法 最终决策树 题目5.2
题目叙述: 己知如表 5.2 所示的训练数据，试用平方误差损失准则生成一棵二叉回归树
解答:
回归树的平方损失准则是: 选择一个切分点, 将训练数据集分为小于等于
和 大于 两个子集, 求这个2个子集的 平方损失之和作为衡量这个切分点好坏的衡量标准.我们用python代码帮助我们便捷快速地选择最优切分点:
import运行如上代码, 不断地对数据进行二叉切分后, 最终得到如下图的二叉回归决策树, 由于没有设置最小阈值, 所以我们是对每个点分到了叶结点.
最小平方损失: 回归树 题目5.3
题目叙述: 证明CART剪枝算法中, 当
确定时, 存在唯一的最小子树 使得损失函数 最小化解答:
采用反证法:
存在性易证, 在特征有限、数据集有限的情况下, 由于能生成的决策树数量有限, 每一棵都对应某一个
损失函数. 此之中一定存在一个最小的损失函数 .唯一性: 对于决策树生成算法生成原始数
，假设存在2棵不同的最小子树 和 使得损失函数 最小化.由于两棵子树不相同, 所以它们的剪枝方法
, 由于根据CART剪枝算法, 其中剪枝的每一步都使得损失函数 变低. 所以令 , 由 剪枝法生成的决策树为 . 那么就会有 以及 . 所以与假设 和 是使损失函数最小化的最小字数矛盾.由此, 得证.
题目5.4题目叙述: 证明CART剪枝算法中求出的子树序列
分别是区间 的最优子树 , 这里 ,解答:
首先我们需要回顾一下CART剪枝算法中, 我们对
中每一内部结点 都计算了:. 剪枝的过程即是在 中减去 第 小的 作为 , 同时将 设为 .
我们想要证明
是区间 的最优子树.首先
, 但是在剪枝序列 中这些结点已经被修剪掉了.而排序在后的结点
, 都有 , 所以当惩罚系数 时, 若对 进行剪枝将会造成损失函数 增长.由此, 得证
是 序列中的最优子树.欢迎大家指出不足或错误, 进行提问和讨论.