内容来自于《机器学习》
基本流程
一般的，一棵决策树包含一个根节点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个节点则对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定的测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，基本流程遵循简单且直观的“分而治之”。
决策树的生成是一个递归过程，在决策树的基本算法中，有三种庆幸会导致递归返回： （1）当前结点包含的样本都属于同一类别，无需划分； （2）当前属性集为空，或者所有样本在所有属性上的取值相同，无法划分； （3）当前结点包含的样本集合为空，不能划分。
在（2）情况下，吧当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。在（3）情况下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别，柱子这两种情形的处理实质不同，情形（2）是在利用当前结点的后验分布，情形（3）是吧父结点的样本分布作为当前结点的先验分布。
划分选择
信息熵是度量样本集合纯度最常用的一种指标。家丁当前样本集合D中第k类样本所占的比例为pk，则D 的信息熵定义为：
Ent(D)的值越小，则D的纯度越高。
| 假定离散属性a有V个可能的取值，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为a^v的样本，记为D^v，我们可以计算出D^v的信息熵。再考虑到不同分支结点所包含的样本数目不同，给分支结点赋予权重 | D^v | / | D | ,即样本数越多的分支结点的影响越大，于是可以计算出用属性a对样本集D进行划分所获得的信息增益： |
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，我们可以用信息增益来进行决策树的划分属性选择。
著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。
实际上信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性：
IV(a)成为属性a的固有值，属性a的可能取值数目越多，即V越大，IV(a)越大。
需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此C4.5并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式，先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数
CART决策树使用基尼指数来选择划分属性，数据集D的纯度可以用基尼值来度量：
直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，Gini(D)越小，则数据集D的纯度越高。
属性a的基尼指数定义为：
于是我们在候选属性集合A中，选择哪个使得划分后基尼指数最小的属性作为最优划分属性。
剪枝处理
剪枝是决策树学习算法对付过拟合的主要手段，在决策树学习中，为了尽可能正确分类训练样本，结点划分的过程将不断重复，有时候会造成决策树分支过多，这时候就可能因训练样本学得太好了，以至于把训练集自身的一些特点当做所有数据都具有的一般性质而导致过拟合。因此可以通过主动去掉一些分支来降低过拟合的风险。
决策树剪枝的基本策略有预剪枝和后剪枝。
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶子结点。
后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能够带来决策树泛化性能提升，则将该子树替换为叶结点。
预剪枝使得决策树的很多分支都没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，预剪枝基于贪心的本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未简直决策树和预剪枝决策树都要大的多。
连续与缺失值
如果属性的取值是连续的，不能直接根据连U型属性的可取值来对结点进行划分，次数连续属性的离散化技术可派上用场，最简单的策略是采用二分法对连续属性进行处理，这证书C4.5决策树算法中采用的机制。
现实任务中常会遇到不完整样本，即样本的某些属性值缺失。
如果简单地放弃不完整样本，仅适用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。