1. 什么是决策树
决策树是一个判别模型，可以用于分类，也可以用于回归。在决策树的每层会选取一个特征对数据点进行划分，一般的决策树是按层扩展的，即决策树第$i$层的节点都是使用同一个特征进行划分，但也有按节点扩展的，即每个节点内部自己决定特征进行扩展。当达到最大深度或节点内部都可以归为同一类时，该节点停止扩展。决策树算法的实现主要有三种，分别是ID3算法，C4.5算法和CART算法。
2. ID3算法
ID3算法构建的决策树有二个要点：第一点是使用信息增益决定采用哪个特征进行划分，信息增益的计算方式决定了该算法构建的决策树只能用于分类任务；第二点是每次选取一种特征后，对该特征的所有取值都构造一个子节点，所以ID3算法构建的决策树，特征值必须是离散的。
信息增益对应着信息熵的减少，信息熵的计算方式如下：
对决策树第$k$层计算信息熵，等于对第$k$层各个节点内部计算信息熵并求和，计算时$p_i$表示在节点内部类别为$i$的概率。假设第$k$层的第$i$个节点的信息熵等于$e_k^i$，则由该节点展开的第$k+1$层的子节点到第$k$层的信息增益等于
其中$|S_i|$表示到达节点$i$的样本集合大小，$|S_j|$表示到达子节点$j$的样本集合大小。ID3算法每次选取特征时，都会使用使得信息增益最大的特征进行划分，即使用贪心的算法思想构建决策树。但是这种方法有一个问题，当一个属性的取值较多时，往往分割出来的结果会更具体，即熵值越低，ID3算法也的确会倾向于选择这种特征进行决策树的展开，但这往往会造成过拟合。
3. C4.5算法
通过前面的介绍，我们可以看到ID3决策树存在三个问题：第一点是ID3决策树只能处理离散特征值，第二点是ID3决策树只能用于分类任务，第三点是ID3决策树使用信息增益作为特征选取的指标存在过拟合的风险。C4.5算法就是为了解决ID3算法第一点和第三点问题而提出的。首先特征值现在可以不是离散值了，所以C4.5在选择特征后，假设需要划分出$j$个子节点，则选择$j-1$个值，将值域划分为$j$个空间，在对应值域的数据划分到对应的子节点。其次使用信息增益率代替信息增益作为特征选择的指标，信息增益率使用下式表示：
其中$r$表示信息增益率，$\Delta$表示信息增益。$IV$的计算公式表示将节点划分成$J$个子节点后数据样本的分布熵，$p_j$表示在第$j$个子空间的数据样本数占在节点总样本数的比例。可以看到当特征按照特征值分得越细，则$IV$值越大，对应的信息增益率也会变小，所以使用信息增益率可以避免ID3总是分割特征值多的特征，从而降低过拟合的风险。
4. CART算法
无论是ID3算法还是C4.5算法，都只能运用在分类任务。CART算法克服了ID3和C4.5只能用于分类任务的问题，既可以用于分类任务也可以用于回归任务。CART有两个重要要点：第一点是CART算法构造的决策树是二叉树，第二点是CART算法使用基尼系数作为特征及特征值的选取指标。CART根据基尼系数选择一个特征当中的一个特征值，将小于该特征值的数据样本划分到左子树，大于等于该特征值的数据样本划分到右子树。基尼系数的计算公式如下：
CART会选择基尼系数最小的特征和特征值进行划分，在计算基尼系数时，$p_i$表示在节点内部数据样本属于第$i$类的频率。在处理分类任务时，CART选择叶节点内样本数目最多的类别作为该节点的分类结果；在处理回归任务时，CART会选择叶节点内样本的统计结果作为该节点的数值预测。
5. 其他
在使用决策树对数据样本进行学习与预测时，有时会出现过拟合，解决过拟合的主要思路是限制树的生长，减小树的规模。可以是限制决策树的深度或叶子节点数，可以是使用验证集对树进行剪枝。使用验证集对决策树剪枝的思路是，如果去掉该节点的子树在验证集表现更好，则去掉这个节点的子树。