一种新的多变量时间序列数据异常检测方法

李权，周兴社



一种新的多变量时间序列数据异常检测方法

李权1,2，周兴社1

（1. 西北工业大学 计算机学院，西安 710072；2. 西安卫星测控中心，西安 710043）

介绍了一种通过建立多变量时间序列数据相似度矩阵，对相似度矩阵进行转换以最大化数据之间的相关性，并采用随机游走模型计算数据点之间的连接系数来检测数据点上异常的方法。该方法充分利用了数据之间的相关性，有效减少了数据中不同程度噪声对异常检测的影响，检测过程中的漏报率和误报率明显减少，通过仿真实验验证了该方法的有效性。

时间序列数据；异常检测；相似性分析

异常检测也称为离群点检测，是近年来数据挖掘领域的重要研究方向之一[1-5]，其目标是在数据集中发现不正常的数据点，与之相关的研究包括：事件检测（event detection）[3]、变化点检测（change-point detection）[4]、异常行为检测（aberrant behavior detection）[5]等。目前，对时间序列的异常还没有一个公认的定义，普遍采用的是D. M. Hawkins给出的定义[6]：“异常点是那些与其他数据点有较大偏差的数据点，以至于怀疑这些偏差并非随机产生，而是产生于一种完全不同的方式”。异常检测技术已在经济、科学、工程等领域取得了广泛应用，如信用卡欺诈[7]、网络入侵检测[8]、航天器在轨诊断等。

异常检测方法主要包括以下几种：1）基于距离的异常点检测方法[9]，其通过计算数据点之间的距离来检测异常点，该方法具有简单高效的优点，但当数据包含多种不同分布的数据时效果不好； 2）基于密度的异常检测方法，如局部异常因子（LOF，local outlier factor）[10]，该方法克服了不同密度子集混合而造成的检测错误，检测精度较高，但当数据集较大时计算量大，复杂度过高，响应速度较慢；3）基于模型的异常检测方法[11]，该方法通过构建数据的概率分布模型，将具有较低概率的数据点作为异常点检出，该方法具有坚实的数学理论基础，其难点在于数据分布的识别和模型参数的估计。

目前大多数时间序列数据异常检测方法存在的主要问题是对数据之间的相关性分析利用不够，对噪声比较敏感[1]。本文介绍的异常检测方法充分利用了数据之间的相关性，采用高斯径向基函数计算序列之间的相似性，降低了噪声对检测结果的影响。该方法适用于数据噪声较大、数据量较小的异常检测，通过仿真实验验证了算法的有效性。

1 异常检测算法

1.1 相关定义

异常检测：在数据中检测那些数值明显背离数据集合总体分布情况的数据，依据检测出的内容可以划分为单数据点检测和子序列数据检测，单数据点检测用于检测时间序列数据中某一点的异常情况，子序列检测用于检测连续数据段（该数据段长度远小于整个数据序列长度）的异常情况。

1.2 相似度的度量

本文介绍的异常检测方法采用高斯径向基函数计算数据之间的相似性，但没有通过直接比较相似度进行异常检测，而是由相似度矩阵求解异常检测矩阵，通过计算检测矩阵的节点连接系数判断数据的异常，该方法能够有效降低噪声影响，最大化地利用数据之间的相关性。

1.3 异常检测矩阵构造

1.4 节点连接系数计算

1.5 算法流程

以上论述的故障检测算法的流程中，输入的是多变量时间序列数据和判断门限，经过一系列计算后，输出异常检测结果，从而可知异常时间点和相应的异常数据。计算步骤为：

1）计算各序列相似度矩阵；

2）由各序列相似度矩阵计算转换矩阵；

3）计算整个序列异常检测矩阵；

4）采用基于随机游走模型计算每个节点的连接系数；

5）对连接系数进行比较，获取输出。

2 实验与结果分析

图1 实验所用的多变量时间序列数据

上述数据采用本文介绍的方法进行异常检测，假设连接系数低于0.3的数据点视为异常，其检测的结果如图2所示。由图2可清晰看出在＝20和＝80这2个点上出现的数据异常，表明即使时间序列中出现了较强的噪声污染，本方法依然检测出了相应的异常点。试验中还比较了采用基于距离的异常检测方法的有效性，结果如图3所示。由图3可以看出，由于，对数据的影响，直接采用距离的方法难以检测出对应的异常点。

图2 采用检测矩阵的结果

图3 基于距离的检测结果

3 结论

本文介绍的多变量异常检测方法采用高斯径向基函数计算时间序列之间的相似性，通过建立相似度矩阵和异常检测矩阵实现了多变量时间序列数据的异常检测。由于本方法计算中有效挖掘了数据之间的相关性，降低了相关数据的噪声影响，因此异常检测的误报率和漏报率得到了下降。高斯径向基函数参数选择对检测结果的影响以及如何降低计算的复杂度将是下一步研究的重点。

[1] BARAGONA R, BATTAGLIA F. Outlier detection in multivariate time series by independent component analysis[J]. Neural Computation, 2007, 19(7): 1962-1984.

[2] LAST L, KANDEL A, BUNKE H. Data Mining in Time Series Databases[M]. Singapore: World Scientific Publishing Company, 2004.

[3] YAMANISHI K, TAKEUCHI J I. A unifying framework to detecting outliers and change-points from nonstationary data[C] // Proceedings of the Eighth ACM SIGKDD International Conference on KDD. New York: ACM, 2002: 676-681.

[4] JAGADISH H V, KOUDAS N, MUTHUKRISHNAN S. Mining deviants in a time series database[C] // Proceedings of 25th International Conference on Very Large Data Bases. San Fracisco: Morgan Kanfman Publishers Inc, 1999: 102-113．

[5] KOTSAKIS E, WOLSKI A. MAPS: a method for identifying and predicting aberrant behavior in time series[C] // Proceeding of 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. New York: ACM, 2001: 314-325.

[6] HAWKINS D M. Identification of Outliers[M]. London: Chapman and Hall, 1980．

[7] 吴婷. 数据挖掘在信用卡欺诈识别上的应用研究[D]. 南京: 东南大学, 2006.

[8] 范秉琪, 朱晓东, 马鸿雁, 等．基于数据挖掘的网络入侵检测系统的设计与应用[J]．河南理工大学学报, 2006, 25 (3): 247-250.

[9] KNORR E M, RAYMOND T N. A unified notion of outliers: properties and computation[C] // KDD-1997 Proceedings. [S.l.]: AAAI Press, 1997: 219-222．

[10] BREUNIG M M, KRIEGEL H P, RAYMOND T N, et al. LOF: identifying density-based local outliers[C] // SIGMOD′ 00 Proceedings of the 2000 ACM SIGMOD International Conference on Management of Date. New York: ACM, 2000: 93-104.

[11] 陈封能, 斯坦巴赫, 库玛尔. 数据挖掘导论[M]. 范明, 范宏建, 译. 上海: 人民邮电出版社, 2006.

[12] CRISTIANINI N, KANDOLA J, ELISSEEFF A, et al. On kernel-target alignment[C] // In Advances in Neural Information Processing Systems(NIPS2001). Vancouver, Canada: MIT Press, 2001: 367-373.

A new method of detecting anomalies in multivariate time series

LI Quan1,2, ZHOU Xing-she1

(1. School of Computer Science, Northwestern Polytechnic University, Xi′an 710072, China; 2. Xi′an Satellite Control Center, Xi′an 710043, China)

A new method of detecting anomalies in MTS (multivariate time series) is introduced, in which a similarity matrix for MTS is set up and the similarity matrix is transformed to maximize the correlation between the data points and then the anomalous data points are detected by comparing the predefined threshold with the connectivity coefficient calculated through the random walk model. This detection method makes full use of the correlation between the data points and effectively reduces the influence of the noise. The omission rate and false alarms decrease obviously, and the simulation has tested and verified the validity of this method.

MTS(multivariate time series); anomalies detection; similarity analysis

TP39

A

1674-0637(2011)02-0154-05

2011-03-06

李权，男，博士研究生，研究员，长期从事测控软件规划设计、数据挖掘、人工智能等方面的研究。