决策树（decision tree）是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。

一、信息论知识

1.信息熵的概念

设离散型随机变量X的取值有$x_{1},x_{2},x_{3},...,x_{n}$x1​,x2​,x3​,...,xn​，其发生概率分别为$p_{1},p_{2},p_{3},...,p_{n}$p1​,p2​,p3​,...,pn​，那么就可以定义信息熵为：

一般对数的底数是2，当然也可以换成e，当对数底数为2时，信息熵的单位为比特，信息熵也称香农熵。当对数不为2而是其他大于2的整数r时，我们称信息熵为r-进制熵，记为$H_{r}(X)$Hr​(X)，它与信息熵转换公式为：

信息熵用以描述信源的不确定度， 概率越大，可能性越大，但是信息量越小，不确定性越小，熵越小。

2.条件熵

设随机变量(X,Y)具有联合概率分布：

条件熵$H(Y|X)$H(Y∣X)表示 在已知随机变量X的条件下随机变量Y的不确定性。
可以这样理解：
(X,Y)发生所包含的熵，减去X单独发生的熵，就是在X发生的前提下，Y发生新带来的熵。
所以条件熵有如下公式成立：

推导如下：

3.相对熵

相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等。定义如下：
设p(x)，q(x)是随机变量X中取值的两个概率分布，则p对q的相对熵为：

在信息理论中，相对熵等价于两个分布的信息熵（Shannon entropy）的差值。 即：

4.互信息

两个随机变量X和Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。即：

所以根据KL散度也就是相对熵的定义，可以推出互信息的表达式如下：

继续推导如下：

所以最后有：

5.几个量之间的关系

结合上述条件熵的两个表达式，可以进一步推出：

当然我们也可以根据熵的定义来直接推出上面这个互信息的公式：

同时我们也可以得到两个不等式：

上面这个不等式告诉我们，对于一个与X相关的随机变量Y，只要我们得知了一点关于Y的信息，那么X的不确定度就会减小。
最后，借助强大的韦恩图来记住这些关系：

二、决策树

1.引入

决策树，顾名思义，就是帮我们做出决策的树。现实生活中我们往往会遇到各种各样的抉择，把我们的决策过程整理一下，就可以发现，该过程实际上就是一个树的模型。比如相亲的时候：

我们可以认为年龄，长相，收入是一个人的三个特征，每次我们做出抉择都是基于这三个特征来把一个节点分成好几个新的节点。
一颗完整的决策树包含以下三个部分：

1. 根节点：就是树最顶端的节点，比如上面图中的“年龄”。
2. 叶子节点：树最底部的那些节点，也就是决策结果，见还是不见。
3. 内部节点，除了叶子结点，都是内部节点。

树中每个内部节点表示在一个属性特征上的测试，每个分支代表一个测试输出，每个叶节点表示一种类别。
给定一个决策树的实例：

构造决策树如下：

1.第一层根节点
被分成14份，9是/5否，总体的信息熵为：
H0= -[(5/14)log5/14+(9/14)log9/14]=0.9403.

2.第二层
晴：被分为5份，2是/3否，它的信息熵为：
H1=-[(2/5)log2/5+(3/5)log3/5]=0.9710.
阴：被分为4份，4是/0否，它的信息熵为：
H2= -[log1]=0.
雨：被分为5份，3是/2否，它的信息熵为：
H3=-[(2/5)log2/5+(3/5)log3/5]=0.9710.
我们规定，假设我们选取天气为分类依据，把它作为根节点，那么第二层的加权信息熵，也就是$H^{'}=5/14H1+4/14H2+5/14H3$H′=5/14H1+4/14H2+5/14H3要比H0小，也就是随着决策的进行，其不确定度要减小才行，要不然我们还决策干什么。。。决策肯定是一个由不确定到确定状态的转变。 算出$H^{'}=0.6936<0.9403$H′=0.6936<0.9403，符合要求。
事实上，随着分类的进行，越来越多的信息被知道，那么总体的熵肯定实惠下降的。
同样，对于晴这个节点，他的两个叶子结点的熵都是0，到了叶子结点之后，熵就变为0了，就得到了决策结果。
因此，决策树采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为0，此时每个叶子节点中的实例都属于同一类。 至于怎么定义下降最快，下面接着讲。

2.决策树的生成算法

首先我们要选择一个根节点，那么选谁当做根节点呢？比如上面的例子，有天气，湿度以及风级三个属性，所以我们要在三个当中选择一个。三个属性f1,f2,f3，以三个属性分别为根节点可以生成三棵树（从第一层到第二才层），而究竟选择谁来当根节点的准则，有以下三种。

1.信息增益与ID3

决策树中信息增益定义如下：
给定一个样本集D，划分前样本集合D的熵是一定的 ，用H0表示； 使用某个特征A划分数据集D，计算划分后的数据子集的熵，用H1表示，则：
信息增益=H0-H1，也可以表示为：

比如上面实例中我选择天气作为根节点，将根节点一分为三，设f1表示天气，则有:
$g(D,f1)=H0-H^{'}=0.9403-0.6936=0.2467.$g(D,f1)=H0−H′=0.9403−0.6936=0.2467.
意思是，没有选择特征f1前，是否去打球的信息熵为0.9403，在我选择了天气这一特征之后，信息熵下降为0.6936，信息熵下降了0.2467，也就是信息增益为0.2467.

信息增益的局限：信息增益偏向取值较多的特征。
原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。 比如说有一个特征可以把训练集的每一个样本都当成一个分支，也就说有n个样本，该特征就把树分成了n叉树，那么划分后的熵变为0，因此信息增益当然是下降最大的。 也就是如果我们在生成决策树的时候以信息增益作为判断准则，那么分类较多的特征会被优先选择。
利用信息增益作为选择指标来生成决策树的算法称为ID3算法。

2.信息增益率与C4.5

为了解决信息增益的局限，引入了信息增益率的概念。分支过多容易导致过拟合，造成不理想的后果。假设原来的熵为0.9，选择f1特征划分后整体熵变成了0.1，也就是信息增益为0.8，而选择f2划分后，熵变为0.3，也就是信息增益为0.6。我们不想选择f1，因为它让决策树分支太多了，那么就可以定义决策指标=信息增益/特征本身的熵。f1划分后分支更多，也就是特征f1本身的熵比f2更大，大的数除以一个大的数，刚好可以中和一下。
即：

还是以这张图为例子算一下：

现在我们要选择谁做根节点。未划分前：（前面都算过一遍了）
H0= 0.9403.
选择天气作为根节点，则有：
晴：被分为5份，2是/3否，它的信息熵为：
H1=0.9710.
阴：被分为4份，4是/0否，它的信息熵为：
H2= -[log1]=0.
雨：被分为5份，3是/2否，它的信息熵为：
H3=0.9710.
划分后总体的信息熵为：
$H^{'}=5/14H1+4/14H2+5/14H3=0.6936$H′=5/14H1+4/14H2+5/14H3=0.6936 。一定要注意，这个算的是总体的信息熵， 那么信息增益为：0.2467.
这个时候我们考虑天气本身的熵，这里算的是天气本身的熵，而不是样本X,也就是是否外出打球的熵，这里一定要将二者区分开。天气本身有三种可能，每种概率都已知，则天气的熵为：
$H0= -[(5/14)log5/14+(4/14)log4/14+(5/14)log5/14]=0.9403=1.5774$H0=−[(5/14)log5/14+(4/14)log4/14+(5/14)log5/14]=0.9403=1.5774.
那么选择天气作为分类依据时，评价指标=0.2467/1.5774=0.1566.

这里还是想要强调一下，很多人在算信息增益率的时候总是出错，是因为搞混了总体的熵与特征的熵！！！ 我在算信息增益的时候，两个相减的熵都是算的总体的熵，也就是依据是否外出来划分的，而我计算特征本身的熵的时候，是依据这个特征本身来算的，比我算天气的熵，那么就看天气分为了哪几类，比如晴天，阴天，雨天之类的，每一类又有自己的概率，然后再根据信息熵的定义来计算，二者相除即是信息增益率。
利用信息增益率作为选择指标来生成决策树的算法称为C4.5算法。

3.Gini系数与CART

定义：基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
定义式：

一些参数的说明：

1. pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)。
2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个。
3. 易知，当样本属于每一个类别的概率都相等即均为1/K时，基尼系数最大，也就是说此时不确定度最小。

关于基尼系数的理解，网上有一种说法比较通俗易懂。现解释如下：
我们知道信息熵的定义式为：

那么基尼系数实际上就是用$1-p_{i}$1−pi​来代替了$-log(p_{i})$−log(pi​)，画出二者图像：

因为概率是属于0到1之间，所以我们只看01区间上的图像：基尼系数对于信息熵而言，就是在01区间内近似的用切线来代替了对数函数。因此，既然信息熵可以表述不确定度，那么基尼系数自然也可以，只不过存在一些误差。
那么如何根据基尼系数来构建决策树呢？未完待续。。。