Skip to content

Latest commit

 

History

History
executable file
·
335 lines (229 loc) · 12.6 KB

README.md

File metadata and controls

executable file
·
335 lines (229 loc) · 12.6 KB
Raw

CH05 决策树

Hits

[TOC]

前言

章节目录

  1. [模型与策略]决策树模型与学习
    1. 决策树模型
      1. 决策树与if-then规则
      2. 决策树与条件概率分布
    2. 决策树学习(三个步骤:特征选择，决策树生成，决策树修剪)
  2. 算法
    1. [算法]特征选择
      1. 特征选择问题(下面两个介绍了常用的准则，另外还有基尼系数在CART算法部分讲解)
        1. 信息增益
        2. 信息增益比
    2. [算法]决策树的生成
      1. ID3算法
      2. C4.5的生成算法
    3. [算法]决策树的剪枝
    4. [算法]CART算法
      1. CART生成
      2. CART剪枝

导读

  • 决策树是一种基本的分类与回归方法. 在书中CART算法之前的章节说的都是分类树，ID3和C4.5都只能处理分类问题，从CART(Classification and Regression Tree)开始有回归树，统称为决策树
  • 以上在章节目录部分添加了一部分标记，把这个章节按照模型，策略与算法进行划分，进一步重新整理了结构，希望可以帮助理清章节内容之间的关系
  • 在CH12中有提到，决策树学习的损失函数是对数似然损失，关于决策树的剪枝，最重要的在于这个损失函数的理解。
  • 这个章节的主题是决策树，内容内涵和外延都很广，这个章节推荐阅读图灵社区的一个访谈1，了解一下李航老师的故事，也可以对本章的最后三个参考文献234有进一步的了解.
  • 引文中关于CART的介绍，是一本368页的书，2017年10月有了Kindle版本，书的共同作者Friedman JH也是另一本神书ESL[参考文献7]的共同作者。
  • CART虽然在本书中排在ID3和C4.5后面，但是发表的时间顺序为CART->ID3->C4.5，了解决策树历史可以参考Loh的报告5
  • 熵, 基尼指数衡量的都是集合的不确定性, 应用在推荐的场景, 不确定性越大, 覆盖率可能就越大.
  • 书中有提到，分类问题中， 决策树表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合， 也可以认为是定义在特征空间上与类空间的条件概率分布。书中第一小节对这个问题做了解释。
  • 剪枝是模型压缩领域中的经典技术。剪枝可以降低模型复杂度，防止过拟合，提升模型泛化性能。LeCun等在1990年提出OBD[^8]方法对神经网络进行剪枝。

概念

熵

$$ H(p)=H(X)=-\sum_{i=1}^{n}p_i\log p_i $$

熵只与$X$的分布有关，与$X$取值无关，这句注意理解

定义$0\log0=0$，熵是非负的。

条件熵

随机变量$(X,Y)$的联合概率分布为

$P(X=x_i,Y=y_j)=p_{ij}, i=1,2,\dots ,n;j=1,2,\dots ,m$

条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性 $$ H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i) $$ 其中$p_i=P(X=x_i),i=1,2,\dots ,n$

经验熵， 经验条件熵

当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵

就是从已知的数据计算得到的结果。

信息增益

特征$A$对训练数据集$D$的信息增益$g(D|A)$，定义为集合$D$的经验熵$H(D)$与特征$A$给定的条件下$D$的经验条件熵$H(D|A)$之差 $$ g(D,A)=H(D)-H(D|A) $$

熵与条件熵的差称为互信息.

决策树中的信息增益等价于训练数据集中的类与特征的互信息。

考虑ID这种特征， 本身是唯一的。按照ID做划分， 得到的经验条件熵为0, 会得到最大的信息增益。所以， 按照信息增益的准则来选择特征， 可能会倾向于取值比较多的特征。

信息增益比

$$ g_R(D,A)=\frac{g(D,A)}{H_A(D)}\\ H_A(D)=-\sum_{i=1}^n\frac{D_i}{D}log_2\frac{D_i}{D} $$

算法

这部分内容，原始的5.1数据中最后的标签也是是和否，表示树模型的时候，叶结点不是很明显，所以简单改了下数据标签。对应同样的树结构，输出的结果如下

# data_5-1.txt
{'有自己的房子': {'否': {'有工作': {'否': {'否': None}, '是': {'是': None}}}, '是': {'是': None}}}
# mdata_5-1.txt
{'有自己的房子': {'否': {'有工作': {'否': {'拒绝': None}, '是': {'批准': None}}}, '是': {'批准': None}}}

先导

算法5.1 信息增益

输入：训练数据集$D$和特征$A$

输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$

  1. 数据集$D$的经验熵$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$
  2. 特征$A$对数据集$D$的经验条件熵$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$
  3. 信息增益$g(D,A)=H(D)-H(D|A)$

算法5.2 ID3算法

输入：训练数据集$D$, 特征集$A$，阈值$\epsilon$ 输出：决策树$T$

  1. 如果$D$属于同一类$C_k$，$T$为单节点树，类$C_k$作为该节点的类标记，返回$T$
  2. 如果$A$是空集，置$T$为单节点树，实例数最多的类作为该节点类标记，返回$T$
  3. 计算$g$, 选择信息增益最大的特征$A_g$
  4. 如果$A_g$的信息增益小于$\epsilon$，$T$为单节点树，$D$中实例数最大的类$C_k$作为类标记，返回$T$
  5. $A_g$划分若干非空子集$D_i$，
  6. $D_i$训练集，$A-A_g$为特征集，递归调用前面步骤，得到$T_i$，返回$T_i$

算法5.3 C4.5生成

输入：训练数据集$D$, 特征集$A$，阈值$\epsilon$ 输出：决策树$T$

  1. 如果$D$属于同一类$C_k$，$T$为单节点树，类$C_k$作为该节点的类标记，返回$T$
  2. 如果$A$是空集, 置$T$为单节点树，实例数最多的作为该节点类标记，返回$T$
  3. 计算$g$, 选择信息增益比最大的特征$A_g$
  4. 如果$A_g$的信息增益比小于$\epsilon$，$T$为单节点树，$D$中实例数最大的类$C_k$作为类标记，返回$T$
  5. $A_g$划分若干非空子集$D_i$，
  6. $D_i$训练集，$A-A_g$为特征集，递归调用前面步骤，得到$T_i$，返回$T_i$ ID3和C4.5在生成上，差异只在准则的差异。

算法5.4 树的剪枝

决策树损失函数摘录如下：

树$T$的叶结点个数为$|T|$，$t$是树$T$的叶结点，该结点有$N_t$个样本点，其中$k$类的样本点有$N_{tk}$个，$H_t(T)$为叶结点$t$上的经验熵， $\alpha\geqslant 0$为参数，决策树学习的损失函数可以定义为 $$ C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T| $$ 其中 $$ H_t(T)=-\sum_k\color{red}\frac{N_{tk}}{N_t}\color{black}\log \frac{N_{tk}}{N_t} $$

$$ C(T)=\sum_{t=1}^{|T|}\color{red}N_tH_t(T)\color{black}=-\sum_{t=1}^{|T|}\sum_{k=1}^K\color{red}N_{tk}\color{black}\log\frac{N_{tk}}{N_t} $$

这时有 $$ C_\alpha(T)=C(T)+\alpha|T| $$ 其中$C(T)$表示模型对训练数据的误差，$|T|$表示模型复杂度，参数$\alpha \geqslant 0$控制两者之间的影响。

上面这组公式中，注意红色部分，下面插入一个图

熵与概率的关系

这里面没有直接对$H_t(T)$求和，系数$N_t$使得$C(T)$和$|T|$的大小可比拟。这个地方再理解下。

输入：生成算法生成的整个树$T$，参数$\alpha$

输出：修剪后的子树$T_\alpha$

  1. 计算每个结点的经验熵
  2. 递归的从树的叶结点向上回缩 假设一组叶结点回缩到其父结点之前与之后的整体树分别是$T_B$和$T_A$，其对应的损失函数分别是$C_\alpha(T_A)$和$C_\alpha(T_B)$，如果$C_\alpha(T_A)\leqslant C_\alpha(T_B)$则进行剪枝，即将父结点变为新的叶结点
  3. 返回2，直至不能继续为止，得到损失函数最小的子树$T_\alpha$
{'有自己的房子': {'否': {'有工作': {'否': {'拒绝': None}, '是': {'批准': None}}}, '是': {'批准': None}}}

重新看一下这个建好的树，同样是字典的key，但是是有区别的。

  • 有自己的房子和有工作，是特征的索引

  • 是，否，是特征的取值

graph TD
	subgraph 决策树
		A--是-->C[批准]
		A((有自己的房子))--否-->B((有工作))
		B--是-->D[批准]
		B--否-->E[拒绝]
	end
	subgraph 子树
		B1((有工作))--是-->D1[批准]
		B1--否-->E1[拒绝]
	end
Loading

这个图里面，每一个划分都能计算经验熵

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	拒绝
2	青年	否	否	好	拒绝
15	老年	否	否	一般	拒绝
5	青年	否	否	一般	拒绝
6	中年	否	否	一般	拒绝
7	中年	否	否	好	拒绝
					
13	老年	是	否	好	批准
14	老年	是	否	非常好	批准
3	青年	是	否	好	批准
					
4	青年	是	是	一般	批准
8	中年	是	是	好	批准
9	中年	否	是	非常好	批准
10	中年	否	是	非常好	批准
11	老年	否	是	非常好	批准
12	老年	否	是	好	批准

这里先不考虑书中提到的剪枝方案，从上面划分的过程，思考如何做前剪枝，显然可以通过控制最后的叶子节点的样本数量来控制，最后的样本数量越少，就越可能出现模型过分的去拟合训练样本中的数据。

该章节代码中有这部分实现，在创建树的时候做预剪枝。

def _min_samples_leaf_check(self,
                            X):
    items, cnts = np.unique(X, return_counts=True)
    return np.min(cnts) < self.min_samples_leaf

剪枝，书中讲的算法是后剪枝，需要计算每个结点的经验熵，这个计算应该是在树构建的时候已经算过。

这里面没有具体的实现例子，给出的参考文献是李航老师在CL上的文章，文章介绍的MDL是模型选择的一种具体框架，里面有介绍KL散度，这部分可以参考下。

CART

关于CART的算法可以看下十大算法里面的第十章6，一转眼就十大数据挖掘算法都发表十年了，这个本书第十章作者放在了ResearchGate上，链接见参考部分。

算法5.5 最小二乘回归树生成

输入：训练数据集$D$

输出：回归树$f(x)$

步骤：

  1. 遍历变量$j$，对固定的切分变量$j$扫描切分点$s$，得到满足上面关系的$(j,s)$ $$ \min\limits_{j,s}\left[\min\limits_{c_1}\sum\limits_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min\limits_{c_2}\sum\limits_{x_i\in R_2(j,s)}(y_i-c_2)^2\right] $$

  2. 用选定的$(j,s)$, 划分区域并决定相应的输出值 $$ R_1(j,s)={x|x^{(j)}\leq s}, R_2(j,s)={x|x^{(j)}> s} \ \hat{c}m= \frac{1}{N}\sum\limits{x_i\in R_m(j,s)} y_j, x\in R_m, m=1,2 $$

  3. 对两个子区域调用(1)(2)步骤， 直至满足停止条件

  4. 将输入空间划分为$M$个区域$R_1, R_2,\dots,R_M$，生成决策树： $$ f(x)=\sum_{m=1}^M\hat{c}_mI(x\in R_m) $$

算法5.6 CART分类树生成

这个算法用到的策略是基尼系数，所以是分类树的生成算法。

概率分布的基尼指数定义

$$ Gini(p) = \sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2 $$

基尼系数是一个来源于经济学的指标. 范围(0, 1), 有很多中表示形式, 比如衡量收入分布的基尼系数. $$ G=\frac{1}{n-1}\sum_{j=1}^n(2j-n-1)p(i_j) $$

经济学基尼系数的解释[^7],基尼系数为$\frac{A}{A+B}$

算法5.7 CART剪枝

例子

例5.1

这个例子引出在特征选择的问题，后面跟着引出了熵，条件熵，信息增益与信息增益比的概念。这些是介绍决策树学习的基础。

例5.2

根据信息增益准则选择最优特征

习题的5.1是让用信息增益比生成树，和这个基本一样，换一个准则就可以了。在单元测试里面实现了这部分代码。

参考

  7. [^7 ]: Gini Coefficient

  8. [^8 ]: Optimal brain damage

⬆ top

Footnotes

  1. 图灵社区李航访谈 ↩

  2. 山西健司 ↩

  3. 决策列表, Text classification using ESC-based stochastic decision lists ↩

  4. 李航，安倍，CL文章，Generalizing case frames using a thesaurus and the MDL principle ↩

  5. A Brief History of Classification and Regression Trees ↩

  6. The Top Ten Algorithms in Data Mining ↩