决策树的算法可谓是贴近我们的生活，通过下面的案例，你就会发现我们每天都在有意无意的使用着决策树算法（好厉害的样子）。
小明同学每天早上都要去学校，可步行、乘公交和坐隔壁老王叔叔的车（皮一下很开心）。这时，小明就开始做决策了：首先看天气，不下雨时就选择步行去学校；下雨时就看隔壁老王叔叔是否有空，有空就乘老王的车去学校，没空就选择乘公交去学校。如图所示。
决策树定义
通过上述案例，就可以对决策树下定义了：上图就是决策树（嗯。。。有点敷衍）。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性（天气，是否有空），叶节点表示一个类（步行、乘公交和坐隔壁老王叔叔的车）。
决策树算法原理
那怎么通过决策树算法来构造这棵树呢？（难道是上帝之手么？）上述案例较简单，我们现在提出一个很经典的案例，如图所示，我们首先到底是通过天气、湿度还是风级来进行决策了？这里就要提出熵和信息增益。
熵
首先，我们看什么是熵。简单来说，熵是描述事物的混乱程度的（也可以说是不确定性）。例如：中国足球进入世界杯，这个不确定性可能是0，所以熵可能就是0；6面的色子的不确定性比12面色子的要低，所以熵也会比其低。现在就来看熵的公式：H = -∑<sup>n</sup><sub>i=1</sub>p(xi)log<sub>2</sub>p(xi)
那6面色子的熵：1/6*log<sub>2</sub>1/6的6倍，也就是2.585
以此类推，那12面的熵就是：3.585
最后，我们计算下该案例的信息熵：不打球为5，打球为9，因此熵计算为：
```
-(5/14 * log(5/14,2) + 9/14 * log(9/14,2))
0.940
```
信息增益
到底先按哪个特征划分数据集呢?我们有个原则，就是将无序的数据变得有序，换句话说，就是让熵变小，变的越小越好。而信息增益就是划分数据集前后熵的变化，这里就是要让信息增益越大越好。
我们以天气为例，计算划分后的信息增益：
- 晴天时：2/5打球，3/5不打球，熵为：
```
-(2/5 * log(2/5,2) + 3/5 * log(3/5,2))
0.971
```
- 阴天熵：0
- 雨天熵：0.971
天气为晴天、阴天和雨天的概率为5/14，4/14和5/14，所以划分后的熵为：5/14 * 0.971+4/14 * 0+5/14 * 0.971得0.693，信息增益为0.940-0.693为0.247，同理可以求出其他特征的信息增益。
这里的天气信息增益最大，所以选择其为初始的划分依据。
选择完天气做为第一个划分依据后，能够正确分类的就结束划分，不能够正确分类的就继续算其余特征的信息增益，继续前面的操作，结果如图所示。
