1 绪论
1.1 研究背景
异常检测旨在从给定数据集中发现异常的数据对象，具有广泛的应用场景。尽管异常检测方法很多，但是在海量数据中进行快速高效的异常检测仍然具有很大挑战。
1.1.1 异常检测业务场景
根据 Hawkins 对异常的定义，异常实例通常是那些与绝大部分观察结果存在巨大差异的实例[7]，因为这种差异性可能预示着截然不同的机制。如图 1-1 中所示，黑色点为异常实例，白色点为正常实例，正常实例因为有相似的属性而聚集在一个聚类中心周围，异常实例远离正常实例的聚类中心。异常实例在数据挖掘和统计文献中也被称为异常、不一致或偏差。在许多实际业务场景下，都会存在或多或少的异常，因而异常是普遍存在的。另外，产生异常的原因多种多样系统。首先，在数据采集阶段，由于数据采集人员可能出现笔误或者计算失误，因此可能得到异常的极端大值或极端小值。其次，各种偶然或非正常因素也有可能造成异常。另外，研究对象本身可能产生异常实例，例如，受某项政策或某个谣传的影响，股市出现巨大波动，因而在股票序列中产生了异常点；突如其来的地震使得死亡人数骤增，因而在人口死亡序列中会形成异常点 [8]。无论是哪种原因引起的异常，都可能对模型的拟合精度造成影响，甚至会得到一些虚假且具有误导性的信息。
异常检测是对不匹配预期模式或数据集中的实例、项目、事件或观测值进行识别[9] ，即通过一种策略找出数据集中与大多数数据不相同的数据。从计算机的产生到现在，使用计算机为现实世界的问题提供解决方案就伴随着异常检测。异常检测的目标是在给定的数据集中发现异常的数据实例，是数据挖掘的重要任务之一，应用场景广泛，下面举例几个应用场景。
...........................
1.2 国内外研究概况
1.2.1 异常检测的相关研究
近年来, 已经涌现了多种异常检测技术。根据监督性来划分[16]，异常检测方法可分为三种：无监督、监督和半监督型方法[9]，其主要区别在于能够利用类别标记(异常与正常)的程度。在异常检测场景下，数据往往缺少类别标记，即训练数据中并未标出哪些是异常点。由此可见，无监督学习方法更加实用，因此本文仅讨论无监督异常检测。无监督异常检测算法可分为以下几类：
（1）统计与概率模型：这类模型首先需要假设数据服从某个分布，然后通过假设检验或极值分析等方式找出假设条件下所定义的“异常”。例如，假设数据时一维数据且服从高斯分布，则可将不在距离均值特定范围之内的数据看做异常点。当数据是高维数据时，如果维度间相互独立，将每个维度上的异常度相加；如果特征间存在相关性，则可用马氏距离来评价数据的异常度[17]。基于统计与概率模型的优势是计算速度一般较快，但由于其依赖于人为做出的“假设”，当假设不当时，算法的准确度不高。
（2）线性模型：这类模型假设数据在低维空间上有嵌入，那些不能投射到低维空间中或者投射到低维空间后表现不好的数据被当做是异常点。例如，
PCA（Principal Component Analysis, 主成分分析）可以用于做异常检测[18]，其识别异常的方式有两种。一种方式是找到 k 个特征向量，并计算每个样本在经过这 k 个特征向量投射后的重建误差，异常样本的重建误差应该大于正常样本。另一种方式计算每个样本到这 k 个选特征向量所构成的超空间的加权欧氏距离（特征值越小权重越大）。同理，还有一种称为软性（Soft PCA）[19]的方法，其直接对协方差矩阵进行分析，并把样本的马氏距离（在考虑特征间关系时样本到分布中心的距离）作为样本的异常度。初次之外，经典算法 One-class SVM[20]也属于线性模型。
（3）基于相似度的模型：由于异常点和正常点的分布不同，因此二者之间的相似度较低，所以产生了一系列算法通过相似度来识别异常点的方法。例如，K-Means在检测异常时将样本到 k 个聚类中心的距离作为异常的评价标准，距离越大，越有可能是异常点。这是因为异常样本通常是离群点，与大部分正常距离较远。基于密度的模型也属于基于相似度的模型的范畴，这类模型主要通过数据的局部密度来检测异常，如 LOF、LOCI 和 LoOP[12]。其主要依据是异常点所处的空间通常数据少且密度觉低。另一种基于相似度的算法 ABOD[22]通过计算每个样本与所有其他样本对所形成的夹角的方差来识别异常样本，由于异常样本通常远离正常样本，因此方差变化小。大多数异常检测算法都可以被认为是在估计相似度，无论是通过密度、距离、夹角或是划分超平面。
.........................
2 孤立森林算法和 Spark 平台概述
2.1 IForest 算法介绍
2.1.1 概述
传统的异常检测方法大都先构建正常实例的画像，然后把不符合这个画像的实例看做异常。这样做的缺点在于：仅根据正常实例进行优化，容易把正常实例识别为异常实例或者只有少量的异常被检测到；计算复杂度高，受限于低维和小数据量。与传统方法不同，IForest 算法不再构建正常实例的画像，而是直接分离异常实例。IForest 利用异常实例数量少且特征值和正常实例不同的特点，使得异常实例可以很容易被分离出来。
IForest 使用了一套非常高效的策略查找容易被孤立（isolated）的点。假如用一个随机超平面对数据空间进行切分, 一次切分可以得到两个子空间。随后，继续用一个随机超平面对每个子空间进行切切，循环往复，直到每个子空间中只剩下一个数据点。可以发现，那些密度很高的簇需要被切分很多次才会停止切割，而那些密度很低的簇可以很快地就停止切分。如图 2-1 所示，黑色的点（ "，异常点）被切几次就停到一个子空间，而白色点（ #，正常点）聚集的地方切分很多次才停止。
...........................
2.2 Spark 平台介绍
Spark 相比与 Hadoop、Storm、Hive 非常易于使用，支持 Java、Scala、Python、R 和 SQL 进行快速编写并行应用程序。Spark 提供了超过 80 高阶操作，使得构建并行应用程序变得容易，交互式使用 Scala、Python、R 和 SQL。如图 2-3 所示，Apache Spark 的架构图。Spark 支持大量的库，包括 SQL 和 DataFrames[37]，用于机器学习的 MLlib，图计算 GraphX 和流式计算 Spark Streaming。Spark 支持绝大多数现有的大数据运行环境。Spark 能够运行以 YARN[38]，Apache Mesos[39]，Kubernetes[40]，Standalone、云端或本地（Local）等模式运行。Spark 能访问各种数据源，访问 HDFS，Alluxio，Apache Cassandra，Apache HBase，Apache Hive和数百个其他数据源中的数据[37]。
Spark 运行架构，包括集群资源管理器 Cluster Manager、执行作业任务的节点 WorkerNode、每个作业的控制节点 Driver 以及每个工作节点上负责具体作业的执行进程 Executor。对比 Hadoop 的 MapReduce 计算框架，Spark 的 Executor利用多线程来执行具体的任务，节省了任务的启动开销；除此之外，Executor 中的BlockManager 将磁盘和内存都作为存储设备，明显减少了 IO 开销。
..........................
3 孤立森林算法的并行化研究................29 3.1 Spark-IForest 并行算法思想 ............................ 20
3.2 数据结构的实现................................ 24
3.3 数据抽样的实现........................ 29)
4 实验结果与分析......................42
4.1 实验环境 ...................................... 42
4.2 实验数据 ........................... 43
5 总结与展望...............49
5.1 全文总结 .......................49
5.2 展望 ..............................49
4 实验结果与分析
4.1 实验环境
4.1.1 硬件支持
本实验采用单机多核测试，Spark本地模式可以启动多个Executor进程并行计算。本实验涉及的机器配置如表 4-1 所示：
.........................
5 总结与展望
5.1 全文总结
异常检测在实际业务场景下应用十分广泛。然而，实际业务场景通常伴随着海量大数据，这使得异常检测的精确度和效率成为挑战。Hadoop 和 Spark 等分布式大数据计算平台为海量数据处理提供了解决方案。传统的异常检测算法难以解决海量数据场景下的性能问题，IForest 算法在训练阶段构建 iTree 和预测阶段调用模型进行异常预测为分布式并行计算提供了可能。当前应用最为广泛的 IForest 算法实现库是基于 Sklearn 的单机实现，四川大学的侯泳旭基于 Hadoop 设计和实现了 IForest 算法库，但无论是单机版的 Sklearn 还是基于磁盘的分布式计算框架 Hadoop 的性能和处理数据量的级别上，与基于内存的分布式计算平台 Spark 相比不够突出的。
通过对并行化 IForest 算法的研究以及对 Spark 平台的研究及应用，本文主要针对 IForest 算法的特性在 Spark 上实现了分布式并行算法库 Spark-IForest。主要工作包括如下:
（1）研究 Spark 分布式计算平台，根据 IForest 特性定义数据结构，遵循 Spark ML Pipeline 规范和 Apache Spark 社区规范，设计并在实现训练阶段和预测阶段都并行化的 IForest 算法库，并进行性能调优。
（2）对Spark-IForest库与Sklearn-IForest库进行对比性能测试，并对Spark-IForest扩展性测试，验证了并行 Spark-IForest 算法库在预测效果上令人满意，且在运行速度上有了巨大提升。
参考文献(略)