决策树学习笔记

作者: 仰望星空的小狗 | 来源:发表于2019-11-20 08:19 被阅读0次

决策树学习笔记整理
机器学习笔记（6）：决策树
《机器学习》西瓜书学习笔记（三）
机器学习笔记--决策树
决策树
[机器学习]决策树
XGBoost: 从决策树说起
决策树算法总结
决策树学习笔记
决策树学习笔记

本文是学习周志华老师的《机器学习》以及其他相关博客之后进行概括和整理，以便自己将来能够快速回忆其决策树的相关内容。大家若想看更加详细的决策树相关知识，请参看《机器学习》

总体概述

本文通过脑图对决策树相关知识进行整理，目前整理了ID3，C4.5，CART以及决策树的剪枝处理等知识，而对于其他决策树的连续值和缺失值的处理以及多变量决策树的相关知识，后续再进行添加。

决策树

ID3

ID3
决策树是从根节点开始，一步一步的选取属性以及属性值进行节点分裂，直到满足一定条件（如当前节点上的样本属于同一类，或者已经达到所对顶的最大高度等）便停止生长。而在这一过程中，比较重要的是选取哪一个属性进行分裂。
在ID3决策树中，是使用信息增益来判断选择那个属性进行分裂的依据。而要了解信息增益，首先需要了解信息熵
信息熵，是衡量样本集合纯度的一种指标。比如，假定当前样本集合D中第k类样本所占比例为，则D的信息熵定义为

当越小，则D的纯度越高。因此，我们希望当对某一个节点进行分裂的时候，分裂之后的信息熵要尽可能小，选取各个可选的属性值中使得信息熵最小的属性为最佳分裂属性。此时，使用信息增益衡量分裂前后信息熵的变化。信息增益公式如下

上式中，相关变量的定义如下：

D: 当前待分裂节点的样本集合
a: 当前可选的属性
V: 属性a的可能取值个数
$D^v$ : 属性a在第v个属性值上的样本个数

因此，在分裂节点的时候，计算所有可能选取的属性对应的信息增益，选取增益最大的属性进行分裂。

但是在ID3决策树中，在分裂节点的时候，往往会比较倾向于取值较多的属性进行分裂。比如，当我们在训练集的属性中使用物品id，由于每一个物品的id不一样，那么当按照物品id进行分裂的时候，分裂后的每一个子节点上的样本都是单一的，此时的信息增益最大。但是此时按照物品id进行分类显然是不合适的，因为当我们在验证集中来了一个新的物品id，那么此时决策树就无法识别。上述现象就出现了过拟合。

C4.5

C4.5
为了避免上节中ID3使用的信息增益对取值较多的属性有偏好，C4.5决策树则不直接使用信息增益，而是使用信息增益率来选择最优的划分属性。信息增益率定义如下：

其中

此时，当a的可能取值越多，的值也会越大，一直对取值多的属性的偏好。
但信息增益率对取值数目少的属性有偏好，故在使用中采用启发式：先从候选划分属性中找出信息增益率高于平均水平的属性，在从中选择信息增益最高的属性。

CART

CART，即Classification and Regression Trees 分类回归树，可以用于分类，也可以用于回归问题.

CART分类树

在CART分类树中，使用基尼值来表示数据集的纯度，进而用于选择划分属性。基尼值定义如下：
$Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\neq k}p_kp_{k'}=1-\sum_{k=1}^{|y|}p_k^2$
则对于属性a的基尼指数为：
$Gini_index(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)$