大数据背景下的最佳异常检测算法

算法要点/总结

我通过下面的综述来非常简洁地总结原来有10页内容的论文：

 

大多数其他异常检测(OD)算法尝试去建立"正常"数据的范围，从而把不属于这个正常范畴的个体标注为不正常。iForest则直接通过利用异常点的隐含特质来把他们分隔开：他们在协变量集上会拥有不寻常的值。

 

现有的方法由于计算成本的原因只能被用在低维数据或者小数据集上。一个恰当的例子是：你会在大数据上使用sklearn.neighbor.KNeighborsClassifier吗？

 

此外，iForest只需要很少的常量和很低的内存需求。也就是说，低开销。特别地：外部节点的数量是n，因为每个观测数据，n，都会被孤立。内部节点的总数显然是n-1，从而总体节点数会是2n-1。因此，我们可以理解为什么需要的内存是有界的，而且随着样本数量n线性增加。

 

孤立树节点的定义： T 或是一个没有子节点的叶子节点，或者是一个经过检验的内部节点，并拥有两个子节点（Tl，Tr）。我们通过递归地进行下述过程来构造一棵iTree：随机选择一项特征q和一个分割值p来划分X，直到发生下列情形之一为止：（i）树到达了限制的高度，（ii）所有样本被孤立成一个只有他们自己的外部节点，或者（iii）所有数据的所有特征都有相同的值。

 

路径长度：一个样本x的路径长度h（x）指的是从iTree的根节点走到叶子节点所经历的边的数量。E（h（x））是一组孤立树的h（x）的平均值。从这个路径长度的平均值，我们可以通过公式E（h（x））：s（x， n） = 2^[^[− E（h（x）） / c（n）]来得到一个异常分数s（x，n）。基本上，s和E（h（x））之间存在一个单调的关系。（想知道细节的话请查阅文末的附录，有一张图描述了他们之间的关系）。这里我不会讨论c（n），因为对于任意给定的静态数据集而言它是一个常数。

 

用户只需要设置两个变量：孤立树的数量和训练单棵树的子采样大小。作者通过对用高斯分布生成的数据做实验来展示了只需要少量的几棵树和少量的子采样数量就可以使平均路径长度很快地收敛。

 

小的子采样数量（抽样的抽样）解决了swamping和masking问题。造成这两个问题的原因是输入的数据量对于异常检测这个问题来说太大了。Swamping是指由于某个"正常"的样本点被异常点所包围而被错误地标注为"异常"，masking则是相反的情况。也就是说，如果构建一个树的样本中有很多异常点，一个正常的数据点反而会看起来很异常。 作者使用乳房x线照相的数据来作为这个现象的一个例子。

 

 

小的子采样数量使得每一棵孤立树都具有独特性，因为每一次子采样都包含一组不同的异常点或者甚至没有异常点。

 

iForest不依赖距离或者密度的测量来识别异常点，因此它计算成本低廉且有较快的速度。这引出了下一个议题。