决策树理论的本质：过年亲戚大拷问你通过了吗

决策树理论的本质：过年亲戚大拷问你通过了吗假设现在有一批以往申请银行贷款的人员历史记录，主要记录了四个特征：申请人的年龄；申请人是否有工作；申请人是否有房；申请人平时的信用情况。最后还有这些人到底有没有得到成功申请到贷款的结果。接下来我们就来看看如何从一批数据中构建出一颗决策树对新的数据归属进行预测或者分类。决策树模型的原理本质上就是一个通过不同特征对事物进行分类的过程，比如在上述例子里，亲戚阿姨就通过四个特征（问题）把我们归类为两类：人生赢家和LOSER。为此她构建了一棵具有三个内部节点，一个根结点，五个叶节点的决策树。（这样想想，亲戚阿姨也真是不容易~~~）

「我们的目标是：要干货！还要看得懂！」

——Kira和极客们

各位小伙伴们，不知道你们过年的时候有没有经历“亲戚大拷问”？大家可不要小看亲戚大拷问，你不知道的是，其实你亲戚在拷问你的时候，他也是很不容易地默默地在心里建立了一颗“决策树”。

你问我什么是决策树？你看，比如这样的问题就是一颗决策树：

决策树模型的原理本质上就是一个通过不同特征对事物进行分类的过程，比如在上述例子里，亲戚阿姨就通过四个特征（问题）把我们归类为两类：人生赢家和LOSER。

为此她构建了一棵具有三个内部节点，一个根结点，五个叶节点的决策树。

（这样想想，亲戚阿姨也真是不容易~~~）

接下来我们就来看看如何从一批数据中构建出一颗决策树对新的数据归属进行预测或者分类。

假设现在有一批以往申请银行贷款的人员历史记录，主要记录了四个特征：申请人的年龄；申请人是否有工作；申请人是否有房；申请人平时的信用情况。最后还有这些人到底有没有得到成功申请到贷款的结果。

从中我们可以看出这个记录中一共具有四个特征，每个特征都有不同的个数。比如年龄特征可以分为青年，中年和老年三种，而是否有工作则只有两种情况，是或否。

而最终要分类的类别也是两种，即银行同意贷款（是）和不同意贷款（否）。

也就是说，构建一颗决策树中所用到的根节点和内部节点就在这些特征之中，而叶节点就是指同意贷款和不同贷款。

那么我到底选哪个特征作为根节点呢？哪个特征作为第一个内部结点呢？这些特征是全部都要用呢还是只要选其中几个就可以了呢？

从这些问题中，就可以发现构建一棵决策树的关键就在于如何选取最合适的特征，搭建出最符合历史数据的分类模型。

那么到底如何评价一个特征是不是比别的特征好？这里我又要用到在《极简图解最大熵原理，其实没有你想的那么复杂》中的涉及的信息论知识。

因为上次有小伙伴反应关于信息熵的内容不是很明白，那么这次我们就给大家从头梳理下。

作为“信息论之父”，香农的工作主要是为了能够“量化信息”，比如对于一个发生概率为pi的事件，它究竟包含了多少信息呢？

首先这个事件的自信息被定义为：

自信息可以从两方面理解，如果这个事件还没有发生，那么自信息可以理解为事件发生的不确定性；如果这个事件发生了，那么自信息可以理解为事件发生使我们对事件的认识加深了，所以我们就获得了额外的信息量。

很多人可能会疑问为什么要这样定义自信息，直接有概率pi还不够吗？

因为关于信息我们需要它至少能够满足样两个条件。

1，小概率事件的不确定性大于大概率事件的不确定性，或者说小概率事件发生后带来的信息量大于大概率事件发生带来的信息量，这点很符合现实需要吧？

2，两个事件同时发生的信息量等于我他们分别发生的信息量，也就是说信息量是可加的。

但是熟悉概率的各位都知道两件事情同时发生的概率是个乘法关系p1p2，也就是说，我们需要找一个函数，既是一个递减函数（符合条件1），又要能够把乘法转换为加法（符合条件2），基于上述理由，香农最后提出了这种以log函数表达信息概念的方式。

（这里大家大致能够理解用log的必要性就可以了，其实据说是根据泛函分析推出来的，小白表示学海无涯，目前还不懂。）

既然自信息是一个事件发生所带来的信息量（或者未发生时的不确定性），那么对于一个系统来说，对系统中的所有事件求期望（可以理解为平均一下），就得到了这个系统的信息熵：

所以说信息熵表示的是整个系统内事件未发生时的不确定性，或者说事件发生后能够带来的信息量。

而所谓最大熵模型就是在构建模型的时候希望模型的不确定性最大，也就是说得到一个最客观的模型而不受主观影响（没看过的小伙伴去看前文去）。

好了，我们还是回到决策树模型中来，在决策树模型中，我们还需要用到条件熵和信息增益的概念。

既然有条件概率，那么当然也有条件熵。所谓条件熵就是在事件X发生的前提下，事件Y再发生所带来的信息量，具体定义如下：

上面这个式子可以这样理解，事件X是由一系列xi组成的，在某个xi发生的前提下事件Y发生的信息熵就是对所有的Y求期望，这个就是当X=xi时，Y的信息熵。

因为事件X中包含了很多xi，所以对所有的xi前提下的Y的信息熵求期望，就得到了以事件X为前提，事件Y 发生的条件熵。

（暂时看不懂没关系，下面有例子，通过计算你就能看懂了。）

有了条件熵我们接下来就可以定义信息增益：

事件Y发生的不确定性为H(Y)，事件X发生后，事件Y再发生的不确定性变为了H(Y|X)，也就是说事件X发生，消除了一部分不确定性。所以信息增益其实就是指事件X发生后对事件Y发生消除的那一部分不确定性。

注意，在机器学习中，我们称g(Y X)为信息增益，表示不确定性的减少。在信息论中，其实信息增益就是指互信息，表示两个事件互相影响减少了原来的不确定性。

了解了信息增益我们就可以根据信息增益最大原则选择合适的特征作为决策树的结点了。

在决策树中的信息增益指的是以特征为前提条件，消除各种分类结果的发生的不确定性。

不同特征为前提的信息增益是不同的，但是其中总有一个是最大的，也就是说这个特征能够消除最多的不确定性（不要和最大熵搞混，最大熵是使系统不确定性最大，信息增益最大是指消除的不确定性最大）。

于是我们要计算所有特征前提下的信息增益，然后选择其中最大的作为根节点。

根据信息增益的定义，首先计算是否同意贷款事件在不考虑特征前提下的信息熵。

（以下计算都基于上图15组数据记录，请注意计算过程，便于理解条件熵和信息增益的实际应用。）

以年龄为例，为了得到以年龄为条件的条件熵，先计算当年龄分别为青年、中年、老年时，贷款事件的信息熵。

之后对这三个年龄求期望，就得到了以年龄为条件的条件熵。

那么年龄特征作为前提条件消除的不确定性就是0.083：

同理，我们用相同的定义计算是否有工作作为特征时的信息增益，结果为0.3237：

以是否有房作为特征时的信息增益为0.42：

以信贷情况作为特征的信息增益为0.363：

根据上述计算，以是否有房计算出的信息增益最大，也就是说有房作为特征能够消除最多的不确定性。

所以我们将选择是否有房这个特征作为根结点。当你有房的时候，你是肯定会得到贷款同意的，也就是说当“有房=是”，得到的叶节点是“纯”的。

而当“有房=否”的时候，分类结果并不“纯”，而是“混合”的，没有房的9个人中，有3个最后得到了贷款，6个没有得到，所以显然我们需要继续分类，选择第二个特征。

也就是说，当根据特征分类得到“纯”的结果的时候，它就是一个叶节点。对于不纯的结果，则需要继续分类。

说了那么多不确定性估计大家也很糊涂，现在我们来直观看一下信息增益最大到底是个什么概念。

下图是分别用四个特征作为根结点分类的结果，其中年龄显然是最不合适的，因为用它的分类结果都是混合的。

而有工作，有房，信贷情况都能产生一个“纯”的分类，即叶节点，但是信贷情况毕竟还有2个混合结果，所以它的分类效果也不是最好。

而有工作和有房都能产生一个混合，一个叶节点，但是直观上来看，按照有工作分类剩下10组数据是混合的（4 6），而有房只有9组数据是混合的（3 6），也就是说有房的分类效果更好。

现在你能更加直观地了解信息增益最大的概念了吗？

消除的不确定性最大，其实也就是尽可能地生成最“纯”的分类，用最少的步骤把这些类分完。（当然，如果只有少数“纯”结点，一大批“混合”结点，说不定混合结点的分类效果会更好，所以说，我们需要计算。）

找完了根节点，我们发现当有房=否的时候，结果不纯，还需要继续分。为了我们需要找到第二个特征，方法也是寻找信息增益最大的特征。

注意，此时我们要处理的数据不再是15组，而是当有房=否的时候剩下的混合9组：6组不同意贷款（蓝） 3组同意贷款（红）。

在不考虑特征的时候，是否同意贷款的信息熵为：

然后我们要从年龄，是否有工作和信贷情况三个特征中选择信息增益最大的。其实不用计算，光看上图我们就能发现第二个特征应该选是否有工作。

因为有工作的那些人都得到了贷款，而没有工作的那些人都没有得到贷款，也就是说用是否有工作分能够得到两个“最纯”的分类，而用其他特征，显然又会存在混合状况（请仔细看数据图）。

当数据少的时候往往可以直接就看出来，但是当数据很多的时候，还是要靠计算信息增益分类，因为人类直观得到的信息量是有限的。比如上述例子吧，通过计算发现，仅次于有房的特征并不是有工作，而是信贷情况。

所以信息论的引入是非常重要的，它通过把概率量化成信息量，使我们可以挖掘到数据更本质的规律，而这些规律有的时候是很难直接观察出来的。

接下来我们还是要亲自算一算它们各自的信息增益，看看是不是是否有工作作为特征是最好的。

以年龄为特征得到的信息增益，结果为0.2516：

以是否有工作作为特征得到的信息增益为0.9183：

以信贷情况作为特征得到的信息增益为0.527：

所以果然如我们观察得到的，以是否有工作作为第二个结点的分类效果是最好的。

也就是说虽然这批数据有四个特征，但是其实只需要用两个特征，我们就能把这些数据分类完全。

最终，我们得到了一棵拥有一个根结点，一个内部结点和四个叶节点的决策树。

如果你得到了新的数据需要预测或者分类这个人是否可以得到贷款，其实只需要看他是不是有房或者有没有工作。

所以典型的决策树算法大致就是：

1. 分别计算各个特征的信息增益，选择最大的作为结点。

2. 判断是否存在不纯分类，存在的话重复第一步，选择第二个特征，直到数据实现完全分类。

以上通过最大信息增益构建决策树的算法被成为ID3算法，细心的小伙伴可能会从上述计算过程中发现，如果一个特征下面包含很多个种类，比如如果我们把年龄细分成9类，每一类只有1~2个元素，那么它的条件熵计算下来都近似0，也就是说它的信息增益会显然倾向最大。

那么在这种情况下难道我们要选年龄作为特征分类，然后产生9个叶节点？这种分类看起来很精确，但是显然是不合理的。

所以在ID3算法的基础上又提出了改进的C4.5算法，也就是用最大信息增益比作为选择特征的条件。

信息增益比是在信息增益的基础上除以特征自己的信息熵：

以上例来看，特征自己的信息熵因为元素多，所以自然也大，通过和信息增益相除，能够弥补元素多带来的偏大倾向：

除此以外，C4.5算法和ID3算法的计算过程都是相同的。除了这两个算法，常用的还有CART算法，主要用GINI系数作为选择特征的依据（其实就是把信息增益换成了另一个概率相关的函数，选择值最小的特征）。

有的时候，由于数据本身存在很多特例的现象，所以即使采用C4.5算法，也难免会产生精确地包含了所有数据的分类情况的决策树（结构也必然复杂），但是很多特例其实是没有必要考虑的，所以这种决策树模型是过拟合的。

对于这种情况则需要对决策树进行剪枝，也就是去掉那些不需要存在的结点。

剪枝算法包含很多种，比如最简单的你可以对一批新的数据用根据历史数据建立的决策树进行分类，依靠剪枝前后的分类错误率决定是不是需要剪枝等。

本篇作为决策树原理的简单科普就不细说了。有兴趣想深入了解的各位可以阅读最后的参考资料。

好了，今天的决策树原理就讲到这里，有问题或者建议的小伙伴们也请给我们留言。

参考资料：

1.《统计学习方法》李航。

2.《决策树1-ID3》 http://blog.csdn.net/app_12062011/article/details/51969224

3.《决策树剪枝原理与CART算法》http://blog.csdn.net/u014688145/article/details/53326910

《极简科普》系列文章

下雨天到底要不要打仗？极简图解入门隐马尔科夫模型

极简图解入门隐马尔科夫模型第二弹，该来的总是要来的

巧克力里到底有没有红包？极简图解朴素贝叶斯分类

极简图解最大熵模型，其实没有你想的那么复杂

关注我们，一起进步！

END