经过前面几章的介绍，我们已经介绍过了3个分类算法模型，包括逻辑回归、K近邻和朴素贝叶斯。接下来我们将介绍下一个分类算法模型——决策树（Decision Tree）。整个第8章的学习路线如图8-1所示，首先我们将介绍决策树的基本思想和它的可视化过程，然后介绍ID3和C4.5这两种经典的决策树生成算法及其剪枝过程的原理，最后再来介绍如何从零实现决策树算法。
8.1 决策树的基本思想#
8.1.1 冠军球队#
一说到决策树其实很多读者或多或少已经使用过，只是自己还不知道。例如最简单的决策树就是通过输入年龄，判读其是否为成年人，即if age >= 18 return True，想想自己是不是经常用到这样的语句。关于什么是决策树这里先来看一个例子。
假如我们错过了某次世界杯比赛，赛后我们问一个知道比赛结果的人“哪支球队获得了冠军”？但是对方并不愿意直接说出结果，而是让我们自己猜，且每猜一次对方都要收一元钱才肯告诉我们是否猜对了。现在的问题是要掏多少钱才能知道哪支球队是冠军球队呢？
现在我们可以把球队从1到16编上号，然后提问： “冠军球队在1~8号中吗？”。假如对方告诉我们猜对了，我们就会接着问： “冠军球队在1~4号中吗？”。假如对方告诉我们猜错了，那么我们也就自然知道冠军球队在5~8号中。这样只需4次就能知道哪支球队获得了冠军。上述过程背后所隐藏着的其实就是决策树的基本思想，并且还可以用更为直观的图来展示上述过程，如图8-2所示。
由此可以得出，决策树的每一步决策过程就是降低信息不确定性的过程，甚至还可以将这些决策看成一个if then的规则集合。如图8-2所示，冠军球队一开始有16种可能性，经过一次决策后变成了8种。这意味着每次决策都可以得到更多确定的信息，而减少更多的不确定性。
不过现在的问题是，为什么要像图8-2这样来划分球队呢？对于熟悉足球的读者来讲，这样的决策树似乎略显多余。因为事实上只有少数几支球队才有夺冠的希望，而大多数球队是没有希望的，因此，一种改进做法是在一开始的时候就将几个热门的可能夺冠的球队分在一边，将剩余的球队放在另一边，这样就可以大大提高整个决策过程的效率。
例如最有可能夺冠的是1、2、3、4这4支球队，而其余球队夺冠的可能性远远小于这4支球队。那么一开始就可以将球队分成1~4和5~16。如果冠军是在1~4中，则后面很快就能知道哪支球队是冠军。退一步将，假如冠军真的在5~16中，那么接下来同样可以按照类似的思路将剩余的球队划分成最有可能夺冠和最不可能夺冠两部分，这样也能快速地找出哪支球队是冠军球队。
于是这时候可以发现，如何划分球队就变成了建立这棵决策树的关键。如果存在一种划分，能够使数据的“不确定性”减少得越多（哪支球队不可能夺冠），也就意味着该划分能获取更多的信息，而我们也就更倾向于采取这样的划分方式。因此采用不同的划分就会得到不同的决策树，所以现在的问题就变成了如何构建一棵“好”的决策树呢？要想回答这个问题，先来解决如何描述“信息”这个问题。
8.1.2 信息的度量#
关于如何定量地来描述信息，几千年来都没有人给出很好的解答。直到1948年，香农在他著名的论文《通信的数学原理》中提出了信息熵（Information Entropy）的概念，这才解决了信息的度量问题，并且还量化出信息的作用。
1. 信息熵
一条信息的信息量与其不确定性有着直接的关系。例如，要搞清楚一件非常不确定的事，就需要了解大量的信息。相反，如果已经对某件事了解较多，则不需要太多的信息就能把它搞清楚，所以从这个角度来看可以认为，信息量就等于不确定性的多少。我们经常说，一句话包含多少信息，其实就是指它不确定性的多与少[1]。
于是，上面8.1.1节中第1种划分方式的不确定性（信息量）就等于“4块钱”，因为我们花4块钱就可以解决这个不确定性问题。当然，香农用的不是钱，而是用比特（Bit）这个概念来度量信息量，1字节就是8比特。在上面的第1种情况中，“哪支球队是冠军”这条消息的信息量就是4比特。4比特是怎么计算出来的呢？第2种情况的信息量又是多少呢？
香农指出，它的准确信息量应该是
$$ H=-({{p}_{1}}\cdot \log {{p}_{1}}+{{p}_{2}}\cdot \log {{p}_{2}}+\cdots +{{p}_{16}}\cdot \log {{p}_{16}})\tag{8-1} $$其中$\log$表示以2为底的对数，$p_1,p_2,...,p_{16}$分别是这16支球队夺冠的概率。香农把式(8-1)的结果称为信息熵（Entropy），一般用符号$H$表示，单位是比特。由于在第1种情况中，默认条件是16支球队夺冠概率相同，因此对应的信息熵就是4比特 [2]。
对于任意一个随机变量$X$（例如获得冠军的球队），它的熵定义如下：
$$ H(X)=-\sum\limits_{x\in X}{P}(x)\log P(x)\tag{8-2} $$其中$\log$表示以2为底的对数。
例如在二分类问题中： 设$P(y=0)=p,P(y=1)=1-p,\;0\leq p\leq1$，那么此时的信息熵$H(y)$即为
$$ H(y)=-(p\log p+(1-p)\log (1-p))\tag{8-3} $$根据式(8-3)还能画出其对应的函数图形，如图8-3所示。
从图8-3可以发现，当两种情况发生的概率均等（$p=1-p=0.5$）时信息熵最大，也就是说此时的不确定性最大，要把这件事搞清楚所需要的信息量也就越大，并且这也很符合我们的常识，例如“明天下雨和不下雨的概率都是50%”，那么这一描述所存在的不确定性是最大的。
2. 条件熵
在谈条件熵（Condition Entropy）之前，我们先来看一看信息的作用。一个事物（哪支球队会获得冠军），其内部会存有随机性，也就是不确定性，假定其为$U$。从外部消除这个不确定性的唯一办法就是引入信息$I$（一人猜，另一人反馈），并且需要引入的信息量取决于这个不确定性的大小，即$I＞U$才能完全消除这一不确定性。当$I＜U$时，外部信息可以消除一部分不确定性，也就是说新的不确定性$U^{\prime}=U-I$。反之，如果没有外部信息的引入，则任何人都无法消除原有的不确定性[1]，而所谓条件熵，直白点就是在给定某种条件（有用信息）$I$下，事物$U$的熵，即$H(U|I)$。
至此，对于条件熵相信各位读者在感性上已经有了一定的认识，至于其具体的数学定义将在决策树生成部分进行介绍。
3. 信息增益
根据8.1.1节内容中的介绍，若一种划分能使数据的“不确定性”减少得越多，也就意味着这种划分获取的信息更多，而我们也就更倾向于采取这样的划分。换句话说，存在某个事物$U$，当引入事物$I$的信息后$U$的熵会变小，而我们要选的就是那个最能使$U$的信息熵变小的$I$，即需要得到最大的信息增益（Information Gain）。
$$ g( U|I )=H( U )-H( U|I )\tag{8-4} $$综上所述，采用不同的划分方式就会得到不同的决策树，而我们所希望得到的是在每一次划分时都采取最优的方式，即局部最优解。这样每一步划分都能够使当前的信息增益达到最大，因此可以得出，构建决策树的核心思想就是每次划分时，要选择使信息增益达到最大时的划分方式，以此来递归构建决策树。
8.1.3 小结#
在本节中，我们首先介绍了决策树的核心思想，即决策树的本质就是降低信息不确定性的过程；然后总结出构建一棵决策树的关键在于找到一种合适的划分，使信息的“不确定性”能够降低得最多；最后我们介绍了如何以量化的方式来对信息进行度量。