决策树

• 也称为：判别树
  
• 有时也称为学习方法。
  
• 有时称为学习树。
  
• 决策树是一种常见的机器学习方法。
  

1. 基本概念

• 问题导入
  

举例：
- 以二分类任务为例。
- 我们希望从给定训练数据集学得一个模型，用以对新示例进行分类。
- 这个把样本分类的任务，可看作对"当前样本属于正类吗?"这个问题的"决策"或"判定"过程。

子决策：
- 我们要对"这是好瓜吗?"这样的问题进行决策时。
- 通常会进行一系列的判断或"子决策"：
- 我们先看"它是什么颜色?"。如果是"青绿色"，
- 则我们再看"它的根蒂是什么形态?"。如果是"蜷缩"，
- 我们再判断"它敲起来是什么声音?"，
- 最后，我们得出"最终决策":这是个好瓜.

1.1 决策树的性质

- 一棵决策树包含"一个"根结点、若干个内部结点和若干个叶结点;
- "叶"结点对应于决策结果。
- 其他每个结点则对应于一个"属性"测试;
- 根结点包含"样本全集"。
- 从根结点到每个叶结点的路径对应了一个"判定测试序列"。

1.2 决策树学习的目的

- 决策树学习的"目的"是为了产生一棵"泛化能力"强的决策树。
- 即处理未见示例能力强的决策树。
- 其基本流程遵循简单且直观的"分而治之"(divide-and-conquer) 策略。
- 我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的"纯度" (purity) 高。

1.3 决策树学习基本算法

输入: 训练集 D = {(x1, y1), (x2, y2), (x3, y3), ..., (xm, ym)}
      属性集 A = {a1, a2, ..., ad}
过程: 函数 TreeGenerate(D, A)
1. 生成节点 node;
2. if D 中样本全属于同一类别 C then
3. 		将 node 标记为 C 类叶节点：
4. 		return;
5. end if
6. if A = null || D 中样本在 A 上取值相同 then
7. 		将 node 标记为叶节点，其类别标记为 D 中样本数最多的类;
8. 		return;    
9. end if
10.从 A 中选择最优划分属性 ai (0 < i <= d);
11.for ai 的每一个值 a_vi do
10.		为 node 生成一个分支; 令 Dj (0 < j <= m) 表示 D 中在 ai 上取值为 a_vi 的样本子集;
11.		if Dj 为空 then
12.			将分支节点标记为叶节点，其类别标记为 D 中样本最多的类。
13.			return;
14.		else
15.			以 TreeGenerate(Dj, A\{ai}) 为分支节点
16.		end if
17.end for
输出：以 node 为根节点的一颗决策树

• 算法解释
  

"名词解释："
1. 机器学习2——绪论里面有专业名称的解释。
2. 训练集 D --> 数据集 data set
3. 属性集 A --> 属性 attribute
4. 一项数据：（x1, y1）, 就有属性集 A 的全部
5. 最优划分属性 ai : 属性集 A 的子集, i 为下标，代表第几个属性
6. a_vi : attribute value, 所对应属性的属性值。
7. TreeGenerate(Dj, A\{ai}) : Dj 是已经训练好的一个节点，A\{ai} : ai 这个属性已经被用了，把它除去。

"算法原理解释："
- 决策树的生成是一个递归过程。
- "决策树学习的关键是" : 从 A 中选择最优划分属性 ai (0 < i <= d);
- 有三种情况会导致递归返回：
1. 当前节点包含的样本全属于同一类别，无须划分。
2. 当前属性集为空，或者所有样本在所有属性集上取值为空，无法划分。（"处理：标记该节点为叶节点"）
3. 当前节点包含的样本集合为空，不能划分（"处理：标记该节点为叶节点"）。 

"第 2 种情况与第 3 种情况不一样"
- 在第 2 种情形下，我们把当前结点标记为叶结点，井将其"类别"设定为：该结点所含样本最多的类别。
- 在第 3 种情形下，同样把当前结点标记为叶结点，将其"类别"设定为：其父结点所含样本最多的类别。

2. 划分选择

• 由1. 基本概念
  

- 训练决策树的"目的"是：
我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的"纯度" (purity) 高。

- 决策树训练的算法"关键"为：
从 A 中选择最优划分属性 ai (0 < i <= d)

• 所以划分选择的概念
  

- 决策树学习的关键是从 A 中选择最优划分属性 ai，即如何选择最优划分属性。
- 一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，
即结点的"纯度" (purity) 越来越高.

2.1 信息增益

• 信息熵
  

定义

"信息熵" (information entropy) 
- 是度量样本集合纯度最常用的一种指标。

"例子："
假定当前样本集合 D 中第 k 类样本所占的比例为 pk (k = 1, 2, ..., |y|) ，则 D 的信息熵定义为:

公式

综上所述

1. 若 p = 0, 则 plog2(p) = 0
2. Ent(D) 的最小值为 0， 最大值为 log2(|y|)
3. Ent(D) 的值越小，则 D 的纯度越高。

• 信息增益
  

英语
information gain, 简写：Gain（D, a）

理解的例子

"题意："
假定离散属性 a 有 V 个可能的取值{a1, a2, ..., aV}, 
若使用 a 来对样本集合 D 进行划分，则会产生 V 个分支节点。
其中第 v 个分支节点包含了 D 中所有在属性 a 上取值为 av 的样本，记为 Dv。

"计算出 Dv 的信息熵："
Ent(Dv)

"不同分支节点包含的样本数不同，给分支节点赋予权重"
|Dv|/|D|
(用意：样本数越多的分支节点影响越大)

公式

综上所述

1. 信息增益越大，属性 a 划分越优。
（则意味着使用属性 a 来进行划分所获得的"纯度提升"越大）
2. 我们可用"信息增益"来进行决策树的划分属性选择。
3. 著名的 ID3 决策树学习算法 [Quinlan 1986] 就是以信息增益为准则来选择划分属性。
4. "改进算法：" 从 A 中选择最优划分属性 ai (0 < i <= d);

• 示例：经过训练的决策树
  

标题：用它作为训练集，训练一个决策树

计算信息熵：Ent

计算信息增益：Gain

计算出来的“纹理”信息增益最大

以“清”为例

- 清晰中有编号为 {1, 2, 3, 4, 5, 6, 8, 10, 15} 9 个样例
- 可用属性集合为 {色泽，根蒂，敲声，脐部，触感 }
- 基于 D^1 计算出各属性的信息增益。

重复直到所有属性都被划分
获取决策树：

• 信息增益的缺点
  

缺点

信息增益准则对可取值数目较多的属性有所偏好

简单的说

就是一个属性它的"属性值"越多，"信息增益"越大。

解释

2.2 增益率

• 与信息增益相同
  

都是为了选择分区属性

"由上可知："
信息增益准则对可取值数目较多的属性有所偏好。

"增益率"
- 为减少信息增益偏好可能带来的不利影响。
- 著名的 C4.5 决策树算法 [Quinlan 1993J 不直接使用信息增益，
- 而是使用"增益率" (gain ratio) 来选择最优划分属性。

• if：数字也用作划分属性
  

- 在上面的介绍中，我们有意忽略了表 4.1 中的"编号"这一列。
- 若把编号同样作为一个划分属性。
- "编号"将产生 17 个分支，每个分支结点仅包含一个样本，这些分支结点的"纯度"己达最大.
- 但是，这样的决策树显然不具有"泛化"能力，无法对新样本进行有效预测。

• 增益率公式
  

公式

起源

- 由信息增益改动而来
- 考虑到属性的取值数目

计算增益率

• 增益率的缺点
  

缺点

增益率准则对可取值数目较少的属性有所偏好

• 综合信息增益和增益率
  

信息增益与增益率相结合

1. 先从候选划分属性中找出信息增益高于平均水平的属性，
2. 再从中选择增益率最高的。

2.3 基尼指数

• 与信息增益相同
  

都是为了选择分区属性

- CART 决策树 [Breiman et al., 1984] 使用"基尼指数" (Gini index) 来选择划分属性。
- CART Classificationand Regression Tree 的简称，
- 这是一种著名的决策树学习算法，分类和回归任务都可用。
- 基尼指数一样可以"选择划分属性"。

• 基尼值
  

公式

综上所述

1. Gini(D) "越小"，则数据集 D 的"纯度越高"。
（Gini(D) 反映了从数据集 D 中随机抽取两个样本，其类别标记"不一致的概率"）

• 基尼指数
  

公式

改进算法
从 A 中选择最优划分属性 ai (0 < i <= d)

3. 剪枝处理

• 问题导入
  

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，
有时会造成决策树"分支过多"，这时就可能因训练样本学得"太好"了，
以致于把训练集"自身"的一些"特点"当作所有数据都具有的"一般性质"而导致"过拟合".
因此，可通过主动"去掉一些分支"来降低过拟合的风险.

• 目的
  

- 剪枝(pruning) 是决策树学习算法对付"过拟合"的主要手段.
- 目的为了提高决策树的"泛化能力"。

• 如何操作
  

决策树剪枝的基本策略有"预剪枝" (pre-pruning) 和"后剪枝"(post-pruning) 。

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

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

• 如何判断决策树的泛化性能是否提高？
  

方法：

"留出法"
预留一部分数据用作"验证集"以进行性能评估

改动上述的西瓜数据集 2.0：

基于训练集的决策树：

具体方法见下文

3.1预剪枝

• 根据信息增益，首先对属性进行预剪枝决策：脐
  

划分前：

拆分前的验证集准确度：

3/7 = 42.9%

验证集里，一共 7 个样例，3 个正例。

分割后：

划分的验证集准确率：

5/7 = 71.4%

验证集一共 7 个样例，5 个样例由划分后的"部分决策树"验证正确。（包含判断出了坏瓜）

预修剪决策：

• 以同样的方式，对其他属性执行相同的操作
  

颜色

预修剪决策

根

预修剪决策

• 来自预剪枝的决策树
  

• 综上所述
  

1. 上述预剪枝决策树的验证精度为：71.4%
2. 预剪枝使得决策树的很多分支都没有展开，降低了"过拟合"的风险。
3. 显著减少了决策树的"训练时间和测试时间"。
4. 有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能"暂时下降"。
5. 但在其基础上进行的后续划分却有可能导致"性能显著"提高。
6. 给预剪枝决策树带来了"欠拟含"的风险。

3.2后剪枝

• 首先从训练集中生成一个完整的决策树
  

计算验证集准确度

3/7 = 42.9%

一共 7 个样例，3 个由上述完整的决策树判断为正例。

• 后剪枝首先从 6 号结点开始
  

1. 若将其领衔的分支剪除，则相当于把 6号结点 替换为叶结点.（相当于把纹理替换为好瓜或坏瓜）
2. 替换后的叶结点包含编号为 {7 15} 的训练样本。
3. 于是该叶结点的类别标记为"好瓜"。
4. 此时决策树的验证集精度提高至 57.1%. 
5. 于是，后剪枝策略决定剪枝。

• 重复操作，从下往上，判断所有节点
  

剪枝后决策树：

其验证集准确度：

5/7 = 71.4%

综上所述：

1. 后剪枝决策树通常比预剪枝决策树保留了"更多的分支".
2. 一般情形下，后剪枝决策树的"欠拟合风险很小"。
3. 泛化能力"优于"预剪枝决策树。
4. 此其训练"时间开销"比未剪枝决策树和预剪枝决策树都要大得多.

4. 连续与缺失值

4.1 连续值处理

• 连续和离散属性
  

- 上面所用的都是"离散属性"来生成决策树(如："纹理")。（可理解为 点）
- 现实中往往都会遇到"连续属性"。（如："密度 = 0.697"）。（可理解为 线）
- 有必要讨论如何在决策树学习中"使用连续属性"。

• 连续属性离散化技术
  

"问题描述："
- 由于连续属性的"可取值数目"不再有限.
- 因此，不能直接根据连续属性的取值来对结点进行划分.
- 由此连续属性离散化技术可派上用场。

"解决策略："
采用"二分法"(bi-partition) 对连续属性进行处理

"简单来说："
就是规定一个划分点 t
>t , 划分为一个样例集
<t , 划分为一个样例集

"怎样确定划分点："
1. 把区间 [a^i, a^i+1) 的中位点作为"候选划分点"。
2. 像离散属性值一样来考察这些划分点。
3. 选取"最优的划分点"进行样本集合的划分。

• 候选分割点集
  
  
• 连续属性 – 信息增益公式
  

• 按照上面的例子
  

西瓜数据集 3.0

连续属性 – 密度

1. 计算候选划分点集合
（17 个密度属性取值，计算得到 16 个结果。）
Ta = {0.244, 0.294, 0.351, 0.381, 0.420, 0.459, 
0.518, 0.574, 0.600, 0.621, 0.636, 
0.648, 0.661, 0.681, 0.708, 0.746}

2. 计算 16 次，算不同候选密度的信息增益

3. 比较 16 个信息增益的大小，取最大值（得到 密度的信息增益）

4. 比如：最大信息增益为 0.262.
- 那么密度的信息增益为 0.262
- 对应的点为 0.381
- 0.381 就是最优划分点 t

难点：计算不同候选密度的信息增益
（以 0.381 为例）

• 生成决策树
  

4.2 缺失值处理

• 问题导入
  

- 现实任务中常会遇到不完整样本，即样本的某些"属性值缺失"。
- "例如："由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值(如 HIV 测试结果)未知。
- 如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对"数据信息极大的浪费"。
例子如下：

• 缺少属性值的西瓜数据集
  

• 两个待解决的问题
  

(1) 如何在属性值缺失的情况 进行划分属性选择?
(2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分?

• 使用的特征名词
  

数学符号

1. D'
给定训练集 D 和属性 a
令 D' 表示 D 中在属性 a 上没有缺失值的样本子
集

2. D'v
假定属性 a 有 V 个可取值 {a1, a2, a3, ..., aV}
D'v 表示 D' 中在属性 a 上的取值为 av 的样本子集

3. D'k
D'k 表示 D' 中属于第 k 类（k = 1, 2, ..., |y|）的样本子集

为每个样本 x 赋予一个权重 wx, 并定义：
4. p
p 表示无缺失值样本所占的比例

5. p'k
p'k 表示无缺失值样本中第 k 类所占的比例

6. r'v
r'v 表示无缺失值样本中在属性 a 上取值为 av 的样本所占的比例

促销信息增益公式

• 对于问题（1）
  

我们仅可根据 D' 来判断属性 a 的"优劣".

• 对于问题（2）
  

"具体操作："
1. 若样本 x 在划分属性 a 上的取值己知
- 则将样本 x 划入与其取值对应的子结点
- 且样本权值在子结点中保持为 ωx.

2. 若样本 x 在划分属性 a 上的取值未知
- 将 x 同时划入所有子结点
- 且样本权值在与属性值 av 对应的子结点中调整为 r'v * wx
("直观来说")让同一个样本以不同的"概率"划入到不同的子结点中去.

• 实际例子——表4.4
  

一个已知的：

样本集 D 中全部 17 个样例，各样例的权值均为1

以“颜色”为例：

该属性上的无缺失值的样例子集 D' :
D' = {2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17}, 
共 14 个样例，6 个正例， 8 个反例

D’ 的信息熵为：

D’ 上属性 ”色泽“ 的信息增益

D 上属性 ”色泽“ 的信息增益

同理，计算出其他所有属性在 D 上的信息增益

• 很巧合的是：我们遇到了问题（2）
  

1. "纹理"在所有属性中取得了最大的倍息增益，被用于对根结点进行划分.
2. 编号为 {8, 10} 的样本在属性"纹理"上出现了缺失值
解决方案如下：

• 最终决策树
  

5. 多变量决策树

• 分类边界
  

- 若我们把每个属性视为坐标空间中的一个坐标轴，则 d 个属性描述的样本
就对应了 d 维"空间"中的一个数据点。
- 对样本分类则意味着在这个坐标空间中寻找不同类样本之间的"分类边界"。

• 查找分类边界的示例
  

数据集：

训练好的决策树：
（方法：连续值的处理）

映射：建立分类边界

• 多元决策树
  

概念：

- "多变量决策树" (multivariate decision tree) 就是能实现"斜划分"甚至更复杂划分的决策树。

例如：

综上所述：

- 红色段就是我们需要的"斜的划分边界"。
- 在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性。
- 而是试图建立一个合适的"线性分类器"。

• 多元决策树示例
  

6. 拓展

• 为什么上面的那些公式？
  

为什么要使用这个数学公式？

• 如何生成多元决策树？
  

• 决策树学习的经典代表
  

1. ID3 基于 信息增益
2. CART 基于 基尼系数

"多变量决策树算法主要有："
OC1 : 
先贪心地寻找每个属性的最优权值，
在局部优化的基础上再对分类边界进行随机扰动以试图找到更好的边界;

• 决策树算法越来越多地跟进
  

亮点1：结合神经网络

还有一些算法试图在决策树的叶结点上嵌入神经网络，以结合这两种学习机制的优势，
例如"感知机树" (Perceptron tree) 在决策树的每个叶结点上训练一个感知机。

亮点2：增量学习

在接收到新样本后可对己学得的模型进行调整，而不用完全重新学习.

代表算法
1. ID4
2. ID5R
3. ITI