原文链接
“决策树是一颗好树，是一颗可以帮我们做决策的树。”
**
所有的机器学习算法中，决策树应该是最友好的了。它可以在整个运行机制上很容易被人翻译成人们能看懂的语言，也因此被称为”白盒模型”。
它不像神经网络这类算法喜欢用隐藏层搞暗箱操作，它比较光明磊落，最后训练出来的树，容易被别人所理解。

直观理解

假设我们开个小店，我们想看一看我们小店一天的销量的高低到底和什么事情有关系？
我们凭经验觉得销量高低可能会和天气好坏、是否周末、是否有促销活动这个方面有关系，我们把这些数据记录下来，如下图所示。

那如果要人工分析这个事情，应该怎么办？
我们先从是否周末入手，按“是否周末”分成的两类；然后在是周末的所有的里面再看天气好坏，如果发现是周末、并且天气好这两个条件同时满足的情况下，销量一定好。
更进一步地，就可以得到下面这样一个图。

上图中，有圆角矩形、矩形、线段。
你看那个圆角矩形，它就已经是最后的结果了，不再往下了，这一类东西呢，在决策树里叫做叶节点。
那个矩形呢，总是要往下分，并不是最终的结果，它叫做中间节点（或内部节点）。
那些带有文字的线段（一般使用有箭头的有向线段），线的一端连的是中间节点、另一端连的是另一个中间节点或叶节点，然后线段上还有文字，它叫做边。
到这里，你可能已经看出来了。所有的内部节点都是自变量、叶节点是因变量的值，而边呢是自变量可能的取值。有了这棵树，那我们知道了明天天气情况、是否周末、是否有促销活动我们就可以预测明天的销量高低，可以提前备货。或者说，如果我们库存有积压，我们应该怎样提高销量尽快把货销出去。
自变量的取值可能不止两种，比如判断一个学生是不是好学生，他的成绩就是一个比较重要的自变量，而成绩的可能取值是[0,100]。那成绩节点就会有100条边出来么？也不一定，前面的文章我们说过，这个时候需要对成绩这个量进行离散化，可能会分成“不及格”D、“及格”C、“良好”B、“优秀”A等。

算法描述

从上述描述知道，决策树从根节点到叶节点，越往下，最后那个因变量的取值越单一。也就是说，越往下的节点它因变量取某一个值的可能性越大，到达叶节点的时候这个可能性达到最大。
我们用最直接、最笨拙的步骤可以实现这个事：

• 1.选择一个自变量作为节点，从一个边引出一个取值（属性值）看这个值对应的变量的值若为空或者单一值，边的另一端生出一个叶结点；
• 2.否则，对生出一个内部结点，即测试结点；
• 3.在2的基础上选择新属性进行划分，直至得到条件1。大家可以对照上面步骤的说法，把01中介绍的例子画成决策树的样子。

上面这种朴素的算法很容易想到，但是太容易得到的它往往不够美好。如果自变量很多的时候，我们该选哪个作为根节点呢？选定了根节点后，树再往下生长接下来的内部节点该怎么选呢？针对这些问题，衍生了很多决策树算法。
我们常见的有ID3、C4.5、C5.0等不同的算法来绘制决策树，如下表所示：

ID3算法

ID3算法在上述中介绍的那种朴素的决策树算法（CLS）的基础上解决了属性选择的问题。
内部节点的每个属性值都会引出一条边来，那么到底哪个好呢？这里要引入一个叫做”信息增益”的概念。
信息增益这个事可以用一大堆公式来证明，也可以先有一个感性的认知。要知道，我们的目标就是希望让节点的某个属性能让我们更有信心预测因变量的取值。以最上面中的例子来所，如果”是否周末”这个节点取是”能让我们更容易得出销量高这个结论，那它的信息增益就高。
如果再往下深究，要想了解信息增益还要知道熵的概念。

这个公式看着挺麻烦的，但是就是为了定量地描述一件事情：一个事情它的随机性越大，越难以预测。具体来说这个概率p越小，最后熵越大(也就是信息量越大)，极端情况下：一件事情发生的概率为1，它的熵就变成了0.
熵越大，随机性越大，如果能准确预测它的取值意义就很大；反之，就没啥意义了。比如，你如果能预测一个彩票的中奖号码就发达了；但是，如果你能预测明天太阳从东方升起则毫无价值。这样一个衡量信息价值的事情，就可以由熵来表示。
那如果我们在进行决策树绘制的时候，如果能够迅速的让这个熵变小，是不是意味着我们可以迅速地找到那个概率接近于1的叶节点呢？事实就是这样，就是找所谓的信息增益最大的那条路。
那这个增益是谁和谁的差呢？它是自变量在取确定的值之前的熵与取确定之之后的熵的这个差值。好比，在不知道明天是否天气好的情况下熵是H，知道了明天天气好坏之后的熵为H，那么H-H就是这个信息增益。条件熵的计算公式为：

其中，为后验熵，它们的具体算法看下面的例子。

更容易理解的式子

假设我们记录了某个学校14届运动会按时举行或取消的记录，举行或取消的概率分别为：，那么它的信息熵为：。
我们同时记录了当天的天气情况，发现天气好坏和校运会举行还是取消有关。14天中，5次晴天（2次举行、3次取消）；5次雨天（3次举行、2次取消）；4次阴天（4次举行）。相应的晴天、雨天和阴天的后验熵。

知道了天气情况后的校运会的条件熵为：

那么相对应的在没有天气情况这个条件前后的信息增益为：

那相对应的ID3的算法很容易找出来：

• 1.在所有的自变量里面找一个信息增益最大的作为节点；
• 2.节点的每种取值看它的熵，如果熵为0，对应一个叶子节点

比如下面这样的一个过程，可以画出决策树：