时间序列相似性研究
- 格式：pdf
- 大小：324.87 KB
- 文档页数：8
http://www.paper.edu.cn
- 1 -时间序列相似性研究
张璐
辽宁工程技术大学理学院，辽宁阜新（123000）
E-mail:zhanglu85517@sohu.com
摘 要：时间序列作为一种数据形式，广泛存在于各种商业、医学、工程、自然科学和社会
科学等数据库中。本文通过对时间序列数据挖掘的概述，引出时间序列相似分析研究方法，
同时在各种相似性定义研究的基础上，说明了欧氏几何距离作为时间序列相似性度量标准的
不足之处，总结出了一种较为统一的时间序列相似性概念体系；并利用股票数据讨论了
DFT(基于正交变换), PAA(基于形态)两种具有代表性的现代时间序列相似性分析方法，说明
其在预测和数据处理算法复杂度上的应用，同时对基于这两种思路的相似性研究的主要方法
做出综合比较，总结出好的相似性研究方法的共有特征；就算法的准确度，本文提出了基于
PLR的算法改进。
关键词：时间序列；相似性；分段线性
1．引言
现代的时间序列分析技术主要是从距离、频域、序列变换、序列外形特征提取等几个方
面来对时间序列进行研究。目前，很多研究人员将时间序列相似性定义为高维空间中的距离，
如欧氏几何距离。由于离散傅立叶变换[1]（DFT, Discrete Fourier Transform）具有保持欧氏几
何距离不变的特点，因而只保留DFT的头几个系数，就可以实现数据的高度压缩和快速比
较。但DFT方法平滑了原序列中局部极大值和局部极小值，因而导致许多重要信息的丢失，
而且对非平稳序列也不适用。自从DFT被Agrawal最早应用于时序数据相似性搜索后，又
有其他一些论文相继提出了DFT的许多扩展和改进方法[6]，但核心思想并没有什么变化。
Chan等人提出Haar小波变换方法，试图对DFT方法进行改进，但类似的问题仍然存在。
Last等人提出采用关键特征（如斜率和信噪比）表征原序列[9]，Guralnik等人采用一个字符
表来压缩序列，都得到了高压缩率，但对序列的描述能力有限，因而在其它许多领域都不适
用。Korn等人提出的奇异值分解[2](SVD)法是一种完全不同的方法，但其计算量相当大，而
且数据动态变化后需要重新计算。Keogh等人先后又提出的分段累积近似法[3]（PAA,
Piecewise Aggregate Approximatio），分段线性分割（PLR, Piecewise Linear Representation），
和适应性分段常数近似法（APCA, Adaptive Piecewise Constant Approximation）等分段方法，
以及Perng等人提出的界标模型（Landmark Model）。与此同时，还有许多相应的其他时间
序列分析方法，这些表示方法或是以上各种方法思路的外延，或是从其他角度试图对时间序
列相似性分析进行研究，这些方法各有所长，为时间序列相似性研究提供了诸多可以借鉴与
参考的方向。本文对已有的现代时间序列相似性研究主要方法作了系统概述，并利用股票数
据分析了基于正交变换的算法与基于形态的算法的优缺点，同时对相似性方法作出了实例应
用，并且就分段线性表示算法的准确度，本文总结并提出了基于PLR的改进算法。
2．基于PLR算法的改进
2.1 时间序列分段算法
所有分段算法都需要一种度量来判别如何进行分段计算[4]，目前使用最广泛的是三种拟
合误差：(1)累计残差；(2)平均残差；(3)最大偏差。
设S是长度为L的时间序列 http://www.paper.edu.cn
- 2 - {}
12,,...,
LSyyy= (2-1)
其对应K个分段的PLR模型为
()(){}
KKRKLRLPtyytyyS,,,...,,,
111= (2-2)
令a与b分别是PLR模型中第i个分段开始时间和结束时间，即
1
1+=
−ita (2-3)
itb= (2-4)
S[a:b]为是S从a到b的一个子序列，记为
[]:Sab＝{}
baayyy,...,,
1+ (2-5)
其中，Lba≤≤≤1。设对应第p个分段拟合数据表示为：
[]{}
''
1'',...,,:
baaPyyybaS
+= (2-6)
有
()
abyy
buyyiLiR
iLua−−
−+=
+' (2-7)
对应拟合误差表示为
[]:Eab={}{}
''
11'
1,...,,,...,,
bbaaaabaayyyyyyeee−−−=
+++ (2-8)
对分段直线各个误差定义如下，AE—累积残差，ME—平均残差，DE—最大偏差
AE=∑
=b
auue2
(2-9)
ME=
1+−abAE
(2-10)
DE=
u
ueMax (2-11)
2.2 改进算法
目前的PLR算法对原始数据都采用一种的误差阀值，而时间序列在不同的地方具有不
一样的线性度，对时间趋势表示而言，分段的结果不能令人满意[5]。主要有两类问题：一是
采用累积残差作为分段标准的算法不能有效识别短时间内数据相对较大的趋势变换；二是采
用平均误差的分段算法对长时间相对拟合较好数据的趋势分界(拐点)识别存在现较大偏差。
累积残差是分段序列中各个点拟合误差的直接累积，对各点与拟合直线的离散程度并不
敏感，因此对短时间内较大波动的子序列数据动态性刻划比较差。如图2-1所示，从75到
100这一部分，是一个典型的短时大波动数据，显然依照目前的划分，覆盖了原始数据的一
个趋势变换。而对于平均残差ME，当分段子序列比较长的时候，即ba−比较大，ME的
计算式中由于分母变大，使得对累积残差AE的敏感度降低。这样，会造成趋势分界点误差
增大。如图2-2所示，由于45到75的子序列比较长，造成划分时间与实际趋势变化时间存
在比较大的误差。 http://www.paper.edu.cn
- 3 -
图2-1 累积残差分段效果图
Fig.2-1 The effect map of cumulative residualaverage residual subparagraph
图2-2 平均残差分段效果
Fig.2-2 The effect map of subparagraph
目前的分段线性算法对时间序列趋势表示都存在着各自的缺陷，对原始序列采用基于累
积残差的PLR算法进行分段，我们可以发现两个问题：
(1)过拟合：对于整个分段，由于累积残差的累积效应，使得线性度较好的一个区间被
划分成2段。
(2)欠拟合：由于累积残差对短时段大波动数据的不敏感造成的。
可以知道，如果可以识别基于累积残差法的每个分段的拟合程度，我们就能很容易的通
过对这些子序列的处理达到趋势表示所要求的准确刻划趋势拐点这一条件，比纠正平均残差
的趋势分界点要容易的多。因此我们提出用子序列线性度来衡量数据拟合好坏，基于PLR
累积残差方法提出一种改进的分段算法。
2.3子序列线性度
对基于累积残差方法的分段，我们采用子序列线性度作为衡量子序列的拟合程度。线性
度越高，则拟合直线与原始数据越接近。假设[]:Sab各个点的拟合误差为[]:Eab＝
[]
baaeee,...,,
1+，而方差表示数据的离散程度，因此我们采用E的方差作为子序列线性度lm
的度量，线性度越好，lm值越小。即
()2
11
∑
=−
+−=b
auuEe
ablm (2-12)
我们将式(2-12)展开变形如下： http://www.paper.edu.cn
- 4 - ()
∑
=+−
+−=b
auuuEEee
ablm222
11
(2-13)
⎟
⎠⎞
⎜
⎝⎛
+−
+−=∑∑∑
===b
aub
aub
auuuEeEe
ab222
11
(2-14)
222
11
EMEEe
abb
auu−=−
+−=∑
= (2-15) 式中，E表示[]:Eab的平均值。根据最小二乘法直线回归理论，有E=0，即有=MElm.
而且在基于累积残差的算法中，我们可以在累积残差计算的基础上，方便的实现平均残差的
计算。图2-3是图2-1、图2-2中6个分段直线对应的累积残差和平均残差。
图2-3 累积残差与平均残差对比
Fig.2-3 Comparison between cumulative residual and average residuals
可以发现，和累积残差相比，平均残差都可以很好的表示其产生的每个分段直线拟合的
好坏程度。在实际应用中，平均残差大小和时间序列值的测量度量等因素有很大的关系，要
根据该值大小来判断分段直线的拟合程度显然比较困难，因此我们提出相对平均残差概念，
用相对平均残差作为各个分段区间直线拟合程度的度量。假设时间序列S有K个分段，平
均误差为
{}
12,,,
KMEmememe="
则第i个分段的子序列线性度为
1i
iK
j
jKme
lm
me
=⋅
=
∑ （2-16）
图2-4是图2-1、图2-2中所示分段的相对平均残差示意图。由于相对平均残差避
免了平均残差的单位量纲，使得识别基于累积残差分段直线的拟合程度变得相对容易。例如，
设定超过1.5作为欠拟合，小于0.5的是过拟合。从图中可以发现，第五段的相对平均残差
达到2.5左右，处于欠拟合状态。而第三段相对平均残差不到0.5，处于过拟合状态。
图2-4 相对平均残差示意图
Fig.2-4 The map of relatiion to average residual
