光滑曲线去噪算法在分段线性拟合时间序列中的应用研究

基金项目：2014年广西壮族自治区级大学生创新创业训练计划立项项目（201411548098）。

作者简介：通讯作者，范雅静，女，广西南宁人，汉族，广西财经学院信息与统计学院教师。

摘 要：时间序列在经济社会等多个领域发挥着重要的作用。然而，时间序列通常含有较多不规则波动，这些不规则波动易对时间序列数据挖掘造成影响。因此，对时间序列进行降噪处理则是一个亟待解决的问题。本文介绍了一种基于光滑曲线去噪算法在分段线性时间序列中的应用方法。通过对时间序列进行光滑去噪处理，从而得到去噪后的光滑曲线数据，再通过时间序列分段线性的方法找出该序列数据的关键点，进行时间序列的线性分段拟合。实验表明：与直接分段拟合相比，先通过光滑去噪后再进行分段线性拟合得到的结果更好。

关键字：时间序列；光滑去噪；线性拟合；分段表示；

中图分类号：TP31 文献标识码：A 文章编号：1672-3791（2014）12（c）-0000-00

Research of Denoising Algorithm Smooth Curve in the Application of Piecewise Linear Fitting Time Series

HUANG Qiuping CHEN Jucan FAN Yajing LI Jinqing

（School of Information and Statistics， Guangxi University of Finance and Economics， Nanning 530003， Guangxi， China）

Abstract： Time series plays an important role in the economic， society， and other fields. However， time series usually contains many irregular fluctuations which are easy to cause an negative effect on time series data mining. Therefore， noise reduction processing is a problem to be solved. This paper introduced a denoising algorithm based on smooth curve in the application of piecewise linear time series. Smooth curve data is created after removing the time series noise. Then by using the method of time series piecewise linear， data points are found out to fit the original time series. The experiments show that： compared with direct subsection fitting methods， the experiments results are much better by doing smooth denoising firstly and then piecewise linear fitting.

key words： Time series； Smooth denoising； Piecewise linear fitting； Segmentation presentation

引 言：

时间序列的数据挖掘研究是从海量的数据中发掘出有价值的具有规律性信息的算法和实现技术，广泛应用于工业、科学、经济等领域[1-2]。由于数据序列数据量大、噪声干扰严重、短期波动频繁，直接在原始时间序列上进行线性拟合、模式识别、相似性查询等操作，存在工作量大、效率低、耗时长等弊端。许多研究者提出相关的时间序列的分段线性方法，进行时间序列线性拟合。过去，国内外众多学者对时间序列分段先行方法进行了研究，并提出极值点拟合法、特征点拟合法、基于关键点拟合法和精确的时间序列拟合法等多种方法，这些方法都能够较好地将原时间序列分段并拟合。而本文试图在此基础上，先对原时间序列进行光滑处理，再分别利用不同的方法提取原时间序列分段点，并评价该点用于原时间序列拟合时的效果。

1.相关算法介绍

1.1 时间序列分段线性算法

极值点拟合法是利用原时间序列数据的单调变化属性提取其中重要的特征数据，这些数据点均为原时间序列的极值点。对于原时间序列数据 ，其中0

特征点拟合法是对极值点拟合法的改进，利用极值点拟合法提取极值点 ，若选出的极值点与前后极值点之间的时间段与该序列长度L的比值必须大于某个阈值C，则和原序列的起点和终点作为特征点保留下来。计算公式为： 。其中， 和 分别表示 和 点所在原序列中的位置。

基于关键点的线性拟合方法是对特征点拟合法的改进，在特征点拟合法的基础上，利用自定义的单调序列中线距离阈值提取转折点。当数据序列中的某个数据点 与前后数据 、 平均值距离 （e>0）时，则 为转折点。

精确的时间序列线性拟合方法将特征点拟合法和斜率法相结合，在找出时间序列极值点（保持阈值C）的同时，通过斜率的方法提取出时间序列中的变化转折点。以 为基准做一条平行于X轴的直线，若 ， 位于 的同侧，则 与前后两个相邻点所确定的线段中，只要有一条线段的斜率大于阈值，则该点是转折点。若 ， 位于 的异侧，所确定的线段的斜率的欧式距离大于阈值，则认为是转折点。

1.2 光滑去噪处理算法

光滑去噪声算法是通过前后数据计算去除当前点的噪声，在长度为m的时间序列中，第i个点的去噪计算公式如式（1）所示。

（1）

式（1）中，d为去噪前的时间序列数据，D为去噪后的数据，n为光滑度指数。但是，式（1）并没有完全定义所有的D点，例如当n等于2，m=100时，式（1）中的i值将大于等于3且小于等于98， ， 直接套用式（1）可得： 。而 、 的值计算不能使用式（1）， 、 计算过程如下： ， ；对序列 点的光滑度指数计算也存此问题，计算方法参考 、 的算法。

2.模型的建立

过去，众多学者已经提出了多个时间序列分段线性拟合方法。在国外，Sanghyun Park等人提出极值点拟合法[3]（IPSegmentation，简称IPS）通过提取极值点来拟合时间序列，算法简单，运算率高，较好的反应了原始时间序列的主要变化模式。在国内，肖辉，胡运发提出特征点拟合法[4]（FPSegmentation，简称FPS）进行线性拟合，在选取极值的基础上，引入极值点保持时间阈值，较好的考虑了噪音处理；杜奕提出基于关键点的拟合方法[5]（KPSegmentation，简称KPS）进行线性拟合，将已有的极值点和三角形中线的方法相结合，能够发现时间序列中的变化转折点；王郝楠提出了一种精确的时间序列线性拟合方法[6]（APSegmentation，简称APS），在找出极值点（保持时间段阈值C）的同时，通过斜率的方法将时间序列中的变化转折点提取出来，从而更好地近似表示原时间序列。

本文对原序列先进行平滑处理，去除序列数据中的噪音，得到去噪后的光滑曲线数据，再分别运用上述极值点拟合法、特征点拟合法、基于关键点拟合法和精确的时间序列拟合法在光滑曲线上提取关键点，进行线性拟合，近似表示原时间序列。本文将这四种方法分别称为SIPSegmentation（简称SIPS）、SFPSegmentation（简称SFPS）、SKPSegmentation（简称SKPS）和SAPSegmentation（简称SAPS）。

本文以原时间序列的压缩率、拟合绝对误差和关键点与绝对误差的乘积值作为评价指标，比较分析直接分段拟合与经过光滑去噪再进行分段拟合的这2种方法的拟合结果。在相同拟合率下，直接比较拟合误差的大小就可以判断出哪种方法较好。在不同压缩率下，无法通过拟合绝对误差的大小来直接判断哪种方法较好，则通过这2种方法分别进行拟合后各自得到的代表原序列的关键点个数与误差率的乘积的比值（W值）来进行分析比较。其中，压缩率、拟合绝对误差和W值的计算公式分别为：

压缩率： （2）

拟合绝对误差： （3）

W值： （4）

式（2）中，L是原序列长度，N是找到的关键点的个数；式（3）中 是原序列数据， 是拟合序列的数据。式（4）中，D、E分别代表提取的关键点个数和拟合绝对误差。下标1表示直接分段拟合方法，2表示经过光滑处去噪后再进行分段拟合的方法。若W>1，则表明经过光滑去噪后的拟合方法比较好；若W

图1 四种光滑处理后的拟合算法流程图

3.实验结果与分析

本实验使用E.Keogh提供的OliveOil数据（http：//www.cs.ucr.edu/～eamonn）和股票平安银行日线数据（2001-7-6到2014-7-21）作为实验数据，这2种的序列数据长度不同，其中，前者的序列长度为570，后者为3000。实验结果如表1、2所示。

表1 OliveOil的实验结果

方法 IPS SIPS FPS SFPS KPS SKPS APS SAPS

关键点（个） 57 27 43 20 52 52 52 52

拟合绝对误差 6.55 7.40 6.55 7.47 1.52 1.26 1.51 1.34

压缩率（%） 90.05 95.26 91.90 96.50 91.70 91.70 91.70 91.70

W 1.87 1.89 1.21 1.13

表2 股票样本的实验结果

方法 IPS SIPS FPS SFPS KPS SKPS APS SAPS

关键点（个） 998 318 188 179 173 173 174 174

拟合绝对误差 11.04 27.61 41.91 33.30 32.30 27.78 33.94 29.07

压缩率（%） 50.10 84.10 90.60 91.05 91.35 91.35 91.30 91.30

W 1.25 1.32 1.17 1.17

由表可知，在相同g的压缩率下，光滑去噪后再进行分段线性拟合方法的结果比直接分段线性的拟合方法的结果好；在不同的压缩率下，W（IPS）和W（FPS）都大于1，这都说明了基于光滑曲线的分段线性时间序列合方法的拟合结果比较好。

4.结论

本文使用2种不同的数据检验光滑去噪算法在分段线性拟合时间序列中的应用效果，从实验结果来看，经过去噪后再进行IPS、FPS、KPS和APS四种时间序列分段拟合可以取得更好的拟合结果。本文方法可以提高时间序列数据的拟合效果，但需要指出的是，由于实验数据有限，本方法有可能会在其他时间序列数据拟合应用中带来拟合误差的上升。

参考文献

[1] Wiegand T，Sullivan G J，Bjontegaard G，et al.Overview of the H.264/AVC Video Coding Standard[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7）：560-576

[2] Joint Video Team.H.264/AVC Reference Software Version JM17.2[EB/OL].（2010-05-21）.http：//iphome.hhi.de/suehring/tml/ download/

[3] Sanghyun Park，Sang-WookKim，Wesley W.Chu.Segment-Based APProach for Subsequence searches in sequence Databases[C].Proceedings of the 16th ACM symposium on Applied Computing.NewYork：ACM Press.2001：248-252.

[4] 肖辉，胡运发.基于分段时间弯曲距离的时间序列挖掘[J].计算机研究与发展.2005，0l：72-78.

[5] 杜奕.时间序列挖掘相关算法研究及应用[D].合肥：中国科技技术大学，2007

[6]王郝楠.时间序列的线性化表示研究[D].辽宁：辽宁师范大学，2012

[7] 赵建秀，王洪国，邵增珍，张岳，丁艳辉.一种基于信息熵的时间序列分段线性表示方法[J]. 计算机应用研究.2013，08：2391-2394