决策树学习算法

决策树的学习算法一共有三点：

决策树的非叶子节点代表选择的一个划分标准（如，第 \(i\) 个分量 \(x^{(i)}\) 是否大于等于 \(0\)），每一个叶子节点代表一个类（样本属于这些类）

特征选择

希望每一步选择的特征都是良好的，引入一个指标来计算：信息增益。

信息增益：得知 特征X 的信息而使得类 Y 的信息的不确定性减少的程度，即经验熵的改变量。 定义为： \[ g(D, A)=H(D)-H(D|A) \] 其中 \(D\) 为数据集，\(A\) 为我们选择的特征，\(H\) 为经验熵函数。

我们希望 \(H\) 越小越好，即每一步的 \(g(D,A)\) 要大。

容易发现，当 \(A\) 表征的特征有更多选项时更容易被选中，所以引入信息增益比： \[ g_R(D, A)=\dfrac{g(D,A)}{H_A(D)} \] 其中 \(H_A(D)\) 为数据集 \(D\) 关于特征 \(A\) 的熵 \[ H_A(D)=-\sum_{i=1}^n \dfrac{|D_i|}{|D|}\log_2{\dfrac{|D_i|}{|D|}} \]

决策树生成

一共两种算法，ID3 和 C4.5

ID3 算法依赖于信息增益，而 C4.5 则是信息增益比作为评价标准

流程：

1. 给定数据集 \(D\) 以及特征集 \(A\) 阈值 \(\epsilon\)

2. 按照每一个特征，计算信息增益（比）；选取信息增益（比）最大的特征 \(A\)，如果节点全部都属于同一类 \(C_k\)，则直接标记为\(C_k\) 类并返回

3. 否则开始划分，按照 \(A\) 的每一个可能的值 \(a_i\) 将划分为 \(D_i\)，递归此过程，直到子节点全部属于一类或者信息增益（比）小于阈值 \(\epsilon\) 或者特征集 \(A\) 为空。

这两个都容易产生过拟合的问题，故考虑剪枝

决策树剪枝

实质上就是一种正则化手段，利用经验熵作为损失函数，叶子节点数作为正则化项。

定义决策树学习的损失函数为：

\[ C_\alpha(T)=\sum_{t=1}^{|T|} N_tH_t(T)+\alpha|T| \]

其中经验熵函数为

\[ H_t(T)=-\sum_k \dfrac{N_{tk}}{N_t}\log \dfrac{N_{tk}}{N_t} \]

其中，\(|T|\) 为决策树的节点数（正则化项），\(t\) 是子节点编号，\(N_t\) 是每个叶节点的样本数，其中第 \(k\) 类的有 \(N_{tk}\) 个。

当 \(\alpha\) 很小的时候，说明选择损失函数最小的模型，调大 \(\alpha\) 相当于限制（减小）模型复杂度。

剪枝算法： 1. 递归，计算每一个叶节点的经验熵

2. 尝试将一个叶子节点缩到父节点，比较前后的经验熵，如果经验熵减小，说明可以直接剪枝，将父节点变为一个新的叶节点。

3. 回到2，继续操作

CART 决策树

概述

CART 是一种二叉决策树，每次提问都是 y/n；

对于回归问题，使用平方误差作为损失函数；对于分类问题，使用 \(\text{Gini}\) 系数；

模型

回归树

\[ f(x)=\sum_{m=1}^M c_m \mathbb{I}(x\in R_m) \]

其中，\(R_m\) 为提问所划分出的区域，\(c_m\) 为其上的代表值（固定的输出值）；

通过平方误差计算时，容易知道 \(c_m\) 应该取 \(R_m\) 的标签的平均值

现在问题在于如何划分。

采用启发式的方法，每次取一个方向 \(x^{(j)}\)，考虑将 D 按照这个方向上的一个数值 \(s\) 来划分

\[ R_1(j,s)=\{x|x^{(j)}\leq s\},R_2(j,s)=\{x|x^{(j)}> s\} \]

现在来求解

\[ \min_{j,s} \left\{ \min_{c_1} \sum_{x_i\in R_1(j,s)} (y_i-c)^2 + \sum_{x_i\in R_2(j,s)} (y_i-c)^2 \right\} \] 固定 \(j\) 有 \(\hat{c}_1=\text{ave}(y_i|x_i\in R_1(j,s)),\hat{c}_2=\text{ave}(y_i|x_i\in R_2(j,s))\)

重复这个过程，直到达到终止条件。

分类树

定义 \(\text{Gini}\) 系数，对于一个概率分布 \(p\) 有

\[ \text{Gini}(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2 \]

容易发现它是一个凸函数。

对于一个集合 D 及其划分 \(C_k\)，类似有

\[ \text{Gini}(D)=\sum_{k=1}^K \dfrac{|C_k|}{|D|} \left(1-\dfrac{|C_k|}{|D|}\right)=1-\sum_{k=1}^K \left( \dfrac{|C_k|}{|D|} \right)^2 \]

类似条件经验熵函数，也可以定义条件 Gini 系数。

\(\text{Gini}\) 系数的概念非常类似经验熵函数，同样描述了数据的不确定程度。

分类树则采用 \(\text{Gini}\) 系数，对于每一个特征 \(A\)，对其所有可能值 \(a_i\)，进行 y/n 分类，将 \(D\) 划分为 \(D_1\)，\(D_2\) 两部分，计算条件 \(\text{Gini}\) 系数；选择最小的作为分类，递归操作直到满足终止条件。

剪枝

TODO

花了一些时间总算搞好了，第一篇文章就简要记录一下踩的坑吧。

数学公式渲染

处于兼容性考虑，我采用了 Mathjax 作为 math engine，同时将默认 Markdown 渲染器换成了 pandoc

一定要把之前的渲染引擎删除干净，否则会有一些很诡异的错误

英文引号变成中文

我想写这篇文章的罪魁祸首。

一开始，所有的英文引号 '/" 都会被渲染成 ‘/“，显示效果奇差无比

查询之后发现这也是渲染引擎的问题，它会自动开启一个类似于 formatting 之类的操作

Github 上比较常见的几个 issue 都是用的 hexo-renderer-marked

但是如上文所说，我换成了 pandoc 之后依然有这个问题（有的文章说换 pandoc 之后就好了），猜测也有一个类似的开关

随问 LLM，发现要传入一些参数：

1
2
3
4
5

pandoc:
  args:
    - '--from'
    - 'markdown-smart' # 这里的 -smart 表示在 markdown 解析中禁用 smart 扩展
    - '--mathjax'

我估计可能是因为 pandoc 版本的不同，旧版本的默认关闭/没有 smart 扩展

Hello! This is my first blog.

A math formula: \[ \frac{\partial p_t(\mathbf{x})}{\partial t} = -\sum_{i=1}^{D} \frac{\partial}{\partial x_i} \left[ f_i(\mathbf{x}, t) p_t(\mathbf{x}) \right] + \frac{1}{2} \sum_{i=1}^{D} \sum_{j=1}^{D} \frac{\partial^2}{\partial x_i \partial x_j} \left[ (g^2(t) \mathbf{I}_D)_{ij} p_t(\mathbf{x}) \right] \]

1

print('This is a piece of code!')

尝试一下中文输入 This's my blog!

• todo 1
• todo 2

Hello

你好

foo

\(1+2\geq 2\)

有\(a+b\geq 3\)

\[a+b\geq 3\]