「决策树」是一种树形分类模型，利用若干个属性变量进行逐步决策，最后输出数据分类结果。训练时，首先对数据进行处理，然后利用归纳算法生成可读的规则，并构建决策树。分类时，使用决策树对新数据的各个属性逐一进行决策判断，直到得到分类结果。

决策树的组成包括决策节点、叶子结点以及属性分枝。决策树中最上面的节点称为「根节点」，是整个决策树的开始。每个分支是一个新的决策节点，或是树的叶子。每个决策节点代表一个样本属性，每个叶子节点代表一种可能的分类结果。

决策树的决策过程就是从根节点出发，沿着决策树从上到下的遍历，每个非叶子节点相当于一个 IF 条件语句，因此在每个非叶子节点都有一个属性测试。测试结果对应不同的分支，最后抵达一个叶子节点，从而得到分类结果。

在决策树构建过程中，需要考虑如下实际问题

• 按照何种顺序进行决策树构造？
• 按照何种依据选择属性节点？
• 对于连续属性如何进行分段处理？
• 对于缺失属性又应该如何处理？如何判断所构建的决策树性能？

从性能上来说，我们期望决策树与训练数据矛盾较小，同时具有很好的泛化能力。理想的决策树形态应该为

• 叶子阶段数最少
• 叶子节点深度最小
• 叶子节点数最少且叶子节点深度最小

决策树的构建过程可以表示为

• 初始：从根节点开始，包括所有训练数据
• 迭代：在每一步中选择最优属性对训练数据进行递归划分。
• 停止：一个节点上的数据都是属于同一个类别；或者没有属性可以再用于对数据进行分割

决策树的构建是一个递归过程，基本流程可以概括为自上而下，分而治之。输入训练集 ，属性集 ，输出对应的决策树。搭建决策树对应的伪代码为

函数 TreeGenerate(D, A)
生成节点 node;
if D 中样本全属于同一类别 C then
	将 node 标记为 C 类节点
end if
if A 为空集或 D 中样本在 A 上取值相同 then
	将 node 标记为叶节点，其类别标记为 D 中样本最多的类; return
end if
从 A 中选择最优划分属性 a*
for a* 的每一个值 a*_v do
	为 node 生成一个分支; 令 D_v 表示 D 中在 a* 上取值为 a*_v 的样本子集
	if D_v 为空集 then
		将分支结点标记为叶节点，其类别标记为 D 中样本最多的类;return
	else
		以 TreeGenerate(D_v, A\{a*}) 为分支结点（递归）
	end if
end for
复制

或用自然语言表示：决策树递归中，有三种情形将导致递归返回

1. 当前结点包含的样本全属于同一类别，无需划分，将当前节点作为叶子节点标记为该类别
2. 当前属性集为空，或者所有样本在所有属性上取值相同，无法划分，将当前节点作为叶子节点标记为所含样本最多的类别
3. 当前节点包含的样本集合为空，不能划分，则将当前节点作为叶子节点标记为父节点

其中，如何从 A 中选择最优划分属性 ？应遵循让决策树的分支结点所包含的样本尽可能属于同一类别，即结点的「纯度」越来越高。可表示为：

划分后划分前

具体来说，如何定义这里的纯度？需要引入多种划分选择：

• ID3 算法
• CART 算法

决策树剪枝

决策树连续值处理

决策树缺失值处理

多变量决策树

在本章中，我们主要讲解了决策树的原理及使用时需注意的情况，主要包含以下内容

• 决策树的概念与决策树构建的基本流程——递归过程
• 如何选择当前节点的最优划分属性：可以使用信息增益、增益率以及 Gini 指数等等，掌握决策树构建过程。
• 如何通过剪枝解决决策树过拟合问题，提升泛化性能；可采用预剪枝、后剪枝，理解其过程与特点
• 如何处理连续值与缺失值；针对连续值与缺失值推广信息增益等划分标准，理解其过程
• 多变量决策树的改变：属性空间中可以采用“非轴平行”的方法对样本集进行划分。