这一章学起来较为简单，也比较好理解。
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

回顾第1章和第2章定义

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

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

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

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

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

待补充

待补充

待补充

待补充

待补充

待补充

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

G i n i ( D ) = 1 − ∑ k = 1 ∣ y ∣ p ~ k 2 G i n i _ i n d e x ( D , a ) = ρ × G i n i _ i n d e x ( D ~ , a ) = ∑ v = 1 V r ~ v G i n i ( D v ) 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) Gini(D)=1−k=1∑∣y∣​p~​k2​Gini_index(D,a)=ρ×Gini_index(D~,a)=v=1∑V​r~v​Gini(Dv)

待补充