[数据结构与算法] 机器学习-决策树、随机森林

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 机器学习-决策树、随机森林 -> 正文阅读

[数据结构与算法]机器学习-决策树、随机森林

参考：

机器学习的熵：机器学习各种熵：从入门到全面掌握 - 知乎 (zhihu.com)

相对熵（KL散度）：相对熵（KL散度）

信息熵、条件熵、交叉熵、相对熵

互信息

什么是「互信息」 - 知乎 (zhihu.com)

信息增益

信息增益表示得知特征 $X$ 的信息而使得类 $Y$ 的信息不确定性减少的程度。

信息增益是决策树ID3算法在进行特征切割时使用的划分准则，其物理意义和互信息完全相同，并且公式也是完全相同。其公式如下：

$g(D, A) = H(D) - H(D | A)$

其中D表示数据集，A表示特征，信息增益表示得到A的信息而使得类X的不确定度下降的程度，在ID3中，需要选择一个A使得信息增益最大，这样可以使得分类系统进行快速决策。
需要注意的是：在数值上，信息增益和互信息完全相同，但意义不一样，需要区分，当我们说互信息时候，两个随机变量的地位是相同的，可以认为是纯数学工具，不考虑物理意义，当我们说信息增益时候，是把一个变量看成是减少另一个变量不确定度的手段。

信息增益比

特征A对训练数据集D的信息增益比 $g_{R}(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集D关于特征A的值的熵 $H_{A}(D)$ 之比，即

$g_{R}(D, A) = \frac{g(D, A)}{H_{A}(D)}$

基尼指数

基尼指数是另一种衡量不确定性的指标。

假设数据集 $D$ 有 $K$ 个类，样本属于第K类的概率为? $p_{k}$ ?，则 $D$ 的基尼指数定义为： $Gini(p) = \sum_{k = 1}^{K}p_{k}(1 - p_{k}) = 1 - \sum_{k = 1}^{K}p_{k}^{2}$

其中? $p_{k} = \frac{\left | C_{k} \right | }{\left | D \right |}$ ?，??是D中属于第k类的样本子集。

如果数据集D根据特征A是否取某一可能值a被分割成 $D_{1}$ ?和 $D_{2}$ 两部分，则在给定特征A的条件下，D的基尼指数为： $Gini(D, A) = \frac{\left | D_{1} \right |}{\left | D \right |}Gini(D_{1}) + \frac{\left | D_{2} \right |}{\left | D \right |}Gini(D_{2})$

容易证明基尼指数越大，样本的不确定性也越大，特征A的区分度越差。

我们优先选择基尼指数最小的特征，由此生成决策树，称为CART算法。

决策树

决策树是一种基本的分类与回归方法，决策树表示给定特征条件下类的条件概率分布

步骤：特征选择、决策树的生成、决策树的修剪

决策树学习思想：

ID3算法
C4.5算法
CART算法

决策树的结点：内部节点（Internal node）表示一个特征或属性、叶节点（leaf node）表示一个类

特征选择

特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比

一般地，熵 $H(X)$ 与条件熵 $H(Y|X)$ 之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

ID3算法

训练数据集D，特征集阈值，信息增益算法

C4.5算法

训练数据集D，特征集阈值，信息增益比算法

剪枝算法

预剪枝：在树的生成过程中剪枝。基于贪心策略，可能造成局部最优
后剪枝：等树全部生成后剪枝。运算量较大，但是比较精准

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现

参考：认真的聊一聊决策树和随机森林 - 知乎 (zhihu.com)

$C_{\alpha} (T) = C(T) + \alpha\left | T \right |$ ，其中 $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，? $\left | T \right |$ 表示模型复杂度，参数控制两者之间的影响。

剪枝就是当参数确定时，选择损失函数最小的模型，即损失函数最小的子树

步骤：

计算每个结点的经验熵
递归地从树的叶结点向上回缩，比较回缩前后两棵树的损失函数值（判断是否剪枝）
直至剪枝不能继续为止，得到损失函数最小的子树

CART算法

是一种典型的二叉决策树

决策树生成：基于训练数据集生成决策树，生成的决策树尽量大
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，用损失函数最小作为剪枝的标准

对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，生成二叉树

作为分类决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本所属类别最多的那一类（即叶子节点中的样本可能不是属于同一个类别，则多数为主）；作为回归决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本的均值。

回归树的生成，一棵回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已经将输入空间划分为M个单元 $R_{1}, R_{2}, ... , R_{M}$ ，并且在每个单元 $R_{m}$ 上有一个固定的输出值 $c_{m}$ (单元 $R_{m}$ 上的 $c_{m}$ 的最优值 $\hat{c_{m}}$ 是 $R_{m}$ 上的所有输入实例 $x_{i}$ 对应的输出 $y_{i}$ 的均值，即 $\hat{c_{m}} = ave(y_{i} | x_{i} \in R_{m})$ )，回归模型树模型可表示为： $f(x) = \sum_{m = 1}^{M}c_{m}I(x \in R_{m})$ 。

当输入空间的划分确定时，可以用平方误差 $\sum_{x_{i} \in R_{m}}(y_{i} - f(x_{i}))^{2}$ 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。

遍历第j个变量，以及其取值寻找最优切分变量和切分点，作为切分变量和切分点

分类树的生成，使用基尼指数，同时决定特征的最优二值切分点 -> 决定最优特征以及最优切分点

CART剪枝， 从"完全生长"的决策树的底端剪去一些子树，使决策树变小（模型变简单），从生成算法产生的决策树 $T_{0}$ 底端开始不断剪枝，直到 $T_{0}$ 的根节点，形成一个子树序列 $\left \{ T_{0}, T_{1}, ..., T_{n}\right \}$ , 然后通过交叉验证在独立的验证数据集上对子树序列进行测试，从而选择最优子树。