《统计学习方法》阅读笔记——第5章-决策树
统计学习方法笔记——第5章-决策树
决策树
决策树模型
决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。决策树学习本质是从训练数据集中归纳出一组分类规则。
决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。
决策树模型可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树的路径或其对应的 if-then 规则集合具有一个重要的性质：互斥并且完备。每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。
决策树对应于给定特征条件下类的条件概率分布\(P(Y|X)\)时(\(X\) 取值于给定划分下单元的集合，\(Y\) 取值于类的集合)，示例如下图所示，决策树的一条路径对应于划分中的一个单元。
决策树策略
需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。决策树学习用损失函数表示这一目标，损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
决策树学习算法
当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是 NP 完全问题，通常采用启发式方法，近似求解这一最优化问题。
决策树学习算法通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，对应着特征空间的划分，也对应着决策树的生成（构建）。
以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象，对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。
决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。
决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。
主要优点
模型具有可读性，分类速度快。
特征选择
特征选择在于选取对训练数据具有分类能力的特征。
特征选择的准则是信息增益或信息增益比。
信息增益和信息增益比
信息论中信息增益也称为互信息，其表示已知一个随机变量的信息后使得另一个随机变量的不确定性减少的程度。 \[ 信息增益=信息熵-条件熵 \] 根据信息增益准则的特征选择方法是：对训练数据集（或子集）D ，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
信息熵
信息熵可以度量随机变量X的不确定性，信息熵越大越不确定，可转换到度量样本集合纯度，信息熵越小样本集合的纯度越高。
样本集合\(D\)中第\(k\)类样本所占比例为\(p_k(k=1,2,3...,N)\)，则\(D\)的信息熵定义为： \[ Ent(D)=-\sum\limits_{k=1}^{N}p_k * log2(p_k) \]
当样本集合中各个类别所占比例相同时(\(p_1=p_2=...p_k=\frac {1}{N}\))，信息熵达到最大值\(log_2N\)，纯度最低；
当样本集合中只有类别\(i\)的样本，其他类别样本数量为0时(\(p_i=1,p_1=p_2=...=p_{i-1}=p_{i+1}=...=p_k=0\))，信息熵达到最小值\(0\)，纯度最高。
条件熵
条件熵表示的是在已知一个随机变量的条件下， 另一个随机变量的不确定性。假设有随机变量 X 和 Y ，且它们服从以下联合概率分布：
\(P(X = x_i , Y = y_j ) = p_{ij} \space\space\space\space i = 1, 2, ...., n; j = 1, 2, ..., m\)
在已知\(X\)的条件下，随机变量\(Y\)的条件熵表示，已知\(X\)取值\(x_i\)后，\(Y\)的不确定性，计算公式如下： \[ Ent(Y|X) = \sum_{i=1}^np_iEnt(Y|X=x_i) \] 从单个特征\(a\)的角度来看，假设其可能取值为{\(a^1,a^2,...,a^V\)}，\(D^v\)表示属性取值为\(a^v∈{}\){\(a^1,a^2,...,a^V\)}的样本集合，\(\frac {|D^v|}{|D|}\)表示占比，那么在已知属性\(a\)的取值后（即在\(D^v\)的样本集合中），样本集合\(D\)的条件熵为： \[ \sum_{v=1}^V\frac {|D^v|}{|D|}Ent(D^v) \]
信息增益
具体地，假设有随机变量\(X\)和\(Y\)，那么在已知\(X\)的信息后，\(Y\)的不确定性减少的程度为： \[ I(Y;X) = Ent(Y) − Ent(Y|X) \] 在已知属性（特征）\(a\)的取值后\(Y\)的不确定性减少的量，也即纯度的提升，信息增益为： \[ Gain(D, a) = Ent(D)−\sum_{v=1}^V\frac {|D^v|}{|D|}Ent(D^v) \]
缺点
信息增益准则对可取值数目较多的属性有所偏好，比如每个样本都不同的ID号，该特征的信息增益可达到0.998（每个样本为一个分支，纯度已达到最大），远大于其他候选划分属性，但无法对新样本进行有效预测。
信息增益比
在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。使用信息增益比（information gain ratio）可以对这一问题进行校正。
信息增益比时信息增益与训练数据集D的经验熵之比： \[ \begin{align} Gain\_ratio(D, a)=\frac {Gain(D, a)}{Ent(D)} \end{align} \]
缺点
信息增益比对可取值数目较少的属性有所偏好。
决策树的生成
一般流程
决策树生成的一般流程可以概括如下：
- 从根结点（root node）开始，根据特征打分准则（如信息增益、信息增益比等）对结点计算所有可能的特征得分，选择对训练数据最具分类能力的特征（如信息增益最大、信息增益比最大等）作为结点的特征，由该特征的不同取值建立子结点；
- 再对子结点递归地调用以上方法，构建决策树；
- 直到所有特征的得分在阈值内或没有特征可以选择为止，最后得到一个决策树。
ID3算法
ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。ID3 相当于用极大似然法进行概率模型的选择。
ID3 算法只有树的生成，所以该算法生成的树容易产生过拟合。
算法流程如下：
C4.5生成算法
C4.5 在生成的过程中，用信息增益比来选择特征。
流程如下：
决策树的剪枝
只进行决策树生成的模型，往往容易造成过拟合。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。
决策树的损失函数
设树\(T\) 的叶结点个数为\(|T |\)，\(t\) 是树\(T\) 的叶结点，该叶结点有$ N_t$ 个样本点，其中 \(k\) 类的样本点有 \(N_{tk}\) 个，\(k =1,2, , ...... K\) ，$ H_t(T )\(为叶结点\)t$ 上的经验熵，\(\alpha ≥ 0\)为参数，则决策树学习的损失函数可以定义为： \[ \begin{align} C_\alpha(T)=&\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T| \\ H_t(T)=&-\sum_k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t} \\又令：C(T)=&\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}N_t\sum_k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t} \\ \therefore C_\alpha(T)=&C(T)+\alpha|T| \end{align} \] \(C(T)\)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，\(|T|\)表示模型复杂度，参数\(\alpha≥0\)控制两者之间的影响．较大的\(\alpha\)促使选择较简单的模型（树），较小的\(\alpha\)促使选择较复杂的模型（树），\(\alpha=0\)意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。损失函数正好表示了对两者的平衡.。
剪枝算法
剪枝，就是当\(\alpha\)确定时，选择损失函数最小的模型，即损失函数最小的子树。
决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
决策树损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。
CART决策树
CART是Classification and Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。其生成的决策树为二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。
CART决策树使用"基尼指数"(Gini index)来选择划分属性。CART 是在给定输入随机变量 \(X\) 条件下输出随机变量\(Y\) 的条件概率分布\(P(Y|X)\)的学习方法。
CART 算法由决策树生成和决策树剪枝两步组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART生成
CART决策树生成是递归地构建二叉决策树的过程。
- 对回归树用平方误差最小化准则，进行特征选择，生成二叉树；
- 对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。
回归树生成
回归树模型
假设已将输入空间划分为\(M\)个单元\(R_1,R_2,...R_M\)，并且在每个单元\(R_M\)上有一个固定的输出值\(c_m\)，于是回归树模型可表示为： \[ \begin{align} f(x)=\sum_{m=1}^Mc_mI(x\in R_m),I为指示函数 \end{align} \]
回归树对训练数据的训练误差
用平方误差来表示回归树对于训练数据的预测误差。 \[ \sum_{x_j\in R_m}(y_i-f(x_i))^2 \] 用平方误差最小的准则求解每个单元上的最优输出值\(\hat c_m\)： \[ \hat c_m=(y_i|x_i\in R_m) \]
启发式方法对输入空间进行划分
这样的回归树通常称为最小二乘回归树（least squares regression tree），算法流程如下：
分类树生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼值相对于ID3决策树中的信息熵，而基尼指数相对于ID3决策树中的条件熵。
基尼值
可以用Gini(D)反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。Gini(D)越小，则数据集的纯度越高： \[ Gini(D)=\sum_{k=1}^Np_k(1-p_k)=1-\sum_{k=1}^N{p_k}^2 \]
基尼指数
属性\(a\)的基尼指数表示在已知属性\(a\)的取值后（即在\(D^v\)的样本集合中），样本集合\(D\)的基尼值之和，即为： \[ Gini\_index(D,a)=\sum_{v=1}^V\frac {|D^v|}{|D|}Gini(D^v) \] 选择基尼指数最小的属性作为最优划分属性： \[ a_∗ = \mathop{arg min}_{a∈A}\space Gini\_index(D, a) \]
CART分类树生成算法流程如下：
CART剪枝
CART 剪枝算法由两步组成：
- 首先从生成算法产生的决策树\(T0\) 底端开始不断剪枝，直到T0 的根结点，形成一个子树序列\(\{T_0,T_1,...,T_n\}\)；
- 然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
剪枝，形成一个子树序列
回顾一下，前面提到决策树的损失函数为： \[ C_\alpha(T)=C(T)+\alpha|T| \] \(T\) 为任意子树，\(C (T )\) 为对训练数据的预测误差（如基尼指数），\(|T |\)为子树的叶结点个数，\(\alpha≥ 0\) 为参数，\(C_\alpha( T )\) 为参数是\(\alpha\) 时的子树\(T\) 的整体损失。参数\(\alpha\) 权衡训练数据的拟合程度与模型的复杂度。
对固定的\(\alpha\) ，一定存在使损失函数\(C_\alpha(T)\)最小的唯一子树，将其表示为\(T_\alpha\) 。（习题5.3）
当\(\alpha\)大的时候，最优子树\(T_\alpha\)偏小；当\(\alpha\)小的时候，最优子树\(T_\alpha\)偏大。当\(\alpha=0\)时，整体树是最优的．当\(\alpha \rightarrow ∞\) 时，根结点组成的单结点树是最优的。
Breiman 等人证明：可以用递归的方法对树进行剪枝。将\(\alpha\) 从小增大，\(0=\alpha_0<\alpha_1<\alpha_2....<\alpha_n<+∞\) ，产生一系列的区间 \([\alpha_i,\alpha_{i+1}),i=0,1,....,n\)；剪枝得到的子树序列对应着区间\(\alpha \in [\alpha_i,\alpha_{i+1}),i=0,1,....,n\)的最优子树序列\(\{T_0,T_1,...,T_n\}\)，序列中的子树是嵌套的。（习题5.4）
剪枝原理如下：
通过交叉验证选取最优子树
利用独立的验证数据集，测试子树序列中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树\(T_i\)都对应于一个参数 \(\alpha_i\)。 所以，当最优子树\(T_i\) 确定时，对应的\(\alpha_i\)也确定了，即得到最优决策树\(T_\alpha\) 。
CART剪枝算法
其他
还有一些关于剪枝的内容在之前的西瓜书笔记中提过了，不再赘述：西瓜书阅读笔记——第4章-决策树
习题
习题5.1
题目
根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。
表5.1 贷款申请样本数据表
| ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
解
信息增益比
\[ \begin{align} Gain\_ratio(D, a)=&\frac {Gain(D, a)}{Ent(D)} \\ Gain(D, a) =& Ent(D)−\sum_{v=1}^V\frac {|D^v|}{|D|}Ent(D^v) \\ Ent(D)=&-\sum\limits_{k=1}^{N}\frac{|C_k|}{|D|} \log2(\frac{|C_k|}{|D|}) \end{align} \]
C4.5决策树算法流程
数据
import pandas as pd |
sklearn.DecisionTreeClassifier实现(只有ID3和CART)
使用sklearn的DecisionTreeClassifier类构建决策树，并使用graphviz包展示。安装graphviz点这里
DecisionTreeClassifier()模型方法中也包含非常多的参数值。例如：
criterion = gini/entropy可以用来选择用基尼指数或者熵来做损失函数（也就是说只有ID3和CART树的实现）。splitter = best/random用来确定每个节点的分裂策略。支持 “最佳” 或者“随机”。max_depth = int用来控制决策树的最大深度，防止模型出现过拟合。min_samples_leaf = int用来设置叶节点上的最少样本数量，用于对树进行修剪。
from sklearn.tree import DecisionTreeClassifier |
# 打印决策树 |
自编程实现C4.5算法
import json |
# 表5.1的训练数据集 |
{ |
习题5.2
题目
已知如表5.2所示的训练数据，试用平方误差损失准则生成一个二叉回归树。
表5.2 训练数据表
| \(x_i\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| \(y_i\) | 4.50 | 4.75 | 4.91 | 5.34 | 5.80 | 7.05 | 7.90 | 8.23 | 8.70 | 9.00 |
解
最小二乘回归树生成算法流程
数据
X_train = np.array([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]).T |
sklearn实现
from sklearn.tree import DecisionTreeRegressor |
自编程实现
import json |
model_tree = MyLeastSquareRegTree(train_X, y, epsilon=0.2) |
{ |
习题5.3
题目
证明 CART 剪枝算法中，当\(\alpha\)确定时，存在唯一的最小子树\(T_{\alpha}\)使损失函数\(C_{\alpha}(T)\)最小。
解
剪枝算法：
- 内部节点是否剪枝只与以该节点为根节点的子树有关；
- 当\(C_\alpha(t) < C_\alpha(T_t)\)时，对以结点tt为根节点的子树进行剪枝。
证明存在
\(\alpha\)确定，生成的子树中，每个子树对应一个损失函数，一定存在一个子树使得损失函数最小；
证明唯一性-反证法
假设有两个子树使得损失最小（一样小），如下图所示：
整个树\(T_1\)有两个子树\(T_2\)和\(T_3\)，其剪枝位置分别为\(t_2\)和\(t_3\)，假设两棵子树都是\(T_1\)的最优子树，使得损失函数最小。则满足以下等式： \[ C_{\alpha}(T_2)=C_{\alpha}(T_3) \] 根据子树\(T_2\)的剪枝位置是\(t_2\)，剩下t3，可得 \[ C_{\alpha}(t_2)<C_{\alpha}(T_2) \] 根据子树\(T_3\)的剪枝位置是\(t_3\)，剩下t2，可得 \[ C_{\alpha}(t_3)<C_{\alpha}(T_3) \] 由上面公式可得： \[ \begin{align} C_{\alpha}(t_2)<C_{\alpha}(T_3) \\ C_{\alpha}(t_3)<C_{\alpha} (T_2) \end{align} \] 根据上述公式，可知\(T_2\)和\(T_3\)都可以进一步剪枝，剪枝之后的子树记作\(T_4\)：
则\(T_4\)的损失函数比\(T_2\)和\(T_3\)更小，假设“两棵子树都是\(T_1\)的最优子树，使得损失函数最小。”不成立，得证。
习题5.4
题目
证明 CART 剪枝算法中求出的子树序列\(\{T_0,T_1,\cdots,T_n\}\)分别是区间\(\alpha \in [\alpha_i,\alpha_{i+1})\)的最优子树\(T_{\alpha}\)，这里\(i=0,1,\cdots,n,0=\alpha_0 < \alpha_1 < \cdots, \alpha_n < +\infty\)。
解
当\(\alpha\)大的时候，最优子树\(T_\alpha\)偏小；当\(\alpha\)小的时候，最优子树\(T_\alpha\)偏大。当\(\alpha=0\)时，整体树是最优的．当\(\alpha \rightarrow ∞\) 时，根结点组成的单结点树是最优的。
即：当\(\alpha_2 \geq \alpha_1\)，\(|T_{\alpha_2}| \geq |T_{\alpha_1}|\)，树\(T\)在\(\alpha_2\)条件下的最优子树一定是树\(T\)在\(\alpha_1\)条件下的最优子树的子树，\(T_{\alpha_1}\)嵌套了\(T_{\alpha_2}\)，\(T_{\alpha_2}\preceq T_{\alpha_1}\)。
- 当\(\alpha \geq \alpha_1\)时，需要进行剪枝，因此\(T_0(\alpha)=T_1\)；
- 当\(\alpha_1 \leqslant \alpha < \alpha_2\)时，\(T_0(\alpha) \preceq T_0(\alpha_1) = T_1 \preceq T_0,且T_2 \prec T_1\)；
所以，\(T_0(\alpha)=T_1(\alpha)=T_1\)，该式说明\(T_1\)是区间\([\alpha_1, \alpha_2)\)的最优子树。依次类推，子树\(T_i\)是区间\([\alpha_i,\alpha_{i+1})\)里最优的，原结论得证。
参考资料
【sklearn决策树算法】DecisionTreeClassifier(API)的使用以及决策树代码实例 - 鸢尾花分类 - Yanqiang - 博客园 (cnblogs.com)
