机器学习入门（吃瓜第四章决策树)

生成结点 node
如果样本全属于同一类则:
- 将node标记为类 $C_k$ 的叶结点
- 返回
如果 A 为空或 D中样本在 A上取值相同则:
- 将node标记为类标记为 D 中样本数最多的类
- 返回
否则:
- 在 A 中选择最优划分属性 $a_v$
- 对于的每个取值 :
  - 为node生成一个分支 node_i
  - 令 $D_v^i$ 为 D 中在 $a_v$ 上取值为 $a_v^i$ 的样本子集
  - 递归调用TreeGenerate(, A \)，将返回的子树作为node_i的子树
返回

决策树的基本思想

决策树的基本思想是依据某种原则（即图4.2 第8行）每次选择一个属性作为划分依据，然后按属性的取值将数据集中的样本进行划分。

二、划分选择

由图4.2可知，决策树学习的关键是第8行，也就是如何选择最优划分属性。随着划分过程的不断进行，希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”(purity) 越来越高。

本节介绍的三种划分选择方法，即信息增益、增益率、基尼指数分别对应著名的 ID3、C4.5 和 CART 三种决策树算法。

1. ID3 决策树——信息增益划分准则

自信息: $I(X) = -\log_b p(x)I$

当 $b = 2$ 时单位为 bit，当 $b = e$ 时单位为 nat。

信息熵(自信息的期望):

度量随机变量 X 的不确定性，信息熵越大越不确定。
例如:
- $p_1 = 1, p_2 = 0$ : 可确定位于 1 的类别，则不确定性很小；
- $p_1 = p_2 = 0.5$ : 不能判断类别，不确定性很大。

以离散型为例: $H(X) = E[I(X)] = - \sum_x p(x) \log_b p(x)$

计算信息熵的约定:
- 若 $p(x) = 0$ ，则 $p(x) \log_b p(x) = 0$ 。

当 X 的各个取值的概率均等时信息熵最大（最不确定），其值为 $\log_b |\mathcal{X}|$ ，其中 $|\mathcal{X}|$ 表示 X 可能取值的个数。

$\text{Ent}(D) = - \sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k$

条件熵:

考虑到不同分支节点所包含的样本数不同，给予分支节点赋予权重 $\frac{|D^v|}{|D|}$ ，即样本数越多的分支节点的影响越大。

条件熵 (Y的信息熵关于分布 X 的期望)) 在已知 X 后 Y 的不确定性: $H(Y|X) = \sum_x p(x) H(Y|X=x)$

从单个属性（特征） $a$ 的角度来看，假设其可能取值为 $\{a^1, a^2, ..., a^V\}$ ， $D^v$ 表示属性 $a$ 取值为 $a^v \in \{a^1, a^2, ..., a^V\}$ 的样本集合， $\frac{|D^v|}{|D|}$ 表示占比，那么在已知属性 $a$ 的取值后，样本集合 $D$ 的条件熵为：

$H(D|a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} \text{Ent}(D^v)$

信息增益:

信息增益越大，则意味着使用属性 aaa 来进行划分所获得的“纯度提升”越大。

信息增益：在已知属性（特征） $a$ 的取值后的不确定性减少的量，也即纯度的提升： $\text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \text{Ent}(D^v)$

ID3决策树：以信息增益为准则来选择划分属性的决策树： $a_* = \arg \max_{a \in A} \text{Gain}(D, a)$

2. C4.5 决策树——以信息增益率为划分准则

例如，将编号作为划分属性的话，每个编号下面只有一个样本，这些分支节点的纯度已经达到最大，但是这样划分的决策树不具有泛化能力，无法对新样本进行有效预测。

信息增益准则的缺点：对可取值数目较多的属性有所偏好。

C4.5 决策树不使用信息增益，而是使用“增益率”（gain ratio）来划分最优划分属性。

增益率准则的缺点：对可取值数目较少的属性有所偏好。因此在实际中，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3. CART 决策树——以基尼指数为划分准则

回归原始角度，保证使用某个划分属性之后的划分纯度。

基尼值：从样本集合 D 中随机抽取两个样本，其类别标记不一致的概率。因此，基尼值越小，碰到异类的概率就越小，纯度自然就越高。

基尼指数：（基尼值和基尼指数的关系类似信息熵和条件熵）

实际中：对每个属性 a 的可能取值 v，将数据集 D 划分为 $a = v$ 和 $a \neq v$ 两部分来计算基尼指数。

三、剪枝处理

剪枝（pruning）是决策树学习算法用来应对“过拟合”的主要手段。过拟合的产生是由于决策树在训练过程中为了尽可能地正确分类训练样本，有时会导致分支过多，从而将训练集中的某些特征误认为是所有数据的普遍特性，最终导致过拟合。通过去掉一些分支，可以降低过拟合的风险，提高模型的泛化能力。

1. 预剪枝（prepruning）

预剪枝是在决策树生成过程中，对每个结点在划分前进行评估。如果当前结点的划分不能提升决策树的泛化性能，则停止划分，并将该结点标记为叶结点。

2. 后剪枝（post-pruning）

后剪枝是在从训练集生成一棵完整的决策树后，自底向上地考察非叶结点。若将某个结点对应的子树替换为叶结点能够提升决策树的泛化性能，则进行替换，将该子树变为叶结点。

决策树的泛化性能是否提升可以通过性能评估方法来判断。假定采用留出法，即预留一部分数据作为“验证集”来进行性能评估。

参考文献

[1] 【吃瓜教程】《机器学习公式详解》（南瓜书）与西瓜书公式推导
[2] 周志华.机器学习[M].清华大学出版社,2016.
[3] 谢文睿秦州贾彬彬.机器学习公式详解第2版[M].人民邮电出版社,2023.

标签：结点,入门,增益,划分,吃瓜,决策树,取值,属性
From： https://blog.csdn.net/Serena_yocio/article/details/140110352

机器学习入门（吃瓜第四章决策树)

一、决策树的算法原理

决策树算法步骤

决策树的基本思想

二、划分选择

1. ID3 决策树——信息增益划分准则

2. C4.5 决策树——以信息增益率为划分准则

3. CART 决策树——以基尼指数为划分准则

三、剪枝处理

1. 预剪枝（prepruning）

2. 后剪枝（post-pruning）

参考文献

相关文章

赞助商

阅读排行

机器学习入门（吃瓜第四章 决策树)

一、决策树的算法原理

决策树算法步骤

决策树的基本思想

二、划分选择

1. ID3 决策树——信息增益划分准则

2. C4.5 决策树——以信息增益率为划分准则

3. CART 决策树——以基尼指数为划分准则

三、剪枝处理

1. 预剪枝（prepruning）

2. 后剪枝（post-pruning）

参考文献

相关文章

赞助商

阅读排行

机器学习入门（吃瓜第四章决策树)