韩 波，章荣丽，鱼先锋

（商洛学院数学与计算机应用学院，陕西商洛726000）

基于关键点的小波提取时间序列近似表示方法

韩 波，章荣丽，鱼先锋

（商洛学院数学与计算机应用学院，陕西商洛726000）

为了克服常见的时间序列近似表示方法参数精确控制不准确而带来的源序列数据表示减损问题，提出一种基于关键点技术的小波变换分解近似表示方法。来自于不同时间序列的仿真实验表明：相比已有的近似表示方法，它保留了原有表示方法的尺度近似系数，摆脱了用户对参数的精确操作控制，在保留住了时序数据的主要特征的同时还极大地实现了时序数据维度的有效约简。

时序数据；数据维度；小波变换

云集群服务、大数据时代的金融、商业、交通、企事业产生了海量的有时序关系数据，这种按时间先后顺序排列的实值集合在计算机数据分析研究中称之为时间序列［1］。随着业务对象的延续和事务进程时间的后续移位，记录这些时间序列的数据关系会变得越来越复杂，结构也越来越庞大，在数据研究分析中直接用原始时间序列进行数据挖掘会产生高昂的代价而且性能不佳［2］。为了解决和提高时间序列数据挖掘的效率，国内外研究者采用的普遍做法是基于近似表示的方法替代原始的时间数据序列，即保留时间数据序列的主要形态，忽略微小的细节，对时间序列进行压缩，挖掘出有益时间序列数据［3］。但是，在时间序列近似表示方法中，如何高效地表示时间序列，成了一个非常难以解决的问题。目前普遍采用序列近似方法表示的时序数据的长度远远小于原始序列的长度，从而降低了时间序列的存储代价、提高了时间序列挖掘的效率、减少了时间序列的细节冗余度，这些极大的加强了数据研究分析的效果［4］。但这些近似方法都是带参数的，基本都需要正确设置输入参数，如果输入的参数很难确定或者不合适时，此时的算法就无法达到最好效果，维度约简会丢失数据的基本信息，无法最大化的还原和接近原始数据［5］。因此，希望出现一种理想的时间序列近似表示方法，这种表示方法不但可以约简时间序列的维度，将序列的主要特征保留，而且需要输入参数要尽可能的少，最理想状态是无参数的［6］。为此，提出了一种新的时间序列符号化近似表示方法，基于关键点技术的离散小波变换多尺度分解近似表示方法。相比已有的近似表示方法，它保留了原有表示方法的尺度近似系数，且不需要用户对参数进行精确控制，却实现了关键点序列近似表示每个尺度的小波近似系数，这既保留住了时序数据序列的主要特征，还极大地实现了时序数据维度的有效约简。

1 基于关键点的时间序列近似表示方法

1.1 模型概念定义

时间序列是按时间顺序排列的实值集合，常用X表示时间序列，X=｛x1，x2，…，xn｝，其中xi是实数，表示时间序列X在时刻i的值，n表示时间序列的长度［7］。这是一种离散化方法，就是将时间序列的实数值或者一段时间内的时间序列波形映射到有限的符号表上，将时间序列表示为有限符号的有序集合，即字符串［8］。此类方法比较常用的有离散傅立叶变换DFT、离散小波变换、奇异值分解等［9］。

为了有效的实现近似表示，首先需要如下模型概念定义。

定义：模型参数和符号

St：待处理的时间序列；

n：时间序列维数，即时间序列的长度；

k：k=log2n表示分解尺度；

cAi：第i层上小波的近视系数；

cDi：第i层上小波的细节系数；

MMi：第i层上的小波近似系数的关键点序列；

Si：第i层上的符号化关键点序列；

Wi：第i层上的符号化编码；

S：源有效时间序列。

1.2 近似表示方法

采用的近似表示研究方法是，先对时序序列做离散小波分解，获取其小波近似系数；然后对每一层的小波近似系数进行关键点提取，用关键点序列替代相应的小波近似系数；再用无参近似表示方法对每一层的关键点序列进行符号化，用符号化序列替代关键点序列；最后对每一层的符号化序列进行编码，把每一层的码收集起来就得到原始时间序列的近似表示。

前两个步骤在保留时间序列的主要信息中具有非常重要的作用，后两个步骤是进行维度约简的关键。

1.3 近似表示方法算法

首先要对源时序序列进行信号预处理，目的是使之满足离散小波变换，以便提取其小波近似系数，用之来近似表示源时序序列［10］。对预处理好时间序列进行近似表示方法算法表述如下：

Step1：定义时间序列St是按照有序时间，即时间先后顺序排列的实值集合｛v1，v2，v3，…，vn｝，这里，vn是时间点ti上的对应离散值，n表示时间序列的个数，即时间序列的维度。

为了算法能用力于大时序数据、高维时间序列小波提取的近似系数的参数，特定义｛v1，v2，v3，…，vn｝∈R∈∞。

Step2：分解提取时序序列的小波系数。在离散小波变换中，一个时序序列的原始信号St被分解成低频信号源，用cA表示；高频信号源，用cD表示，即分解具有关系St=cA+cD。

低频信号源cA含有信号的主要特征信息，可以看成是对原始信号的一个近似，所以被称为小波近似系数。而高频信号源cD捕获的是原始信号中滤除的细节信息，可视为噪声。这样就实现了小波近似系数cA中不仅含有原始信号的主要信息，还滤除了原始信号中的噪声［11］。

Step3：提取时间序列St上的起始点、结束点、局部极大值点以及局部极小值点，j表示为序列的关键点。

Step4：对提取了关键点的离散时序序列进行符号化，方法是用时间序列St=｛v1，v2，v3，…，vn｝∈R，得到一个有限的离散符号集合R=｛ri|1＜i＜m｝。

Step5：获得高维度n的时间序列的近似表示，为了找到它具有维度m的近似表示St，以下小波分解：

第一层分解：将原始时间序列St分解成低频部分，即小波近似系数cAl，和高频部分，即小波细节系数cDl；

第二层分解：因为分解得到的低频部分cA1保留了源时序序列的主要特征信息，所以对之继续进行分解，得到低频部分cA2，和高频部分cD2；

……

如此迭代执行下去n次，依次对每一层的低频部分进行分解，直到分解尺度完成后结束，记为第log2n；那么便有第i层上小波近似系数cAi和细节系数cDi的计算公式：

可以看到，分解得到的小波近似系数和细节系数有两部分组成，其中even｛cAi-1｝代表系数cAi-1的偶数项部分，而odd｛cAi-1｝代表cAi-1的奇数项部分。

Step6：实现维度约简，采用的方法是把获取到的小波近似系数预先进行噪声信息的滤除［12］。所以可以对每一个尺度上的小波近似系数cAi筛选出关键点，然后保留这些关键点，丢掉其非关键点，从而将数据的压缩表示｛cAi|i=1，…，log2（n-1）｝转换为｛MMi|i=1，…，log2（n-1）｝。很明显原信号源的维度n大于压缩约简后的信号源维度log2（n-1），从而实现了时序序列维度的有效约简。

算法总结，小波近似系数的提取主要是基于以下考虑：如果把一个时间序列离散表示为一个信号源，对于大部分的信号而言，它的低频部分是信号源的最重要部分，是识别信号的重要部分。而高频部分仅是对信号的进一步标识和修正。这就像一个人的声音的信号源一样，如果去掉高频部分，声音虽然听起来不同，但是仍然可以知道在说什么；如果去掉低频部分，则只能听到一片嘈杂即噪音。所以提取小波近似系数可以突显出序列的主要特征，综上所述可以看到，该方法提取的时间序列的小波近似系数包含了滤除噪声的原始序列St的主要特征信息。

2 实验结果与分析

2.1 不同时间序列仿真实验

为了验证算法极大程度的维度约简的同时也能保留住原始序列的基本特征。实验数据选用了仿真时间序列和真实时间序列来验证，如图1、图2所示，仿真时间序列包含一条正弦周期的时间序列Yl和一条随机噪声序列Y2及三条真实信号源Y3、Y4、Y5，它们是真实的时间序列。

图1 Y1、Y2仿真时间序列

图2 Y3、Y4、Y5仿真时间序列

实验中先对五条实验序列的基本特征进行定性和定量的仿真，计算出时间序列的样本熵、组合熵、复杂度和指数四个指标值，具体结果如表1所示。在相同压缩率下，基于小波变换的关键点时间序列近似表示方法与传统方法对序列基本特征保留能力比较，实验结果表明，在相同的维度约简程度下，相比于现有的符号化近似表示，新方法可以保留住原始时间序列更多的基本信息，且在时间序列的相似性检索上具有更优的性能，实验结果如表2所示。

表1 时间序列基本特征描述

表2 时序序列基本特征保留能力比较

2.2 不同时间序列实验结果分析

通过仿真实验可以看到，对于时序序列Y1，它的样本熵、组合熵和复杂度值都很低，这说明该序列比较规则、稳定；而Y1的指数值为0.395＜0.5，说明序列的周期性波动很强，所以Y1的时序序列特征被有效的仿真表示具有较强的周期性波动、比较规则、比较稳定。

对于序列Y2，它的样本熵、组合熵和复杂度值都很高，表明序列的随机性波动很强，而指数值0.499≈0.500，接近熟知的布朗噪声值，这说明序列Y2序列波动强、不稳定。同时一现象在时序序列基本特征保留能力比较表2中也得以验证，而这些特征的有效仿真描述，如果采用传统的时序序列近似表示方法提取的样本熵、组合熵是反映不出来，这有效的验证了该方法的优越性。

分析时序序列Y3，它的样本熵、组合熵和复杂度值都很低，表示序列比较规则，这一点与序列Yl类似，但是实验数据中，它的指数值0.724大于序列Yl的指数值0.395，这意味着Y3的周期性波动相比与Yl会比较平缓；同时Y3的基于关键点的小波提取时间序列近似表示方法，在第二到第四尺度上连续出现了3次编码22，它的长度是小于Yl的主要形态编码52，这充分说明在保留序列的主要特征的同时，方法有效的实现了时间序列的维度约简。

分析序列Y4，可以发现它的样本熵、组合熵和复杂度值都很高，表明序列的随机波动性比较强，而指数值为0.802＞0.5，这表明序列趋势性增强，周期性波动变弱，所以表明序列Y4具有呈现一定趋势特征的伪周期性波动，且具有大量毛刺，在时序序列基本特征保留能力比较表2中Y4的具体形态验证了这一说法的正确性，同时分析可以发现在第四尺度到第六尺度上的编码虽然不相同，但是非常接近，分别为43、44、46，这反映除了序列的伪周期性波动的特点，又由于其它尺度上编码相差很大，可以发现序列含有大量的随机成分，而传统的序列表示方法无法观察到这些基本特征。

最后研究分析Y5，它的样本熵、组合熵都很高，代表序列具有大量随机成分，复杂度值比较低，代表序列比较稳定，而指数值0.986≈1.000表示序列有非常强的趋势性，即要么单调上升，要么单调下降，所以综合起来看Y5是呈现带有毛刺的稳定强趋势性，观察它对应的时序表示方法，可以发现在最后三个尺度上出现了相同编码1，这意味着序列的主要形态是上升趋势，而其它尺度上编码相差很大，则代表上升趋势中含有大量噪声，所以序列的基本特征都得到验证，而传统的时序近似表示方法却无法达到这样的性能。

综合实验的分析，可以发现新方法在维度约简程度很高的情况下，原始序列的基本特征得以被有效地保留，而传统的近似时序序列同等条件下会丢失掉大量的时序主要信息，无法为序列的基本特征的辨析提供可靠支持。这样的实验结论充分验证了基于关键点技术的小波提取时间序列近似表示方法的可靠性和优越性。

3 结语

时间序列近似表示方法是研究解决海量有效时序数据的有效技术，目前人们普遍采用一种接近源时序序列的近似表示方法来解决这一问题，其缺点是无法克服大量参数控制难以确定最佳值带来的源序列数据表示减损状况；对此，提出了一种基于关键点的小波变换近似表示方法。该方法采用典型的离散小波分解源信号获取小波近似系数；然后对每一层的小波近似系数进行关键点的提取，用关键点序列替代相应的小波近似系数，用符号化序列替代关键点序列；实验仿真表明它对原始序列实现极大程度的维度约简的同时，可以有效的接近原始序列的特征系数，这表明在相同的维度约简程度下，相比于现有的符号化近似表示方法，参考文献：

它可以保留住原始时间序列更多的基本信息，并且在时间序列的相似性检索上具有更优的性能。

［1］Agrawal R，Fallouts C，Swami A.Efficient similarity search in sequence database［C］.In：Proceedings of 4th InternationalConferenceonFoundationsofData Organization and Algorithm，New York：Springer，2013：69-84.

［2］Keogh E，Chu S，Hart D，et al.Segmenting time series：A survey and novel approach［M］.Data Mining in Time Series Databases，World Scientific Publishing Company，2013.

［3］龚薇.基于变化点的时间序列近似表示［J］.微计算机信息，2012（10）：12-13.

［4］Prat K B，Fink E.Search for patterns in compressed timeseries［J］.International Journal of Image and Graphics，2012，2（1）：89-106.

［5］何书元.应用时间序列分析［M］.北京：北京大学出版社，2012：12-13.

［6］Bagnall A，Janacek G.Clustering time series with clipped data［J］.Machine Learning，2005，58（2）：151-178.

［7］杨志明.时间序列分段线性表示及相似性算法研究［J］.微计算机信息，2011（23）：20-21.

［8］张娜，李莉娟.时间序列分段线性表示的几种算法比较［J］.中国西部科技，2009（14）：17-18.

［9］Chawla S，Glonis A.Kmeans-A unified approach to clustering and outlier detection［C］∥Proceedings of the SIAM international conference on data mining，SIAM. Texas，USA，2013：189-190.

［10］Esling P，Agon C.Time series datamining［J］.ACM Compute Surv，2012，45（1）：33-34.

［11］Fink E，Gandhi H S.Compression of time series by extracting major extreme［J］.Journal of Experimental &TheoreticalArtificialIntelligence，2011，23（2）：255-256.

［12］Fu A，Keogh E，Laul Y，et a1.Scaling and time warping in time series querying［J］.The VLDB Journal，2008，17（4）：89-90.

（责任编辑：张国春）

A Wavelet Extraction Time Series Approximation Methods Based on Key Point

HAN Bo，ZHANG Rong-li，YU Xian-feng
（College of Mathematics and Computer Application，Shangluo University，Shangluo726000，Shaanxi）

In order to overcome the problem that the source series date damaged by precise parameter control was not accurate，which is usually seen in the common approximate representation methods，an approximate wavelet transform decomposition representation method based on the key points technology is proposed.Compared with the existing approximate representation，the method retains the approximate coefficient of the scale of the existing approximate representation.The method gets rid of the user preciseoperationontheparameterscontrol.Andtheapproximationwaveletcoefficientofthe approximate presentation scale of the key point sequence is given，which can not only keeping the main features of time-series data，but also can greatly realize the effective reduction of the time-series data dimension.

time series；data dimension；wavelet transform

TP311.13

A

1674-0033（2015）04-0029-04

10.13440/j.slxy.1674-0033.2015.04.008

2015-04-23

陕西省教育厅专项科研计划项目（12JK0950）

韩波，男，陕西商州人，硕士，讲师