biscuitの博客

熵#

设样本集合 $D$ 中有 $K$ 类 $\{C_1, C_2, \ldots, C_K\}$，将样本划分成 $K$ 个子集 $D=\{D_1, D_2, \ldots, D_K\}$，第 $j$ 类样本占比 $p_j=\frac{|D_j|}{|D|}$ （用频率近似），则 $D$ 的熵定义为：

• 熵度量不确定性。
• 熵越大，类别越混；
• 熵越小，类别越纯。
• 若 $D$ 全部属于同一类，则 $H(D)=0$。

条件熵#

用特征 $A$ 对 $D$ 划分：假设特征 $A$ 有 $v$ 种可能的取值，将样本 $D$ 分为$v$ 个子集 $D=\{D_1, D_2, \ldots, D_v\}$，则条件熵（按特征 $A$ 划分后的加权平均熵）为：

• $|D_i|$ 表示集合 $D_i$ 的元素个数，按子集大小加权求和
• 对于 $v$ 的含义，例如$A$ 是”颜色”，可能取值为”红、绿、蓝”，则 $v=3$；如果A是二值特征（如”是否发烧”），则 $v=2$。对于近似连续的特征（如”身高”），可以先离散化为若干区间（找分裂阈值）。

TIP

条件熵用特征的取值可能来划分样本集合，熵用类别标签来划分

信息增益(Information Gain)#

特征 $A$ 对数据集 $D$ 的信息增益：

ID3 策略#

在每一步选择 $\text{IG}(D, A)$ 最大的特征A来分裂，递归构建，直到：

• 子集中所有样本属于同一类
• 无可选特征
• 超过预设深度

:::warning [信息增益的偏好] 信息增益天然偏向取值多的特征（$v$ 较大的特征）（比如”编号”这种每个样本一个取值的特征，信息增益极大但毫无泛化能力）。

原因：信息增益计算的是划分前后熵的减少量，取值多的特征，$v$ 更大，划分后子集更小，熵更低，导致信息增益更大。 :::

增益率#

定义特征 $A$ 的固有值（Intrinsic Value）或分裂信息（Split Information），其实就是特征 $A$ 本身的熵。：

NOTE

这个和熵的公式很像，但是这里的 $D_j$ 是按特征 $A$ 的取值可能划分的子集，而不是按类别划分的子集。

增益率：

C4.5 策略：不直接选增益率最大的特征（因为 $\text{IV}(A)$ 小时增益率会被过度放大），而是先选出信息增益高于平均水平的特征，再从中选增益率最大的。

C4.5 的其他改进#

基尼指数#

对于数据集 $D$，有$K$个类别，将样本集合划分为 $K$ 个子集 $D=\{D_1, D_2, \ldots, D_K\}$，第 $j$ 类样本占比 $p_j=\frac{|D_j|}{|D|}$，基尼值（Gini impurity）定义为：

$\text{Gini}(D)$ 反映了从 $D$ 随机抽取两个样本，其类别不一致的概率。越小表示纯度越高，越大越不纯。

基尼指数和熵在物理意义上完全等价（都表示不纯度），只是数值范围不同（基尼最大0.5，熵最大1）

用特征 $A$ 划分后（CART 对每个特征做二分），基尼指数：

CART 分类策略：选 $\text{GiniIndex}(D, A)$ 最小的特征和分裂点。

CART 回归树#

对于回归任务，分裂准则不再是基尼指数，而是均方误差（MSE）：

其中 $c_1, c_2$ 分别是左右子集的输出值（取该子集 $y$ 的均值）。递归划分，叶子节点的预测值即为该叶子上样本的均值。

预剪枝#

在构建过程中提前停止：

• 限制树的最大深度
• 限制节点的最少样本数
• 限制分裂后的信息增益阈值
• 用验证集评估：若划分不能提高验证集精度则停止

优点：效率高 缺点：可能过早停止，错过后续的好划分（视界局限效应）

后剪枝#

先让树充分生长，再自底向上合并叶子：

CART 代价复杂度剪枝（CCP）： 定义损失函数：

• $|T|$ 是叶子数
• $N_t$ 是叶子 $t$ 的样本数
• $\alpha$ 是平衡拟合度与复杂度的参数

对每个 $\alpha$，存在一棵最优子树。通过交叉验证选择最优 $\alpha$。

C4.5 悲观剪枝（PEP）： 用训练集估计误差，加上一个惩罚项（连续修正），自底向上判断是否合并。