Decision_tree

ML

---

决策树

由于决策树的内容我之前有做过一个比较详细的PPT分享，所以这一章的笔记暂时不打算花太大精力，主要是理清最重要的定义和思路，更详细的之后有时间会考虑补上。

这一章的内容大致如下：

• 基本流程：决策树是如何决策的？决策树学习的目的是什么？如何生成一颗决策树？

• 划分选择：怎样选择最优划分属性？有哪些判断指标？具体是怎样运作的？

• 剪枝处理：为什么要剪枝？如何判断剪枝后决策树模型的泛化性能是否提升？预剪枝和后剪枝是怎样工作的？有什么优缺点？

• 连续与缺失值：如何把连续属性离散化？如何基于离散化后的属性进行划分？和离散属性有何不同？如何在属性值缺失的情况下选择最优划分属性？给定划分属性，如何划分缺失该属性值的样本？

• 多变量决策树：决策树模型的分类边界的特点是怎样的？多变量决策数是如何定义的？又是如何工作的？

基本流程

决策树（decision tree）是一种模仿人类决策的学习方法。举个例子，比方说买电脑，我们首先看看外观帅不帅气，然后再看看性能怎么样，还得看看价格如何，最终经过一系列的判断做出是否购买电脑的决策。

一棵决策树可以分成三个部分：叶节点，非叶节点，分支。叶节点对应决策结果，也即分类任务中的类别标记；非叶节点（包括根节点）对应一个判定问题（某属性=？）；分支对应父节点判定问题的不同答案（可能的属性值），可能连向一个非叶节点的子节点，也可能连向叶节点。

决策就是从根节点开始走到叶节点的过程。每经过一个节点的判定，数据集就按照答案（属性值）划分为若干子集，在子节点做判定时只需要考虑对应的数据子集就可以了。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

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

生成算法：

1. 传入训练集和属性集
2. 生成一个新节点
3. 若此时数据集中所有样本都属于同一类，则把新节点设置为该类的叶节点，然后返回$^1$。
4. 若此时属性集为空，或者数据集中所有样本在属性集余下的所有属性上取值都相同，无法进一步划分，则把新节点设置为叶节点，类标记为数据集中样本数最多的类，然后返回$^2$
5. 从属性集中选择一个最优划分属性
   
   • 为该属性的每个属性值生成一个分支，并按属性值划分出子数据集
   • 若分支对应的子数据集为空，无法进一步划分，则直接把子节点设置为叶节点，类标记为父节点数据集中样本数最多的类，然后返回$^3$
   • 将子数据集和去掉了划分属性的子属性集作为算法的传入参数，继续生成该分支的子决策树。

稍微注意以下，3处返回中的第2处和第3处设置叶节点的类标记原理有所不同。第2处将类标记设置为当前节点对应为数据集中样本数最多的类，这是利用当前节点的后验分布；第3处将类标记设置为为父节点数据集中样本数最多的类，这是把父节点的样本分布作为当前节点的先验分布。

划分选择

在决策树模型中，我们不断进行判定的初衷是希望划分后需要考虑的可能更少，准确地说，是希望所得子节点的纯度（purity）更高（也可以说是混乱程度更低）。

信息熵（information entropy）是一种衡量样本集纯度的常用指标：

$$Ent(D) = -\sum_{k=1}^{|\mathcal{Y}|}p_klog_2p_k$$

一定要记得最前面的负号！！！其中 $|\mathcal{Y}|$ 为类别集合，$p_k$ 为该类样本占样本总数的比例。

信息熵越大，表示样本集的混乱程度越高，纯度越低。

信息增益

信息增益（information gain）是ID3算法采用的选择准则，定义如下：

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

它描述的是按某种属性划分后纯度的提升，信息增益越大，代表用属性 $a$ 进行划分所获得的纯度提升越大。其中 $V$ 表示属性 $a$ 的属性值集合，$D^v$ 表示属性值为 $v$ 的数据子集。求和项也称为条件熵，我们可以理解为它是先求出每个数据子集的信息熵，然后按每个数据子集占原数据集的比例来赋予权重，比例越大，对提升纯度的帮助就越大。

多个属性都取得最大的信息增益时，任选一个即可。

信息增益又称为互信息（Mutual information）。

• 一个连续变量X的不确定性，用方差Var(X)来度量
• 一个离散变量X的不确定性，用熵H(X)来度量
• 两个连续变量X和Y的相关度，用协方差或相关系数来度量
• 两个离散变量X和Y的相关度，用互信息I(X;Y)来度量(直观地，X和Y的相关度越高，X对分类的作用就越大)

（信息）增益率

增益率（gain ratio）是C4.5算法采用的选择准则，定义如下：

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

一定要记得最前面的负号！！！**IV称为属性的固有值（intrinsic value），它的定义和信息熵是类似的，信息熵衡量的是样本集在类别上的混乱程度，而固有值衡量的是样本集在某个属性上的混乱程度。固有值越大，则该属性混乱程度越高，可能的取值越多**。

之所以要定义增益率是为了避免模型过份偏好用取值多的属性作划分。这是使用信息增益作准则非常容易陷入的误区，比方说每个样本都有一个“编号”属性，这个属性的条件熵肯定是最小的，但如果选择了该属性作为根节点，那么构建出的决策树就没有任何意义了，因为这个模型根本不具备泛化性能。

注意了，C4.5并非直接选择增益率最高的属性，它使用了一个启发式：先从属性集中找到信息增益高于平均水平的属性作为候选，然后再比较这些候选属性的增益率，从中选择增益率最高的。

基尼指数

基尼指数（Gini index）是CART算法采用的选择准则，定义如下：

基尼值：

$$Gini(D) = \sum_{k=1}^{|\mathcal{Y}|}\sum_{k' \neq k}p_kp_{k'}\\ =1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2$$

基尼指数：

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

基尼值是另一种衡量样本集纯度的指标。反映的是从一个数据集中随机抽取两个样本，其类别标志不同的概率。

基尼值越小，样本集的纯度越高。

由基尼值引伸开来的就是基尼指数这种准则了，基尼指数越小，表示使用属性 $a$ 划分后纯度的提升越大。

剪枝处理

剪枝（pruning）是决策树学习算法应对过拟合的主要手段。因为决策树模型太强大了，很可能把训练集学得太好以致于把训练集本身的特性也给学习了（特别是属性数多于样本数的情况），所以去除掉一些分支是有必要的。

怎么判断剪枝有没有用呢？具体来说就是判断剪枝后模型的泛化性能有没有提升？这就涉及到第二章模型评估与选择的内容了。不过这里不用做比较检验，我们需要做的首先是选定一种评估方法划分训练集和测试集，然后选定一种性能度量用来衡量剪枝前后的模型在测试集上的效果。

预剪枝

预剪枝（prepruning）是在决策树生成的过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升（比方说，划分后在测试集上错得更多了 / 划分前后在测试集上效果相同），就停止划分并将当前节点标记为叶节点。

后剪枝

后剪枝（postpruning）是先从训练集生成一颗完整的决策树，然后自底向上地逐个考察非叶节点，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。实际任务中，即使没有提升，只要不是性能下降，一般也会剪枝，因为根据奥卡姆剃刀准则，简单的模型更好。

特别地，只有一层划分（即只有根节点一个非叶节点）的决策树称为决策树桩（decision stump）。

优缺点

预剪枝是一种贪心策略，因为它在决策树生成时就杜绝了很多分支展开的机会，所以不但降低了过拟合的风险，同时也显著减少了模型的训练时间开销和测试时间开销。但是！这种贪心策略有可能导致欠拟合，因为有可能当前划分不能提升模型的泛化性能，但其展开的后续划分却会显著提升泛化性能。在预剪枝中这种可能被杜绝了。

后剪枝是种比较保守的策略，欠拟合的风险很小，泛化性能往往优于预剪枝的决策树。但是由于后剪枝是在生成了完整决策树后，自底向上对所有非叶节点进行考察，所以训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

连续与缺失值

连续值

前面线性模型已经谈到了离散属性连续化，而决策树模型需要的则是连续属性离散化，因为决策树每次判定只能做有限次划分。最简单的一种离散化策略是C4.5算法采用的二分法（bi-partition）。

给定一个包含连续属性 $a$ 的数据集，并且 $a$ 在数据集中有 $n$ 个不同取值，我们先把属性 $a$ 的 $n$ 个属性值从小到大进行排序。所谓“二分”是指将这些属性值分为两个类别（比方说把身高这一属性分为高于170和低于170两个类别）。

这就产生了一个新问题，怎么找到合适的划分点（例如上面例子的170）呢？

在对连续属性值排序完之后，由于有 $n$ 个不同取值，取每两个取值的平均值作为划分点的话，就有 $n-1$ 个候选划分点。我们需要做得就是按照准则（比方说用ID3算法的话就是信息增益）进行 $n-1$ 次判断。每次拿出一个候选划分点，把连续属性分为两类，转换为离散属性。然后基于这个基础计算准则，最终选出一个最优的属性值划分点。

注意！和离散属性不同，连续属性用于当前节点的划分后，其后代节点依然可以使用该连续属性进一步划分。比方说当前节点用身高低于170划分了，那么它的后代节点还可以用身高低于160来进一步划分。

缺失值

确实值在实际任务中是非常常见的，如果直接丢弃包含缺失值的样本会造成极大的浪费。具体来说缺失值的处理分以下两个部分：

• 如何在属性值缺失的情况下选择最优划分属性？

假设数据集为 $D$，有缺失值的属性为 $a$，令 $\tilde{D}$ 表示 $D$ 中没有缺失属性 $a$ 的样本子集。我们只能基于 $\tilde{D}$ 来判断属性 $a$ 的优劣。但是我们又希望包含缺失值的样本也能在建模过程体现出一定的影响了，因此要重新定义准则。在那之前，先定义几个新定义用到的变量：

$$\rho = \frac{\sum_{\mathbf{x} \in \tilde{D}}w_\mathbf{x}}{\sum_{\mathbf{x} \in D}w_\mathbf{x}}$$

$$\tilde{p_k} = \frac{\sum_{\mathbf{x} \in \tilde{D_k}}w_\mathbf{x}}{\sum_{\mathbf{x} \in \tilde{D}}w_\mathbf{x}},\quad (1 \leq k \leq |\mathcal{Y}|)$$

$$\tilde{r_v} = \frac{\sum_{\mathbf{x} \in \tilde{D^v}}w_\mathbf{x}}{\sum_{\mathbf{x} \in \tilde{D}}w_\mathbf{x}},\quad (1 \leq v \leq V)$$

$\rho$ 表示无缺失值样本所占的比例;

$\tilde{p_k}$ 表示无缺失值样本中第 $k$ 类所占的比例;

$\tilde{r_v}$ 表示无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占的比例 ;

注意，这里的 $w_\mathbf{x}$ 表示样本的权值，它是含缺失值样本参与建模的一种方式。在根节点处初始时，所有样本 $\mathbf{x}$ 的权重都为1。

接下来重新定义信息熵和信息增益，推广到样本含缺失值的情况：

$$Ent(\tilde{D}) = -\sum_{k=1}^{|\mathcal{Y|}}\tilde{p_k}log_2\tilde{p_k}$$

$$Gain(D,a) = \rho \times Gain(\tilde{D},a)\\ = \rho \times (Ent(\tilde{D}) - \sum_{v=1}^V\tilde{r_v}Ent(\tilde{D^v}))$$

按照新的定义来计算包含缺失值的属性的信息增益，然后和其他属性的信息增益相比，选出最优的。

• 给定划分属性，如何划分缺失该属性值的样本？

假设有一个包含缺失值的属性被计算出是最优划分属性，那么我们就要按该属性的不同取值划分数据集了。缺失该属性值的样本怎么划分呢？答案是按概率划分，这样的样本会被同时划入所有子节点，并且其权重更新为对应的 $\tilde{r_v} \dot w_\mathbf{x}$。

可以把无缺失值的决策树建模想象为各样本权值恒为1的情形，它们只对自己所属的属性值子集作贡献。而样本含缺失值时，它会以不同的概率对所有属性值子集作贡献。

多变量决策树

前面提到的决策树都是单变量决策树（univariate decision tree）， 即在每个节点处做判定时都只用到一个属性。它有一个特点，就是形成的分类边界都是轴平行（axis-parallel）的。

如果把属性都当作坐标空间中的坐标轴，由于我们建模时假设样本的各属性之间是没有关联的，所以各坐标轴是相互垂直的。而决策数每次只取一个确定的属性值来划分，就等同于画一个垂直于该属性坐标轴的超平面（只有两个属性时就是一条线），它与其他坐标轴都是平行的，这就是轴平行。最终由多个与坐标轴平行的超平面组成分类边界。

这样有一个弊端就是，如果真实分类边界特别复杂，就需要画出很多超平面（线），在预测时就需要继续大量的属性测试（遍历决策树）才能得到结果，预测时间开销很大。

多变量决策树（multivariate decision tree），顾名思义，它不再是选择单个最优划分属性作为节点，而是试图寻找一个最优的多属性的线性组合作为节点，它的每个非叶节点都是一个形如 $\sum_{i=1}^d w_ia_i = t$ 的线性分类器。多变量决策树的决策边界能够斜着走，甚至绕曲线走，从而用更少的分支更好地逼近复杂的真实边界。

习题

4.1

试证明对于不含冲突数据（即特征向量完全相同但标记不同）的训练集，必存在与训练集一致（即训练误差为0）的决策树

假设不存在与训练集一致的决策树，那么训练集训练得到的决策树至少有一个节点上存在无法划分的多个数据（若节点上没有冲突数据，那么总是能够将数据分开的）。这与前提-不含冲突数据 矛盾，因此必存在与训练集一致的决策树

4.2

试析使用“最小训练误差”作为决策树划分选择的缺陷。

若以最小训练误差作为决策树划分的依据，由于训练集和真是情况总是会存在一定偏差，这使得这样得到的决策树会存在过拟合的情况，对于未知的数据的泛化能力较差。因此最小训练误差不适合用来作为决策树划分的依据。

4.3

试编程实现基于信息熵进行划分选择的决策树算法，并为表4.3中数据生成一棵决策树

最近时间不多，暂且挖个坑。

4.4

试编程实现基于基尼指数进行划分选择的决策树算法，并为表4.2中数据生成预剪枝、后剪枝决策树，并与未剪枝决策树进行比较。

最近时间不多，暂且挖个坑。

4.5

试编程实现基于对率回归进行划分选择的决策树算法，并为表4.3中数据生成一棵决策树

最近时间不多，暂且挖个坑。

4.6

试选择4个UCI数据集，对上述3种算法所产生的未剪枝、预剪枝、后剪枝决策树进行实验比较，并进行适当的统计显著性检验。

最近时间不多，暂且挖个坑。

4.7

图4.2是一个递归算法，若面临巨量数据，则决策树的层数会很深，使用递归方法易导致“栈”溢出，试使用“队列”数据结构，以参数maxDepth控制数的最大深度，写出与图4.2等价、但不使用递归的决策树生成算法。

下面算法我没有尝试写对应的代码，若有朋友写过欢迎交流/指正。

以下代码为 队列+MaxDepth控制，即广度优先搜索。其实我觉得这里如果要用MaxDepth进行控制的话，应该选择堆栈而非队列，即应该用深度优先搜索。但下面还是给出队列的形式。若要改为深度优先搜索只需要将先进后出 改成 先进先出即可（即数据存取都在一端）。

——————————————————————————————————————————————————————
输入：训练集 D={(x1,y1),(x2,y2),...,(xm,ym)};
      属性集 A={a1,a2,...,ad}
      最大深度 MaxDepth
过程：函数TreeGenerate(D,A,MaxDepth)
1:生成节点root
2:if D中样本全部属于同一类别C then
3:     将root标记为C类叶节点;return
4:end if
5:if A=空集 or D中样本在A上取值相同 then
6:     将root标记为叶节点，其类别标记为D中样本数最多的类；return
7:end if
8:从A中选择最优划分属性a*;
9:将root标记为分支节点，属性为属性a*;
10:将root放入NodeQueue;
11:将D放入DataQueue;
12:将A\{a*}放入AQueue;
13:初始化深度depth=1;
14:将depth放入DepthQueue;
15:while NodeQueue 非空:
16:     取出NodeQueue队尾的节点rNode，其对应的属性是ra*;
17:     取出DataQueue队尾的数据集rD;     #此处r均指队尾rear
18:     取出AQueue队尾的属性集rA;
19:     取出DepthQueue队尾的元素rdepth;
20:     if rdepth==MaxDepth:
21:          将rNode标记为叶节点，类别标记为rD中样本最多的类;
22:          continue;     #跳过本次循环，即不再对这个节点做展开
23:     for ra*的每一个取值ra*v do:
24:          为rNode生成一个分支节点，令rDv表示rD在ra*上取值为ra*v的样本子集;
25:          if rDv为空 then：
26:               将分支节点标记为叶节点，其类别标记为rD中样本最多的类;
27:          else if rD中样本全部属于同一类别C then
28:               将分支节点标记为C类叶节点;
29:          else if rA=空集 or rD中样本在A上取值相同 then
30:               将分支节点标记为叶节点，其类别标记为rD中样本数最多的类;
31:          else：
32:               从rA中选择最优划分属性a*v;
33:               将分支节点的属性记为a*v;
34:               将分支节点放入NodeQueue的队头;
35:               将rDv放入DataQueue的队头;
36:               将rA\{a*v}放入AQueue的队头;
37:               将(rDepth+1)放入DepthQueue的队头;
38:          end if
39:     end for
40:end while
输入：以root为根节点的一棵决策树
——————————————————————————————————————————————————————

4.8

试将决策树生成的深度优先搜索过程修改为广度优先搜索，以参数MaxNode控制树的最大结点数，将题4.7中基于队列的决策树算法进行改写。对比题4.7中的算法，试分析哪种方式更易于控制决策树所需储存不超过内存。

在4.7中写的基于队列的算法本身就是广度优先搜索的。若要写成深度优先搜索的方式应该将队列换成堆栈即可。

以下对4.7中的代码进行改写，用队列+MaxNode控制

——————————————————————————————————————————————————————
输入：训练集 D={(x1,y1),(x2,y2),...,(xm,ym)};
      属性集 A={a1,a2,...,ad}
      最大节点数 MaxNode
过程：函数TreeGenerate(D,A,MaxNode)
1:生成节点root
2:if D中样本全部属于同一类别C then
3:     将root标记为C类叶节点;return
4:end if
5:if A=空集 or D中样本在A上取值相同 then
6:     将root标记为叶节点，其类别标记为D中样本数最多的类；return
7:end if
8:从A中选择最优划分属性a*;
9:将root标记为分支节点，属性为属性a*;
10:将root放入NodeQueue;
11:将D放入DataQueue;
12:将A\{a*}放入AQueue;
13:初始化节点数numNode=1;
14:while NodeQueue 非空:
15:     取出NodeQueue队尾的节点rNode，其对应的属性是ra*;
16:     取出DataQueue队尾的数据集rD;     #此处r均指队尾rear
17:     取出AQueue队尾的属性集rA;
18:     if numNode==MaxNode:
19:          将rNode标记为叶节点，类别标记为rD中样本最多的类;
20:          continue;     #跳过本次循环，即不再对这个节点做展开。对于下一个节点，由于条件任然成立，故任然不展开
21:     for ra*的每一个取值ra*v do:
22:          为rNode生成一个分支节点，令rDv表示rD在ra*上取值为ra*v的样本子集;
23:          if rDv为空 then：
24:               将分支节点标记为叶节点，其类别标记为rD中样本最多的类;
25:          else if rD中样本全部属于同一类别C then
26:               将分支节点标记为C类叶节点;
27:          else if rA=空集 or rD中样本在A上取值相同 then
28:               将分支节点标记为叶节点，其类别标记为rD中样本数最多的类;
29:          else：
30:               从rA中选择最优划分属性a*v;
31:               将分支节点的属性记为a*v;
32:               将分支节点放入NodeQueue的队头;
33:               将rDv放入DataQueue的队头;
34:               将rA\{a*v}放入AQueue的队头;
35:               将(rDepth+1)放入DepthQueue的队头;
36:          end if
37：         numNode+=1
38:     end for
39:end while
输入：以root为根节点的一棵决策树
——————————————————————————————————————————————————————

讨论：4.7中与4.8中用队列的话均为广度优先搜索，我觉得是出题的时候的疏忽。。

应该是广度优先搜索（队列）+MaxNode控制 与 深度优先搜索（堆栈）+MaxDepth控制 两种方法之间的比较。

个人认为，广度优先搜索（队列）+MaxNode 的方法更容易控制决策树所需内存不溢出。因为最大节点数目是固定的。队列中储存的是当前深度未处理的节点以及当前深度以处理节点的下一级节点，其数目是可控的，总小于最大节点数。而深度优先搜索在堆栈中储存的是当前节点的兄弟节点、当前节点的父节点、当前节点的父节点的兄弟节点.....若一些分支节点的分支数很多，那么堆栈的深度就会比较深，虽然有MaxDepth控制最大深度，但还是可能出现栈溢出的情况。

4.9

试将4.4.2节对缺失值的处理机制推广到基尼指数的计算中去。

最近时间不多，暂且挖个坑。

4.10

从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集3.0上产生的结果。
答：此处要求实现一种多变量决策树算法。实际上4.3与4.4题就是多变量决策树算法。其在西瓜数据集3.0上产生的结果如下

最近时间不多，暂且挖个坑。