第四章 决策树
4.1 基本流程
- 决策树（decision tree）：基于树结构来进行决策。
- 决策过程的最终结论对应了我们所希望的判定结果；
- 决策过程中提出的每个判定问题都是对某个属性的“测试”；
- 每个测试的结果或是导出的最终结论，或是导出的进一步的判定问题。
- 决策树包含：
- 一个根结点：包含样本全集
- 若干个内部结点：根据属性测试的结果划分的样本子集。
- 若干个叶结点：对应于决策结果。从根结点到叶结点的路径对应了一个判定测试序列。
- 目的：产生一颗泛化能力强，处理未见示例能力强的决策树。遵循“分而治之”策略。
- 决策树的产生是一个递归过程，有三种情形会导致递归返回
- 当前结点包含的样本全属于同一类别，无需划分；
- 当前属性集为空，或是所有样本在所有属性上去取值相同，无法划分；在此情况下，把当前结点标记为叶结点，将其类别设定为该结点所含样本最多的类别。
- 当前结点包含的样本集合为空，不能划分。在此情况下，把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。
4.2 划分选择
- 随着划分的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（purity）越来越高。
4.2.1 信息增益
- 信息熵（information entropy）是度量样本集合纯度最常用的一种指标
- 假定当前样本集合$D$中第$k$类样本所占的比例为$p_k(k=1,2,…,\mid Y\mid )$，则$D$的信息熵定义为：$Ent(D)=-\sum_{k=1}^{\mid Y\mid }p_klog_2p_k$
- $Ent(D)$的值越小，则$D$的纯度越高
- 假定离散属性$a$有$V$个可能的取值${a^1,a^2,…,a^V}$，若使用$a$来对样本集$D$进行划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$个取值为$a^v$的样本，记为$D^v$。
- 计算$D^v$的信息熵
- 考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$\mid D^v\mid /\mid D\mid $，即样本数越多的分支结点的影响越大
- 可以计算出属性$a$对样本集$D$进行划分所获得的“信息增益”（information gain）：$Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{\mid D^v\mid }{\mid D\mid }Ent(D^v)$
- 信息增益越大，意味着使用属性$a$来进行划分所获得的“纯度提升”越大。
- 可以用信息增益来进行决策树的划分属性选择。$a_*=\mathop{\arg \max}\limits_{a\in A}Gain(D,a)$，ID3决策树学习算法就是以信息增益为标准来选择划分属性。
4.2.2 增益率
- C4.5决策树算法不直接使用信息增益，而是使用增益率（gain ratio）来选择最有划分属性。$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$，其中$IV(a)=-\sum_{v=1}^V\frac{\mid D^v\mid }{\mid D\mid }log_2\frac{\mid D^v\mid }{\mid D\mid }$，称为属性$a$的固有值（instrinsic value）
- 属性$a$可能的取值数目越多（V越大），$IV(a)$的值通常会越大。
- 增益率准则对可取值书目较少的属性有所偏好，C4.5算法不是直接选择增益率最大的候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益率高于平均水平的属性，再从中选择增益率最高的。
4.2.3 基尼指数
-
CART决策树使用基尼指数（Gini index）来选择划分属性。数据集$D$的纯度可用基尼值来度量：$Gini(D)=\sum_{k=1}^{\mid Y\mid }\sum_{k’\not=k}p_kp_{k’}=1-\sum_{k=1}^{\mid Y\mid }p_k^2$
-
直观来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。
- $Gini(D)$越小，数据集$D$纯度越高。
- 属性$a$的基尼指数定义：$Gini_index(D,a)=\sum_{v=1}^V\frac{\mid D^v\mid }{\mid D\mid }Gini(D^v)$
- 在候选属性集合$A$中，选择那个使得划分后基尼指数最小的属性作为最有划分属性，$a_*=\mathop{\arg \min}\limits_{a\in A}Gini_index(D,a)$
4.3 剪枝处理
- 剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。
- 为尽可能正确分类训练样本，结点划分过程将不断重复；
- 造成决策树分支过多，导致训练样本学习太好而过度拟合。
- 剪枝策略：
- 预剪枝（prepruning）：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶节点。
- 后剪枝（postpruning）：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
4.3.1 预剪枝
- 预剪枝要对划分前后的泛化性能进行估计
- 划分之前，所有样例集中在根节点，若不进行划分，该节点将被标记为叶节点，其类别标记为训练样例最多的类别。
- 仅有一层划分的决策树，称为决策树桩（decision stump）
- 预剪枝使得决策树的很多分支都没有展开，降低了过拟合的风险，减少了决策树的训练时间开销和预测时间开销。
- 预剪枝基于“贪心”本质禁止分支展开，带来了欠拟合的风险。
4.3.2 后剪枝
- 后剪枝先从训练集生成一颗完整的决策树。
- 后剪枝决策树通常比预剪枝保留了更多分支，欠拟合风险很小，泛化性能往往优于预剪枝决策树。
- 后剪枝过程是在生成完全决策树之后进行的，要自底向上地对书中的所有非叶节点进行逐一考察，训练开销时间开销比未剪枝决策树和预剪枝决策树要大。
4.4 连续与缺失值
4.4.1 连续值处理
- 讨论如何在决策树学习中使用连续属性
- 连续属性的可取值数目不再有限
- 不能直接根据连续属性的可取值来对结点进行划分
- 采用连续属性离散化技术。
- 二分法（bi-partition）处理连续属性
- 给定样本集$D$和连续属性$a$，假定$a$在$D$上出现了$n$个不同的取值，将这些值从小到大进行排序，记为${a^1,a^2,…,a^n}$。基于划分点$t$可将$D$分为子集$D_t^-$和$D_t^+$，其中$D_t^-$包含那些在属性$a$上取值不大于$t$的样本，而$D_t^+$则包含那些在属性$a$上取值大于$t$的样本。
- 对连续属性$a$，我们可以考察$n-1$个元素的候选划分点集合：$T_a={\frac{a^i+a^{i+1}}{2}\mid 1≤i≤n-1}$，即把区间$[a^i,a^{i+1})$的中位点$\frac{a^i+a^{i+1}}{2}$作为候选划分点。
- 然后就可以像离散属性值一样来考察这些划分点。
4.4.2 缺失值处理
-
缺失值处理需要解决两个问题：
-
如何在属性值缺失的情况下进行划分属性选择？
-
给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
-
-
给定训练集$D$和属性$a$，令$\bar D$表示$D$在属性$a$上没有缺失值的样本子集，对问题1，可以根据$\bar D$来判断属性$a$的优劣。
- 假定属性$a$有$V$个可取值${a^1,a^2,…,a^V}$，令$\bar D^V$表示$\bar D$中在属性$a$上取值为$a^V$的样本子集，$\bar D_k$表示$\bar D$中属于第$k$类$(k=1,2,…,\mid Y\mid )$ 的样本子集，显然有$\bar D=\bigcup_{k=1}^{\mid Y\mid }\bar D_k$，$\bar D=\bigcup_{v=1}^V\bar D^v$
- 假定我们为每个样本$x$赋予一个权重$w_x$，并且定义$\rho=\frac{\sum_{x \in \bar D}w_x}{\sum_{x \in D}w_x}$，$\bar p_k=\frac{\sum_{x \in \bar D_k}w_x}{\sum_{x \in D}w_x}$，$\bar r_v=\frac{\sum_{x \in \bar D_v}w_x}{\sum_{x \in D}w_x}$，其中$(1\le k\le \mid Y\mid )$，$(1\le v\le V)$。
4.5 多变量决策树
- 把每个属性视为坐标空间中的一个坐标轴，$d$个属性描述的样本就对应了$d$维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。
- 决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。
- 如果能够使用斜的划分边界，决策树模型将大为简化。多变量决策树（multivariate desicision tree）就可以实现这样的斜划分。
- 在此类决策树种，非叶结点不再仅对某个属性，而是对属性的线性组合进行测试。
- 每个非叶结点是一个形如$\sum_{i=1}^dw_ia_i=t$的线性分类器，其中$w_i$是属性$a_i$的权重，$w_i$和$t$可在该结点所含的样本集和属性集上学得。
