一篇文章搞懂机器学习中决策树的那些事儿
“ 决策树是一颗好树，是一颗可以帮我们做决策的树。”
所有的机器学习算法中，决策树应该是最友好的了。它呢，在整个运行机制上可以很容易地被翻译成人们能看懂的语言，也因此被归为“白盒模型”。
它不像神经网络这类算法喜欢用隐藏层搞暗箱操作，它呢相对较为磊落，最后训练出来的树，比较容易为人所理解。
01
—
直观理解
假设我们开个小店，我们想看看我们小店某一天的销量的高低到底和什么事情有关系？
我们凭经验觉得销量高低可能会和天气好坏、是否周末、是否有促销活动这几个方面有关联，我们把这些数据记录下来，如下图所示。
那如果要人工分析这个事，该怎么办呢？
我们先从是否周末入手，按“是否周末”分成的两类；然后在是周末的所有的里面再看天气好坏，如果发现是周末、并且天气好这两个条件同时满足的情况下，销量一定好。
更进一步地，就可以得到下面这样一个图。
上图中，有圆角矩形、矩形、线段。
你看那个圆角矩形，它就已经是最后的结果了，不再往下了，这一类东西呢，在决策树里叫做叶节点。
那个矩形呢，总是要往下分，并不是最终的结果，它叫做中间节点（或内部节点）。
那些带有文字的线段（一般使用有箭头的有向线段），线的一端连的是中间节点、另一端连的是另一个中间节点或叶节点，然后线段上还有文字，它叫做边。
到这里，你可能已经看出来了。所有的内部节点都是自变量、叶节点是因变量的值，而边呢是自变量可能的取值。有了这棵树，那我们知道了明天天气情况、是否周末、是否有促销活动我们就可以预测明天的销量高低，可以提前备货。或者说，如果我们库存有积压，我们应该怎样提高销量尽快把货销出去。
自变量的取值可能不止两种，比如判断一个学生是不是好学生，他的成绩就是一个比较重要的自变量，而成绩的可能取值是[0,100]。那成绩节点就会有100条边出来么？也不一定，前面的文章我们说过，这个时候需要对成绩这个量进行离散化，可能会分成“不及格”D、“及格”C、“良好”B、“优秀”A等。
那，我们整理上面图里那样的决策树的时候，发现还有两个问题：
- 我们选哪个作为根节点？
- 根节点选定后，我们怎样再选中间节点？
- 最后的叶节点又是怎样确认的？到什么程度呢？
- 我们怎样把这个事弄的更细致，能够让计算机来实现。
02
—
算法描述
从01中的描述知道，决策树从根节点到叶节点，越往下，最后那个因变量的取值越单一。也就是说，越往下的节点它因变量取某一个值的可能性越大，到达叶节点的时候这个可能性达到最大。
我们用最直接、最笨拙的步骤可以实现这个事：
- 选择一个自变量作为节点，从一个边引出一个取值（属性值）看这个值对应的变量的值若为空或者单一值，边的另一端生出一个叶结点；
- 否则，对生出一个内部结点，即测试结点；
- 在2的基础上选择新属性进行划分，直至得到条件1。
大家可以对照上面步骤的说法，把01中介绍的例子画成决策树的样子。
上面这种朴素的算法很容易想到，但是太容易得到的它往往不够美好。如果自变量很多的时候，我们该选哪个作为根节点呢？选定了根节点后，树再往下生长接下来的内部节点该怎么选呢？针对这些问题，衍生了很多决策树算法。
我们常见的有ID3、C4.5、C5.0等不同的算法来绘制决策树，如下图所示：
限于篇幅，我们只讲ID3算法，不过你理解了ID3其它的也就很容易看明白了。
03
—
ID3算法
ID3算法在02中介绍的那种朴素的决策树算法（CLS）的基础上解决了属性选择的问题。
内部节点的每个属性值都会引出一条边来，那到底哪个好呢？这里要引入一个叫“信息增益“的概念。
信息增益这个事可以用一大堆公式来说明，也可以先有个感性的认识。要记住，我们的目标呢就是希望让节点在去某个属性的时候能更快生长出叶节点。换句话说，就是节点的某个属性能让我们更有信心预测因变量的取值。以01中的例子来说，如果”是否周末“这个节点取”是“能让我们更容易得出销量高这个结论，那它的信息增益就高。
如果再往下深究，要想了解信息增益还要知道熵的概念。
这个公式看着挺麻烦的，其实就是为了定量地描述一件事实：一个事情它的随机性越大就越难预测。具体来说这个概率p越小，最后熵就越大（也就是信息量越大），如果极端情况一件事情概率为1，它的熵就变成0了。
熵越大，随机性越大，如果能准确预测它的取值意义就越大；反之，就没啥意义了。比如，你如果能预测一个彩票的中奖号码就发达了；但是，如果你能预测明天太阳从东边升起来则毫无价值。这样衡量一个信息价值的事，就可以由熵来表示。
那如果我们在进行决策树绘制的时候，如果能够迅速的让这个熵变小，是不是就意味着我们可以迅速的找到那个概率接近1的叶节点了呢？事实就是这样，就是好所谓的信息增益最大的那条路。
那这个增益是谁和谁的差呢？它是自变量在取确定的值之前的熵与取确定值之后的熵的这个差值。好比，在不知道明天是否天气好的情况下熵是H1，知道了明天天气好坏之后的熵为H2，那么H1-H2就是这个信息增益。条件熵的计算公式为：
其中，H(X|yi)为后验熵，它们的具体算法看下面的例子。
再来看一个更容易理解的例子：假设我们记录了某个学校14届校运会按时举行或取消的记录，举行或者取消的概率分别为：9/14、5/14，那么它的信息熵为：
我们同时记录了当天的天气情况，发现天气好坏和校运会举行还是取消有关。14天中，5次晴天（2次举行、3次取消）、5次雨天（3次举行、2次取消）、4次阴天（4次举行）。相对应的晴天、阴天、雨天的后验熵
那知道天气情况后校运会的条件熵为：
那么相对应的在有没有天气情况这个条件前后的信息增益就是：
那相对应的ID3的算法很容易就可以想出来了：
- 在所有的自变量里面找一个信息增益最大的作为节点；
- 节点的每种取值看它的熵，如果熵为零，对应一个叶子节点
比如下面这样的一个过程，可以画出决策树（参考1）。
04
—
总结
有几个比较有意思的概念：熵（先验熵）、后验熵、条件熵、信息增益。以及对应的ID3算法。
参考：
- https://blog.csdn.net/robin_Xu_shuai/article/details/74011205
- https://zhuanlan.zhihu.com/p/26486223