基本流程

决策树是基于树结构来进行决策的，类似于人类面临决策问题时的处理机制，决策过程的最终结论对应了我们所希望的判定结果。

决策过程中提出的每一个判定问题就是对某个属性的测试，测试结果是导出最终结论或是进一步的判定问题，且考虑范围是在上次决策结果的限定范围之内。

训练一棵决策树大致需要这么几个步骤：

根节点包含所有的样本，对于根节点：
为这个节点选取最优划分属性。
根据节点属性取值将节点中样本分流到若干个子节点。
对所有子节点重复步骤2，直至：
- 当前节点所有样本都属于同一类别。取这一类别作为叶子节点类别。
- 当前节点样本为空。去多数样本所属类别作为叶节点类别。
- 不再有可以使用的划分属性。取其父节点多树样本所属类别作为节点类别。

在得到一棵决策树后，最终叶节点对应决策结果，其他节点对应属性测试。对于新来样本按照属性取值从根节点流过决策树，到叶子节点后获取其分类。这是一个分而治之的策略。

划分选择

决策树生成的算法的关键是如何选择最优化分属性。我们认为：如果一个属性将节点样本划分得“纯度”（purity）越高，则性能越好。如何衡量划分纯度，有这么几种方法：

我们需要的就是选择有最优的信息增益的属性来划分。

剪枝是决策树学习算法对付过拟合的主要手段，通过主动去掉一些分支来降低过拟合的风险。基本策略有预剪枝和后剪枝：

预剪枝 (prepruning)：在使用训练集训练决策树时不断在测试集上进行验证，将当前节点使用最优属性进行划分，划分得到若干个节点作为叶节点分类，得到的分类正确率若不高于使用原本的节点作为叶节点分类正确率，那么这个节点将不再被扩展划分：预剪枝使得决策树十分精简，训练时间开销也很小，不过可能造成欠拟合的现象。
后剪枝 (postpruning)：在训练完整棵决策树后自底向上进行验证，若某个节点的划分在训练集上没有对分类正确率有正向促进，就进行剪枝。后剪枝效果更好，不过时间开销必然要远高于预剪枝——它在训练完整棵树后再进行更多的操作！

简单的想法是对取值连续的属性进行二分处理：对训练集中该属性上的取值从小到大排个序，然后取任意两个相邻值的中位数作为一个分割点，样本就可以在这个属性上被分为两个分支。取分割点同样可以使用信息增益最大的一个。

分类问题都是在空间中寻找分类边界，决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。但是真实的分类任务中属性过多时，必须使用很多划分才能获得较好的近似，而且很难解释。

一个看起来更简单的决策树对每个节点使用多个属性的线性组合来作为划分依据，称作“多变量决策树” (multivariate decision tree)。相较于传统决策树的分类边界平行于坐标轴，多变量决策树可以实现斜向的分类边界，或许更符合样本的分布。

主要算法有OC1，或者嵌入神经网络。