从“女神相亲记”带你走进决策树（机器学习经典方法）

本文内容来自于《从零开始：机器学习算法与实践》这本书，强烈推荐！！

1.决策树算法概述

决策树算法是机器学习中很经典的算法，它既可以作为分类算法，也可以作为回归算法，但是其使用频率最高的场景还是分类问题。决策树算法本质是通过属性分类，进而对整个特征空间进行划分，进而区别出不同的分类样本。

2.典型的决策树是什么样子的

我们进行机器学习的目的是通过对历史样本数据的学习，找到一个模型（学习的结果）​，能够总结原来的样本的规律并且对于未知的样本进行预测。一种思路就是线性回归或者逻辑回归，通过寻找特征变量和目标变量之间的关系表达式；还有一种思路就是通过模拟人们日常生活进行决策的这个过程，而这个模拟决策的过程就是机器学习里面的决策树模型；

决策树通过训练数据构建一种类似于流程图的树结构来对问题进行判断，它与我们日常问题解决的过程也非常类似。例如一个女生在中间人给她介绍了潜在相亲对象的情况后，她需要做出“是否要去见面相亲”的决策。其实这个决策经常会分解成为一系列的“子问题”​：女生先看“这个人学历/学位如何”​，如果是“学历/学位大专以上”​，那么女生再看“这个人身高如何”​，如果是“身高一米七以上”​，那么女生再看“这个人月收入如何”……经过一系列这样的决策，女生最后做出决策：愿意去相亲。决策过程如图所示:

我们假设这个女生是一个女神​，有很多中间人给她介绍对象。中间人给她介绍相亲对象的信息包括学历/学位、身高、收入、长相、性格、家庭背景、工作地点、工作单位等。​“女神”在听完中间人对相亲对象的介绍后，同意去见其中的一部分人，拒绝去见另外一部分人。

（1）这个时候如果我们发现女神对于所有这个潜在的相信对象都件或者都不见，这个时候的决策就是非常简单的；

（2）如果女神对于所有的这个潜在的相亲对象部分见面，这个时候我们就需要划分情况进行考虑了；

如果把“女神”是否见面的决策看作一棵决策树的话，这棵决策树会有多种可能性：根节点可能是“学历/学位”​“身高”​“收入”​“长相”​“性格”​“家庭背景”​“工作地点”​“工作单位”等等因素，同样内部节点和叶节点也有多种可能性。机器学习决策树建模的目的，就是找到一棵具体的决策树，从而帮助我们快速准确地做出判断。

3.根节点的选择–信息增益

如何选择根节点？这个选择的规则就是谁的信息增益（消除决策的不确定性）越大，谁就越有可能成为根节点；

下面举个例子说明一下：

女神见了博士学历之上的人，但是不见不是学历之下的人；

女神见了身高高的人，也见了身高低的人；

这个时候如果让你去选，在上面的两个因素里面，你会把谁作为根节点。我想一定是学历因素，因为我们通过一个人学历就可以判断我们的女神会不会去见面，但是通过身高就无法很确定（因为可能见也可能不见），对于学历这个因素，我们可以消除这个不确定性。所以和身高相比，学历的信息增益就会更大（通过这个可以直接判断：是或者否），这个是一个比较通俗的解释；

为了更加透彻的理解这个概念，我们学习一下信息，信息熵，信息量的概念：

4.信息和信息量

4.1如何理解信息

信息就是不确定性的消除：

本来明天可能下雨，也可能不下雨，但是气象局告诉你：明天不下雨，这样就消除了不确定性，所以“明天不下雨”这就是信息；

4.2如何计算信息量

信息量的量化计算最早也是由哈特莱提出的:消息的可能情况取对数得到的结果就是信息量；

$$ I=\log _2m\left( m\text{表示可能的情况} \right) $$

下面举例说明：

第一个情况： 大龙的性别为男：

$$ I_1=\log _22=1 $$

第二个情况： 大龙的年龄是43岁”​（假设人类最长寿命为128岁）：

$$ I_2=\log _2128=7 $$

上面的性别只有男和女（不考虑特殊情况，不要杠），所以是对于2取对数，年龄啊的话，要求是最大128，所以有128个情况，所以就是对于128取对数，因为7>1，所以情况二的这个信息量更大；

4.3信息论里面的计算方法

上面的这个方法是哈特来的计算方法，这个方法默认我们的所有的可能情况出现的这个概率都是一样的，但是现实情况下，一个事件可能得结果并不是等可能得概率出现；如何把这个概率的情况包含进去，信息论里面给出来了更加科学的计算方法；

$$ H\left( X_i \right) =-\log _2p\left( p\text{表示的就是事件发生概率} \right) $$

Xi对应的就是具体的时事件，p就是这个事情发生概率，下面通过例子解释一下：我们统计的是历史上面所有叫做“大龙”的人的性别发现10个人中有9个都是男性，那么根据信息论的公式

（1）发现10个人中有9个都是男性，那么根据信息论的公式

$$ H=-\log _2p=-\log _20.9=0.152 $$

（2）发现100个人中有90个都是男性，那么根据信息论的公式

$$ H=-\log _2p=-\log _20.99=0.0145 $$

（3）发现1000个人中有999个都是男性，那么根据信息论的公式

$$ H=-\log _2p=-\log _20.999=0.00144342 $$

（4）发现10000个人中有9999个都是男性，那么根据信息论的公式

$$ H=-\log _2p=-\log _20.9999=0.000144277 $$

总结： 某个事件出现的先验概率越大，那么“告知这个事件即将发生”所携带的信息量越小（根据上面的计算结果是显而易见的）。

4.信息熵是什么

信息熵是信息论创立者香农受到热力学“熵”这个概念的启发而创立的，它度量了信源的不确定性程度；

信息量度量的是某一个事件发生时的信息量，那么信息熵表示的就是所有可能结果的信息量的期望值。

信息熵公式：就是概率论里面的求解期望（需要一点基础）Xi表示的就是具体时间，外面加上p就是对应时间的概率

$$ H\left( X \right) =-\sum_{\boldsymbol{i}=1}^{\boldsymbol{n}}{\boldsymbol{p}\left( \boldsymbol{Xi} \right) \log 2\boldsymbol{P}\left( \boldsymbol{X}{\boldsymbol{i}} \right)} $$

还是上面的例子，我们计算一下这个信息熵，实际上就是求解期望：（下面为了这个公式的美观，我把这个公式前面的负号挪动了这个对数的身上，但是这个不影响计算的结果）

（1）发现10个人中有9个都是男性，那么根据信息论的公式

$$ H=0.9*\left( -\log _20.9 \right) +0.1*\left( -\log _20.1 \right) =0.468996 $$

（2）发现100个人中有90个都是男性，那么根据信息论的公式

$$ H=0.99*\left( -\log _20.99 \right) +0.01*\left( -\log _20.01 \right) =0.0807931 $$

（3）发现1000个人中有999个都是男性，那么根据信息论的公式

$$ H=0.999*\left( -\log _20.999 \right) +0.001*\left( -\log _20.001 \right) =0.0114078 $$

（4）发现10000个人中有9999个都是男性，那么根据信息论的公式

$$ H=0.9999\left( -\log _20.9999 \right) +0.0001*\left( -\log _20.0001 \right) =0.00147303 $$

通过上面的这个过程，我们就可以发现，第四个情况下的这个信息熵是最小的，也就是在这个情况下，大龙的性别是什么这件事情的确定性是最高的，信息熵实际上描述的就是这个系统的纯净度的指标；

上面的这个信息熵就是事件的结果的不确定性程度，这个事件不确定性的变化，就是信息增益：即信息增益是信息熵的变化程度

5.实战：根据信息增益生成决策树

上面一直在说这个女神相亲的这个例子，因此下面我们通过这个女神的相信对象的这个相关的数据，看一下上面介绍的理论如何运用，生成一棵决策树：

下面的这个是相关的历史数据（我简单的截一下图）

接下来，看一下这个信息增益的计算过程：

5.1计算样本信息熵

样本信息熵计算公式：

见面概率：9/20（根据表里面的数据）

不见面的概率：11/20（根据表里面的数据）

带入公式：

5.2计算属性信息熵

下面的这个所有的log都是以2作为底数，希望大家理解（就是套公式）计算

5.3计算属性信息增益熵Gain

学历学位这个属性的信息增益就是第一位计算的这个样本的信息熵和我们的第二问里面的计算的期望信息熵的差值：

Gain(X,学历）=0.9928-0.78328=0.2095

剩下的几个我们可以按照上面的方法依次进行计算：

Gain(X,长相）=0.9928-0.2345=0.7583

Gain(X,身高）=0.9928-0.7132=0.2796

Gain(X,收入）=0.9928-0.9642=0.0286

可见：长相的信息增益最大（对于是否见面的估计提供的确定性的贡献最大），因此这个就是根节点

5.4确定根节点和各个节点

画出来以长相作为根节点的决策树：

集合X1中序号为{1,2,5,8,10,12,13,14,15,16}的10个样例，可用属性集合为{学历/学位，身高，收入}。

我们基于X1计算各属性的信息增益（上面5.3计算的信息增益是在20个数据的基础上面进行的，而下面的这个是在x1也就是10个数据的基础上面，没进行一次分类，对应的这个样本的数据就是发生变化，因为我们要的是符合条件的，在长相=帅气这个条件下面，20个里面只有10个是符合要求的）但是计算方法和5.3里面是一样的；

Gain ( X1，学历/学位)=0.4690-0.2=0.2690

Gain ( X1，身高)=0.4690-0.2=0.2690

Gain ( X1，收入)=0.4690-0.275 5=0.1935

在x1之下，我们的学历和身高对应的信息增益是一样的，我们任意选择一个就可以了（我下面的这个是使用的身高），按照这个分支的结构依次进行下去即可： 下面的这个就是基于信息增益生成的决策树：

6.总结

上面的这个过程只是为了帮助没有学习过决策树的同学理解相关的概念和计算的方法，这个计算过程还是有些复杂的（不可否认，我亲自经历了整个流程），但是我相信python里面一定有相关得第三方库供我们进行使用（虽然我还没有学到），之所以会觉得很复杂，是因为我们第一次使用，相信多见几次，多用几次，这些都不是啥问题啦；

这个决策树只是机器学习的冰山一角，更加详细的内容需要我们去学习，我也很想大家推荐，我文章开始的那个书籍，真的让我受益匪浅，真心希望对大家有所帮助~~

创作不易，您的支持是我前进的最大动力~~