决策树思维导图[3]

1 信息论基础

1.1 熵

熵是度量样本集合纯度最常用的一种指标。假定当前样本集合\(D\)中第\(k\)类样本所占的比例为\(p_{k}(k=1,2,...,|K|)\)，则样本集合\(D\)的熵定义为：

\[Ent(D)=-\sum_{k=1}^{K}p_{k}log_{2}p_{k} \]

\(Ent(D)\)的值越小，则\(D\)的纯度越高。

1.2 信息增益

假定离散属性\(a\)有\(V\)个可能的取值\(\{a^{1}, a^{2}, ..., a^{V}\}\)，若使用\(a\)对样本集\(D\)进行划分，则会产生\(V\)个分支，其中第\(v\)个分支包含了\(D\)中所有在属性\(a\)上取值为\(a^{v}\)的样本，记为\(D^{v}\)。我们可以根据熵的公式计算出样本集\(D^{v}\)的信息熵，再考虑到不同分支节点所包含的样本数量不同，给分支节点赋予权重\(|D^{v}|/|D|\)。于是可计算出用属性\(a\)对样本集\(D\)进行划分所获得的信息增益：

\[Gain(D,a)=Ent(D)--\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v}) \]

信息增益越大，表明用某个属性划分数据集所带来的”纯度提升“越大。

2 树的分裂

决策树的学习过程如下图所示，其中最重要的是决策树的生长过程，即决策树是如何分裂的，下面介绍三种常用的算法。

2.1 ID3算法

ID3算法采用信息增益作为节点分裂的依据，即选择信息增益最大的属性划分数据集，该次划分使用过的属性将不再使用（不会作为后续子树划分的依据）。
ID3算法的缺点

• 倾向于选择取值数量较多的属性
• 不能处理连续值
• 不能处理缺失值

2.2 C4.5算法

C4.5算法是对ID3算法的改进，改进之处包括但不限于：

• 能够处理连续值
• 能偶处理缺失值
• 使用信息增益率代替信息增益，消除了ID3算法倾向于选择取值较多的属性作为划分属性的缺点
• 给出树的剪枝策略

信息增益率

\[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| }$$

2.3 CART树

CART（Classification And Regression Tree）是一棵二叉树，它既能处理分类问题，又能够处理回归问题。

CART解决分类问题

对于分类问题，CART使用基尼指数（Gini index）来选择划分属性，基尼指数定义为：

\[Gini(D)=1-\sum_{k=1}^{K}p_{k}^{2} \]

\(Gini(D)\)反映了从数据集\(D\)中随机抽取两个样本，其类别标记不一致的概率，因此\(Gini(D)\)越小，数据集\(D\)的纯度越高。
为什么要引入基尼指数？？
当处理分类问题时，虽然ID3或C4.5定义的熵仍然可以使用，但是由于对数函数\(\log\)的计算代价较大，CART将熵中的\(\log\)在\(p=1\)处利用一阶泰勒展开便是基尼指数。
属性\(a\)的基尼指数定义为：

\[Gini\_index(D,a)=\sum_{v=1}^{V}\frac{ |D^{v}| }{ |D| }Gini(D^{v}) \]

在侯选属性集合\(A\)中选择那个使得划分后基尼指数最小的属性作为最优化分属性，即：

\[a_{*}=arg\quad min\quad Gini\_index(D,a) \]

注意
在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别A1,A2,A3，我们会在决策树上建立一个三叉点，这样决策树是多叉树。
CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3}，然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开，后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同，在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。

CART解决回归问题

建立CART回归树的步骤
输入：训练数据集D
输出：回归树T

1. 计算各个特征各个值划分的两部分\(D_{1}\)和\(D_{2}\)的误差平方和，选择误差平方和最小的作为最右特征和最优分裂点。

\[\underset{A,a}{min}\left [ \underset{c_{1}}{min}\sum_{x_{i}\in D_{1}(A,a)}^{}(y_{i}-c_{1})^{2} + \underset{c_{2}}{min}\sum_{x_{i}\in D_{2}(A,a)}^{}(y_{i}-c_{2})^{2} \right ] \]

其中，\(c_{1}\)为\(D_{1}\)的样本输出均值，\(c_{2}\)为\(D_{2}\)样本的输出均值。
2. 根据最优特征A和最优切分点a，将本节点的数据集划分为两部分\(D_{1}\)和\(D_{2}\)，并给出相应的输出值

\[D_{1}(A,a)=(x,y)\in D | A(x) \leqslant a \]

\[D_{2}(A,a)=(x,y)\in D | A(x) > a \]

\[c_{1}=average(y_{i} | x_{i} \in D_{1}(A,a)) \]

\[c_{2}=average(y_{i} | x_{i} \in D_{2}(A,a)) \]

3. 继续对两个子集调用1-2步骤
4. 生成回归树，利用生成的CART回归树做预测时，用叶子节点的均值来作为预测的输出结果。

3 决策树节点的分裂顺序

假设当前已经处理完了节点2的分裂，所有黄色节点（包括2号节点）都是当前已经存在的树节点，那么我们接下来究竟应该选取叶节点3号、4号和5号中的哪一个节点来继续进行决策以生成新的叶节点6号和7号？
在sklearn中提供了两种生长模式，它们分别被称为深度优先生长和最佳增益生长，当参数max_leaf_nodes使用默认值None时使用前者，当它被赋予某个数值时使用后者。
深度优先生长采用深度优先搜索的方法：若当前节点存在未搜索过的子节点，则当前节点跳转到子节点进行分裂决策；若当前节点为叶节点，则调转到上一层节点，直到根节点不存在未搜索过的子节点为止。对上图而言，当前节点为2号，它的两个子节点4号和5号都没有被搜索过，因此下一步则选择两个节点中的一个进行跳转。当决策树使用最佳增益生长时，每次总是选择会带来最大相对信息增益的节点进行分裂，直到叶节点的最大数量达到max_left_nodes。

4 连续值和缺失值的处理

4.1 处理连续值

随机分割法

取\(s\sim U\left [ x_{min},x_{max} \right ]\)，其中\(U\left [ x_{min},x_{max} \right ]\)代表特征最小值和最大值范围上的均匀分布，将节点的样本按照特征\(x\)中的元素是否超过\(s\)把样本分成两个集合，根据这两个类别来计算树节点分裂的信息增益。

最佳分割法

给定样本集\(D\)和连续属性\(a\)，假定\(a\)在\(D\)上出现了\(n\)个不同的取值，将这些值从小到大进行排序，记为\(\left \{ a^{1},a^{2},...,a^{n} \right \}\)。基于划分点\(t\)可将\(D\)分为子集\(D_{t}^{-}\)和\(D_{t}^{+}\)，其中\(D_{t}^{-}\)包含那些在属性\(a\)上取值不大于\(t\)的样本，而\(D_{t}^{+}\)则包含那些在属性\(a\)上取值大于\(t\)的样本。显然，对于相邻的属性取值\(a^{i}\)与\(a^{i+1}\)来说，\(t\)在区间\([a^{i},a^{i+1})\)中取任意值所产生的划分结果相同。因此，队连续属性\(a\)，我们可考察包含\(n-1\)个元素的候选划分点集合

\[T_{a}=\left \{ \frac{a^{i}+a^{i+1}}{2} | 1\leqslant i\leq n-1 \right \} \]

我们可以像离散属性那样考察这些划分点，选取最优的划分点进行样本集合的划分。

4.2 处理缺失值

C4.5算法处理缺失数据的思想非常简单，样本的缺失值占比越大，那么对信息增益的惩罚就越大，这是因为缺失值本身就是一种不确定性成分。设节点\(N\)的样本缺失值比例为\(\gamma\)，记非缺失值对应的类别标签和特征分别为\(\tilde{Y}\)和\(\tilde{X}\)，则修正的信息增益为

\[\tilde{G}(Y,X) = (1-\gamma)G(\tilde{Y},\tilde{X}) \]

当数据完全缺失时\(\gamma=1\)，信息增益为0；当数据没有缺失值时\(\gamma=0\)，信息增益与原来的值保持一致。

5 决策树的剪枝

决策树具有很强的拟合能力，对于任何一个没有特征重复值的数据集，决策树一定能够在训练集上做到分类错误率或均方回归损失为0，因此我们应当通过一些手段来限制树的生长，这些方法被称为决策树的剪枝方法。其中，预剪枝是指树在判断节点是否分裂的时候就预先通过一些规则来阻止其分裂，后剪枝是指在树的节点已经全部生长完成后，通过一些规则来摘除一些子树。

5.1 预剪枝

预剪枝是在决策树生成过程中，对每个节点在划分前进行估计，若当前节点的划分不能带来决策树泛化能力的提升，则停止划分并将当前节点标记为叶节点。

5.2 后剪枝

后剪枝则是先从训练集在生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化能力的提升，则将该子树替换为叶节点。

参考

• 《机器学习》，周志华著
• https://datawhalechina.github.io/machine-learning-toy-code/
• 决策树算法--CART分类树算法