基于滑动窗口预测的水文时间序列异常检测

摘要：针对水文时间序列分析与决策中存在的数据质量问题，提出了基于滑动窗口预测的水文时间序列异常检测算法。首先基于滑动窗口对时间序列进行子序列分割，再以子序列为基础建立预测模型对未来值进行预测，并将预测值和实测值间差异范围大于预设阈值的序列点判定为异常。探讨了算法中的滑动窗口和参数设置，并以实例数据对算法进行了验证。实验结果表明，所提算法不仅能够有效挖掘出水文时间序列中的异常点，而且将异常检测的灵敏度和特异度分别提高到80%和98%以上。

关键词：时间序列；异常检测；预测模型；置信区间；滑动窗口

中图分类号： TP393.08； TP18

文献标志码：A

Abstract： To solve data quality problems for hydrological time series analysis and decisionmaking， a new predictionbased outlier detection algorithm was proposed. The method first split given hydrological time series into subsequences so as to build a forecasting model to predict future values， and then outliers were assumed to take place if the difference between predicted and observed values was above a certain threshold. The setup of sliding window and parameters in the detection algorithm were analyzed， and the corresponding result was validated with the real data. The experimental results show that the proposed algorithm can effectively detect the outliers in time series and improves the sensitivity and specificity to at least 80 percent and 98 percent respectively.

Key words： time series； outlier detection； forecasting model； confidence interval； sliding window

0引言

时间序列挖掘作为数据挖掘领域的十大挑战性研究问题之一[1]，已被广泛应用于水文时间序列相似性搜索、序列模式挖掘和周期分析等领域。大部分水文时间序列挖掘的目的是为了发现频繁出现的模式，期望发现某种规律，异常数据通常被作为噪声而忽略。水文时间序列中的异常是与水文现象的数据模型或一般规律显著不同或不一致的数据对象，可能潜藏着更有价值和意义的水文信息和知识。因此，发现水文时间序列中的异常点并减少其对数据分析的影响是一项很有意义的工作。

本文采用基于滑动窗口的时间序列预测方法挖掘水文时间序列中的异常，算法通过基于滑动窗口方法预测未来数据值，并通过设定预测值和实测之间的以判定异常。实验结果表明，该方法能有效检测出水文时间序列中存在的异常，从而达到提高水文时间序列分析结果的目的。

1相关研究

异常检测（Outlier Detection）也称为异常挖掘或异常检测，是从大量数据中提取隐含在其中的人们事先不知道的但又是潜在有用的信息和知识的过程[2]。异常检测可以形式化地描述如下：给定一个包含n个数据点或对象的集合及预期的异常点数目k，发现与剩余的数据相比是显著异常的、孤立的或不一致的前k个对象的过程。异常检测需要解决两个主要问题：在给定的数据集合中定义什么样的数据是异常的；找到一个有效的方法来检测这样的异常数据。

按异常在时间序列中的不同表现形式，时间序列异常可以分为3种：序列异常、点异常和模式异常。目前，时间序列异常检测方法主要包括如下。

1）基于窗口的方法[3-4]。将时间序列划分成若干个固定大小的子序列（窗口），在各子序列中定位异常点，该方法的基础是时间序列中的异常点可能是其一个或多个子序列中的异常点导致。

2）基于距离的方法[5-6]。该方法通过特征点表征序列，利用二次回归模型实现对序列的不等长划分，以动态时间弯曲（Dynamic Time Warping， DTW）距离为基础计算子序列的异常分数，选取异常分数最大的前k个值来确定异常。

3）基于密度的方法[7-8]。该方法不是简单用Yes或No来断定一个点是否是离群点，而是用一个权值来评估它的离群度。它是局部的，意思是该程度依赖于对象相对于其邻域的孤立情况。这种方法可以同时检测出全局离群点和局部离群点。

4）基于支持向量机（Support Vector Machine， SVM）[3，9-10]的方法。该方法采用支持向量回归（Support Vector Regression， SVR）技术，对历史时间序列建立回归模型，判断新到来的序列点与模型的匹配程度。此外，一类支持向量机（OneClass SVM）技术[3，10]也在异常检测领域取得广泛应用。

5）基于聚类的方法[11]。该方法先将数据集分成若干簇，不属于任何簇的数据点就是异常点。在异常检测领域，聚簇技术被用于无监督检测和半监督检测。但异常检测通常是聚类算法的副产品，因此对异常点的挖掘效率较低。

综上所述，基于窗口的方法性能依赖于窗口宽度大小，窗口宽度过大或过小都可能影响检测结果的精度；基于距离的方法时间复杂度较高，效率不能保证；基于聚类的方法依赖于所有簇的个数和数据中离群点的存在性。文献[12-13]认为基于预测的时间序列异常检测是最简洁直观的异常检测方法，但该方法依赖于预测模型的预测能力，并且难以确定合理的阈值。

本文借鉴基于窗口方法中子序列分割的思想对时间序列进行子序列分割，再以子序列为基础建立预测模型对未来值进行预测，并根据分割的窗口大小及用户期望的置信度量动态计算阈值，不仅能够保证准确全面挖掘出水文时间序列中的异常点，而且提高异常检测精度和可靠性。

2.3参数选择

为了检测在时间序列中的异常值，基于滑动近邻窗口的异常点预测方法需要计算出测试点的合理的阈值τ。为提高异常检测方法的效率并改进算法性能，合理选择算法中涉及到的2个参数：k和p，成为提高异常检测算法的关键。因此，采用下述实验方法选择适当的参数值：

1）窗口的宽度k。k决定了参与预测的滑动邻接点数量。k值越大，参与计算的滑动邻接点越多，计算复杂度相应增加。为选择最优滑动窗口宽度，令k值范围为3～15，增量为1，即k={3，4，…，15}。

2）置信系数p。p定义了测量值在取值置信区间范围内的预期频率，置信系数越大，预测取值置信区间范围越大，令p值范围为80%～100%，增量为2%，即p={80%，82%，…，100%}。

异常检测的目标是尽可能多地检测出时间序列中存在的异常点并减少误检测的概率，因此，参数对（k，p）的取值准则是使得检测正确率和误检率之间的比值最大化。

3实验分析

为验证本文提出的水文时间序列异常检测方法的有效性，选择国家水文数据库中某测站的日均水位和流量数据进行实验，并对算法的检测结果进行分析和讨论。

3.1数据准备

选择某水文站（测站编码40105150，数据来源于水利部水文局）日均水位（单位为m）和日均流量（单位为m3/s日均流量的单位是以秒为单位的吗？是否正确？请仔细核实。）两种不同的水文要素进行算法验证，该水文站是黄河流域上重要的防洪控制站，在水文数据采集和预报、防洪调度、河流控制实验和水资源开发等领域对黄河下游重要的作用。采用该测站20060101―20071231的实测数据，图2为该数据对应的曲线。从图2可知，给定的时间序列数据集带有一定的周期性，曲线总体趋势平滑；但也存在一些明显可疑的“异常”点信息。

评估结果表明，本文算法能有效检测出水文时间序列中存在的异常点；特别说明的是，特异度指标基本上达到了98%。这些数据值意味着，本文算法检测的异常具有很高的可靠性。除此之外，算法的灵敏度、阳性预测值、阴性预测值也都维持着较高的比率，表明算法的整体检测效果的可靠性。

通过对参数对（k，p）的计算性实验还表明，降低置信度p的值会导致更多的数据点被判定为异常值；减小窗口的宽度值会导致FN增加而FP减小。

3.3算法分析

将本文方法与其他方法，如k近邻方法[14]、基于混沌方法[15]和基于中位数的自动检测算法[13]在同一数据集上进行比较，并将比较结果展示在接收者操作特征曲线（Receiver Operating characteristic Curve， ROC）上[16]。ROC的横轴是误报率（False Positive Rate， FPR），纵轴是检测率TPR（True Positive Rate），直观地展示了二者的对应关系。在异常检测的实际应用中，人们希望获得高的TPR和低的FPR；TPR表示检测算法的“灵敏度”，而1-FPR表示检测算法的“特异性”。理想的ROC是纵轴然后转为y=1的直线，越是接近坐标左上区域的ROC表示分类算法越精确。本文算法和其他算法在给定数据集上检测效果的ROC对比如图4所示。

4结语

针对水文时间序列异常挖掘，本文在基于预测的异常检测算法基础上，提出了基于滑动窗口的预测算法以检测水位时间序列中异常；并采用动态参数选择方法选择最优参数模型以提高检测算法的效率。本文采用黄河流域上某测站真实水文数据进行实验，验证了该方法的可行性和有效性，并与其他经典算法进行了比较，结果表明该方法能够较准确、及时地发现时间序列的异常点，满足水文数据质量控制的目标和要求。

参考文献：

[1]YANG Q， WU X. 10 challenging problems in data mining research [J]. International Journal of Information Technology and Decision Making， 2006， 5（4）： 597-604.

[2]HAN J， KAMBER M， PEI J. Data mining： concepts and techniques [M]. Waltham： Morgan Kaufmann Publishers， 2006.

[3]GAO B， MA H Y， YANG Y H. HMMs （Hidden Markov Models） based on anomaly intrusion detection method [C]// Proceedings of the 2002 International Conference on Machine Learning and Cybernetics. Piscataway： IEEE Press， 2002： 381-385.

[4]CHANDOLA V， BANERJEE A， KUMAR V. Anomaly detection： a survey [J]. ACM Computing Surveys， 2009， 41（3）： 15.

[5]RAMASWAMY S， RASTOGI R， SHIM K. Efficient algorithms for mining outliers from large data sets [C]// ACM SIGMOD Record， 2000， 29（2）： 427-438.

[6]YU H， WANG B， XIAO G， et al. Distancebased outlier detection on uncertain data [J]. Journal of Computer Research and Development， 2010， 47（3）： 474-484.（于浩，王斌，肖刚，等.基于距离的不确定离群点检测[J].计算机研究与发展，2010，47（3）：474-484.）

[7]BREUNIG M M， KRIEGEL H P， NG R T， et al. LOF： identifying densitybased local outliers [J]. ACM SIGMOD Record， 2000， 29（2）： 93-104.

[8]XUE A， JU S， HE W， et al. Study on algorithms for local outlier detection [J]. Chinese Journal of Computers， 2007， 30（8）： 1455-1463.（薛安荣，鞠时光，何伟华，等.局部离群点挖掘算法研究[J].计算机学报，2007，30（8）：1455-1463.）

[9]MOUNCE S R， MOUNCE R B， BOXALL J B. Novelty detection for time series data analysis in water distribution systems using support vector machines[J]. Journal of Hydroinformatics， 2011，13（4）：672-686.

[10]TIAN J， GU H. Outlier one class support vector machines [J]. Journal of Electronics and Information Technology， 2010， 32（6）： 1284-1288.（田江，顾宏.孤立点一类支持向量机算法研究[J].电子与信息学报，2010，32（6）：1284-1288.）

[11]BUDALAKOTI S， SRIVASTAVA A， AKELLA R， et al. Anomaly detection in large sets of highdimensional symbol sequences， NASA TM2006214553 [R]. Moffett Field： NASA Ames Research Center， 2006.

[12]HILL D J， MINSKER B S. Anomaly detection in streaming environmental sensor data： a datadriven modeling approach [J]. Environmental Modelling and Software， 2010， 25（9）： 1014-1022.

[13]BASU S， MECKESHEIMER M. Automatic outlier detection for time series： an application to sensor data [J]. Knowledge and Information Systems―Special Issue on Mining LowQuality Data， 2007， 11（2）： 137-154.

[14]POKRAJAC D， LAZAREVIC A， LATECKI L J. Incremental local outlier detection for data streams [C]// CIDM 2007： Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Data Mining. Piscataway： IEEE Press， 2007： 504-515.

[15]NG W W， PANU U S， LENNOX W C. Chaos based analytical techniques for daily extreme hydrological observations [J]. Journal of Hydrology， 2007， 342（1）： 17-41.

[16]FAWCETT T. An introduction to ROC analysis [J]. Pattern Recognition Letters， 2006， 27（8）： 861-874.