适用于包含数值特征的二元分类的精确分屏器

在本单元中,您将探索最简单、最常见的分屏算法,该算法会在以下设置中创建形式为 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% 橙色),则香农熵最小(值为 0)。

三个图表。高熵图显示了两个不同类别之间存在大量的混合。低入门图展示了两个不同类之间的轻微混合。无熵图显示两个不同类别之间没有混合;也就是说,无熵图仅显示单个类别。

图 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%)。

    “蓝色标签的比例”和“熵”图表均表明,在该阈值范围内,标签可以相对较好地分离。

  • “信息增益”图表证实了这一点。我们发现,当 t 约为 28 时,信息增益最大,信息增益值约为 0.074。因此,分屏器返回的条件将为 x28

  • 信息增益始终为正数或 null。随着阈值趋近于最大值 / 最小值,该值会趋近于零。在这些情况下,FT 会变为空,而另一个集合包含整个数据集,并且熵等于 D 中的熵。当 H(T) = H(F) = H(D) 时,信息增益也可能为零。在阈值为 60 时,TF 的“蓝色”标签比例与 D 相同,并且信息增益为零。

实数集 (R) 中的 t 候选值无限。但是,对于有限数量的示例,D 只能以有限的方式划分为 TF。因此,只有有限数量的 t 值有意义。

传统方法是按升序 xs(i) 对值 xi 进行排序,以便:

xs(i)xs(i+1)

然后,针对 xi 的连续排序值中间的每个值测试 t。例如,假设您有 1,000 个特定特征的浮点值。假设排序后,前两个值分别为 8.5 和 8.7。在本例中,要测试的第一个阈值为 8.6。

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

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

此算法的时间复杂度为 O(nlogn),其中 n 是节点中的示例数量(由于特征值的排序)。在决策树上应用时,分屏算法会应用于每个节点和每个特征。请注意,每个节点会收到其父级示例的约 1/2。因此,根据主定理,使用此拆分器训练决策树的时间复杂度为:

O(mnlog2n)

其中:

  • m 是特征数。
  • n 是训练示例的数量。

在此算法中,特征的值无关紧要;只有顺序才重要。因此,此算法的工作方式与特征值的规模或分布无关。因此,在训练决策树时,我们无需对数值特征进行归一化或缩放。