检测非平稳时间序列中离群点和变化点的统一框架

刘 利 何先平 袁文亮

（1.池州学院 数学计算机系，安徽 池州 247000；2.长江大学 信息与数学学院，湖北 荆州 434023）

检测非平稳时间序列中离群点和变化点的统一框架

刘 利1何先平2袁文亮1

（1.池州学院 数学计算机系，安徽 池州 247000；2.长江大学 信息与数学学院，湖北 荆州 434023）

文章为在非平稳时间序列的在线学习理论的基础上检测离群点和变化点提出了一个统一框架.在这个框架中数据源的一个概率模型用一种在线折扣学习算法被逐步学习，该算法能通过逐渐忘记过去数据的效果自适应地跟踪变化的数据源.然后任一给定数据的分数被计算出来测量它与学习模型的偏差，高分表明更有可能是离群点.进一步地数据流中的变化点通过用这一学习模型应用这种得分方法到一个移动平均损失预测时间序列中来检测.特别地我们为来自时间序列数据的自回归模型的在线折扣学习发明了一种有效算法，并通过仿真和在股票市场数据分析的实际应用验证框架的有效性.

离群点；变化点；非平稳时间序列；在线学习

0 引言

现有非平稳数据源的离群点检测算法中，适应性离群点检测算法已经被提出了.可是，没有得出任何明确的统计模型以便于时间序列能被处理.

为检测离群点和变化点我们用AR模型来代表时间序列数据的统计行为.AR模型是一种最典型的时间序列统计模型，该模型在统计中已经被广泛采用.大多数现有的估计AR模型的参数的算法都是在数据源是平稳的假定下设计的，一种处理非平稳数据的方法是介绍一种系数是随时间变化的AR模型.相反地，我们通过模型化AR模型评估算法来处理非平稳数据，逐步更新它的参数估计值以便过去例子的效果逐渐被打折.然后我们给每个数据／时间点一个分数，高分表明更有可能是离群点.这使得程序更有效率，并可适用于不能用简单的分段模型表示的数据源.

在文［1］中解决变化点检测问题时没有假设数据是局部平稳的.反而，在文［1］中用分段函数来拟合依赖于时间的数据，变化点被定义为连续函数的分界点.在该方法中，可通过找模型拟合误差最小的点作为变化点.可是，找到这样的点计算复杂度太大，因为数据每输入一次，有多少分界点，就得拟合多少次局部模型.进一步当数据源不能很好地用一个简单的分段函数表示时它不能保证有效.

尽管在大多数先前的工作中离群点检测和变化点检测没有明确地相关，本文给出了它们间一个清楚的联系，并提出了从非平稳时间序列在线打折学习的角度同时处理他们的一个统一框架.在我们的框架中，我们能在同一个学习算法的基础上同时检测离群点和变化点.本文提出的变化点探测算法计算效率高，达到了很高的探测准确性.

1 数据模型和在线学习算法

我们记一个数据序列为｛x t：t＝1，2，…｝，这里t是时间变量.设该序列的概率密度函数为｛p t：t＝1，2，…｝，它描述了底层机制的生成数据.这一序列应该从｛x t｝中被逐步学习，一旦一个数据x t被输入进来，我们也建造一个预测值｛＾x t：t＝1，2，…｝，这里＾x t应该在｛p t｝和｛x t｝的基础上计算.下面我们描述构造｛p t｝和｛x t｝的模型和学习算法.

1.1 独立模型

我们首先考虑数据每次是独立抽取的情况.假定多维域X⊂Rn是连续的，我们用x代表X上的一个随机变量，用下面形式的Gaussian混合模型代表非平稳独立数据生成的一个概率密度函数：

SDEM算法由推广的Neal和Hinton的逐步EM算法［2］介绍，以便过去例子的效果能随着时间流逝逐渐打折.SDEM算法用依赖于折扣参数r的带权的平均值更新参数估计值，这里r值越小表明SDEM算法对过去例子的影响越大.

在SDEM算法中，参数α为了提高c i估计值的稳定性被提出来，ci被设定在1.0～2.0.

1.2 时间序列模型

注意：上述学习AR模型的算法中假定数据源是平稳的，一旦我们看到完整的数据就要估计参数.

我们介绍SDAR算法在以下两方面来修改文［2］中的算法：

1）在线评估.即：一旦观测到数据就要更新参数.

2）折扣属性.介绍一种折扣参数r使统计指数随时间带有乘法因子（1－r）衰变.这使我们能够处理非平稳数据.

SDAR算法描述如下：

SDAR算法（0＜r＜1）

Step1 初始化

对每一时间t，SDAR算法更新依赖于折扣参数r（＞0）的带权平均值的参数估计值，r值越小表明SDEM算法对过去例子的影响越大.

我们记p t为SDAR算法在时间t更新的参数指定的方程（1）的概率密度函数.然后可得到一个概率密度序列：｛p t：t＝1，2，…｝.

2 得分

2.1 离群点检测

对x t的每一个输入值，我们由下面的公式计算得分：

方程（3）左边表示与概率密度函数p t－1相关的x t的预测［3］损失，我们称作对数损失.从信息理论的角度，对数损失可以被看作代码长度在数据是根据概率密度p t－1生成的假定下把x t编码成二进制序列的代码长度.

我们也可以定义分数为x t前后间的统计偏离.

这里p（＊），q（＊）是概率密度函数.

直觉地，分数测量了概率密度函数在从x t中学习后从p t－1移动了多少.

注意：x t分数越高表明x t更有可能是离群点.

2.2 变化点检测

设T是一个正的常量，｛x t｝是一数据序列，我们就像T－平均分数｛Score（x i）：i＝t－T＋1，…，t｝定义y t为：

这里Score（x i）根据（3）或（4）计算，然后我们获得一个时间序列｛y t：t＝1，2，…｝.

为了表示时间序列｛y t｝我们用AR模型，再用SDAR算法来构建由AR模型决定的概率密度函数的一个序列，记为｛qt：t＝1，2，…｝.然后给出T′，如方程（3）（对数损失）定义t时刻的T′平均分如下：

或者我们可以就像方程（8）那样用下面的分数：

这里d是测量前面部分两个概率密度函数间区别的函数.

因此我们能够在同样范例中同一学习算法的基础上处理离群点检测和变化点检测.这给出了这两个问题间很强的联系.

注意：Score（t）越高表明时间点t更有可能是变化点.

在方程（9）中，在T是小的情况下，离群点和变化点能在它们一出现就立即被检测，可是它们很难相互区分.在T是大的情况下，导致了探测变化点的时间耽搁，可是，离群点被过滤，只有变化点被准确检测.

3 实验结果

3.1 仿真

我们用两种数据集由数字模拟评估我们的方法.第一类数据集是一个数据序列使得变化点间每一个数据都根据下面的AR模型抽取：

这里εt是具有均值0和方差1的高斯随机变量.该数据集由10 000个记录组成.变化点在时间x×10 000（x＝1，2，…，9）.记x－th和（x－1）－th变化点的变化量为Δ（x），称为x处变化大小.在这种情况下设Δ（x）＝x.检测大些的x的变化点要容易些.

我们测试了数据建模和得分的两种组合.在第一种组合（称为SDEM1）中，我们为数据建模用独立模型（具有两个组成的有限混合），为得分用k＝2的AR模型.在第二种组合（称为SDAR1）中，我们为数据建模用k＝2的AR模型，为得分用k＝2的AR模型.这里我们用对数损失作为分数，SDAR和SDEM算法中的参数是r＝0.005.就像在方程（5）和（6）中一样我们为计算得分令T＝5，T′＝5.我们可以看到SDAR1检测变化点与SDEM1一样好，但SDAR1给出的分数比SDEM1更准确地反映了变化程度.

第二类数据集是一数据序列使得变化点间的每一个数据都是根据AR模型抽取.方差和均值都随着时间改变.变化点在时刻x×10 000（x＝1，2，…，9），标准偏差定义为0.1／（0.01＋time／10 000）我们记xth.

变化点的变化大小与标准偏差的比为R（x），称为改变信噪比.在这个数据集中，我们设R（x）≈x（x＝1，2，…，9）我们观察到SDAR1能够准确地探测变化点尽管方差随时间改变.

接下来，我们检查了错误警率和SDAR1的查全率，错误警率定义为非变化点被定义为变化点的百分比，查全率定义为准确检测到的变化点与应该被检测到的变化点的总数比.我们准备了具有变化的信噪比的三个数据集.每个数据集由AR模型（8）产生100 000个记录.对每个数据集，变化点在时刻x×1 000（x＝1，2，…，9）发生.三个数据集对每个变化点x的信噪比分别为R（x）＝20，10，5.如果一个检测到的变化点位于正确的变化点后50个记录内就认为检测是正确的.

3.2 真实数据实验

我们用TOPIX（股票价格指数）数据来看我们的变化点探测方法对实际问题效果如何.

我们用k＝4的AR模型来建模，k＝4的AR模型来计算得分.设x t是最原始的时间序列数据，y t＝x t－x t－1，我们处理二维数据（x t，y t）.我们标示这种策略为SDAR2.这里我们用对数损失作为分数，SDAR算法中用的打折参数为r＝0.005，如（5）和（6）中那样计算得分令T＝5，T′＝5.高分的时间点表示指数发生了重要变化的点.我们观察到SDAR能够探测指数的真正的重要变化.所有重要点都被准确探测到.这表明我们的方法能够发现指数中有意义的变化点.

4 结束语

本文提出了检测来自非平稳时间序列的离群点和变化点的一个框架.该框架由两部分组成：数据建模和计算得分.在数据建模部分，我们逐步获得一个数据序列的概率密度函数.具体来说，在文中我们采用了AR模型，并为AR模型的在线折扣学习引入了SDAR算法.SDAR算法的特点在于它的打折属性：过去数据的效果逐渐被打折.这使得我们能够处理非平稳数据.在计算得分部分我们在学习模型的基础上给每个数据或每个时间点一个分数.具体来说减少了变化点检测到来自移动平均分数的离群点检测的问题.因此我们能够用在同一个范式的同一个学习算法来处理这两个问题.这给出了离群点检测和变化点检测的一个统一观点.

［1］Hamiltion J D.Time senes analysis［M］.New Jersey：Princeton University Press，2000：26-42

［2］Hawkins D.Identification of outliers［M］.London：Chapman and Hall，1980

［3］Trevor Hastie，Robert Tibshirani，Jerome Friedman.统计学习基础——数据挖掘、推理与预测［M］.范 明，译.北京：电子工业出版社，2004

［4］黄 超.基于特征分析的金融时间序列挖掘若干关键问题研究［D］.上海：复旦大学，2005

［5］Enke D，Thawornwong S.The use of data mining and neural networks for forecasting stock market returns［J］.Expert systems with applications，2005，18（29）：201-205

［6］David West.Neural network credit scoring models［J］.Computers Operation Research，2000，27（11-12）：1 131-1 152

A Unifying Framework for Detecting Outliers and Change Points from Non-Stationary Time Series Data

Liu li1He Xianping2Yuan Wenliang1
（1.Department of Mathematics and Computer，Chizhou College，Chizhou 247000；2.Information and Mathematical college of Yangtze University，Jingzhou 434023，China）

We present a unifying framework for dealing with outlier and change point on the basis of the theory of on-line learning of non-stationary time series.In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm，which can track the changing data source adaptively by forgetting the effect of past data gradually.Then the score for any given data is calculated to measure its deviation from the learned model，with a higher score indicating a high possibility of being an outlier.Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model.Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data，and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.

outlier；change point；non-stationary time series；on-line learning

王映苗】

1672-2027（2011）03-0005-04

O212.1

A

2011-03-15

国家自然科学基金项目（60873021／F0201）.

刘 利（1981-），女，湖北天门人，硕士，池州学院数学计算机系讲师，主要从事概率与数理统计的研究.