基于Spark ML library的anomaly detection算法与模型的研究文献综述

调研报告：

1. 异常检测 (Anomaly Detection)

（1）异常检测介绍

异常检测问题是指从数据中发现与期望不同的一些现象。这些现象大多是由于各种各样的系统错误、异常、故障或者恶意破坏所导致的。异常检测已经被广泛的运用在各种各样不同的领域之中，取得了很好的效果。

与异常检测相关的技术还有noise removal[1], novelty detection[2] 等等。

(2) 异常的种类

一般来说，异常可以被分为3个不同的种类

1. 异常点(Point Anomalies)

如果说一个单独的数据点可以被判断为异常，那么久被称为点异常。这种事最简单的一种异常，也是最为广泛使用的一种异常。

如下图所示，点 都属于点异常。

Figure 1

例如，在检测信用卡欺诈的时候，我们用一个最简化的模型：支付的金额 来进行异常检测，那么一个具有高价值的账单数据，就会形成一个点异常。而小额的支付通常是安全的而不被认为是异常。

II． 上下文相关异常（Contextual Anomalies）

在这种情况下，异常在一定的上下文中被检测出来。一个数据单独看来有可能是很正常的，但是放在某种环境下，就显示出了异常。[3][4]

下图表示了某地区的气温变化情况。可以看到，在时刻的温度和时刻的温度是相同的，单独从这一点并不能发现它的异常信息。但是结合上下文可以发现，时刻的温度远远低于它之前和之后的温度，因此应当被判定为异常情况。像这样的异常就属于上下文相关的异常。

Figure 2

1. 集合异常(Collective Anomalies)

如果说一系列数据构成的一个集合是异常的，但是其中任意一个数据却不是异常的，那么久称为集合的异常。下图展示了集合异常的一个例子[5]。

Figure 3

中间红色的部分是一个异常的集合，因为它持续的时间已经超出了正常的其它周期。但是从单个点看，其中的每一个点都不足以构成一个异常的数据。其他类似于这中情况的都被称之为集合异常。

（3）异常数据的种类

异常数据通常可以分为有标注、部分标注（只有正常的数据）、无标注三类。对于不同的数据，应分别采用监督学习、半监督学习、无监督学习的方法。由于异常检测问题的特殊性，有标注的数据是稀少的，通常要面临的都是后面两种问题。

（4）异常检测的输出

异常检测通常有两种输出。第一种是对数据进行打分，不同的分数表示了异常的程度。另一种则是直接输出结论，即输出检测的数据是否是异常。

（5）异常检测的常见应用

I．入侵检测。Denning [6] 将异常检测用于网络入侵检测。提出了基于Host和基于Network的检测模型

II. 欺诈检测。Fawcett 和Provost 提出了基于活动的信用卡欺诈检测算法和利用神经网络的保险欺诈的检测算法 [7].

III．内部交易检测。 这是一种近期发展的异常检测应用领域。主要是对股票、期货市场的内部交易进行检测。Donoho [8], Aggarwal [9] 提出了不同的算法来解决问题。

此外，异常检测还可以被用在医学[10]，工业探伤[11],图像处理[12]等等不同的领域。

（6）异常检测的常用算法

I．基于分类的检测法。

异常检测可以认为是一个分类问题，因此可以用解决分类问题的方法来处理。包括神经网络[12]、贝叶斯网络[13]、SVM [14]等分类器都可以用于异常检测。

II. 基于密度的算法

由于异常的数据通常远离正常的数据，比较分散，而正常的数据通常比较靠近。所以可以通过对数据周围的密度进行计算来判断是否异常。欧几里得距离(Euclidean distance)是比较常用的标准[15]。采用不同的测量标准会在不同的问题上有不同的效果。

III. 基于聚类的方法

如果异常的正常的数据可以被有效的进行聚类，那么各种聚类算法也可以应用在异常检测上。例如DBSCAN, ROCK,和SNN 聚类。

IV．基于统计的方法

异常现象在统计的角度看来是稀少的，发生的概率比较低的。如果对事件的概率进行建模，就可以利用统计的方法进行一场检测。可以使用一些参数的方法[16] 或者非参数的方法。

V．基于复杂度的方法

异常的数据会带来比较大的信息量。如果定义是数据的复杂度，那么就是找到一个子集满足最大。相关的算法有线性算法[17]等。

(7) 时间序列数据的异常检测

时间序列数据是一种非常广泛的数据形式。在Anomaly Detection 领域，也有着重要的意义。由于其数据的特殊性，不能直接使用在(6)节中提到的算法，需要进行一些专用的算法来解决问题。

时间序列数据通常要面临更多的问题。比如序列的长度有可能是不一样的、序列有可能是未经过对齐的等等。

为了处理时间序列数据，可以采用两种不同的策略。第一是将时间序列问题想办法转化到点异常，然后使用之前提到的算法来解决。如果序列式等长的，可以直接看作是一个向量，也可以用盒模型对其进行编码再处理。而另一种更好的办法是充分利用时间序列的特点来进行检测。通常有基于时间的规则归纳，Finite State Automaton(FSA)，Hidden Markov Model(HMM)，Probabilistic Suffix Trees(PST)等等。

(8) 小结

异常检测是一个重要的研究方向、它可以被广泛的应用在不同的领域之中，处理各种不同的数据。这些应用都有很高的实际意义。为了能够更加有效的处理这些问题，新的模型和算法被不断的提出，在不同的问题上取得新的进展。

2． Apache Spark

Apache Spark 向程序员提供了一系列基于RDD（resilient distributed dataset，弹性分布式数据集）的 API (Application programming interface). RDD 是一种分布式的数据集，是为了克服 Hadoop 中MapReduce用到的数据模型的种种缺点而被设计出来的。不同于Hadoop极大的依赖硬盘存储，RDD可以在内存中进行主要的工作，这大大提高了其运行的速度。

Spark 依赖集群管理和分布式存储系统来工作。对于集群管理，spark支持单机运行，Hadoop YARN和 Apache Mesos. 对与分布式存储，spark可以系统兼容，包括Hadoop分布式存储(Hadoop Distributed File System ,HDFS), MapR-FS, Cassandra等等不同的系统。

Spark Core作为Spark 的核心，负责任务分发与调度、I/O管理等等。提供了一系列Scala/Java/Python/R的接口。Spark SQL则与数据库想结合，同时提供了对半结构化数据的处理。Spark Streaming则提供了对流进行处理和分析的工具。 而MLlib (Machine Learning Library) 提供了分布式条件下的机器学习算法库，包括需要用到的数据结构和一些算法的实现。

Spark起源于 UC伯克利的AMPLab. 2009年，Matei Zaharia发布了最早的Spark，并于2010年使用BSD协议进行开源。2013年，Spark被捐赠给了Apache 软件基金会，使用 Apache 2.0 开源协议进行开源。到2014年，已经成为Apache基金会的顶级项目，如今是该基金会最活跃的开源项目之一。

参考文献

[1] Teng, H., Chen, K., and Lu, S. 1990. Adaptive real-time anomaly detection using inductively generated sequential patterns. In Proceedings of IEEE Computer Society Symposium on Re-search in Security and Privacy. IEEE Computer Society Press, 278–284.

[2] Markou, M. and Singh, S. 2003a. Novelty detection: a review-part 1: statistical approaches. Signal Processing 83, 12, 2481–2497.

[3] Weigend, A. S., Mangeas, M., and Srivastava, A. N. 1995. Nonlinear gated experts for time-series - discovering regimes and avoiding overfitting. International Journal of Neural Systems 6, 4, 373–399.

[4] Salvador, S. and Chan, P. 2003. Learning states and rules for time-series anomaly detection. Tech. Rep. CS–2003–05, Department of Computer Science, Florida Institute of Technology Melbourne FL 32901. march.

[5] Goldberger, A. L., Amaral, L. A. N., Glass, L., Hausdorff, J. M., Ivanov, P. C., Mark,R. G., Mietus, J. E., Moody, G. B., Peng, C.-K., and Stanley, H. E. 2000. Physio Bank, Physio Toolkit, and Physio Net: Components of a new research resource for complex physiologic signals. Circulation 101, 23, e215–e220.

[6] Denning, D. E. 1987. An intrusion detection model. IEEE Transactions of Software Engineering 13, 2, 222–232.

[7] Fawcett, T. and Provost, F. 1999. Activity monitoring: noticing interesting changes in behavior. In Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 53–62.

[8] Donoho, S. 2004. Early detection of insider trading in option markets. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM Press, New York, NY, USA, 420–429.

[9] Aggarwal, C. 2005. On abnormality detection in spuriously populated data streams. In Proceedings of 5th SIAM Data Mining. 80–91.

[10] Wong, W.-K., Moore, A., Cooper, G., and Wagner, M. 2003. Bayesian network anomaly pattern detection for disease outbreaks. In Proceedings of the 20th International Conference on Machine Learning. AAAI Press, Menlo Park, California, 808–815.

[11] Keogh, E., Lonardi, S., and chirsquo; Chiu, B. Y. 2002. Finding surprising patterns in a time series database in linear time and space. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM Press, New York, NY, USA, 550–556.

[12] Augusteijn, M. and Folkert, B. 2002. Neural network classification and novelty detection. International Journal on Remote Sensing 23, 14, 2891–2902.

[13] Barbara, D., Couto, J., Jajodia, S., and Wu, N. 2001b. Detecting novel network intrusions using bayes estimators. In Proceedings of the First SIAM International Conference on Data Mining.

[14] Vapnik, V. N. 1995. The nature of statistical learning theory. Springer-Verlag New York, Inc., New York, NY, USA.

[15] Tan, P.-N., Steinbach, M., and Kumar, V. 2005. Introduction to Data Mining. Addison-Wesley.

[16] Eskin, E. 2000. Anomaly detection over noisy data using learned probability distributions. In Proceedings of the Seventeenth International Conference on Machine Learning. Morgan Kaufmann Publishers Inc., 255–262.

[17] Arning, A., Agrawal, R., and Raghavan, P. 1996. A linear method for deviation detection in large databases. In Proceedings of 2nd International Conference of Knowledge Discovery and Data Mining. 164–169