决策树（decision tree）是一种基本的分类和回归方法，由于其采用的是一种树形的结构，因此，具有很强的解释性和计算速度，也正是因为这些特点，使得决策树在很多行业都得到了应用，比如风控行业等。决策树的建模过程一般分为三个步骤：特征选择、决策树的生成和决策树的剪枝，根据这三个步骤所采用的规则，衍生出了很多不同的模型，比较经典的有Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及Breiman等人在1984年提出的CART算法，本文将以分类决策树为例，对这几个算法分别进行介绍，并用python进行实现。

    决策树是由结点和有向边组成的树形结构，其中，结点包含两种类型：内部结点和叶结点。内部结点表示一个特征或者属性，叶结点则表示一个类。如下图所示，其中每个圆圈表示内部结点，每个正方形表示叶结点。

    对于给定的训练数据集$D=left{left(x_{1}, y_{1}right),left(x_{2}, y_{2}right), cdots,left(x_{N}, y_{N}right)right}$

1. 首先，构建根结点，然后将整个训练集都放在根结点。
2. 接着，从所有特征中选择一个最优特征，并根据该特征将训练数据集分割为多个子集，使得每一个子集有一个当前条件下的最好分类，如果某个子集已经基本分类正确，则将其作为叶结点，其对应的类别作为该叶结点的类别，否则，对每个子集继续选择最优的特征进行分割，如此递归下去，直到所有的子集基本被正确分类为止。最后，每个叶结点都代表一个子集，也是特征空间中的一个子区域，每个子区域之间都是不相交的。
3. 最后，由于第二步为了将训练集划分正确，往往构建的决策树会过于庞大，这时，模型可能会出现过拟合，导致对新的测试数据可能分类效果不好，因此，需要对决策树自下而上进行剪枝，去掉一些过于细分的叶结点，使其回退到父结点或者更高的结点，然后将父结点或者更高的结点作为新的叶结点。

    这样一来，当对一个实例$x$进行预测时，会根据决策树的分支情况，将实例$x$划分到其归属的叶结点，并将该叶结点对应的类别作为实例$x$的预测类别，从而达到分类的效果。下面，我们将根据决策树的三个步骤，对各个算法的思想进行介绍和对比。

适用场景：特征和目标变量都是离散型

    特征选择是指决策树在每一次分支时，从所有的特征中选择能够对当前数据集具有最优分类能力的特征，这样可以提高模型的学习效率。ID3决策树的特征选择采用的是信息增益的方法。在介绍信息增益的概念之前，需要先介绍一下熵和条件熵的概念。

    在信息论中，熵表示随机变量不确定性的度量，设$X$是一个取有限个值的离散随机变量，则其熵的计算公式如下：
$H(X)=-sum_{i=1}^{n} p_{i} log p_{i}$

    条件熵则表示在已知随机变量$X$的条件下随机变量$Y$的不确定性，其计算公式如下：
$H(Y | X)=sum_{i=1}^{n} p_{i} Hleft(Y | X=x_{i}right)$

    信息增益则表示在得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。其计算公式如下：
$g(Y, X)=H(Y)-H(Y | X)$

    ID3算法构造决策树的思想大致如下：首先从根结点开始，对结点，对结点计算所有可能特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归地调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止，最终得到一个决策树。其具体的算法步骤如下：

1. 给定训练数据集$D$，特征集$A$，阈值$varepsilon$;
2. 若$D$中所有实例属于同一类$C_k$
3. 若$A=varnothing$
4. 否则，计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$
5. 如果$A_g$
6. 否则，对$A_g$