机器学习笔记2_决策树

作者: cuiyr123 | 来源:发表于2019-11-23 22:17 被阅读0次

机器学习笔记2_决策树
机器学习笔记（6）：决策树
《机器学习》西瓜书学习笔记（三）
机器学习笔记--决策树
[机器学习]决策树
《机器学习实战》
6.machine_learning_Decision_Tree
机器学习笔记--决策树
机器学习决策树笔记
机器学习 | 决策树及若干基础问题

@[toc]

2.1简介

决策树算法经典的机器学习算法，也是使用的很普遍的一类算法，集成学习中的随机森林就是以决策树算法为基础的。决策树是Quinlan(昆兰)在1986年提出来的，最开始的版本是ID3算法，之后他又提出来C4.5算法。后来，有人在昆兰的基础上提出了CART算法，本文主要介绍这三种算法的主要思想。

2.2 信息论基础

可以把决策树当成一系列if-else的集合。比如我们在写程序时总会连用多个if-else，但是哪个特征做if的条件最合适呢？也就是哪个特征最具有区分度？这就是决策树要做的事情。一个叫昆兰的大佬1978年在Standford访问期间选修了图灵的助手D.Michie的课，在完成大作业时，昆兰提出使用信息熵的思路解决，这就是决策树的前身。

我们先介绍信息论中的信息熵，奠基人是另一个大牛香农。在信息论中，熵(entropy)是用来度量事物的不确定性的。所谓不确定性与概率有关，如果一个事情发生的概率 $p_i$ 越小，不确定性就越大。举个简单的例子：天气预报说明天的降水概率是10%，那就是说明天可能为雨天、晴天、多云...等各种天气，留给人想象的空间很多，但如果天气预报说明天降水概率99%，那基本上可以确定明天会下雨，也就不用多想，带伞就好了。这个例子就是说小概率事件所含的信息量多。信息量可以用负对数 $-\log p_i$ 来描述，其图像如下：

在这里插入图片描述
对于一个离散的分布，随机变量的取值可能为多个值，信息熵就表示每个取值所含信息量的加权平均，以下表达式表示量化信息熵：

由于信息熵与X的取值无关，只与不同取值的概率有关，因此上式可以写为：

其中表示随机事件，为X的第个取值发生的概率，若，则定义。对于一个随机变量来说，如果每个取值发生的概率相等的话，则此时的信息熵最大。如对于只有两个取值的伯努利分布：

X	0	1
$p_i$	$p$	$1-p$

则信息熵为：
$H(p) = -p\log p-(1-p)\log (1-p)$
这个就是我们熟悉的交叉熵(cross-entropy)啦，其图像如下所示：

在这里插入图片描述
也就是说当p=0.5时熵最大，为。这个结论可以推广到对于X取多个离散值的情况，因此有：

对于多个随机变量，有联合熵，

在此基础上又条件熵，注意，用到的概率是联合概率：

如果概率用到是数据的频率，则得到的熵和条件熵称为经验熵和经验条件熵。把信息增益(information gain)定义为，经验熵与经验条件熵的差：

也就是，原来随机变量X的不确定度为，这时Y发生，在这个条件下，X发生的不确定度减小为，不确定度的减少程度就是信息增益，也就是增加了多少信息。计算公式如下：

在这里插入图片描述

2.3 特征选择

我们绕回决策树，把训练集的划分看成随机变量 $D$ ，特征看成随机变量 $A$ ， $H(D)$ 表示分类的不确定度， $H(D|A)$ 表示加入某个特征A后对D进行新的分类的不确定度，他们的差就是信息增益，也就是特征A使得D不确定度减小的程度，很显然，如果某个特征让不确定度减小的程度多，那就说明这是个好特征。
一个简单的例子如下(来自李航《统计学习方法》)：
数据如图：

在这里插入图片描述
特征选择的过程如下：

人们在实测中发现，相同条件下，取值比较多的特征比取值少的特征信息增益大。为了解决这个问题，大佬昆兰又提出信息增益率的概念：
$g_R(D,A) = \frac{g(D,A)}{H(D)}$

在这里插入图片描述

2.4 ID3与C4.5

ID3算法的基本思路就是：从根节点开始选择信息增益最大的特征，根据该特征的不同取值建立不同的子节点，每个子节点递归地选择特征，直到没有特征或者信息增益小于某个阈值为止。
算法过程为：
输入：信息增益的阈值 $\epsilon$ ，训练的数据集 $D=\{ (x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)})\}$ ，特征集 $A=\{ A_1,A_2,...,A_n\}$ , 每个特征的取值有 $i$ 个
输出：决策树T

判断 $D$ 中的所有样本是否为同一类，即所有训练数据的标签是否为同一个。如果是，则T为单结点树，这时返回T
判断特征是否为空，如果是则返回单节点树T，把训练集 $D$ 中实例树最大的类作为该结点的类标记。否则计算 $A$ 中每个特征的信息增益，选择信息增益最大的特征 $A_g$
判断刚刚计算的最大信息增益 $g(D,A_g)$ 是否小于阈值 $\epsilon$ ，如果是，则把T作为单结点树，把 $D$ 中实例数最多的类别作为该结点的类标记
否则，按照 $A_g$ 的不同取值把 $D$ 划分为不同的子集 $D_i$ ，把 $D_i$ 中实例数最多的类别作为该结点的类标记，返回T
对于所有子节点，令 $D=D_i$ ， $A=A-{A_g}$ 地洞调用1-4

C4.5方法与ID3方法相同，在生成树的过程中用信息增益比代替信息增益。

2.5 决策树的剪枝

如果决策树的分支过多，分类过细则会造成过拟合现象，模型在训练数据上表现很好，但在测试时则表现很差。这时需要主动把分支结点合并到父结点中，达到裁剪决策树的目的，从而降低过拟合。剪枝分为“预剪枝”和“后剪枝”。

预剪枝
所谓“预剪枝”，就是在生成决策树时就用一定的方法控制子树的生成，一种可行的方法，就是用验证集数据，当划分的子树在验证集上仍能保持较好的准确率，则按照特征的不同取值进行划分，否则停止划分。
后剪枝
对于后剪枝，就是先生成一个完整的决策树，接着定义损失函数，按照使得损失函数最小的方法合并叶结点到父结点。

下边介绍一种可行的后剪枝方法：
我们知道，一颗理想的决策树中，所有同一类的训练样本都落入到同一个叶子节点中，但现实中每个叶子节点中总有错误的分类，假设树 $T$ 中有 $|T|$ 个子叶子节点，其中第 $t$ 个结点中有 $N_t$ 个训练样本，由于存在错误的分类，这些样本点中第 $k$ 类有 $N_{tk}$ 个， $k=1,2,3,...K$ ，可以用经验熵来衡量这种分类损失，即：
$H_t(T) = - \sum _{k=1}^{K} \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$
因为前边介绍过，经验熵的取值范围为：
$0 \leqslant H_t(T) \leqslant \log K$
如果叶子节点没有分类错误，则 $H_t(T) =0$

这是每个叶子节点的损失，而对于整个树的损失则可以表示为叶子节点损失的加权平均，权重就是叶子节点中训练样本(样本点)的个数，所以有：
$C_a(T) = \sum_{t=1}^{|T|} N_t H_t(T)$
在之前LR中讲正则项时有提到，权重过大会造成过拟合，而在决策树中，子节点的个数太多同样会造成过拟合，因此我们需要加一个正则项来约束子节点的个数 $|T|$ ，因此损失函数如下：
$C_a(T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T|$
假设一个叶结点回缩到父结点之前与之后整体树的损失为 $C_a(T_B)$ 与 $C_a(T_A)$ ,如果 $C_a(T_B) \leqslant C_a(T_A)$ ，则进行剪枝。

2.6 CART

CART的全称是classification and regression tree. 由Breiman等人在1984年提出，是应用广泛的决策树学习方法。与ID3和C4.5不同的是，CART构建的是二叉树，我们知道在数据结构中，二叉树有很多优良的性质！sklearn内部默认的决策树算法也是CART。下边分开两部分介绍：

2.6.1 CART分类树

在ID3中，使用信息增益选择特征，在C4.5中使用信息增益比来选择特征，在MART中则使用基尼系数(Gini)来代替信息增益。信息熵由于需要大量的对数运算，计算速度偏慢，而基尼系数则只需要做乘法和加减法运算，其定义如下：
$Gini(p) = \sum_{k=1}^{K} p_k(1-p_k) = 1- \sum_{k=1}^{K} p_k^2$
其中 $p_k$ 表示训练样本属于第 $k$ 类的概率。特别地，在二分类问题中，样本点属于第一类的概率为 $p$ ，则基尼系数为：
$Gini(p) = 2p(1-p)$
如果训练样本集合为 $D$ ，则基尼系数为：
$Gini(D) = 1- \sum_{k=1}^{K} \left ( \frac{|C_k|}{|D|} \right)^2$
$C_k$ 表示属于第 $k$ 类的样本子集，如果根据特征A的取值把样本集合 $D$ 分成 $D_1$ 和 $D_2$ 两部分，则在特征A的条件下，训练样本集合 $D$ 的基尼系数为：
$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
也就是两个子集基尼系数的期望(加权平均)

与ID3和C4.5不同，CART分类算法建立的是二叉决策树，比如特征A有三种特征 $A_1,A_2,A_3$ 三种特征，CART会把特征分为 $\{A_1\}$ 和 $\{A_2,A_3\}$ , $\{A_2\}$ 和 $\{A_1,A_3\}$ 以及 $\{A_3\}$ 和 $\{A_1,A_2\}$ 三种，分别计算着三种组合的基尼系数，对于未分开的特征，后边还有机会做计算。

分类算法的具体流程为：
输入：输入训练集 $D$ ，基尼系数阈值，样本个数阈值
输出：CART决策树T

对于当前节点的数据集D，如果样本个数小于阈值，返回T
计算D的基尼系数，如果基尼系数小于阈值，返回T
对于各个特征A和特征的各个取值a，把D划分成 $D_1$ 和 $D_2$ 两部分，根据上述例子计算各个特征各个取值的基尼系数
选择基尼系数最小的特征A和对应的特征值a，根据是否取a把D分成 $D_1$ 和 $D_2$ 两个子树。
递归调用(1)-(4)
仍是上述例子，构建的CART决策树为：

在这里插入图片描述

2.6.2 CART回归树

对于回归模型，同样是测试每个特征的每个取值。由于要拟合的函数 $f(x)$ 是连续的，所以考虑输入数据集的划分，用平方误差表示回归树对训练数据的误差：
$\sum_{x_i \in R_m} (y_i-f(x_i))^2$
目标就是如何划分训练数据集 $D$ ，找到划分点 $s$ ，使得划分后的两个子集 $D_1$ 和 $D_2$ 的误差最小，同时他们的平方误差和也最小。注意，我们训练集 $D=\{(x^{(1)},y^{(1)}),x^{(2)},y^{(2)},...x^{(m)},y^{(m)}\}$ 其中 $x^{(1)}<x^{(2)}<...<x^{(m)}$ 我们要找的划分点 $s$ 是其中的第 $j$ 个变量，因此目标函数可以表示为：
$\min_{A,s} \left[ \min_{c1} \sum_{x^{(i)} \in D_1(A,s)} (y^{(i)}-c_1)^2 + \min_{c1} \sum_{x^{(i)} \in D_2(A,s)} (y^{(i)}-c_2)^2\right]$
其中 $c_1,c_2$ 分别表示 $D_1,D_2$ 中所有 $y^{(i)}$ 的均值。在预测时，回归树输出的也是叶子节点的均值。树建立的过程与分类树类似。

2.6.3 CART的剪枝

与2.5介绍的剪枝策略类似，只不过选用的是损失函数为基尼系数。

机器学习笔记2_决策树
@[toc] 2.1简介决策树算法经典的机器学习算法，也是使用的很普遍的一类算法，集成学习中的随机森林就是以决策...
机器学习笔记（6）：决策树
本文来自之前在Udacity上自学机器学习的系列笔记。这是第6篇，介绍了监督学习中的决策树模型。决策树决策树是...
《机器学习》西瓜书学习笔记（三）
上一篇笔记在这里：《机器学习》西瓜书学习笔记（二）第四章决策树 4.1 基本流程决策树的生成是一个递归过程，...
机器学习笔记--决策树
这里开始机器学习的笔记记录。今天的这篇是一个分类方法--决策树。决策树优点：计算复杂度不高，输出结果易于理解，对...
[机器学习]决策树
决策树 @(技术博客)[机器学习, 决策树, python] 学习决策树首先要搞清楚决策树是什么（what），在弄...
《机器学习实战》
有道笔记原文机器学习实战 Github代码第一章机器学习基础 2007年选出的十大数据挖掘算法C4.5决策树...
6.machine_learning_Decision_Tree
1 机器学习决策树 1.1机器学习中的决策树模型 ① 树模型不用做scaling ② 树模型不太需要做离散化 ③ ...
机器学习笔记--决策树
这里开始机器学习的笔记记录。今天的这篇是一个分类方法--决策树。方法适用问题模型特点模型类别学习策略学习的损失函...
机器学习决策树笔记
信息熵（entropy) 变量的不确定性越大，熵也就越大 ID3算法有A节点的信息获取量和没有A的信息获取量之间...
机器学习 | 决策树及若干基础问题
决策树 1.构造决策树学习决策树就是学习一系列if/else问题，是我们能够以最快的速度得到正确答案。在机器学习...

机器学习笔记2_决策树

2.1简介

2.2 信息论基础

2.3 特征选择

2.4 ID3与C4.5

2.5 决策树的剪枝

2.6 CART

2.6.1 CART分类树

2.6.2 CART回归树

2.6.3 CART的剪枝

相关文章

机器学习笔记2_决策树

机器学习笔记（6）：决策树

《机器学习》西瓜书学习笔记（三）

机器学习笔记--决策树

[机器学习]决策树

《机器学习实战》

6.machine_learning_Decision_Tree

机器学习笔记--决策树

机器学习决策树笔记

机器学习 | 决策树及若干基础问题

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读