RCF工作原理

Amaz SageMaker on Random Cut Forest (RCF) 是一种无监督算法，用于检测数据集中的异常数据点。这些数据点是与良好结构或模式化数据存在偏差的观察数据。异常可以表现为时间序列数据中意外峰值、周期性中断或无法分类的数据点。它们很容易描述，表现为在图中查看时，它们通常很容易与“常规”数据区分。数据集中包括这些异常会显著增加机器学习任务的复杂性，因为“常规”数据通常使用简单模型描述。

该RCF算法背后的主要思想是创建一个树林，其中每棵树都是使用训练数据样本的分区获得的。例如，首先确定输入数据的随机样本。然后，根据森林中树的数量对随机样本分区。向每个树提供一个这样的分区，并将这些点的子集整理到 k-d 树中。由树分配给数据点的异常分数定义为将该点添加到树中导致的树的复杂性变化；这大致与点在树中生成的深度成反比。Random Cut Forest 通过从组成的每棵树计算平均分数，并根据样本大小缩放结果，从而分配异常分数。该RCF算法基于参考文献 [1] 中描述的算法。

随机采样数据

RCF算法的第一步是获取训练数据的随机样本。具体而言，假设我们希望从总共 个数据点中提取 个数据点的样本。如果训练数据集足够小，可以使用整个数据集，并且我们可以从此数据集随机提取 个元素。但是，训练数据经常会太大，无法一次使用，此方法不可行。我们改用一种称为水库采样的技术。

水库采样是一种算法，可用于从一个数据集 中有效地提取随机样本，其中数据集中的元素只能观察一次或者批量观察。事实上，即使 不是事先知道，水库采样仍可工作。如果只请求一个样本，例如当 时，算法类似于：

算法：水库采样

• 输入：数据集或数据流

• 初始化随机样本

• 对于每个观察到的采样 ：

  • 选取统一随机号码

  • 如果

    • Set

• 返回值

此算法选择随机采样，这样对于所有 ，可计算 。当 时，算法更复杂。此外，必须区分使用替换和不使用替换的随机采样。RCF基于 [2] 中描述的算法，在不替换训练数据的情况下执行增强的储层采样。

训练RCF模型并生成推论

下一步RCF是使用随机数据样本构建随机砍伐森林。首先，该样本分为多个大小相等的分区，其数量与森林中树的数量相同。然后，每个分区发送到单个树。树通过将数据域分区到边界框，以递归方式将其分区组织到二进制树中。

这个过程可以通过一个例子来很好地说明。假设向一颗树提供了以下二维数据集。对应的树初始化到根节点：

图：一个二维数据集，其中大部分数据位于聚类中（蓝色），只有一个异常数据点（橙色）除外。使用根节点初始化树。

该RCF算法通过首先计算数据的边界框，选择一个随机维度（为 “方差” 较高的维度赋予更大的权重），然后随机确定穿过该维度的超平面的位置，从而将这些数据组织在树中。生成的两个子空间定义自己的子树。在本示例中，通过砍伐将单一点与样本中其余数据分离开。生成的二进制树的第一级包含两个节点，其中一个由初始砍伐左侧点的子树组成，另一个表示右侧的单一点。

图：对二维数据集进行随机切分的分区。异常数据点更可能隔离在边界框中，相比其他点具有较小的树深度。

然后，对两等分的数据计算左侧和右侧的边界框，重复该过程，直至树的每个叶表示来自样本的一个数据点。请注意，如果单一点足够远，则随机砍伐更可能产生点隔离。此观察提供的直觉感受是，大致来说，树深度与异常分数成反比。

使用经过训练的RCF模型进行推理时，最终的异常分数将报告为每棵树报告的分数的平均值。请注意，经常会出现新的数据点不在树中的情况。要确定与新数据点关联的分数，请将数据点插入指定树中，按照与上述训练过程相等的方式，高效 (并且临时) 重组树。也就是说，就像输入数据点是最初用于构造树时所用样本的成员那样生成了树。报告的分数与输入点在树中的深度成反比。

选择超参数

用于调整RCF模型的主要超参数是num_trees和。num_samples_per_tree增加 num_trees 具有减少在异常分数中观察到的噪音的效果，因为最终分数是各个树报告的分数的平均值。尽管最优值取决于应用，我们建议使用 100 个树开始，以在分数噪声和模型复杂性之间取得平衡。请注意，推理时间与树的数量成正比。虽然训练时间也会受影响，但主要由上述的水库采样算法决定。

参数 num_samples_per_tree 与数据集中的预期异常密度相关。具体而言，num_samples_per_tree 的选择应该使得 1/num_samples_per_tree 大致相当于异常数据与普通数据的比率。例如，如果每个树中使用 256 个样本，则我们预期数据包含 1/256 的异常，或者大约为 0.4% 的时间。同样，此超参数的最优值取决于应用。

参考信息

1. Sudipto Guha、Nina Mishra、Gourav Roy 和 Okke Schrijvers。“基于流上异常检测的可靠 Random Cut Forest。” 机器学习国际会议会刊，第 2712-2721 页。2016 年。

2. Byung-Hoon Park、George Ostrouchov、Nagiza F. Samatova 和 Al Geist。“可在数据流中进行替换的基于水库的随机采样。” 载于《2004年数据挖掘SIAM国际会议论文集》，第492-496页。Society for Industrial and Applied Mathematics，2004 年。