点变化幅度的控制， 可以较好地过滤变化短暂的噪音 数据； 缺点是： 由于限定了极值点的变化幅度， 对于变 化时长小于 Ｃ的转折点则无法有效识别， 如图 １ （ 选取 ， 和Ｘ 之间的点） 因为保持极值的时间段 Ｃ ＝ ０ ０ ４ Ｘ １ ６ ３ ２ ， 则这些数据被认为是噪音数据 与 Ｌ的比值小于 ０ ０ ４ 而删除； 但同时， 对于短暂变化的尖峰数据， 则有可能 被认为是噪音数据而被忽略， 比较图 １ 和图 ２ ， 点保 Ｘ ６ ０ ３ 持极值的时间段与 Ｌ的比值 ＝ ， 在 Ｃ＝０ ＝０ ０ ３ ０ ３ １ ０ ０ 时为一特征点， 但在 Ｃ＝０ ０ ４时该点被认为是噪音数 从分析中可知， 阈值 Ｃ是特征点判断的影响 据被忽略 ． 因子， 其取值和领域知识、 序列长度以及用户关注角度 有关， 因此不同的 Ｃ值会得到不同的拟合结果， 直接影 响拟合的质量； 同时， 当 时间 序 列 的 长 度 Ｌ为 无 穷 大 则Ｆ 算法不再适用 ． 时， Ｃ为无穷小， Ｐ Ｓ ｅ ｇ ｍ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ
ቤተ መጻሕፍቲ ባይዱ２ １ 符号说明
定义本文使用的一些符号如下： （ ） 〈 （ ， ） ， …（ ， ） ， …（ …〉 （ １ Ｔ＝ ｘ ｔ ｘ ｔ ｘ ｔ ０ ＜ｉ １ １ ｉ ｉ ɕ， ɕ） ： 采样时间间隔相同的时间序列， 其中（ ， ） 表 ＜ɕ） ｘ ｔ ｉ ｉ 示采样时间 ｔ 时刻的数值为 ｘ ； ｉ ｉ （ ） （ ， ） ， … （ ， ） ， …Ｘ ２ Ｘ＝〈 Ｘ ｔ ｘ Ｘ ｘ ｔ ｘ １ １ １ ｉ ｔ ｉ ｉ ɕ（ ɕ， ɕ） …〉 ， 将 Ｔ经过归一化处理后用直角坐标系 ０ ＜ｉ ＜ɕ： 表示的点序列， 横坐标为时间轴， 纵坐标为数值轴； － Ｘ （ ）Ｘ ： 表示时间序列中 （ ， ） 和 Ｘ （ ， ３ Ｘ ｔ ｘ ｔ ｉ ｊ ｉ ｉ ｉ ｊ ｊ ） 在坐标平面内的欧氏距离； ｘ ｊ （ ） （ ） ： 极值点， ４ Ｅ Ｐ Ｅ ｘ ｔ ｒ ｅ ｍ ｅ Ｐ ｏ ｉ ｎ ｔ Ｔ的单调性在极值 点发生改变； ） （ ） ： 关键点， 满足筛选条件的极值点； （ ５ Ｋ Ｐ Ｋ ｅ ｙ Ｐ ｏ ｉ ｎ ｔ （ ） ， …， ： 关键点集 ６ Ｋ Ｐ Ｓ ＝＜Ｋ Ｐ Ｋ Ｐ １ ｎ＞ （ ） ： 筛选角度 ７ α０
２ 相关工作
本节 对三 种 主 要 的 时 间 序 列 分 段 线 性 拟 合 算 法
［ ］ ［ ］ ［ ］ ４ ６ ２ （ ， 和Ｋ ） Ｉ Ｐ Ｓ ｅ ｇ ｍ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ Ｆ Ｐ Ｓ ｅ ｇ ｍ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ Ｐ Ｓ ｅ ｇ ｍ ｅ ｎ ｔ ａ ｔ ｉ ｏ ｎ 进行比较分析， 说明现有 Ｐ 算法存在的问题和不足 ． Ｌ Ｆ
摘 要： 本文提出了一种无限长时间序列的分段线性拟合（ ， 简称 Ｉ Ｉ ｎ ｆ ｉ ｎ ｉ ｔ ｅ Ｔ ｉ ｍ ｅＳ ｅ ｒ ｉ ｅ ｓ ｉ ｅ ｃ ｅ ｗ ｉ ｃ ｅ Ｌ ｉ ｎ ｅ ａ ｒ Ｆ ｉ ｔ ｔ ｉ ｎ ｇ Ｔ Ｓ －Ｐ － ） 算法， 该算法根据关键点保持时间段的统计特性， 确定选择关键点的区间范围； 若极值点的保持时间段不在区间 Ｐ Ｌ Ｆ 范围， 则根据包含极值点的连续三个时间数据之间的夹角与筛选角度之间的关系， 判断该极值点成为关键点的可能 性． 实验表明， 算法的执行不依赖于时间序列长度及领域知识， 可以有效识别关键点， 并可根据数据压缩率的 Ｉ Ｔ Ｓ Ｌ Ｆ －Ｐ 变化实现自适应拟合 ． 关键词： 时间序列；分段线性拟合；压缩率 Ｔ Ｐ ３ １ １ １ ３ 文献标识码： Ａ 文章编号： ）０ ０ ３ ７ ２ ２ １ １ ２（ ２ ０ １ ０ ２ ０ ４ ４ ３ ０ ６ 中图分类号：
Ａ ｎＰ ｉ ｅ ｃ ｅ ｗ ｉ ｓ ｅＬ ｉ ｎ ｅ ａ ｒ Ｆ ｉ ｔ ｔ ｉ ｎ ｇＡ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｆ ｏ ｒ Ｉ ｎ ｆ ｉ ｎ ｉ ｔ ｅＴ ｉ ｍ ｅＳ ｅ ｒ ｉ ｅ ｓ
， Ｙ Ａ ＮＱ ｉ ｕ ｙ ａ ｎ Ｘ Ｉ ＡＳ ｈ ｉ ｘ ｉ ｏ ｎ ｇ
（ ， ， ， ， ） Ｔ ｈ ｅ Ｓ ｃ ｈ ｏ ｏ ｌ ｏ ｆ Ｃ ｏ ｍ ｐ ｕ ｔ ｅ ｒ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ａ ｎ ｄＴ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ Ｃ ｈ ｉ ｎ ａＵ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ｏ ｆ Ｍ ｉ ｎ ｉ ｎ ｇＴ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ Ｘ ｕ ｚ ｈ ｏ ｕ Ｊ ｉ ａ ｎ ｇ ｓ ｕ２ ２ １ １ １ ６ Ｃ ｈ ｉ ｎ ａ
： Ｉ Ａ ｂ ｓ ｔ ｒ ａ ｃ ｔ ｎｏ ｒ ｄ ｅ ｒ ｔ ｏｒ ｅ ｓ ｏ ｌ ｖ ｉ ｎ ｇｔ ｈ ｅ ｐ ｒ ｏ ｂ ｌ ｅ ｍｏ ｆ ｄ ｅ ｐ ｅ ｎ ｄ ｉ ｎ ｇｏ ｎｔ ｈ ｅｌ ｅ ｎ ｇ ｔ ｈｏ ｆ ｔ ｉ ｍ ｅｓ ｅ ｒ ｉ ｅ ｓ ａ ｎ ｄｄ ｏ ｍ ａ ｉ ｎｋ ｎ ｏ ｗ ｌ ｅ ｄ ｇ ｅｏ ｆ ｔ ｒ ａ ｄ ｉ ｔ ｉ ｏ ｎ ａ ｌ ， （ ） Ｐ Ｌ Ｆａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ ｗ ｅ ｐ ｒ ｏ ｐ ｏ ｓ ｅ ｄａ Ｐ ｉ ｅ ｃ ｅ ｗ ｉ ｓ ｅ Ｌ ｉ ｎ ｅ ａ ｒ Ｆ ｉ ｔ ｔ ｉ ｎ ｇａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｆ ｏ ｒ Ｉ ｎ ｆ ｉ ｎ ｉ ｔ ｅ Ｔ ｉ ｍ ｅ Ｓ ｅ ｒ ｉ ｅ ｓ Ｉ Ｔ Ｓ Ｌ Ｆ ． Ｔ ｏｄ ｅ ｔ ｅ ｒ ｍ ｉ ｎ ｅ ｔ ｈ ｅ ｉ ｎ ｔ ｅ ｒ ｖ ａ ｌ ｏ ｆ －Ｐ ， ｔ ｈ ｅ ｓ ｔ ａ ｔ ｉ ｓ ｔ ｉ ｃ ａ ｌ ａ ｔ ｔ ｒ ｉ ｂ ｕ ｔ ｅ ｓ ｏ ｆ ｍ ａ ｉ ｎ ｔ ａ ｉ ｎ ｉ ｎ ｇｔ ｉ ｍ ｅｏ ｆ ｔ ｈ ｅ ｓ ｅＫ ｅ ｙＰ ｏ ｉ ｎ ｔ ｓ ｗ ａ ｓ ｃ ｏ ｎ ｓ ｉ ｄ ｅ ｒ ｅ ｄ ． Ｉ ｆ ｔ ｈ ｅｍ ａ ｉ ｎ ｔ ａ ｉ ｎ ｉ ｎ ｇｔ ｉ ｍ ｅｏ ｆ ａ Ｋ ｅ ｙ Ｐ ｏ ｉ ｎ ｔ ｓ ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｎ ｇ ， Ｅ ｘ ｔ ｒ ｅ ｍ ｅ Ｐ ｏ ｉ ｎ ｔ ｂ ｅ ｙ ｏ ｎ ｄｔ ｈ ｅ ｓ ｅ ｌ ｅ ｃ ｔ ｉ ｏ ｎｉ ｎ ｔ ｅ ｒ ｖ ａ ｌ ｔ ｈ ｅ ｒ ｅ ｌ ａ ｔ ｉ ｏ ｎｂ ｅ ｔ ｗ ｅ ｅ ｎｔ ｈ ｅ ｔ ｈ ｒ ｅ ｓ ｈ ｏ ｌ ｄａ ｎ ｇ ｌ ｅ ａ ｎ ｄｔ ｈ ｅ ａ ｎ ｇ ｌ ｅ ｏ ｆ ｔ ｈ ｒ ｅ ｅｃ ｏ ｎ ｓ ｅ ｃ ｕ ｔ ｉ ｖ ｅｄ ａ ｔ ａｐ ｏ ｉ ｎ ｔ ｓ ｃ ｏ ｎ ｔ ａ ｉ ｎ ｉ ｎ ｇｔ ｈ ｅ Ｅ ｘ ｔ ｒ ｅ ｍ ｅ Ｐ ｏ ｉ ｎ ｔ ｗ ａ ｓ ｓ ｅ ｌ ｅ ｃ ｔ ｅ ｄ ｔ ｏ ｄ ｅ ｔ ｅ ｒ ｍ ｉ ｎ ｅ ｗ ｈ ｅ ｔ ｈ ｅ ｒ ｔ ｈ ｅ Ｅ ｘ ｔ ｒ ｅ ｍ ｅ Ｐ ｏ ｉ ｎ ｔ ｗ ａ ｓ ａ Ｋ ｅ ｙ Ｐ ｏ ｉ ｎ ｔ ｏ ｒ ｎ ｏ ｔ ． Ｔ ｈ ｅ ｅ ｘ ｐ ｅ ｒ ｉ ｍ ｅ ｎ ｔ ａ ｌ ｒ ｅ ｓ ｕ ｌ ｔ ｓ ， ｓ ｈ ｏ ｗｔ ｈ ａ ｔ Ｉ Ｔ Ｓ Ｌ Ｆａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍｄ ｏ ｅ ｓ ｎ ｏ ｔ ｄ ｅ ｐ ｅ ｎ ｄｏ ｎｔ ｈ ｅ ｌ ｅ ｎ ｇ ｔ ｈｏ ｆ ｔ ｉ ｍ ｅ ｓ ｅ ｒ ｉ ｅ ｓ ａ ｎ ｄｄ ｏ ｍ ａ ｉ ｎｋ ｎ ｏ ｗ ｌ ｅ ｄ ｇ ｅ ｃ ａ ｎｅ ｆ ｆ ｅ ｃ ｔ ｉ ｖ ｅ ｌ ｙｉ ｄ ｅ ｎ ｔ ｉ ｆ ｙｔ ｈ ｅ Ｋ ｅ ｙ －Ｐ Ｐ ｏ ｉ ｎ ｔ ａ ｎ ｄａ ｄ ａ ｐ ｔ ｉ ｖ ｅ ｌ ｙｆ ｉ ｔ ｔ ｈ ｅ ｔ ｉ ｍ ｅ ｓ ｅ ｒ ｉ ｅ ｓ ａ ｃ ｃ ｏ ｒ ｄ ｉ ｎ ｇｔ ｏｔ ｈ ｅ ｃ ｈ ａ ｎ ｇ ｉ ｎ ｇｏ ｆ ｔ ｈ ｅ ｄ ａ ｔ ａ ｃ ｏ ｍ ｐ ｒ ｅ ｓ ｓ ｉ ｏ ｎｒ ａ ｔ ｉ ｏ ． ： ｔ ； ； Ｋ ｅ ｙｗ ｏ ｒ ｄ ｓ ｉ ｍ ｅ ｓ ｅ ｒ ｉ ｅ ｓ ｐ ｉ ｅ ｃ ｅ ｗ ｉ ｓ ｅ ｌ ｉ ｎ ｅ ａ ｒ ｆ ｉ ｔ ｔ ｉ ｎ ｇ ｃ ｏ ｍ ｐ ｒ ｅ ｓ ｓ ｉ ｏ ｎｒ ａ ｔ ｉ ｏ
基金项目： 国家自然科学基金（ ） ； 中国矿业大学青年科研基金（ ） Ｎ ｏ ． ５ ０ ６ ７ ４ ０ ８ ６ Ｎ ｏ ． ２ ０ ０ ８ Ａ ０ ４ １
内容版权归作者所有
更多技术文章，论文请登录
４ ４ ４ 电 子 学 报 年 ２ ０ １ ０
点的保持时间段不在区间范围， 选择包含极值点的连 续三个数据点， 并根据三点构成的夹角与筛选角度之 间的关系判断其成为关键点的可能性， 从而解决了 Ｐ Ｌ Ｆ 算法依赖于时间序列长度 Ｌ及领域知识的问题 ． 实验 算法的执行不依赖于 Ｌ及领域知识， 可 表明， Ｉ Ｔ Ｓ Ｌ Ｆ －Ｐ 以有效识别关键点， 并可根据数据压缩率的变化实现 自适应拟合 ．
２ ２ 相关算法比较
本文 选 取 Ｑ ， ｕ ａ ｒ ｔ ｅ ｒ ｌ ｙＳ ＆ Ｐ５ ０ ０ｉ ｎ ｄ ｅ ｘ １ ９ ０ ０－１ ９ ９ ６ ． ［ ］ ７ ： ， ） 的 Ｓ ｏ ｕ ｒ ｃ ｅ Ｍ ａ ｋ ｒ ｉ ｄ ａ ｋ ｉ ｓ Ｗｈ ｅ ｅ ｌ ｗ ｒ ｉ ｇ ｈ ｔ ａ ｎ ｄＨ ｙ ｎ ｄ ｍ ａ ｎ（ １ ９ ９ ８ 前１ 条数据， 对三种算法的拟合效果进行说明： ０ ０
１ 引言
时间序列 的 分 段 线 性 拟 合 （ Ｐ ｉ ｅ ｃ ｅ ｗ ｉ ｓ ｅＬ ｉ ｎ ｅ ａ ｒ Ｆ ｉ ｔ ｔ ｉ ｎ ｇ 简称 Ｐ ） 是时间序列的模式表示方法中研究最早和最 Ｌ Ｆ 多的方法之一 ． 是指用 Ｋ条首尾相邻的线段近似表 Ｐ Ｌ Ｆ ］ １ 的时间序列［ 示一条长度为 Ｌ ． 在时间序列的 Ｐ 方法中， 线段的数目决定了对原 Ｌ Ｆ 始序列的近似粒度， 线段越多， 线段的平均长度就越短， 反映了时间序列的短期波动情况； 线段越少， 线段的平 ］ ２ 均长度就越长， 反映了时间序列的中长期趋势［ ， 通常 ［ ］ ３ 用数据的压缩率 来表征这个参数， 这里的压缩率为从 数据序列中删除的数据点所占的比例， 如８ ０ ％的压缩 率即为选择 ２ 一种好 ０ ％个数据点并删除剩余的 ８ ０ ％． 的时间序列的模式表示方法必须能够准确识别噪音数 据， 并对噪音数据进行有效过滤， 从而保证较高的数据 压缩率 ．