大话系列|决策树—相亲？怎么说？

↑关注+星标，听说他有点东西

全文共3123字，阅读全文需16分钟

情景一：留学归来韩梅梅

都说女大十八变，确实不假，用在韩梅梅身上更甚贴近。

韩梅梅：留学归来，金融硕士，名企上班，不过她最近却遇到了烦心事

韩妈妈与韩爸爸眼看女儿年龄也不小，又刚从国外回来，国内认识的朋友也不多，影响找对象啊！

两老人在着急的同时也发动亲戚朋友帮助张罗一二。

俩老人心里盘算着：首先通过亲戚朋友确定50个男孩子，条件不能比我们家梅梅差，要人品好，有房有车，工作稳定。

然后从这50个人里面筛选一下，长相最好也要能配得上梅梅

最后剩下的人就拟个名单出来。

按照二八法则，最终选出10个男孩子，应该就是这50个人中佼佼者了，韩爸妈计划完心里美滋滋

在被韩妈妈的彻夜长谈之后，韩梅梅决定去挨个见见爸妈选的10个男孩子。

……

……

眼看10个男孩子都快见完了，韩梅梅每次回来的心情却越来越差了

问又不敢问，韩妈妈决定去找自己的多年好闺蜜许媒婆支支招

情景二：媒婆许姨心憔悴

许媒婆：韩妈妈闺中密友，人称媒婆中的智多星

不愧是专业媒婆，面对好闺蜜女儿的问题，许媒婆给出了这样的建议。

许媒婆：既然是给孩子找对象，那肯定不能依你们的标准来啊

许媒婆：而且你的亲戚朋友介绍的男孩子，也都在你们那个圈子里，50个人和5个人没啥区别啊

韩妈妈恍然大悟，果然是越着急越误事啊，都忘了征求梅梅的意见，赶忙去将梅梅带过来

韩梅梅大呼无奈，却还是被妈妈逼着来见许媒婆

韩梅梅：（羞涩一笑）害，其实我的标准挺简单的，有上进心进行。工作可以不稳定，但是可以一起奋斗嘛，可以没房没车，这个以后总会有的嘛，最好能热爱生活一些，不然老是工作多无趣啊（说到这，韩梅梅不禁想到了一个人，这次他应该有机会出现在名单里面了吧，嘿嘿）

韩妈妈与许媒婆相视会心一笑，孩子长大了啊！

许媒婆人缘广，资源多，掏出小本本准备从1000个男孩子中拟一个名单出来。

许媒婆：看，树图我都画好了，我们按照这个去筛选，名单上的保准是梅梅喜欢的

韩妈妈：什...什么图？

许媒婆：高科技图，我干儿子教我的，保准没错

时间很快过去了

……

……

一个上午过去了，两人只选了三分之一，还有600多男孩子等着被选择

情景三：决策树来斗芳菲

许媒婆：你看我这个傻脑筋，费这功夫干嘛。

说罢，许媒婆从包里拿出她的ipad，打开了一个软件，将韩梅梅的标准输进去

十秒不到，名单拟出来了，恰好李雷雷也在名单里面。

韩妈妈：嚯，你这是什么软件？这么厉害，快告诉我怎么弄的

许媒婆：我干儿子教我的，这是通过决策树算法算出来的，神奇着呢，来我给你讲讲

我先给你介绍一下决策树：

根据给定结果的样本数据集构建一个决策树，使它能够对未知结果的数据进行预测，对未知样本进行正确的分类

决策树是一个：有监督的分类算法

决策树的构造包括三个过程：特征选择、决策树生成和决策树剪枝

再给你说几个很重要的概念，你认真听

信息纯度：即分歧程度。纯度越高，分歧越小，越容易确定。

信息熵：表示信息的纯度（不确定度）。需要注意的是，信息熵的值越小，表示信息的纯度越高（函数性质决定）

信息增益：表示样本纯度的提升（下降）。信息增益越大，即提升越高，越容易划分。

就这几个概念，你先理解理解

韩妈妈：好了好了，可以开始了吗，我都等不及了！

许媒婆：

特征选择

先给你提几个问题，看看你有没有天赋

• 问题一：既然是一个树，那树的根节点应该怎么确定？

• 问题二：怎么计算每个特征对树的影响？

韩妈妈：你还是直接说答案吧，我这笨脑筋

我们是要构造一棵树，所以上面这两个问题至关重要，第一个问题是如何确定第一步，第二个问题是接下来每一步怎么确定

当我们知道第一步选什么，然后确定每一个分叉点怎么选特征，这棵树不就出来了吗？

在整个决策树的特征选择中，就是一个寻找纯净划分的过程。

而如何寻找一个纯净的划分，即基于纯度来划分，就是整个决策树的核心

而经典的“不纯度”的指标有三种，分别是信息增益（ID3算法）、信息增益率（C4.5算法）、基尼指数（CART算法）

韩妈妈：这不就是上面说的几个概念嘛，我可得好好听听

首先来看ID3 算法

ID3 算法计算的是信息增益，即如果我进行特征的划分，肯定是选择纯度提升的特征

前面我们也提过，纯度越高，表示分歧越小，划分效果越好

嗯，这里不得不放一个数学公式进来了

emmm，还得再放一个

稍微解释一下：

• Gain(D,a)表示a特征的划分可以带来的纯度提升，其中a作为D节点的属性选择，Di表示D节点子节点

• Ent(D)表示D节点的信息熵，p(i|t)表示在t的样本集中i出现的概率

其实就是父亲节点的信息熵减去所有子节点的信息熵，只不过在选取子节点的时候有一个选中的概率

所有我们在计算的过程中需要计算下面这些：

• 当前节点(父节点)的信息熵

• 当前节点的所有子节点的信息熵

• 在当前节点确定的条件下选中相应子节点的概率

要不我再举个简单的例子?

韩妈妈：好啊，刚好我听的有点迷糊

这几个特征要构造一棵决策树，考虑一下下面两个问题

• Q1：如何确定根节点

• Q2：如何选择子节点？例如选择了天气之后，如何选择下一个节点?

根节点的确定：

依次计算四个特征（天气、温度、湿度、刮风）下对结果的信息增益

每个子节点的信息熵可以这样计算：

代入公式就可以计算通过天气进行特征划分的信息增益Gain(D,天气)  = 0.02

同样的方法计算出温度、湿度和刮风特征的信息增益，选择信息增益最大的作为根节点（这里温度的信息增益最大）

子节点的选择：

这一步的重点是确定子节点

上一步已经确定根节点是温度，特征分别是：温度高 & 温度中 & 温度低

然后需要确定每个特征的子节点，即温度高的子节点：天气 & 湿度 & 刮风；温度中的子节点…温度低的子节点…

同样的计算规则计算三个子节点的信息增益，选择信息增益最大的

重复同样的步骤

许媒婆：你觉得上面的ID3算法适用于所有情况吗？

韩妈妈：我觉得应该、可能...都适用吧？

并不是的，当节点的分支特别多，每个分支仅有一个样本时，此时节点的信息增益会很大，但是训练出来的模型只适用于当前样本集，也就是过拟合现象。

你可以想象，两个节点A、B，都有10个样本，节点①划分为两个分支（5,5），节点②划分为10个分支（1,1…,1），此时节点②的信息增益是远大于节点①的

所以啊：ID3会对取值数据较多的属性有所偏好

C4.5算法

科学家是不会允许这样的问题出现的，于是在ID3的基础上做了改进，形成了C4.5算法

还是要放一下公式

你可以理解成，在信息增益的基础上加了一个参数，这个参数可以有效的弥补信息增益的缺点

因为当属性取值数据较多，会很小，此时的信息增益率也会降低

许媒婆：这个时候的C4.5一定是正确的吗？

韩妈妈：emmm…

万事不绝对，这个时候C4.5也存在一些问题

我们说属性取值数据较多，会很小

但是当属性取值数据较少，又会很大

所以C4.5会对取值数据较少的属性有所偏好

韩妈妈：有解决方法吗？

有，从候选划分属性中找出信息增益高于平均水平的，然后在选择信息增益率最高的

当然，上面这两个算法都是基于信息增益来计算的，我们还有一个更厉害的算法：CART算法

而且，就算我们的决策树出现问题，还可以通过剪枝进行优化，方法多着呢。

韩妈妈：嗯啊哦好，还是你这个决策树靠谱（就是有点难）。刚想起来我还有点事，先走了啊，改天请你吃大餐！！

韩妈妈落荒而逃……

许媒婆会心一笑

写在后面的话

大话算法系列第一篇，打算换个风格来写文章

算法很枯燥，少有人看的下去，但这又是进阶必会的技术栈

小一想着尽可能的用大白话去写，除了必要的数学公式会贴出来

虽然没有数学可能会少一些内容，很不严谨，但却可以让新手尽快入门

建议大家私下抽时间看看数学推导，看看延伸内容，很有必要

算法系列文章每篇都会紧跟着一个实战项目，从数据清洗到模型优化，也算是对以前的所有文章有一个很好的总结应用

下节介绍CART算法和剪枝优化，希望你不要和韩妈妈一样落荒而逃

我是小一，我们下节见

好巧啊，你也读到这了！    

点个在看让小一看到你