在本单元中,您将探索最简单、最常见的分屏算法,该算法会在以下设置中创建形式为 的条件:
- 二元分类任务
- 示例中没有缺失值
- 未对示例预计算索引
假设有一组 个示例,其中包含一个数值特征和一个二元标签“橙色”和“蓝色”。形式上,我们将数据集 描述为:
其中:
- 是 (实数集)中的数值特征的值。
- 是 {orange, blue} 中的二元分类标签值。
我们的目标是找到一个阈值 (阈值),使得根据 条件将示例 划分为 和 组,从而改进标签分离效果;例如, 中包含更多“橙色”示例, 中包含更多“蓝色”示例。
香农熵是一种混乱程度的衡量标准。对于二元标签:
- 当示例中的标签平衡(50% 为蓝色,50% 为橙色)时,香农熵最大。
- 如果示例中的标签是纯色(100% 蓝色或 100% 橙色),则香农熵最小(值为 0)。
图 8. 三种不同的熵级别。
形式上,我们希望找到一个条件,以降低 和 中的标签分布熵的加权和。相应的得分是信息增益,即 的熵与 {,} 熵之间的差值。这项差异称为信息增益。
下图显示了一种不良的拆分,其中熵保持较高,信息增益较低:
图 9. 糟糕的分块不会降低标签的熵。
相比之下,下图显示了一种更好的分块,其中熵变低(信息增益变高):
图 10. 良好的分块可降低标签的熵。
正式:
其中:
- 是将 拆分为 和 的信息增益。
- 是样本集 的熵。
- 是集合 中的元素数量。
- 是阈值。
- 是正面标签值,例如上例中的“blue”。选择其他标签作为“正例标签”不会改变熵或信息增益的值。
- 是样本 中正例标签值的比率。
- 是数据集(如本单元前面所定义)。
在以下示例中,我们考虑一个包含单个数值特征 的二元分类数据集。下图显示了对于不同的阈值 值(x 轴):
- 特征 的直方图。
- 根据阈值的大小,、 和 集中“蓝色”示例的比例。
- 、 和 中的熵。
- 信息增益;即 与 {,} 之间的熵差,乘以示例数量。
图 11. 四个阈值图。
这些图表会显示以下内容:
- “频率”图表显示,观察结果分布相对均匀,浓度介于 18 到 60 之间。值范围较大意味着存在许多潜在的分块,这对训练模型很有帮助。
数据集中“蓝色”标签的比例约为 25%。“蓝色标签的比例”图表显示,对于介于 20 到 50 之间的阈值值:
- 集包含过多的“蓝色”标签示例(如果阈值为 35,则最多占 35%)。
- 集包含“蓝色”标签示例的补充缺口(阈值为 35 时仅为 8%)。
“蓝色标签的比例”和“熵”图表均表明,在该阈值范围内,标签可以相对较好地分离。
“信息增益”图表证实了这一点。我们发现,当 t 约为 28 时,信息增益最大,信息增益值约为 0.074。因此,分屏器返回的条件将为 。
信息增益始终为正数或 null。随着阈值趋近于最大值 / 最小值,该值会趋近于零。在这些情况下, 或 会变为空,而另一个集合包含整个数据集,并且熵等于 中的熵。当 = = 时,信息增益也可能为零。在阈值为 60 时, 和 的“蓝色”标签比例与 相同,并且信息增益为零。
实数集 () 中的 候选值无限。但是,对于有限数量的示例, 只能以有限的方式划分为 和 。因此,只有有限数量的 值有意义。
传统方法是按升序 xs(i) 对值 xi 进行排序,以便:
然后,针对 的连续排序值中间的每个值测试 。例如,假设您有 1,000 个特定特征的浮点值。假设排序后,前两个值分别为 8.5 和 8.7。在本例中,要测试的第一个阈值为 8.6。
正式地,我们考虑以下 t 候选值:
此算法的时间复杂度为 ,其中 是节点中的示例数量(由于特征值的排序)。在决策树上应用时,分屏算法会应用于每个节点和每个特征。请注意,每个节点会收到其父级示例的约 1/2。因此,根据主定理,使用此拆分器训练决策树的时间复杂度为:
其中:
- 是特征数。
- 是训练示例的数量。
在此算法中,特征的值无关紧要;只有顺序才重要。因此,此算法的工作方式与特征值的规模或分布无关。因此,在训练决策树时,我们无需对数值特征进行归一化或缩放。