【学习步骤】
决策树学习通常包括特征选择、决策树生成、决策树剪枝三个步骤：
- 特征选择：选择最优的特征作为决策结点
- 决策树生成：即决策树的构建，仅考虑局部最优，对应模型的局部选择
- 决策树剪枝：对生成的决策树进行简化，考虑全局最优，对应模型的全局选择
【特征选择】
如果利用一个特征进行预测的结果与随机选取的结果没有很大的差别，那么这个特征是与预测无关的
为提高决策树学习的效率，要对其进行特征选择，即在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征
具体来说，对于一般的决策树，通常采用信息增益（Information Gain）或信息增益比（Information Gain Radio）作为特征选择的标准；对于分类与回归树 CART 来说，通常采用基尼指数（Gini Index）作为特征选择的标准
- 关于信息增益与信息增益比，详见：信息增益与信息增益比
- 关于基尼指数，详见：基尼指数
【决策树生成】
生成过程
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练集进行分割，使得各子数据集有一个最好的分类的过程
这一过程对应着特征空间的划分，也对应着决策树的构建，具体步骤如下：
Step 1：构建根结点，将所有训练数据都放在根结点
Step 2：选择一个最优特征，按该特征将训练集分割为若干子集，使得各子集有一个在当前条件下最好的分类
1）若各子集已经被基本正确分类，那么构建叶结点，并将这些子集分到对应的叶结点中去
2）若各子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续进行分割，建立相应的结点
Step 3：按 Step 2 不断地进行递归，直到所有训练子集被基本正确分类，或没有合适的特征为止
在决策树构建完毕后，每个子集都被分到叶结点上，即都有了明确的类
生成算法
常见的决策树生成算法有：ID3、C4.5、CART
关于 ID3 与 C4.5 生成算法，详见：决策树的 ID3 与 C4.5 生成算法
关于 CART 生成算法，详见：决策树的 CART 生成算法
其中，ID3 是最基础的决策树生成算法，其不存在决策树剪枝这个过程，C4.5 在 ID3 的基础上进行了若干改进，其中一项改进就是进行了剪枝
此外，ID3 无法对连续值进行处理，C4.5 在 ID3 的基础上采用连续特征离散化策略，将连续型特征转为离散型特征，但这种转换过程可能会破坏连续型变量的内在性质，也就是说，ID3 与 C4.5 所生成的决策树，都是分类决策树，只能用来处理分类问题
进一步，在 C4.5 的基础上又有了 CART，其是分类回归树，既可以用于处理分类问题，也可以用于回归问题
【决策树的剪枝】
以上方法生成的决策树可能对训练数据有着很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能出现过拟合现象
为此，需要对生成的决策树自下而上的进行剪枝，将决策树进行简化，从而使得具有更好的泛化能力
具体来说，就是去掉过于细分的叶结点，使其退回父结点甚至更高的结点，然后将父结点或更高的结点改为叶结点
关于决策树的剪枝，详见：决策树的剪枝策略
【结点停止分裂的条件】
无论是使用 ID3、C4.5 还是使用 CART，在构建决策树时，决策树不可能不限制地生长，总有停止分裂的时候
最极端的情况是当结点分裂到只剩下一个数据点时自动结束分裂，但这种情况下决策树的结构过于复杂，而且预测的精度不高
一般情况下，为降低决策树复杂度，并提高预测的精度，会适当提前终止节点的分裂
常见的决策树结点停止分裂的条件有：
1.最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂
有两个原因：
- 数据量较少时，再做分裂容易强化噪声数据的作用
- 提前结束分裂，在一定程度上有利于降低过拟合的影响
2.熵或者基尼值小于阀值
熵和基尼指数的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，结点停止分裂
3.决策树的深度达到指定的条件
结点的深度可以理解为结点与决策树跟结点的距离，例如：根结点的子结点的深度为 $1$，因为这些结点与跟结点的距离为 $1$，子结点的深度要比父结点的深度大 $1$
决策树的深度是所有叶结点的最大深度，当深度到达指定的上限大小时，停止分裂
4.所有特征已经使用完毕，不能继续进行分裂
被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶结点
