决策树（decision tree）是一类常见的机器学习方法。一般地，一颗决策树包含一个根节点、若干个内部节点和若干个叶节点。 叶节点则对应决策结果 。决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树。

一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的 纯度 ( purity )越来越高。 根据划分方式的不同，也产生了不同的决策树算法 。

信息增益是基于信息熵基础上的，因此先讲下信息熵是什么。

“ 信息熵 ”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占比例为
p k ​ （k=1,2,…,|y|），则D的信息熵定义为：

假定我们只有2类，每类所占的比例都为1/2。则这个时候Ent（D）的值为1。假设这个时候有10类，每个类所占比例都是1/10，则Ent（D）的值为3.32。
这里我们约定，当p=0时，log2p=0。我们这里也可看出来，熵值越大，则D的纯度越低。

信息增益指的是用某个属性对样本集合进行划分之后样本信息熵 减小 的值。
假定离散属性a有V个可能的取值 ∣ D v ∣ / ∣ D ∣ ，即样本数越多的分支节点的影响越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”计算公式如下：

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度”提升越大 。因此，我们可用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来选择属性划分。

上节所讲信息增益算法其实有个很大的缺点。缺点在于，信息增益准则对可 取值数目较多的属性 有所偏好。这也很容易理解，如果属性可取值数目较多，用这个属性划分数据集后的分支节点的纯度相对来说会更大。取极限情况来说，假设对每个样本都进行编号，则使用编号这个属性进行划分，只需一次便可产生一颗完整的决策树。为减少这种偏好可能带来的不利影响，著名的 C4.5决策树算法 不直接使用信息增益，而是使用 增益率 来选择最优划分属性。

增益率的定义为：

IV （a）称为属性a的固有值。属性a的可能取值数目越多（即V越大），则 IV （a）的值通常也会越大。需要注意的是，C4.5算法对可取值数目较少的属性会有所偏好。因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式的算法： 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的 。

（为了克服ID3算法和C4.5算法的缺点，不知道是不是，笔者瞎编的），CART（Classification and RegressionTree）则是使用 基尼指数 来选择划分属性。我们这里用基尼值来度量数据D的纯度：

直观来说，Gini(D)反应了从数据集D中随机抽取两个样本，其 类别标记不一致的概率 。因此，Gini（D）越小，则数据集D的纯度越高。属性a的基尼指数定义为：

于是，我们在候选集属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。在决策树学习过程中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学的“太好”了，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合风险。
决策树剪枝的基本策略有“预剪枝”和“后剪枝”。

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分当前节点并将当前节点标记为叶节点。
现在问题来了？ 如何判断决策树泛化性能是否提升了呢？
答案在验证集中进行测试。学过机器学习的同学都知道，数据集可分为训练集和测试集。我们在训练集中可预留出一部分数据作为验证集。通过使用决策树对验证集进行分类，若验证集分类准确率上升，我们则可认为决策树泛化性能提升了。

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察。若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶结点。
一般情形下， 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树 。但是后剪枝过程是在生成决策树之后进行的，并且要自底向上地对树中所有非叶节点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大很多。 若不考虑计算开销影响，一般往往选择后剪枝方式进行处理。

在现实学习任务中会遇到连续属性的情况，这种情况下需如何处理呢？最简单的策略是采用二分法对连续属性进行处理。这也是C4.5决策树算法中采用的机制。

给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为 D t + ​ 则包含那些在属性a上取值大于t的样本。显然，对相邻的属性取值ai与ai+1来说，t在区间[ai,ai+1)中取任意值所产生的划分结果相同。因此，对连续属性a，我们可以考察包含n-1个元素的候选划分点集合:

即把区间的中位点作为候选划分点，然后，我们就可象离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。我们可对公式稍加改造：

其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益。于是，我们就可以选择使Gain（D,a,t）最大化的划分点。
需注意的是，若当前节点划分属性为连续属性，该属性还可作为其后代结点的划分属性 。

决策树在sklearn中有库函数可以直接调用实现。我们这里讲下使用python从底层进行实现。这里我们实现的是C4.5决策树算法。ID3算法中没有对连续属性值的处理。将增益率换为信息增益，则退化为了ID3决策树算法，替换为基尼指数则进化为了CART决策树算法。可以自己实现。
声明 ，代码搬运至某个github项目，然而找不到地址了，如果作者看到这篇文章，请联系我加上去，这里先用下，谢谢。笔者跑通后加了许多注释和讲解。

数据集直接在python中创建，省去许多不必要的麻烦。