一种无限长时间序列的分段线性拟合算法

1、Vol.38 No.2F4> 2010第2期2010年2月电 子学 报ACTA ELECTRONICA SINICA一种无限长时间序列的分段线性拟合算法闫秋艳夏士雄(中国矿业大学计算机科学与技术学院，江苏徐州221116)摘 S:本文提岀了一种无限长时间序列的分段线性拟合(Infinite Tune Seri«. Kecewice Linear Fitting,简称 皿一 PLF)算法,该算法根据关键点保持时间段的统计特性，确定选择关键点的区间范的;若极值点的保持时间段不在区间 范圈，则根据包含极值点的连续三个时间数据之间的夹角与筛选角度之间的关系判断该极值点成为关键点的可能

2、性实验表明.fTS.PLF算法的执行不依赖于时间序列长度及领域知识可以有效识别关键点并可根据数据压编率的 变化实现H适应拟合.关笛词：时何序列；分段线性拟合；压缩率中图分类号：Trail.13文献标识码：A 文蜜编号：0372-2112 (2010) 02-04434)6An Piecewise Linear Fitting Algorithm for Infinite Time SeriesYAM Qiu-yan,XlA Shi-xiong(77 Sduxl of QjnpuUr Scknoe and Technology. China t'nomtfy <jf Mining

3、Ttdmolagy. XuJwu. Jianpu 221116, Ouwi)Abstract： In order to resolving the problem of dependir on the length of time series and domain knowledge of traditionaJ PLF algorithm,we poposed a Piecewise Linear Htting algorithm for Infinite Time Series (ITS. PLF).To detomine the interval of Key Points selec

4、ting.the statistical anributes of mainlining time of these Key Points was considered If the maintaining time of a Extreme Point beyond the selection interval.the relation between the threshold angle and the anc of thnx consecutive data points containing tte Extreme Point was selected to determine wh

5、ether the Extreme ftjim was a Key Point or not.The experimental results show that ITS_ PLF algorithm does not depend on the let堆th of time series and domain knowledge,can effectively identify the Key Poiitt and adaptively Ht the tune series according to (he changing of the data compression ratio.Key

6、 words： tune series；piecewise linear fitting;compression ratio亠关于时间序列分段线住拟合算法的研究自论文1 513以来得到了广泛关注叫这种简单虫观的线性拟合Vol.38 No.2F4> 2010收回H 期:2009816基金项目：诫家自然科学M(No.50674086);中国矿业大学青年科研基金(No.2008AM1)时间序列的分段线性拟合(Piecewise Linear Fitting 简祢PLF)是时间序列的模式表示方法中研究最早和域 多的方法之一PLF是指用K条首尾相邻的线段近似表 示一条长度为L的时间序列在时间序列的

7、PLF方法中，线段的数目决定了对原 始序列的近似粒度线段越多，线段的平均长度就越短. 反映了时间序列的短期波动情况;线段越少线段的平 均长度就越长反映了时间序列的中长期趟势，通常 用数据的压缩率来表征这个参数这里的压缩率为从 数据序列中删除的数据点所占的比例如80%的压缩 率即为选择20%个数据点并刪除剩余的80%一种好 的时间序列的模式表示方法必须能够准确识别噪音数 据，并对噪音数据进行有效过滤,从而保证较高的数据 压缩率.表示方法采用首尾相邻的一系列线段近似表示时间序 列圧缩原始序列换取更小的存储和计算代价;保留时 间序列主要形态的同时去除了细节干扰更能反映时间 序列的变化模式通过对已有的

8、PLE算法进行分析，发 现这些PLF算法存在两个缺点：(1) 极值点选择的阈值依赖于相关的领域知识不 同的时间序列选择的阈值不同，因此算法不具有普遍的 适用性；(2) 极值点选择的阈值依赖于时间序列的长度L. 当乙为无穷大时,传统的PLF算法就不再适用.为解决上述问题本文走出了一种无限长时间序列 的分段线性拟合算法(Infinite Time Series- Becewice Linear Rtting.简称ITS- PLF算法)该算法根据已有关键点保持 时间段的统计待性，判断极值点选择的区间范围;若某 第2期何秋艳:一种无限长时间序列的分段线性拟合算法447点的保持时间段不右区间范围,选择包

9、含极值点的连 续三个数据点并根据三点构成的夹角与筛选角度之 间的关系判断其成为关键点的可能性，从而解决了 PLF 算法依赖于时间序列长度£及领域知识的问题实验 表明，rrsPLK算法的执行不依赖于厶及领域知识可 以有效识别关键点并可根据数据压编率的变化实现 自适应拟合.2相关工作本节对三种主要的时间序列分段线性拟合算法 (Segmentation 4, FTSegmentation和 KPSmemation) 进行比较分析说明现有PLF算法存在的问題和不足. 2.1符号说明定义本文使用的一些符号如下：(1) r=(刼 “1 ),(%#),(, /.)>(o< i <

10、00)：采样时间间隔相同的时间序列其中(曲*)表 示采样时间©时刻的数值为禺；(2) X 二(f宀)， & (切鉤)，Xs ( 八) ->,0<：< 8：将经过归一化处理后用査角坐标系 表示的点序列横坐冻为时间轴纵坐标为数值轴；(3) 也易I：表示时间序列中X心4)和畑 勺)在坐标平面内的欧氏距离；(4) EP(ExtremePoini)：极值点理的单调性在极值 点发生改变；KP(IPoint)：关键点，满足筛选条件的极值点；(6) KPS= <炉“.闵>：关键点集(7) a0:筛选角度2.2相关算法比较本文选取 Quarterly S&

11、P 500 index, 1900 - 1996. Source： Makridakist Wheelwright and Hyndman (1998)的 前100条数据对三种算法的拟合效果进行说明：(1) 极值点拟合法(IPSegmenlation).该算法利用序 列数据的单调变化屈性识别极值点疗,通过依次连接 EP点实现序列的分段线性拟合这种拟合算法尽管操 作简单运算效率高，较好地保留了原始时间序列的变 化模式但不能有效地去除噪音过多地保闕了细节变 化降低门玉缩率.(2) 特征点拟合法(FPSegmentalion).可以看作是极 值点拟合法的改进算法其实现思路为:选择原始序列 中对序列形

12、态影响最大的点作为特征点(Featu代 Pbim)，通过依次连接这些特征点实现序列的线段化特 征点需要同时满足以下条件:该数据点必须是序列 的极值点;该极值点保持极值的时间段(即该点与前 后极值点的时间段)与该序列长度的比值必须大于某 个阈值CJPSegmenUtion的优点是:通过阈值C对转折 点变化幅度的控制，可以较好地过滤变化短暂的噪音 数据;缺点是:由于限定了极值点的变化幅度对于变 化时长小于C的转折点厠无法有效识别，如图1(选取 C = 0.04,XI6和X32之间的点)因为保持极值的时间段 与L的比值小于0.04则这些数据被认为是噪音数据 而删除;但同时，对于短暂变化的尖峰数据，则

13、有可能 被认为是噪音数据而被忽略，比较图1和图2,X60点保 持极值的时间段与厶的比值= = 0.03,在C = 0.03 时为一特征点，但在C = 0.04时该点被认为是噪音数 据被忽略从分析中可知阈值C是待征点判断的影响 因子，其取值和领域知识、序列长度以及用户关注角度 有关，因此不同的C值会得到不同的拟合结果直接彬 响拟合的质吊；同时，当时间序列的氏度L为无穷大 时，C为无穷小则FPSegmentation算法不再适用.图 I FPSegmcntition算法00.04(3) 关键点拟合法(KPSegmena如.该算法提出: 包含极值点&的三个数据点构成的最小序列模式 总|也必“

14、中.如果三点连线形成的夹角越小,则中 间点Xt为关键点的可能性越大为便于进行在线运算, 提出了基于三角形中线距离的关键转折点选择算法 (IKP算法)将计算三点夹角转换为计算距离，若补节3 >“(対为极值 点纵坐标上>0,为自定义的单调序列中线距离阈值). KPSegnrntation 算法采用 FPSepnenlalion 算法和 IKP 算法 保存数据序列中的特征点与突变序列中的关镀点，然 后利用特征点保持时间段阈值C过滤数据序列中的噪 音干扰利用关键点发现短暂变化的尖峰数据其划分 效果如图3为方便计算，取扎.|儿,心.1的筛选夹角 为45SC = 0.03. KPSsgment

15、ation算法在取的适当时. 可以部分地发现时间序列中的关键点如图3中点XII 和X68保持极值的时间段与乙的比值为0.02,在图2 中不長待征点但运用KPSegmenta!ion算法其包含极值 点的夹角小于筛选角度，因此成为关键点存在的问 题:因为该算法在判新关键点时基于Flgntation的 距离阈值C过滤噪音数据也不可避免地遗传了 FPSegmentation算法的所右缺点且e的取值依赖于领 域知识.图 3 KPSegmcoStion算法C=O03,4F综匕，尽管IPSegmentaion算法的序列拟合效果较 好但无法有效过滤噪音和细节干扰，压缩率较低; 叫nentaion算法在较麻压缩

16、率的悄况下仍能较好地 过滤噪音保持原数务序列的形态但该算法无法及时 定位突变状态的起点和终点也不能拟合原始序列中 的尖峰状态;KPTntation算法则在较高压缩率的情 况下过滤了细节干扰能较好地线性拟合原始序列，但 该算法过分依锻两个经验闕值对无线大时间序列的 拟合设置了较大障碍基于以上分析本文提出一种无 限长时间序列的分段线性拟合(Infinite Time Series Becewice Linear Fitting,简称 ITS. PLF)耳法该算法可以 不依赖于领域知识，并在时间序列长度为无穷大时准 确识别噪音数据并保证较岛的数据压缩率.3算法思想圣于以上分析可知，极tf点X、成为关

17、镀点(KP)的 条件为：条件1心保持极值的时间段与该序列长度的比 值必须大于某个阈值C;条件2若条件1不满足则包含扎的最小序列 模式X-“人，人“中三点连线形成的夹角小与筛选 角度a°为了方便对极值点进行判断得到如下定理1-3： 定理1设时间序列X长度令表示Q点 保持极值的时间段，则满足的正态分布, 其中“二+ S沙,n为n .IV n - 1 i.i关键点集础中元素的个数.由中心极限定理任总随机事件在样本数趟于无 穷时随机变墩均脱从的正态分布时间序列 本身是一个随机过程极值点保持极值的时间段Ac的 变化幅度是一个随机事件，因此Z在序列长度趋于无 穷时必满足正态分布.推论1设时间序列

18、的数推压缩率为p.由定理1 可得p的度昱公式：24>(x)-Ul-p(I)证明 若时间JT列的数据压缩率为p则被保留 的关键点占时间序列数据总和的比例应W 1 - p,即关 键点的存在概率应W1-P；同时由定理1可知某个数据被保留，则其极值点 保持时间段M満足的正态分布即被保留的 极值点的以戸为中心对称分布越靠近"存在的 概率越大反之概率越小因此，被保留的极值点的Z 应分布在-对,“ 的范圈内(代表偏离“的程 度)概率令丫表示该随机事件,则有：< y<p + pwip (2)因为中-N(0,l)则对式(2)变换后可得即 20(x)-ll-p 得证.例如，要得到大于8

19、0怆的数据压缩率，则由式(1) 得：2e(£lw022©(Jwl2 e(%)w06査表得z = 0.25.即若极值点X.为关键点，则该点的 »应分布在“ -025"“ +025d)范围内.推论1得出了通过预先设定的数据压缩率确定选 择关键点区间范旳的方法.定理2若扎不満足定理1則2|忙号LI曲殉“I - I tga°设为筛选角度且|却.1 刼| M丨刼-刼1| )是 儿为关键点的充分条件.证明 以图4为例我们注意到在图4所示的角 度变化中由于时间序列 guz是等间隔的时 间点因此乂山卫三点的取值只能够在与时间轴 垂苴的三条虫线上（图4中的厶厶）

20、,若X、点固定. 比较IXi-Xi.,1和1珀广叩的大小取其中较大者（设 较大者的端点为人“）;通过条水平线，与直 线厶交于点Pi.Khd）,与直线心交于Pg 珀J,则一定存在么赵证略）, 因此，只需要对ZPmXXm进行考察，若ZP-XXm > a。则儿点一定不是极值点令ZPi“ = 20 tg= |曲.I |（ I Xi 1为两点纵坐标的差值）, 妝。=1-诜6,因此当定理1不満足时,&为极值点 必满足召g詁;< tgao,反之不成立,充分性得证.I禺禺“1-1图4序列a兀兀,何的夹角关系定理3若人不满足定理1, /I*.牛斗$ a1I xi*l " xi tg

21、（®0）- u "斗tga°且W I 足X）为夭握*I 珀1 珀 +<«（%）点的充要条件.证明如图4,当*争即詁严% 2| 珀禺“| -1时，还必须要求ZXiX/ww®则Zxx/wO Wa°。令 0二 ZXi.|X尢 9I + tg(a0)tg()(3)电（a。）二tg（e）城a°）丨斗“-殉丨勺53"如占11 毛丨 tgCa。) - 1证毕I - Xi + tg(a0)4算法步骤输入:时间序列 F3 （X| «1）.（ U2）» （Xiut）f （*.A）,0<i< 8,筛

22、选夹角a°,预设数据压缩 率p输出:关键点集合KPS =KPwWstepl根据推论1 由p计算系数*step2 初始化KPi = Xj（t|t%|）f/z = l,a = 0;step3从启开始判析时间序列的单调性,获得包 含三个极值点儿7（«"曲*）儿（切肴）人"（如“ 珀.）的局部时间序列X =Xi十. &.,待考察的极值点为人仏,曲）,包含该点的最短 时间序列为X必必“$血皿 计算点儿保待极值的时间段若+ mh则X.足关键点将Xi点并人集合 眈对下一个极值点进行判断否则继续；stepS 计算 max（|, |轧广曲| ），设返回 X：. （

23、/ j;step6若（I工笔I如则禺一定不足| 御毛 11 -1关键点，返回&ep4对下一个极值点进行判断否则继 续；I习“ 曲I诫弘）I珀广斗丨+tg（a。），则扎一定不是关键点返冋亦只对下一个极值点进行判 断否则继续;stepS将扎点并入集合储,更新区间“巾" +灯;返回或禅对下一个极值点进行判断.5实验结果及分析 5.1实验环境及实验数据本实验的运行环境为CPU2.51hz.2G内存.160C硬 盘淼作系统为WindowsXP,开发工具为Visual C + + 考虑到序列形态（振幅及角度）变化对数据压缩率 的形响，实验选取形态变牝较大和形态变化均匀的时 间序列1、2，

24、预设筛选夹角a0及数据压缩率p,运用 ITS.PLF算法进行分段线性拟合实验结果表明.rrs. PLF算法可以通过对比实际获得的数据压缩率与预设 数据圧缩率，自适应地调整筛选夹角a0及关键点保持 时间段的选择区间从而使rrs. PLF算法不依赖于任何 参数及领域知识，使rrs fu算法适用于无限长时间序 列的线性拟合，具体拟合结果和分析见5.2节实验数 据如下：（1） Quarterly S&P 500 index, 1900 - 1996. Source： Makridakis, Wheelmight and Hyndman （1998） .9 * 17b. DAT449电 子 学

25、报2010 年(2)Simulated series Z( T) =0.9. Z( T-1) + A( T) * /V(0, 1). Source： 0. D. Andereon (1976). ANDERSONS DAT5.2实验结果实验1时间序列1的形态变化较大考察不同的 筛选角度对拟合效果及数据压缩率的形响为了图像 的清晰选取时间序列1前100条数据进行拟合预设 筛选角度a0 = 45%数据压缩率为08由推论1得二 025拟合效果如图5图5时间序列1, TTS_PLF算法在at-45°时的拟合效果 将图5与图3进行比较，二者均能较好反映时间序 列影态变化的趋势.KPSpgrnp

26、mmion算法的数据压缩率1 = 0.82,ITS. PLF算法的数据压缩率为I-磊二 0.87. K间(“-0.25几“+0.25小的变化情况如表1,当 筛选角度相同时,KPSegmentation算法的间值C = 0.03, ITS.PLF 算法的/严3,盒=003,与 KPSmentaticm 算 法的阈值一致但由于rrs-Pir算法是一个在线算法, 因此二者只能具有相似的数据压缩率.«1 rrS.PLF算法在a甥时d,区间的变化債况坐标点At.Pafi -0.25c*0.25aJ1101J532.83(2.79,4.2l)-3.422.672.082.48,3.52-3,32

27、2.J1.73【2.07.2.93 J2.242.Si.61»3J432.4(2.4,3.6w3,3从以上分析也可看岀a0 = 45°时rrS.PLF算法的 压缩率为0.87与预期的压缩率匕08相近说明筛选角 度选择的较为合适.改变筛选角发ao = 30ITS.PLF算法的拟合效果 如图6图中可以看出，对于时间序列1随着筛选角度 的滅小.FTS.PLF算法的数据压缩率明显增加，达到 092但此时拟合的&果欠佳，如X60点小心二3,而此 时才会成为关键点，同时X60所在的夹角大于30因此该点没有被保留分析原因，在a0 = 3(F时 rrS.PLF算法

28、的压缩率0 92与预期的压缩率-0.8相 差较大，说明选择的筛选角度不合适可见在序列形 态变化较大时.rrs.PLFM法可将实际数据压缩率与预 期数据压缩率相对照判断筛选角度选取的是否合适. 从而去除了算法对于初始参数ao的依赖性.Quarterly S&P 500 indexj900-1996( 1-100)图6时阿序列1. ITS.PLF算法在a30。时的拟合效果 «2 FR.PLFW法在时山,区闽的变化債况坐标点Pa严-0.25a.4-0.25aX110(M)Xn21.50.71ri.32.1.68Ul.llXn42.31.5lw(2,2心32.51.

29、292.18,2.82 *2.2X.42.81.9813.3.3 w 3,3实验2时间序列2的形态变化均匀考察此时不 同的筛选角度对拟合效果及数据圧缩率的影响预设 筛选角度a0 = «Ft数据压缩率08前50条数据的拟合 效果如图7在益点将筛选区间更新为1,3,此后基 本维持不变,数据压缩率为11 = 0.28.将筛选角度 a。调整为a。= 15°,发现数据的压缩率维持在0.28附近 基本保持不变，从图7可看岀，该时间序列数据的振幅和角度变化比较均匀的分布区间为U3.因此大 部分数据都符合关键点的标准而被保留这种结果也 同时骏证了定理1确定关键点选择区间的有效性在这 种悄况

30、下如果需要继续对数据进行压缩，则可动态调 整区何至2,3,拟合效果如图8数据压缩率为，黑 = 0.66.可见，对于形态变化均匀的时间序列，筛选角度 无法有效判断关键点此时.ns. PLF算法可以随着时 间数据的不断到来根据以往实际获得的数据压缩率 动态调整关键点选择区间，实现对未来数据压缩率的 控制从而实现了在无任何领域知识的条件下对无限 长时间序列的自适应拟合.S8时间序列2,50-100条数馆的械合效杲，压细車0666结束语本文在对现有时间序列分段线性拟合(PIF)算法 进行分析的基础上总结现有算法在对无限长时间序 列进行拟合时的不足和不适用性提出了在时间序列 无限长时判定某极值点为关键点

31、的三条定理并在此 基础上提出了 ITS. PLF算法实验表明在不同变化形 态的时间序列上rrSPLF算法的性能不依赖于涉列长 度和领域知识,可以有效识别关键点，并可根据数据压 缩率的变化实现自适应拟合.參考文歆：1 T P»vlxfisvS L Horowitz .Segmentation of plane curvcs J. IEEE Transactions on Carpiters.1974,23(8):860- 870.2 杜奕时间序列挖掘相关算法研究及应用D合肥：中国 科学技术大学博士论文20073 Kevin B Pran. Eugene Fink. Search for

32、 patterns in compressed time seriesL J. Intematioml Journal of Image and Graphics. 2002.2(1):89- 106 Sanghyun Parte, Sang-wook Kim, Wesley W.Chu. Segment - based approach for subsequence searches in sequence databases Aj. Proceedings of the 16(h ACM Symposium on Applied ConutingtC. New YoA ACM Press

33、,2000.248 - 252. Sanghyun Part.Dongwon Lee.Wesley W Chu.Fast retrieval of similar subsequences in long sequence databases A Proceedings of the 1999 Workshop on Knowledge and Data Engineering ExchangeCJ.Washington: IEEE.Computer Society, 1999 60-67 6 肖解,胡运发茎于分段时间弯曲距离的时间序列挖#8 J计算机研究与发展.2005.42(1) :72-

34、78Hyndman, R J(n d). Tine Series Data Library (DB/OL), hnp：/www. robhyndman info/TSDL,2009-5.#电 子 学 报2010 年#电 子 学 报2010 年作者简介:#电 子 学 报2010 年耳秋艳 女博七研克生主嬰研究方向为 数据漁技术时间序列处理败据挖讯.E-rail： yanqyl±tt男博七生辱师枚授主要研究方 向为数字化矿山耆能信息处理.rnHHSiBLU WAHFANGDATA一种无限长时间序列的分段线性拟合算法作者：闫秋艳， 夏士雄，YAN Qiu-yan, XIA Shi-xiong作者单位：中国矿业大学计