决策树

信息熵的定义

随机变量$X$的熵定义为：

$$H(X) = - \sum^n_{i=1}{p_i\log{p_i}}$$

怎么理解信息熵呢，通俗理解就是它是衡量混乱程度的一个指标。假设如果有两个变量，那么取这两个变量的概率都是0.5，那么此时的熵最大。就像你买东西的时候，有两个选择，概率都是0.5，就相当于你问你女朋友，然后她说随便，这个时候你就很无奈，不知道选哪个，纠结。那么如果其中一个概率为1，那么这个事情就是确定的，不存在什么混乱的情况，这个时候熵最小。

决策树就是一个信息熵下降的过程，从原本无法确定这个样本是什么，从树的根节点一直往下走，降低信息熵，也就是慢慢地明确了自己的选择，最终确定这个样本的类别或者是预测值。

信息增益

信息增益的定义为：

$$g(D, A) = H(D) - H(D|A)$$

单单看这个式子很抽象，我们举个实际的例子，这个例子要完成的任务给定申请人的特征信息，包括年龄，工作，房子以及信贷情况，给出是否同意申请人的贷款。具体的数据信息如下表：

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

现在我们来看$H(D)$是怎么计算的，总共有15个样本，其中同意贷款申请的有9个样本，剩下的6个样本是不同意的，那么计算过程如下：

$$H(D) = - \frac{9}{15}\log_2\frac{9}{15} - \frac{6}{15}\log_2\frac{6}{15} = 0.971$$

接下来需要计算的是$H(D|A_1)$，其中$A_1$表示的是这里的特征，这里选择年龄，年龄共有三个取值，分别是青年、中年、老年，分别各有5个样本，分别记为$D_1、D_2、D_3$最终$H(D|A_1)$的结果如下：

$$H(D|A_1) = \frac{5}{15}H(D_1) + \frac{5}{15}H(D_2) +\frac{5}{15}H(D_3)$$

其中$H(D_1)$的计算如同我们计算$H(D)$是一致的，需要关注到在$D_1$这个类别的条件下贷款申请的同意情况，查看表格可以得到，在青年的类别中，共有2个同意申请，3个拒绝申请的，所以计算如下：

$$H(D_1) = -\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5}$$

那么就可以按照这个方法依次算出$H(D_2)$和$H(D_3)$，最终我们就可以算出最后的$H(D|A_1)$，最终对于$A_1$特征，即给定年龄特征的条件下的信息增益为：

$$\begin{align} g(D, A_1) &= H(D) - \bigg[ \frac{5}{15}(-\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5}) \\ &+ \frac{5}{15}(-\frac{3}{5}\log_2\frac{3}{5}-\frac{2}{5}\log_2\frac{2}{5}) \\&+ \frac{5}{15}(-\frac{4}{5}\log_2\frac{4}{5}-\frac{1}{5}\log_2\frac{1}{5}) \bigg] \\ &= 0.971 - 0.888 = 0.083 \end{align}$$

然后可以依次算出$g(D, A_2)​$ 、$g(D, A_3)​$以及$g(D, A_4)​$ ，就可以得到四个特征中选择信息 增益最大的那个特征作为当前的根节点了。这里选择的就是$A_3$特征，即有自己的房子作为最优特征。

$$g(D, A_1) = 0.083 \\g(D, A_2) = 0.324\\g(D, A_3) = 0.420\\g(D, A_4) = 0.363$$

决策树的生成算法

决策树的生成算法分为三个，总结下特点：ID3会倾向于选择取值较多的特征。原因是信息增益反应的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益也就越大。这个是实际应用的缺陷。C4.5是对ID3的优化，引入了信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现的过拟合特征，提升决策树的泛化能力。

从样本类型的角度来看，ID3只能处理离散型便令，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量的时候，通过对数据排序后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续型变量。

从应用角度，ID3和C4.5只能用于分类任务，而CART不仅仅可以用于分类，也可以用于回归任务（回归树使用的是最小平方误差准则）

从实现细节、优化过程等角度，ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理； ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点上只会产生两个分支，最后会形成一个二叉树，且每个特征可以被重复使用。ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树的结构进行对比。

ID3

Iterative Dichotomiser，该算法使用的是信息增益作为分支选择特征的标准。

C4.5

C4.5选择是利用信息增益比来作为特征的选择标准。

CART

gini系数的一种理解方式可以结合方差来考虑，假设有$K$个类，样本点属于第$k$类的概率为$p_k$,Gini的定义如下:

$$Gini(p) = \sum^K_{k=1}p_k(1-p_k)=1-\sum^K_{k=1}p_k^2$$

而我们如果下面这样一个随机变量$X$的方差为$p(1-p)$，那么它衡量的是随机变量$X$的离散程度，方差越大，那么它的离散程度越高。

$X$	1	0
$P$	$p$	$1-p$

那么延伸到多分类就可以得到$Gini(p) = p_1(1-p_1)+p_2(1-p_2)+...p_k(1-p_k)$

$X$	1	2	3	...	k
$P$	$p_1$	$p_2$	$p_3$	...	$p_k$

另外一种理解，就是将$f(x)=-\ln x$在$x=1$处展开，忽略高阶无穷小，可以得到$f(x)≈1-x$，即：

$$H(X) = -\sum_{k=1}^K{p_k}\ln p_k \\ ≈\sum_{k=1}^Kp_k(1-p_k) = Gini(p)$$

同样的以上面的贷款申请的为例来计算$Gini$系数，$A_1,A_2,A_3,A_4$分别表示的年龄、有工作、有自己的房子和信贷情况4个特征，并以1，2，3表示年龄的值为青年、中年和老年，以1，2表示有工作和有自己的房子的值为是和否，以1，2，3表示信贷情况的值为非常好、好和一般。

特征$A_1$的基尼指数分别如下：

$$Gini(D, A_1=1)=\frac{5}{15}\bigg(2×\frac{2}{5}\times\bigg(1-\frac{2}{5}\bigg)\bigg)+\frac{10}{15}\bigg(2×\frac{7}{10}\times\bigg(1-\frac{7}{10}\bigg)\bigg) = 0.44\\ Gini(D, A_1=2)=\frac{5}{15}\bigg(2×\frac{3}{5}\times\bigg(1-\frac{3}{5}\bigg)\bigg)+\frac{10}{15}\bigg(2×\frac{6}{10}\times\bigg(1-\frac{6}{10}\bigg)\bigg) = 0.48\\ Gini(D, A_1=3)=\frac{5}{15}\bigg(2×\frac{4}{5}\times\bigg(1-\frac{4}{5}\bigg)\bigg)+\frac{10}{15}\bigg(2×\frac{5}{10}\times\bigg(1-\frac{5}{10}\bigg)\bigg) = 0.44$$

这里我们以$A_1 = 1$也就是年龄特征取值为青年的时候的数据信息，青年的数据有5个，其余信息为10个，所以$Gini(D, A_1=1)$就由两部分构成，比例分别为$\frac{5}{15}$和$\frac{10}{15}$，那么来计算取值为青年中的基尼指数，青年的5个样本中共有2个样本是同意贷款的，那么对于同意的类别概率计算为：$\frac{2}{5}(1-\frac{3}{5})$，那么对于不同意就是否的类别概率计算为：$\frac{3}{5}(1-\frac{2}{5})$，所以会有一个两倍系数，其他的计算就是一样的过程，不在描述了。

Q: 既然一颗树的根和叶子节点都是确定的，那么为什么还会有随机森林呢？

Q: 树模型特征选择除了信息增益、信息增益率、基尼系数三个指标之外，还有哪些？

Ans：如果是连续值的话，还可以用MSE来做。如果是分类的话，也可以考虑用AUC。

Reference

• [1]邹博.机器学习升级版.小象学院，2018.

• [2]李航.统计学习方法[M].北京：清华大学出版社，2012.

• [3]诸葛越，葫芦娃.百面机器学习[M]. 北京：人民邮电出版社，2018