大数据的意义

> Photo by Simon Godfrey on Unsplash

隔离林或" iForest"是一种惊人的美丽且优雅的简单算法，可以识别很少参数的异常。原始论文可供广大读者使用，并且数学内容很少。在本文中，我将解释为什么iForest是目前最适合大数据的最佳异常检测算法，并提供了该算法的摘要，该算法的历史以及共享代码实现。

为什么iForest是目前针对大数据的最佳异常检测算法

一流的综合性能。基于ROC性能和精度，iForest在各种数据集上的性能比大多数其他异常值检测（OD）算法更好。我从Python离群值检测包（PyOD;原始论文）的作者那里获取了基准数据，并在Excel中应用了行向绿-红渐变条件格式。深绿色表示数据集的最佳算法，深红色表示性能最差的算法：

> I took benchmark data from PyOD (Python Outlier Detection toolbox) and applied row-scope green-red gradient conditional formatting in Excel. Green means "good" and red means "bad." We see that iForest leads across most datasets and in aggregate, as shown by mean, median and standard deviation colors. Image source: author. Data source:

我们看到，iForest在大多数数据集中均处于领先地位，如我所计算的均值，中位数和标准差行的颜色所示。对于iForest而言，相同的优异结果也适用于N次精度：

Image source: author. Data source:

可扩展性。iForest是性能最快的算法。预期在所有数据集中，基于PCA和基于直方图的离群值（HBOS；纸张，海报）都更快。k最近邻（KNN）慢得多，并且随着更多的观测值N而扩展得非常厉害。

我已经成功建立了隔离林，其中包含在集群环境中以分钟为单位的，包含36列的100M观测值的数据集。对于sk-learn的KNN（），我不能说同样的话。

Image source: author. Data source:

算法要点/摘要

我将简要概述10页的论文，并提供以下概述：

· 其他大多数异常检测（OD）算法都试图建立"正常"实例的描述文件，然后标记不符合该正常性描述文件的实例。iForest通过利用异常的固有属性显式隔离异常记录：它们对于协变量集具有异常值。

· 由于计算量大，现有方法仅限于低维数据和小数据大小。举例：曾经尝试对大数据使用sklearn.neighbor.KNeighborsClassifier吗？:)

· 此外，iForest具有"低常量和低内存需求"，即低开销。细节：外部节点的数量为n，因为每个观测值n都是独立的。内部节点的总数显然为n-1，而节点的总数为2n-1。因此，我们了解了为什么内存需求是有界的并且随n线性增长。此外，iForest具有"低常量和低内存需求"，即低开销。

· 隔离树节点定义：T是无子外部节点或具有一个测试且恰好有两个子节点（Tₗ，Tᵣ）的内部节点。要构建iTree，我们通过随机选择属性q和拆分值p递归地将X划分为：（i）树达到高度限制，（ii）所有观测值都隔离在其自己的外部节点上，或者（iii）所有数据的所有属性值都相同。

· 路径长度。观测值x的路径长度h（x）通过从根节点横穿iTree直到横向终止于外部节点的边数x来度量。E（h（x））是来自隔离树集合的h（x）的平均值。可以从平均路径长度E（h（x））得出异常分数s（x，n）：s（x，n）= 2 ^ [-E（h（x））/ c（n）]。基本上，s和E（h（x））之间存在单调关系（有关详细信息，请参见附录附录，并提供一个说明它们之间关系的有用图）。我不会涉及术语c（n），所以我可以保持简短，但是对于任何给定的静态数据集来说，它都是常数。

· 仅要求用户设置两个变量：要构建的树数和子采样大小。作者介绍了使用生成的高斯分布数据进行的实验，这些数据显示了如何在很少的树和较小的子样本的情况下相对快速地实现平均路径长度的收敛。

· 较小的子采样（样本的样本）大小解决了沼泽和掩蔽问题。沼泽和掩盖是由于输入数据太大而无法进行异常检测。沼泽是指将"正常"观测值误认为是"异常"观测值，因为它被异常包围，而掩蔽则相反。换句话说，当给一棵树喂食由大多数异常组成的样本时，正常数据点可能看起来异常。作者用乳腺X射线摄影数据提供了这种现象的例子。

· 较小的子样本可让每个隔离树都得到专门化，因为每个子样本都包含一组不同的异常甚至没有异常

· iForest无需依靠任何距离或基于密度的措施来识别异常，因此它速度快且计算成本低，这将导致下一个问题

· 线性时间复杂度O（n）。非正式地，这意味着运行时间最多随输入大小线性增长。这很好：

算法历史

广博的读者知道，一个伟大的新想法与广泛采用之间的时滞可能长达数十年。例如，逻辑函数在1845年发现，在1922年重新发现（了解更多），现在被现代数据科学家定期用于逻辑回归。在最近几十年中，新想法与更广泛采用之间的滞后时间有所减少，但可以说仍然是很长一段时间。iForest于2008年首次共享，直到2018年下半年才发布具有商业可行性的应用！时间表如下：

12/2008-发布iForest的原始文件（纸）07/2009-iForest作者最后修改其代码实现（代码）10/2018-h2o团队向R和Python用户提供iForest（代码）01/2019-PyOD版本异常适用于Python用户的检测（OD）工具包（代码，论文）08/2019 — LinkedIn工程团队发布了iForest的Spark / Scala实现（代码，新闻稿）

代码实现

由于本文是关于大数据的，因此我假设使用集群环境。我下面的实现适用于存储在AWS S3中的数据，但可以进行最小程度的修改以在其他地方使用。几乎省去了代码支架（代码到QA对象，调试等）。需要帮助为AWS集群环境安装软件包吗？请参阅我的中篇文章：如何为SparkSQL设置具有成本效益的AWS EMR集群和Jupyter Notebook

我发现iForest可以轻松快速地处理750万行和36个功能，并在几分钟内完成计算。

Python（h2o）：

下面的直方图是由上面的代码生成的。对于我的DataFrame projections_fullX中的观察结果，大多数观察结果并非异常，如较大平均路径长度的频率所证明的那样。

> Image source: author using a proprietary data set

如果您的数据带有您要与iForest确认的标签，则可以将具有异常实例的一组正常实例的分布与原始数据集进行比较，以进行进一步推断。例如，您可以按原始数据集中的功能的不同组合查看计数，如下所示：

N = df.count()df[['v1', 'v2', 'id']].groupby(['v1', 'v2']).count() / Ndf[['v1', 'v3', 'id']].groupby(['v1', 'v3']).count() / N...

并与iForest确定的正常/异常实例集进行比较，如下所示：

################################################################### column bind predictions from iForest to the original h2o DataFrame##################################################################hf_X_y_fullX = hf.cbind(predictions_fullX)################################################################### Slice using a boolean mask. The output dataset will include rows # with column value meeting condition##################################################################mask = hf_X_y_fullX["label"] == 0hf_X_y_fullX_0 = hf_X_y_fullX[mask,:]mask = hf_X_y_fullX["label"] == 1hf_X_y_fullX_1 = hf_X_y_fullX[mask,:]################################################################### Filter to only include records that are clearly normal##################################################################hf_X_y_fullX_ml7 = hf_X_y_fullX[hf_X_y_fullX['mean_length'] >= 7]hf_X_y_fullX_0_ml7 = hf_X_y_fullX_1[hf_X_y_fullX_0['mean_length'] >= 7]hf_X_y_fullX_1_ml7 = hf_X_y_fullX_3[hf_X_y_fullX_1['mean_length'] >= 7]################################################################### Convert to Pandas DataFrame for easier counting/familiarity##################################################################hf_X_y_fullX_ml7_df = h2o.as_list(hf_X_y_fullX_ml7, use_pandas = True)hf_X_y_fullX_0_ml7_df = h2o.as_list(hf_X_y_fullX_0_ml7, use_pandas = True)hf_X_y_fullX_1_ml7_df = h2o.as_list(hf_X_y_fullX_1_ml7, use_pandas = True)################################################################### Look at counts by combinations of variable levels for inference##################################################################hf_X_y_fullX_ml7_df[['v1', 'v2', 'id']].groupby(['v1', 'v2']).count()hf_X_y_fullX_0_ml7_df = h2o.as_list(hf_X_y_fullX_0_ml7, use_pandas = True)...# Repeat above for anomalous records:################################################################### Filter to only include records that are clearly anomalous##################################################################hf_X_y_fullX_ml3 = hf_X_y_fullX[hf_X_y_fullX['mean_length'] < 3]hf_X_y_fullX_0_ml3 = hf_X_y_fullX_1[hf_X_y_fullX_0['mean_length'] < 3]hf_X_y_fullX_1_ml3 = hf_X_y_fullX_3[hf_X_y_fullX_1['mean_length'] < 3]################################################################### Convert to Pandas DataFrame for easier counting/familiarity##################################################################hf_X_y_fullX_ml3_df = h2o.as_list(hf_X_y_fullX_ml3, use_pandas = True)hf_X_y_fullX_0_ml3_df = h2o.as_list(hf_X_y_fullX_0_ml3, use_pandas = True)hf_X_y_fullX_1_ml3_df = h2o.as_list(hf_X_y_fullX_1_ml3, use_pandas = True)

我做了所有这些工作，还将数据导出到Excel以快速产生一些累积分布函数，如下所示：

> Image source: author's own work. Green line represents label=1, or known normal observations; red line represents observations with a label=1, acknowledged as maybe or maybe not anomalous.

Python（pyod）（如果注释中有要求，我会添加代码！）

更新（2020年12月15日）：

PyOD github（链接）上有很多很棒的例子，所以我不需要补个例子。如果您有特定要求，请在评论中让我知道。由于Github并未显示结果，因此我的增值功能是显示代码应输出的内容。的输出应类似于：

> Image source: author

Scala（即将发布）

我将LinkedIn团队的iForest（github）实现用于Scala，因为PyOD和h2o是针对Python的。目前无法使其正常工作，但会在可能的情况下进行更新。

参考文献

· 刘F.T.刘，丁国K和Z.-H.周。隔离林。在：第八届IEEE数据挖掘国际会议（ICDM'08）会议录，意大利比萨，2008年，第413–422页。[代码]该论文在IEEE ICDM'08上获得了理论/算法亚军最佳论文奖

· Zhao，Y.，Nasrullah，Z.和Li，Z.，2019。PyOD：用于可扩展离群值检测的Python工具箱。机器学习研究杂志（JMLR），20（96），第1-7页。

关于作者

Andrew Young是Neustar的研发数据科学家经理。就上下文而言，Neustar是一家信息服务公司，从航空，银行，政府，营销，社交媒体和电信等领域的数百家公司中提取结构化和非结构化文本和图片数据。Neustar结合了这些数据成分，然后向企业客户出售具有附加值的成品，用于咨询，网络安全，欺诈检测和营销等目的。在这种情况下，Young先生是一个小型研发数据科学团队的动手首席架构师，负责构建，优化和维护一个系统，为所有产品和服务提供系统服务，为Neustar带来10亿美元的年收入。

附录

算法要点/摘要，要点5：

· 当E（h（x））→c（n）时，s→0.5（观察到的不是明显的异常）

· 当E（h（x））→0，s→1（异常）

· 当E（h（x））→n − 1，s→0（不是异常）

因此，以本文的话总结一下：

· （a）如果实例返回的s非常接近1，则肯定是异常，

· （b）如果实例的个数远小于0.5，则被视为普通实例是相当安全的，并且

· ©如果所有实例都返回s≈0.5，则整个样本实际上没有任何明显的异常。

有用的图，说明了异常得分s和平均路径长度E（h（x））之间的关系

> Figure 2 from Isolation Forest paper.

(本文由闻数起舞翻译自Andrew Young的文章《Isolation Forest is the best Anomaly Detection Algorithm for Big Data Right Now》，转载请注明出处，原文链接：)