决策树，听名字就知道跟树有关，而且很容易猜到是一种类似依靠树形结构来辅助决策过程的策略。所以重点就是如何构建这个树，如何依次选取树的各个节点，以便能在测试集中有较好的表现。
信息熵与信息增益说到如何选取节点，就要引入信息熵的概念。我以前一看到“熵”这个字就头疼，以为是跟高深的物理学相关，其实很好理解，简单说就是纯度。假设有一罐混合了氧气和二氧化碳的气体：
我们通常会说这罐气体不纯，那么怎么来度量这个纯度呢？假设氧气占20%，二氧化碳占80%，则可以看做是二氧化碳里混入了少量的氧气，二氧化碳相对纯一些；如果看做是氧气中混入了大量的二氧化碳，那么这个氧气也太不纯了。我们在这里所讨论的纯度，都是针对某一特定对象而言，而又不适用于这个系统里的其他对象。如果把这个罐子当做整个系统的话，信息熵就可以看做是系统级的纯度。一般这样度量信息熵，系统纯度越低，信息熵越大，反之，系统纯度越高，信息熵越小。如果罐子里只剩一种气体，则信息熵为0。
信息熵的计算公式如下：
其中k表示系统中特征的数量，p(xi)表示每个特征再系统中的占比。所以我们可以算出此时的信息熵为：
假设由于保存不当，罐子中混入了一种有色气体（比如二氧化硫）：
假设目前三种气体的占比为：氧气15%，二氧化碳50%，二氧化硫35%，根据信息熵的理论，现在整个系统的信息熵应该比原先更大了（纯度降低）。我们不妨再算一下此时的信息熵：
可以看到信息熵增大了，符合之前的理论。那么如果我们现在要分离这三种气体，就需要选择一个标准，或者说，选择能够区分这三种气体的特征进分离。最直观的特征就是有色跟无色：
如果按这个特征对系统进行划分，则会将系统划分为有色气体跟无色气体两个子集。划分后的系统，已经由最初较为混沌的状态（三种气体混合）变成了有色跟无色两部分，所以，此时的信息熵就变成了有色子集的信息熵与无色子集信息熵的加和。但考虑到这两类气体在系统中的占比，需要将占比作为子集信息熵的权重，所以此时的信息熵为：
所以经过对气体颜色这一特征的划分，系统的信息熵由1.125变成了0.418，说明系统纯度有所提升。为了准确的表示提升的具体情况，就把这个提升空间叫做信息增益。
写成标准式：
其中，D表示整个样本数据集，a表示所选的用户划分系统样本的特征，Ent(D)表示划分前的信息熵，|Di|表示划分后的每个子集的样本个数，|D|表示划分前的样本总数，Ent(Di)表示每个子集各自的信息熵。后面一项实际上就是子集信息熵的期望。
从公式可以看出，如果选取不同的特征，划分后的信息熵可能会有大小之分，而系统当前的信息熵是不变的，所以划分后的信息熵如果越小，信息增益就越大，说明系统纯度提升的幅度就越大，反之亦然。所以，我们就需要遍历所有已知特征，找出能够提升幅度最大的那个特征，作为首选的划分特征。
至此，就把信息熵和信息增益的概念介绍清楚了，虽然有点啰嗦，但是应该是比较通俗易懂的。我们上面介绍的这种选取划分特征的算法也叫做ID3算法。下面来看西瓜书中对应的例子。 ID3算法