使用数值特征的二元分类的精确拆分器

在本单元中，您将探索最简单、最常见的拆分器算法，该算法使用以下设置创建 $\mathrm{feature}_i \geq t$ 形式的条件：

• 二元分类任务
• 示例中没有缺失值
• 这些示例上没有预计算索引

假设有一组 $n$ 示例，其具有数值特征和一个二进制标签“橙色”和“蓝色”。正式地，让我们将数据集 $D$ 描述为：

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

其中：

• $x_i$ 是 $\mathbb{R}$（一组实数）中数值特征的值。
• $y_i$ 是以 {orange, blue} 表示的二进制分类标签值。

我们的目标是找到一个阈值 $t$（阈值），以便根据 $x_i \geq t$ 条件将样本 $D$ 划分为 $T(rue)$ 和 $F(alse)$ 组，从而改善标签分离；例如，$T$ 中的更多“橙色”示例以及 $>F 中的更多示例。

香农熵是衡量障碍的一种指标。对于二进制标签：

• 如果示例中的标签处于平衡状态（50% 为蓝色，50% 为橙色），那么香农熵最大。
• 如果示例中的标签是纯色（100% 蓝色或 100% 橙色），则香农熵至少为最小值。

图 8. 三种不同的熵级别。

 

在形式上，我们希望找到一个条件，用于降低 $T$ 和 $F$ 中标签分布的加权总和。对应的分数是信息增益，即 $D$' 熵与 {$T$,$F$} 熵之间的差值。这种差异称为信息增益。

下图显示了一个错误的分屏，其中熵保持较高值，并且信息增益较低：

图 9. 拆分错误不会减少标签的熵。

 

相比之下，下图显示了一个更好的分屏，其中熵变为低值（信息增高）：

图 10. 良好的分屏会减少标签的熵。

 

正式名称：

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

其中：

• $IG(D,T,F)$ 表示将 $D$ 拆分为 $T$ 和 $F$ 后的信息增益。
• $H(X)$ 是 $X$ 这组示例的熵。
• $|X|$ 是集合 $X$ 中的元素数。
• $t$ 是阈值。
• $pos$ 是正标签值，例如，在上面的示例中为“blue”。选择其他标签作为“正值标签”不会更改熵值或信息增益。
• $R(X)$ 是样本 $X$ 中正例标签值的比率。
• $D$ 是数据集（如本单元前面所定义）。

在以下示例中，我们考虑了一个具有单个数值特征 $x$ 的二元分类数据集。下图显示了不同阈值 $t$ 的 x 轴值：

1. $x$ 特征的直方图。
2. $D$、$T$ 和 $F$ 中的“蓝色”样本的比率是根据阈值设定的。
3. $D$、$T$ 和 $F$ 中的熵。
4. 信息增益；即 $D$ 到 {$T$,$F$} 之间的熵增量，按样本数加权。

图 11. 四个阈值图。

 

这些图表显示了以下内容：

• “频率”图显示观察结果相对分散，其浓度介于 18 到 60 之间。广泛的价值分布意味着存在大量的潜在拆分，这有助于训练模型。

• 数据集中的“蓝色”标签的比率约为 25%。“蓝色标签比率”图表显示，对于 20 至 50 之间的阈值：

  • $T$ 集包含过多的“蓝色”标签样本（阈值 35 最多为 35%）。
  • $F$ 集包含“蓝色”标签样本的补充缺陷（阈值 35 只有 8% 的缺陷）。

  “蓝色标签比率”和“熵”曲线图均表示标签可以在此阈值范围内获得相对良好的分离。

• 此观察结果已在“信息增益”图中得到确认。我们发现，信息增益值约为 0.074，而 t~=28 可以获得最大信息增益。因此，分离器返回的条件将为 $x \geq 28$。

• 信息增益始终为正或为 null。其会随着零值收敛到其最大值 / 最小值而收敛到零。在这些情况下，$F$ 或 $T$ 要么为空，而另一个包含整个数据集，并且显示与 $D$ 中的相应值相同的熵。当 $H(T)$ = $H(F)$ = $H(D)$ 时，信息增益也可能为零。$6$($D) 和 F 值分别是 $T 和 $D。

一组实数 ($\mathbb{R}$) 中 $t$ 的候选值是无限的。然而，由于样本数量有限，$D$ 与 $T$ 和 $F$ 的除法有限。因此，仅测试有限数量的 t$ 值才有意义。

一种经典方法是按 x_s(i) 的升序对 x_i 值进行排序，使得：

$$ x_{s(i)} \leq x_{s(i+1)} $$

然后，在 $x_i$ 的连续排序值之间测试每个值 $t$。例如，假设特定特征有 1000 个浮点值。排序后，假设前两个值分别为 8.5 和 8.7。在这种情况下，第一个要测试的阈值为 8.6。

正式地，我们考虑以下 t 的候选值：

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

该算法的时间复杂度为 $\mathcal{O}（n \log n），其中 $n 为节点中的样本数（由于特征值的排序）。 应用于决策树时，会将拆分器算法应用于每个节点和每个特征。请注意，每个节点大约获得其父示例的 1/2。因此，根据主定理，使用此拆分器训练决策树的时间复杂度为：

$$ \mathcal{O} ( m n \log^2 n ) $$

其中：

• $m$ 是特征的数量。
• $n$ 是训练样本数。

在此算法中，特征的值无关紧要；仅顺序很重要。因此，此算法与特征值的比例或分布无关。正因如此，我们在训练决策树时不需要对数值特征进行归一化或缩放。