4.1 基本流程
决策树（decision tree）是基于树结构来进行决策的。
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略。

4.2 划分选择
一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。
4.2.1 信息增益
“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。信息熵的值越小，纯度越高。信息增益（information gain）越大，意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，可用信息增益来进行决策时速的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。
4.2.2 增益率
著名的C4.5决策树算法是使用“增益率”（gain ratio）来选择最优划分属性。增益率是信息增益与属性的“固有值”（intrinsic value）的比值。属性的可能取值数目越多，则固有值通常会越大。
增益率准则对可取值数目较少的属性有所偏好——先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
*4.2.3 基尼指数 *
CART决策树使用“基尼指数”（Gini index）来选择划分属性。基尼值反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此，基尼值越小，则数据集的纯度越高。——选择那个使得划分后基尼指数最小的属性作为最优划分属性。

4.3剪枝处理
剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。
决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（postpruning）。
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底而上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

4.4 连续与缺失值
4.4.1 连续值处理
由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。C4.5决策树算法中采用二分法（bi-partition）对连续属性进行处理。
需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
4.4.2 缺失值处理
给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
——让同一个样本以不同的概率划入到不同的子结点中去。