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

在本单元中,您将探索最简单、最常见的拆分器算法,该算法使用以下设置创建 featureit 形式的条件:

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

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

D={(xi,yi)}i[1,n]

其中:

  • xiR(一组实数)中数值特征的值。
  • yi 是以 {orange, blue} 表示的二进制分类标签值。

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

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

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

三个示意图。高熵图展示了两个不同类的许多混合现象。低条目图展示了将两种不同的类混合在一起的一点。无熵图显示两个不同的类没有混合;也就是说,无熵图只显示一个类。

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

 

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

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

两个图,两个图显示了两个不同类别几乎完全相同的混合。

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

 

相比之下,下图显示了一个更好的分屏,其中熵变为低值(信息增高):

两张示意图。一个示意图由大约 95% 的橙色类和 5% 的蓝色类组成。另一个图由大约 95% 的蓝色类和 5% 的橙色类组成。

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

 

正式名称:

T={(xi,yi)|(xi,yi)D with xit}F={(xi,yi)|(xi,yi)D with xi<t}R(X)=|{x|xX and x=pos}||X|H(X)=plogp(1p)log(1p) with p=R(X)IG(D,T,F)=H(D)|T||D|H(T)|F||D|H(F)

其中:

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

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

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

四张阈值阈值与其他参数的对比图。此图表后面的列表总结了这些图表。

图 11. 四个阈值图。

 

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

  • “频率”图显示观察结果相对分散,其浓度介于 18 到 60 之间。广泛的价值分布意味着存在大量的潜在拆分,这有助于训练模型。
  • 数据集中的“蓝色”标签的比率约为 25%。“蓝色标签比率”图表显示,对于 20 至 50 之间的阈值:

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

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

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

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

一组实数 (R) 中 t 的候选值是无限的。然而,由于样本数量有限,DTF 的除法有限。因此,仅测试有限数量的 t$ 值才有意义。

一种经典方法是按 xs(i) 的升序对 xi 值进行排序,使得:

xs(i)xs(i+1)

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

正式地,我们考虑以下 t 的候选值:

X={xs(i)+xs(i+1)2|xs(i)xs(i+1)}

该算法的时间复杂度为 Onlognn 为节点中的样本数(由于特征值的排序)。 应用于决策树时,会将拆分器算法应用于每个节点和每个特征。请注意,每个节点大约获得其父示例的 1/2。因此,根据主定理,使用此拆分器训练决策树的时间复杂度为:

O(mnlog2n)

其中:

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

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