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