第四章决策树

watermelon

4.1 基本流程

顾名思义，决策树是基于树结构来进行决策的。

这与人们面临决策时很自然的一种处理机制，即通过一系列的判断或“子决策”得出最终决策。决策过程中的每个判定问题都是对某个属性的测试，每个测试结果或是导出下一步的判定的问题，或是导出最终结果。

一般的，一颗决策树包含一个根节点，若干个内部节点和若干个叶节点；叶节点对应于决策结果；其他节点则对应于一个属性测试，每个节点包含的样本集合根据属性测试的结果划分到叶子节点中。从根节点到每个叶子节点的路径对应了一个判定测试序列。其基本流程遵循“分而治之”的策略。

Untitled

决策树的生成过程是一个递归过程。

在决策树基本算法中有三种情况导致递归返回：

当前节点的样本全部属于一个类别，无需划分
当前样本的属性集为空或属性取值相同，无法划分（定义为叶子结点，类别为多数样本）
当前样本的集合为空，无法划分（标记为父节点的类别）

4.2 划分选择

构建决策树的关键是选择每一次划分的属性；随着划分的不断进行，我们希望样本的纯度越来越高，尽可能属于同一类别。

4.2.1 信息增益

信息熵：度量样本集合纯度最常用的一种指标。

假设样本集合D中，第k类样本所占的比例为Pk（如好瓜和坏瓜这两种），则信息熵的定义为：

$\begin{align} Ent(D) &= - \sum_{k=1}^{|y|} {p_k log_2 {p_k}} \end{align}$

值越小，纯度越高

信息增益：考虑到不同分支的样本数不同，给与分支不同的权重，即样本数越大的分支影响越大，

于是可以计算用属性a对样本集合D进行划分的信息增益：

$\begin{align} Gain(D,a) = Ent(D)- \sum_{v=1}^{V}{ {\frac {|D_v|} {|D|}}Ent(D^v)} \end{align}$

一般来说，信息增益越大，意味着用属性a来划分的所获得的纯度越高。

举例：西瓜数据集2.0，一共有17个样本，两种类别。

Untitled

一开始时，两种类别，D包含所有样例，正例8/17，反例9/17.所以信息熵为：

$\begin{align} Ent(D) &= -\sum_{k=1}^{|y|} {p_k log_2 {p_k}} = -(\frac 8 {17}\log_2{\frac 8 {17}}+\frac 9 {17}\log_2{\frac 9 {17}}) =0.998 \end{align}$

下面我们计算色泽的信息增益：

$\begin{align} Ent(D^1) = -(\frac 3 {6}\log_2{\frac 3 {6}}+\frac 3 {6}\log_2{\frac 3 {6}}) = 1.000 \end{align}$ $\begin{align} Ent(D^2) = -(\frac 4 {6}\log_2{\frac 4{6}}+\frac 2 {6}\log_2{\frac 2 {6}}) = 0.918 \end{align}$ $\begin{align} Ent(D^3) = -(\frac 1 5\log_2{\frac 1 5}+\frac 4 5\log_2{\frac 4 5}) = 0.722 \end{align}$

所以“色泽”的信息增益为：

$\begin{align} Gain(D, 色泽) &= Ent(D) - \sum_{v=1}^{V}{ {\frac {|D_v|} {|D|}} Ent(D^v) } \\ &= 0.998 -(\frac6{17} \times 1.000 +\frac6{17} \times 0.918+\frac5{17} \times 0.722) \\ &= 0.109 \end{align}$

类似的，我们可以计算其他属性的信息增益。

Gain(D,根蒂)=0.143；Gain(D,敲声)=0.141；Gain(D,纹理)=0.381；Gain(D,脐部)=0.289；Gain(D,触感)=0.006；

“纹理”的信息增益最大，所以被选为划分属性。划分结果：

Untitled

按照此过程继续划分，可以得到：

Untitled

4.2.2 增益率

上述方法有个问题，如果考虑将编号也作为一个划分属性，其信息增益为0.998，远大于其他。其将产生17个分支，每个分支一个样本，纯度也是最大的。但是这样的决策没有泛化能力，无法对新样本进行预测。

实际上，信息增益对可选取值数目较多的属性有所偏好。

所以著名的C4.5算法不直接使用上述算法，而是使用增益率来选择最优属性。增益率定义为：

$\begin{align} Gain\_ratio(D,a) &=\frac {Gain(D,a)}{IV(a)} \\IV(a)&=- \sum_{v=1}^{V}{ \frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}} \end{align}$

IV(a)称为属性a的固有值，如果属性可取值的数目越多，那么IV(a)的值通常也会越大。

但是，增益率又会对可取值较少的属性有偏好，所以一般不是直接选择增益率最大的属性，而是使用启发式算法。

先从属性里面找到信息增益比较高的，在从中找出增益率最高的。

4.2.3 基尼指数

CART决策树使用“基尼指数”来选择划分的属性。数据集D的纯度可以用基尼值来度量：

$\begin{align} Gini(D,a) &= \sum_{k=1}^{|Y|}{ \sum_{k'\neq k}p_kp_{k'}} \\&=1- \sum_{k=1}^{|Y|}{ p_k^2} \end{align}$

直观来说，反映了数据集D中随机抽取两个样本，其类别标记不一样的概率，Gini值越小，纯度越高。

如果改成与公式11相同的形式，则：

$\begin{align} Gini\_index(D,a) &=- \sum_{v=1}^{V}{ \frac{|D^v|}{|D|}Gini(D^v)} \end{align}$

最后在候选属性集合A中，选择基尼指数最小的即可。

4.3 剪枝处理

剪枝算法是决策树学习处理“过拟合”的主要手段，在节点划分的过程中，有可能造成决策树的分支过多，这时候可能因为训练样本而训练得“太好了”，以致于过拟合。所以可以主动去掉一些分支来降低过拟合的风险。

未剪枝的决策树

4.3.1 预剪枝

预剪枝就是在生成过程中，对每个节点划分前进行估计，如果当前节点划分不能带来决策树泛化性能的提升，则停止划分。

举例：一开始根节点的类别标记为样例最多的类别

预剪枝的决策树

1、用脐部划分之后，验证集的准确率提升为0.714，于是划分确定。

2、之后再对节点2进行划分，根据信息增益挑选“色泽”，划分后，验证集准确率为0.571，取消划分。

……

4.3.2 后剪枝

首先是生成一颗完整的决策树，然后自底向上地对非叶子结点进行考察，如果将子树变成叶子结点，泛化性能有提升，则将子树替换成叶子结点。

举例：先生成完整的决策树。

1、考察节点6-纹理。将节点替换成叶子结点，准确率提升为0.571，剪枝

……

结果为：

Untitled

对比预剪枝和后剪枝：
可以看出，后剪枝保留了更多的分支，欠拟合风险小，而且泛化性能高于预剪枝；
但是后剪枝需要建立完整的决策树，需要时间开销。

4.4 连续与缺失值

4.4.1 连续值处理

到目前为止，我们讨论的都是离散值，而我们常常会遇到连续值。连续属性往往数目不再有限，此时，我们可以使用连续值离散化处理，比如最简单的二分法进行处理。这也是C4.5中使用的方法。

样本集合D，给定连续属性a，则取n个不同的取值，将其从小到大排序，则有n-1个划分方法。（样本排序后，两两之间的均值作为候选划分点）。

$\begin{align} Gain(D,a) &= \max_{t \in T_a}{Gain(D,a,t)} \\ &= \max Ent(D) - \sum_{ \lambda \in \{ -,+ \}}{\frac {|D_\lambda|} {|D|} Ent(D^\lambda_t)} \end{align}$