笔记心得

这一章学起来较为简单，也比较好理解。
4.1基本流程——介绍了决策树的一个基本的流程。叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。并且给出了决策树学习的基本算法。

上述算法递归返回的情形2和情形3不同之处：情形2是利用当前结点的后验分布，情形3则是把父结点的样本分布作为当前结点的先验分布。
4.2划分选择——对应决策树学习基本算法的第8步，选择最优划分属性，ID3决策树学习算法以信息增益为准则来选择划分属性，C4.5决策树算法使用增益率，CART决策树使用基尼指数来选择划分属性。
4.3剪枝处理——它是对付overfitting的主要手段，基本策略有预剪枝和后剪枝。
4.4连续与缺失值——连续属性离散化技术可以面对学习任务中遇到的连续属性，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。面对缺失值需要解决两个问题：1是如何在属性值缺失的情况下进行划分属性选择？2是给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
4.5多变量决策树——介绍了多变量决策树，一定程度上能简化决策树。

术语学习

决策树 decision tree
分而治之 divide-and-conquer
纯度 purity
信息熵 information entropy
信息增益 information gain
迭代二分器 Iterative Dichotomiser ID3算法中的ID
增益率 gain ratio
固有值 intrinsic value
CART Classification and Regression Tree
基尼指数 Gini index
剪枝 pruning
预剪枝 prepruning
后剪枝 postpruning
决策树桩 decision stump
二分法 bi-partition
轴平行 axis-parallel
多变量决策树 multivariate dicision tree
斜决策树 oblique decision tree
增量学习 incremental learning

课后习题

4.1 试证明对于不含冲突数据(即特征向量完全相同但标记不同)的训练集，必存在与训练集一致(即训练误差为 0) 的决策树。

回顾第1章和第2章定义

我们把"色泽" “根蒂” “敲声"作为三个坐标轴，则它们张成一个用于描述西瓜的三维空间，每个西瓜都可在这个空间中找到自己的坐标位置.由于空间中的每个点对应一个坐标向量，因此我们也把一个示例称为一个"特征向量” (feature vector).

这里关于示例结果的信息，例如"好瓜"，称为"标记" (labe1); 拥有了标记信息的示例，则称为"样例" (examp1e).

更一般地，我们把学习器的实际预测输出与样本的真实输出之间的差异称为"误差" (error),学习器在训练集上的误差称为"训练误差" (training error)或"经验误差" (empirical error) ，在新样本上的误差称为"泛化误差" (generalization
error).

结合上述决策树学习的基本算法，可以知道如果以每个西瓜的编号作为划分属性，那么得到的决策树桩就是与训练集一致的。

4.2 试析使用"最小训练误差"作为决策树划分选择准则的缺陷。

在上面的介绍中，我们有意忽略了表 4.1 中的"编号"这一列.若把"编号"也作为一个候选划分属性，则根据式4.2均可计算出它的信息增益为 0.998 ，远大于其他候选划分属性.这很容易理解："编号"将产生 17 个分支，每个分支结点仅包含一个样本，这些分支结点的纯度己达最大.然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测.

4.3 试编程实现基于信息熵进行划分选择的决策树算法，并为表 4.3 中数据生成一棵决策树。

待补充

4.4 试编程实现基于基尼指数进行划分选择的决策树算法，为表 4.2 中数据生成预剪枝、后剪枝决策树并与未剪枝决策树进行比较.

待补充

4.5 试编程实现基于对率回归进行划分选择的决策树算法，并为表 4.3 中数据生成一棵决策树.

待补充

4.6 试选择 4 个 UCI 数据集，对上述 3 种算法所产生的未剪枝、预剪枝、后剪枝决策树进行实验比较，并进行适当的统计显著性检验.

待补充

4.7 图 4.2 是一个递归算法，若面临巨量数据，则决策树的层数会很深，使用递归方法易导致"栈"溢出。试使用"队列"数据结构，以参数MaxDepth 控制树的最大深度，写出与图 4.2 等价、但不使用递归的决策树生成算法.

待补充

4.8 试将决策树生成的深度优先搜索过程修改为广度优先搜索，以参数MaxNode控制树的最大结点数，将题 4.7 中基于队列的决策树算法进行改写。对比题 4.7 中的算法，试析哪种方式更易于控制决策树所需存储不超出内存。

待补充

4.9 试将 4.4.2 节对缺失值的处理机制推广到基尼指数的计算中去.

使用式4.9,4.10,4.11，对照式4.5,4.6

$$\begin{gathered} Gini(D)=1-\sum _{k=1}^{|y|}{\tilde{p}}_k^2 \\ Gini\_index(D,a)=\rho \times Gini\_index(\tilde{D},a) \\ =\sum _{v=1}^V{\tilde{r}}_{v}Gini(D^v) \end{gathered}$$

4.10 从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集 3.0 上产生的结果

待补充