#5机器学习（西瓜书）自学记录

目录

第四章.决策树

1.概念：

2.公式：

2.1决策树生成：General 算法

2.2划分准则：

2.3 决策树生成：ID3算法

2.4 决策树生成：C4.5算法

2.5决策树生成：CART算法

2.6🔖 随机森林

---

第四章.决策树

1.概念：

• 判定测试序列：从根节点到叶子节点的路径

• 纯度：当前节点包含单一目标类别的程度

• 信息熵：纯度的一种衡量方法

• 信息增益：基于信息熵的纯度提升衡量方法

• 增益率：基于信息增益的纯度提升衡量方法，克服了信息增益对取值数目更多的属性的偏好

• 剪枝：去除决策树中部分路径、防止过拟合的一种方法

• 预剪枝：划分节点前进行剪枝方法，其准测试估计本次划分是否能提升泛化性能，若不能，则标记为叶节点

• 后剪枝：生成决策树后进行剪枝的方法，其准则是自底向上判断将子树替换为节点能否提升泛化性能，若能，则替换子树的根节点为叶节点

• 多变量决策树：各节点学习属性的线性组合、具有斜划分边界的决策树

2.公式：

2.1决策树生成：General 算法

2.2划分准则：

• 信息熵

• 信息增益

• 增益率

• 基尼系数

2.3 决策树生成：ID3算法

1. 函数 ID3(训练数据集D，属性集合A)
2.     如果 D 中的所有实例都属于同一个类 C
3.         返回 叶节点，类 C
4.     如果 A 为空
5.         返回 叶节点，多数类
6.     计算 A 中每个属性 a 的信息增益
7.     选择信息增益最大的属性 a*
8.     如果 a* 的信息增益为 0
9.         返回 叶节点，多数类
10.    创建内部节点，节点属性为 a*
11.   对于 a* 的每个可能值 v
12.       创建分支，分支的子集为 D_v
13.       D_v 是 D 中 a* = v 的实例
14.       递归调用 ID3(D_v, A - {a*})
15.       将返回的子树附加到分支上
16.    返回内部节点

2.4 决策树生成：C4.5算法

1. 函数 C45(训练数据集D，属性集合A)
2.     如果 D 中的所有实例都属于同一个类 C
3.         返回 叶节点，类 C
4.     如果 A 为空 或者 D 中的实例都是空的
5.         返回 叶节点，多数类
6.     计算 A 中每个属性 a 的信息增益率
7.     选择信息增益比率最大的属性 a*
8.     如果 a* 的信息增益率为 0
9.         返回 叶节点，多数类
10.    创建内部节点，节点属性为 a*
11.    对于 a* 的每个可能值 v
12.       创建分支，分支的子集为 D_v
13.       D_v 是 D 中 a* = v 的实例
14.       递归调用 C45(D_v, A - {a*})
15.       将返回的子树附加到分支上
16.    返回内部节点
​
函数 信息增益比率(属性 a, 数据集 D)
17.    计算 a 关于 D 的信息增益
18.    计算 a 关于 D 的固有值
19.    返回信息增益 / 固有值
​

2.5决策树生成：CART算法

1. 函数 CART(训练数据集D，特征集合F)
2.     如果 D 中的所有实例都属于同一个类或者 F 为空
3.         返回 叶节点，类为 D 中的类
4.     选择最优特征 f* 和阈值 t，使得 D 在 f 上的分割最大化某个标准（如基尼不纯度或信息增益）
5.     创建内部节点，节点特征为 f*，阈值为 t
6.     将 D 根据 f* 和 t 分割为子集 D1 和 D2
7.     对于每个子集 Di
8.         递归调用 CART(Di, F - {f*})
9.         将返回的子树附加到当前节点的分支上
10.    返回内部节点
​
// 用于分类问题的 CART 算法
1. 对于 CART 分类问题
2.     选择分割标准为最小化基尼不纯度
3.     基尼不纯度(D, f, t) = ∑(Di 属于 D 的比例) * ∑(Cj 属于 Di 的比例) * (1 - ∑(Ck 属于 Di 的比例))
​
// 用于回归问题的 CART 算法
1. 对于 CART 回归问题
2.     选择分割标准为最小化均方误差
3.     均方误差(D, f, t) = ∑(Di 属于 D 的比例) * (∑(yi - Di 的预测值)^2)
​
// 辅助函数：计算基尼不纯度
1. 函数 计算基尼不纯度(数据集D)
2.     如果 D 中的所有实例都属于同一个类
3.         返回 0
4.     计算 D 中每个类的样本数量比例
5.     计算基尼不纯度 = 1 - ∑(p_i^2)，其中 p_i 是第 i 类的比例
6.     返回基尼不纯度
​
// 辅助函数：计算均方误差
1. 函数 计算均方误差(数据集D)
2.     计算 D 的平均值
3.     对于 D 中的每个实例 yi
4.         计算 (yi - 平均值)^2
5.     计算总和并除以实例数量
6.     返回均方误差

2.6🔖 随机森林

随机森林（Random Forest）集成多个决策树并结合其预测结果为最终结果，以提高模型的准确性和稳定性。

分类和回归的预测过程：

• 对于分类问题，对于森林 F 中的每棵树 t，计算它在实例 x 上的预测结果 p，然后返回森林中最常见的预测结果。

• 对于回归问题，对于森林 F 中的每棵树 t，计算它在实例 x 上的预测结果 p，并将所有预测结果收集起来。最后，返回这些预测结果的平均值。

1. 函数 随机森林(训练数据集D，决策树数量n，特征选择方法m)
2.     创建一个空的森林 F
3.     for i = 1 to n do
4.         创建一个随机子集 S 从 D，通常使用自助采样（bootstrap sampling）
5.         创建一个决策树 ti
6.         for each node in ti do
7.             选择一个随机子集 A of features from m
8.             使用最佳分割特征和阈值来分割节点，基于 A
9.         end for
10.        将 ti 添加到 F
11.    end for
12.    返回 F
​
// 使用随机森林进行分类
1. 函数 分类(森林F，实例x)
2.     for each tree t in F do
3.         计算 t 在 x 上的预测结果 p
4.     end for
5.     返回 F 中最常见的预测结果
​
// 使用随机森林进行回归
1. 函数 回归(森林F，实例x)
2.     predictions = []
3.     for each tree t in F do
4.         计算 t 在 x 上的预测结果 p
5.         将 p 添加到 predictions
6.     end for
7.     返回 predictions 的平均值

 

此内容是本人第一次通过看书和相关视频学习周志华《机器学习》，在此发表的一些个人的看法与见解，如有错误在里面必然是本人见识低陋，望读者朋友务必指出，我好加紧改正。本内容仅仅是本人学习的记录。想要深入了解《机器学习》的朋友务必下去看看书。谢谢。

参考说明：

相关截图：来自b站 周志华老师亲讲-西瓜书全网最详尽讲解-1080p高清原版《机器学习初步》BV1gG411f7zX

【吃瓜教程】《机器学习公式详解》（南瓜书）与西瓜书公式推导直播合集 BV1Mh411e7VU