决策树原理

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。也就是说，决策树既可以用来解决分类问题，也可以解决回归问题。

决策树其实是一棵倒树，它的根在最上面，叶子在下面。

决策树由节点(node)和有向边(directed edge)组成。节点有两种类型：内部节点(internal node)和叶节点(leaf node)。内部节点表示一个特征或属性，叶节点表示一个类。

下面我们通过一个小例子来看下，这棵树到底怎么用

决定我们是否打篮球的因素有三个，是否下雨，温度是否适合，是否是室内。我们一步一步，通过判断不同的条件，最后得出不同的结论。

我们首先选取了决定是否打篮球的条件，并且以是否下雨为根节点开始分裂，然后根据不同情况构造了一棵树，最后根据该树的分枝，来决定是否打篮球。

概括来说，就是根据特征的值做判断，最后得出不同的分类。

决策树学习过程

那么决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树生成和修剪。

特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树生长。

剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

特征选择

特征选择是为了选择出对于训练数据具有分类能力的特征。比如说，使用某一个特征进行决策树分类的结果与随机分类的结果没有任何区别，那么该特征就不具备分类能力，可以直接丢弃掉该特征。当然我们要选择能够分类出更好的类别的特征，作为根节点。

那么一般情况下该如何选择特征呢，业界通常会使用信息增益的方式来选择。

先来看几个概念：

信息熵

条件熵

信息增益

信息熵

信息熵是信息的期望值，是用来衡量信息不确定性的指标。信息的不确定性越大，熵越大。

比如说对于抛硬币事件，每次抛硬币的结果就是一个不确定的信息。

如果根据我们的经验，一个均匀的硬币正面和反面出现的概率是相等的，都是50%。所以我们很难判断下一次是出现正面还是反面，所以这个事件的信息熵值很高。

但是如果该硬币不是均匀的，并且根据历史数据显示，100次试验中，出现正面的次数有98次，那么下一次抛硬币，我们就很容易判断结果了，故而该事件的信息熵很低。

其计算公式为：

其中：

P(X=i)为随机变量 X 取值为 i 的概率

n 代表事件的 n 种情况

我们还是以上面抛硬币的例子来求解下两种情况下的信息熵各为多少

注意，由于编辑器的原因，以下所有 log(2) 均表示以2为底的对数

均匀硬币

信息熵 = -0.5 * log(2)0.5 - 0.5 * log(2)0.5 = 1

非均匀硬币

信息熵 = -0.98 * log(2)0.98 - 0.02 * log(2)0.02 = 0.14

思考：如果正面的概率是100%，那么此时的信息熵是多少呢

答：此时信息熵是0，也可以说明，信息熵是0到1之间的数值。

条件熵

条件熵是通过获得更多的信息来减小不确定性。当我们知道的信息越多时，信息的不确定性越小。

比如说某个用户曾经购买了一种商品，但是我们没有办法仅仅根据这个信息来判断，该用户是否会再次购买该商品。但是如果我们增加一些条件，比如双十一促销活动信息之后，我们就能够更加容易的发现用户购买商品与促销活动之间的联系，并通过不同促销力度时用户购买的概率来降低不确定性。

其计算公式为：

其中：

Y 为条件

P(Y = v)表示 Y 有多种情况，当 Y 处于 v 的概率

H(X|Y = v)表示 Y 处于 v 条件时的信息熵

信息增仪

信息增益的定义就是信息熵减去条件熵

这里只是数学上的定义，那么该如何使用信息增益来创建决策树呢，还是举例来看。

在上图中，我先按照某种条件，把红点和黄框分成了如图所示的两类，接下来我们计算下熵值

父节点信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.97

上面子节点信息熵 = -(2/6log(2)2/6)-(4/6log(2)4/6) = 0.91

下面子节点信息熵 = -(2/4log(2)2/4)-(2/4log(2)2/4) = 1

此处两个子节点其实就是某种条件下的信息熵，因为在分类的时候，是隐含了某种分类条件的。

下面根据条件熵的定义，可以得到条件熵

条件熵 = 上面子节点出现的概率 * 该条件下的信息熵 + 下面子节点出现的概率 * 该条件下的信息熵

= 6/10 * 0.91 + 4/10 * 1

= 0.946

再根据信息增益的定义，可以得到信息增益

信息增益 = 父节点信息熵 - 条件熵

= 0.97 - 0.946

= 0.024

再来看另一种分类方式

父节点信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.442

上面子节点信息熵 = -(6/6log(2)6/6)-(0/6log(2)0/6) = 0

下面子节点信息熵 = -(4/4log(2)4/4)-(0/4log(2)0/4) = 0

条件熵 = 0

信息增益 = 0.442

从图中明显可以看出，第二种分类是好于第一种的，而此时第二种的信息增益是较大的，由此可以得到，在通过信息增益来确定节点时，需要使用信息增益最大的那个特征。   也就是说，信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。

决策树生成

构建决策树的工作原理：

拿到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此此时可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

构建决策树的算法有很多，比如 C4.5、ID3 和 CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。ID3 和 C4.5 算法可以生成二叉树或多叉树，而 CART 只支持二叉树。

基于ID3算法

ID3 算法其实就是计算信息增益，在决策树各个结点上对应信息增益准则（选取信息增益最大的）选择特征，递归地构建决策树。

具体方法是：从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。

我们使用如下的数据集来演示下该如何通过 ID3 算法构建决策树，该数据集记录的是某位客户，在不同天气下打高尔夫的情况。

计算根节点

我们首先来计算是否打高尔夫球的信息熵

根据信息熵的计算公式可以得出，Play Golf 的信息熵为

H(play golf) = -[-0.531 + (-0.410) ] = 0.940

下面计算3种天气状况下的条件熵

以天气状况为节点

各种天气状况出现的概率

各种天气状况下的条件熵

以 weather 为节点的条件熵 0.36 * 0.971 + 0.29 * 0 + 0.36 * 0.971 = 0.69

此时的信息增益为 0.94 - 0.69 = 0.25

以温度为节点

各种温度出现的概率

各种温度下的条件熵

以 temp 为节点的条件熵 0.29 * 1 + 0.43 * 0.918 + 0.29 * 0.811 = 0.92

此时的信息增益为 0.94 - 0.92 = 0.02

以风力为节点

各种风力出现的概率

各种风力下的条件熵

以 wind 为节点的条件熵 0.57 * 0.811 + 0.43 * 1 = 0.89

此时的信息增益为 0.94 - 0.89 = 0.05

对比上面的信息增益可知，以 weather 为节点分类为最佳，此时可以得到如下的一棵树

因为通过观察数据可是，只要是 overcast，一定会去打高尔夫球，所以我们已经得到了一个叶子节点

对于 rainy 和 sunny，下面到底需要使用 temp 还是 wind 来最为节点分类，需要继续求解信息增益，以此来确定节点信息。

计算第二层

在 sunny 为节点的情况下

信息熵为 0.971

以风力为节点

在 sunny 情况下各种风力出现的概率

各种风力下的条件熵

以 wind 为节点的条件熵 0.6 * 0 + 0.4 * 0 = 0

此时的信息增益为 0.971 - 0 = 0.971

在 sunny 情况下各种温度出现的概率

各种温度下的条件熵

以 temp为节点的条件熵 0.6 * 0.915 + 0.4 * 1 = 0.949

此时的信息增益为 0.971 - 0.949 = 0.022

因为以 wind 为节点时信息增益大，所以在 sunny 节点下选择以 wind 为节点继续分叉

同理我们再来看看 rainy 情况下是怎样的

在 rainy 为节点的情况下

信息熵为 0.971

以风力为节点

在 rainy 情况下各种风力出现的概率

各种风力下的条件熵

以 wind 为节点的条件熵 0.6 * 0.915 + 0.4 * 1 = 0.949

此时的信息增益为 0.971 - 0.949 = 0.022

在 rainy 情况下各种温度出现的概率

各种温度下的条件熵

以 temp为节点的条件熵 0.4 * 0 + 0.4 * 1 + 0.2 * 0 = 0.4

此时的信息增益为 0.971 - 0.4 = 0.571

因为以 temp 为节点时信息增益大，所以在 rainy 节点下选择以 temp 为节点继续分叉

最后再把 mild 情况继续划分即可

最终我们可以得到一棵如下的决策树

基于CART算法

其实 CRT 算法是基于 ID3 算法而来的，ID3 是基于信息增益做判断，而 CART 选择属性的指标则是基尼系数。

基尼系数在经济学中非常出名，它是用来衡量一个国家收入差距的常用指标。当基尼系数大于0.4时，说明财富差异悬殊，当基尼系数在0.2-0.4之间说明分配合理，财富差距不大。

在数学上，基尼系数本身反应了样本的不确定度。当基尼系数越小时，说明样本之间的差异性越小，不确定程度低。在构造决策树的过程，其实质就是降低不确定度的过程，所以可以选择基尼系数最小的属性作为属性的划分。

其计算公式为：

其中：

p(Ck|t) 表示节点 t 属于类别 Ck 的概率

剪枝

那么决策树构造出来后，如果该树的节点过多，树的结构过于复杂，则有可能该模型存在过拟合的风险，此时就需要对决策树进行剪枝的操作。

剪枝就是给树瘦身，这一步想实现的目标就是，让树不需要太多的判断，同样可以得到不错的结果。

造成过拟合的原因有很多，其中一个原因就是训练集的样本过小。如果决策树选择的属性足够多，那么构造出来的决策树一定可以完美的把训练集中的样本分类，但是这样有可能模型把训练集中一些数据的特点当作了所有数据的特点，但是这些特点并不一定是全部数据的特点，这就使得决策树在真实的数据分类中产生错误，该模型的“泛化能力”就比较差。

所谓的泛化能力就是指分类器通过训练集抽象出来的分类能力，即举一反三的能力。

决策树常用的剪枝方法有两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。

预剪枝是根据一些原则及早的停止树增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、不确定度下降的最大幅度小于用户指定的幅度等。

预剪枝的核心问题是如何事先指定树的最大深度，如果设置的最大深度不恰当，那么将会导致过于限制树的生长，使决策树的表达式规则趋于一般，不能更好地对新数据集进行分类和预测。另外一个方法来实现预剪枝操作，那就是采用检验技术对当前结点对应的样本集合进行检验，如果该样本集合的样本数量已小于事先指定的最小允许值，那么停止该结点的继续生长，并将该结点变为叶子结点，否则可以继续扩展该结点。

后剪枝则是通过在完全生长的树上剪去分枝实现的，通过删除节点的分支来剪去树节点，可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。后剪枝操作是一个边修剪边检验的过程，一般规则标准是：在决策树的不断剪枝操作过程中，将原样本集合或新数据集合作为测试数据，检验决策树对测试数据的预测精度，并计算出相应的错误率，如果剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低，那么剪掉该子树。

为了使决策树达到最好的效果，一般情况下预剪枝和后剪枝都是同时使用。

决策树优缺点

优点

可解释性高，可以可视化

能够处理非线性的数据

不需要做数据的规范化

缺点

容易过拟合

不稳定，一个微小的变动，都会导致整个树的改变

对类别不平衡的数据，支持度不好

得到的结果并不一定是最优解

总结

今天我们讲了决策树的原理，以及信息熵、条件熵和信息增益的原理及详细工作原理。当然，上面的公式太多了，还不是很好了解，需要怎么记忆呢，其实我们可以在一些数据挖掘工具中直接使用封装号的工具来调用它们，比如 sklearn 中就封装了决策树的实现。在这里我们了解决策树的工作原理，才能更好的明白其优缺点，从而在以后的工作中更加灵活的使用。

决策树包括根节点，子节点和叶子节点，而决定节点的方法有多种，最常用的就是 ID3 算法和 CART 算法。ID3 算法是基于信息增益来判断分类节点的优劣性的，而 CART 是通过尼基系数来判断。之后我们还介绍了为了方式决策树过拟合，可以采用的剪枝技术，预剪枝和后剪枝。

练习题

如下的约会数据集，你能否手动推导，生成一棵决策树呢？