收稿日期: 2009唱11唱11; 修回日期: 2010唱01唱18 基金项目: 黑龙江省自然科学基金资助项目( F2007唱11) ;黑龙江省教育厅自然科学基金
资助项目(11521005)
作者简介:尚福华(1962唱) ,男,吉林延吉人,教授,博士,主要研究方向为人工智能、机器学习、数据挖掘、图像处理等;孙达辰(1976唱),男,黑龙
江鸡西人,硕士研究生,主要研究方向为人工智能及其应用( sdc061013@yahoo.com.cn).
基 于 时 间 序 列 趋 势 转 折 点 的 分 段 线 性 表 示
倡
尚福华, 孙达辰
(大庆石油学院 计算机与信息技术学院, 黑龙江 大庆 163318)
摘 要: 在充分利用时间序列时变特征的基础上,以有效地提取序列中的趋势和压缩原始数据为目标,提出了
基于时间序列趋势转折点的分段线性表示方法。 该方法在有效地提取序列中的趋势和压缩原始数据的同时,能
够随着时间序列长度的增长对序列进行划分,具有高效、实现方法简便、效果直观的优点,对于不同领域的数据
适应性良好。
关键词: 时间序列; 分段线性表示; 趋势转折点; 拟合误差
中图分类号: TP391 文献标志码: A 文章编号: 1001唱3695(2010)06唱2075唱03
doi:10.3969 /j.issn.1001唱3695.2010.06.022
PLR based on time series tendency turning point
SHANG Fu唱hua, SUN Da唱chen
( School of Computer & Information Technology, Daqing Petroleum University, Daqing Heilongjiang 163318, China)
Abstract: Based on time series time唱variable characteristic, aimed at extracting the tendency in the time series and compres唱
sing primary data, introduced a method named PLR based on time series tendency turning point.This method is good at ex唱
tracting the tendency in the series and compressing primary data, at the same time, it can partition time series as the series
growing and has the merit of easily being carried out, remarkable result and suitable ability for the data from different field.
Key words: time series; PLR(piecewise linear representation); tendency turning point; fitting error
时间序列是按时间顺序排列的一系列观测数据,其观测值
按固定的时间间隔采样。 时间序列广泛存在于商业、经济、科
学工程和社会科学等领域,如股票价格数据、销售数据、图像数
据、影像数据、手写体数据、脑扫描数据等都可以看做是时间序
列数据
[1]
。 这些数据中隐藏着大量重要的信息,反映的大都
是某个待观察过程在一定时期内的状态或表现
[2]
。
面对海量数据,直接去操作一个高维的数据空间是很困难
的。 因此,需要研究合适的数据表示形式,进行维度约简,在高
效、方便的表示形式上进行有效的挖掘
[3]
。
几种主要技术,如离散傅里叶变换、小波变换和奇异值分
解等是精确的方法。 为提高相似匹配效率,也有学者提倡使用
近似方法,可采用有损耗的数据压缩模式,如分段线性表示
(PLR)方法、序列离散化、字符串匹配方法等
[3]
。 其中,分段线
性表示方法利用直线段来近似表示时间序列的局部波动,具有
时间多解析,而且支持快速的相似性检索和新的距离,是一种
很好的数据压缩和消除噪声的方法
[4]
,而且多数的 PLR 表示
方法支持时间序列的动态增量更新。 时间序列的 PLR 表示方
法已经在下列一些领域得到应用
[5]
:a) 快速的相似性搜索;b)
支持新的距离度量,包括模糊查找、加权序列、DTW 距离,信息
反馈等;c) 支持文本和数据序列;d) 支持新的聚类和分类算
法;e)支持奇异检测。
目前的 PLR 算法对原始数据分段均采用单一的拟合误差
作为阈值,分段效果不太理想
[6]
,算法本身的通用性、时间复
杂度等性能都有待提高;而时间序列相似性研究中,有效的数
据表示是提高相似搜索效率和减少搜索时间的关键
[7]
。 由于
来自不同领域的时间序列数据具有明显的数据特征差异,同一
时间序列数据在不同的时间段上呈现出来的数据特征也不相
同,这些均可看做是数据的波动特征,而波动特征是时间序列
趋势变化的转折点和时间序列随时间变化的表现形式,能更好
地代表这个时间序列的本质特征。 因此,本文认为将这些转折
点作为 PLR 方法中提取分段点的依据,来对序列数据进行分
段线性表示,更能反映时间序列的变化趋式,同时,也能达到对
时间序列进行有效压缩的目的。
1 时间序列的分段线性表示
Keogh 在文献[5]中提出了一种时间序列分段线性表示方
法,这种方法能够对时间序列进行有效的压缩,在一定程度上
能反映时间序列的变化趋式,因而在时间序列数据挖掘中得到
大量的应用。 在 Keogh 的分段线表示方法中,分段近似的目标
是使原时间序列与其线性近似表示之间的残差平方和最小,在
这种目标函数的限制下,不能保证时间序列的每一分段内只具
有一种基本趋势,也就是只具有上升、下降或平稳中的一种,因
此将导致时间序列的某些点的基本趋势被错误提取
[8]
。
大量的学者提出了很多、新的时间序列的分段线性表示方
法,主要有基于特征点的分段线性表示方法
[6 ]
、基于时态边缘
算子的时间序列分段线性表示
[4]
、基于重要点的时间序列趋
势特征提取的方法
[8]
等。 在这些研究方法中都表明,在进行
分段线性表示原始时间序列数据的同时,原序列中的一些重要
数据点是必须被保留的,如达到一定变化幅度的极值点、边缘
第 27 卷第 6 期
2010 年 6 月
计 算 机 应 用 研 究
Application Research of Computers
Vol.27 No.6
Jun.2010