1. 算法原理
决策树（Decision Tree），又称判断树，它是一种以树形数据结构来展示决策规则和分类结果的模型，作为一种归纳学习算法，其重点是将看似无序、杂乱的已知实例，通过某种技术手段将它们转化成可以预测未知实例的树状模型，每一条从根结点（对最终分类结果贡献最大的属性）到叶子结点（最终分类结果）的路径都代表一条决策的规则。决策树算法的优势在于，它不仅简单易于理解，而且高效实用，构建一次，就可以多次使用，或者只对树模型进行简单的维护就可以保持其分类的准确性。
决策树的优点：
- 具有可读性，如果给定一个模型，那么根据所产生的决策树可以很容易推理出相应的逻辑表达；
- 分类速度快，能在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
决策树的缺点：
- 对未知的测试数据未必有好的分类、泛化能力，即可能发生过拟合现象，此时可采用剪枝或随机森林。
2. 决策树的生成
2.1 构造过程
决策树的构造过程一般分为3个部分，分别为：
- 特征选择；
- 决策树生产；
- 决策树裁剪。
特征选择：从众多的特征中选择一个特征作为当前节点分裂的标准，如何选择特征有不同的量化评估方法，从而衍生出不同的决策树，如ID3（通过信息增益选择特征）、C4.5（通过信息增益比选择特征）、CART（通过Gini指数选择特征）等。特征选择的目的是使用某特征对数据集划分之后，各数据子集的纯度要比划分钱的数据集D的纯度高（也就是不确定性要比划分前数据集D的不确定性低）
决策树的生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。这个过程实际上就是使用满足划分准则的特征不断的将数据集划分成纯度更高，不确定行更小的子集的过程。对于当前数据集的每一次划分，都希望根据某个特征划分之后的各个子集的纯度更高，不确定性更小。
决策树的裁剪：决策树容易过拟合，一般需要剪枝来缩小树结构规模、缓解过拟合。
更多细节，请移步：机器学习之-常见决策树算法(ID3、C4.5、CART)
2.2 特征选择举例
前面说过，决策树的生成的第一步是特征选择，现有如下的二元分类问题的数据集，要求判断选取A和B哪一个属性作为当前分裂的依据。
|
A |
B |
类标号 |
|
T |
F |
+ |
|
T |
T |
+ |
|
T |
T |
+ |
|
T |
F |
- |
|
T |
T |
+ |
|
F |
F |
- |
|
F |
F |
- |
|
F |
F |
- |
|
T |
T |
- |
|
T |
F |
- |
- 计算按照属性A和B划分时的信息增益。决策树归纳算法将会选择那个属性？
- 计算按照属性A和B划分时Gini系数。决策树归纳算法将会选择那个属性？
3. 提升方法
提升是指给每个训练元组赋予权重，迭代地学习k个分类器序列，学习得到分类器Mi之后，更新权重，使得其后的分类器Mi+1“更关注”Mi误分的训练元组，最终提升的分类器M*组合每个个体分类器，其中每个分类器投票的权重是其准确率的函数。在提升的过程中，训练元组的权重根据它们的分类情况调整，如果元组不正确地分类，则它的权重增加，如果元组正确分类，则它的权重减少。元组的权重反映对它们分类的困难程度，权重越高，越可能错误的分类。根据每个分类器的投票，如果一个分类器的误差率越低，提升就赋予它越高的表决权重。在建立分类器的时候，让具有更高表决权重的分类器对具有更高权重的元组进行分类，这样，建立了一个互补的分类器系列。所以能够提高分类的准确性。