> For the complete documentation index, see [llms.txt](https://linlh.gitbook.io/cs-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://linlh.gitbook.io/cs-notes/ji-qi-xue-xi/jue-ce-shu.md).

# 决策树

## 信息熵的定义

随机变量$$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