基于EMD的时间序列相似性度量算法

贾瑞玉，王 瑞

(安徽大学 计算机科学与技术学院，安徽 合肥 230601)

基于EMD的时间序列相似性度量算法

贾瑞玉，王 瑞

(安徽大学 计算机科学与技术学院，安徽 合肥 230601)

时间序列本身具有高维、高噪声的特点。在进行相似性度量之前，需要对序列进行特征表示。针对时间序列相似性度量工作中,使用分段线性表示方法对序列进行特征表示，分段拟合效果依赖于划分粒度，若分段数和分段点选取不当，可能导致拟合效果不佳、难以准确反映序列整体形态趋势的问题，提出一种新的基于趋势的相似性度量方法。该方法将经验模态分解方法与分段线性表示方法相结合，首先用经验模态分解方法过滤细节信息，提取序列的主要形态趋势，得到趋势拟合序列。在此基础上，再用分段线性表示方法对趋势拟合序列进行分段表示，减少拟合结果对划分粒度的依赖性。最后给出序列的分段向量距离计算方法,对趋势分段序列计算加权向量距离，得到不同序列之间的相似性。仿真实验表明，该算法稳定有效、对噪声不敏感。

时间序列；相似性；趋势；向量距离

0 引 言

时间序列是一组与时间相关的高维数据，在金融、商业、医学及社会科学等领域中广泛存在，如股市行情、Web访问量、脑电图分析和气象变化数据等[1-2]。时间序列相似性度量是时间序列的聚类、预测及相似性搜索的基础，所以时间序列的相似性研究具有重要的现实意义和广泛的应用前景[3]。由于时间序列具有数据量巨大、噪声含量多、短期起伏、非稳态等特点，对这类数据进行挖掘分析的难度较大，因此时间序列的近似表示与相似性度量成为时间序列数据挖掘的研究热点[4-5]。

基于分段思想的序列表示方法能较好地保留时间序列的全局特征，降低数据维度，并且计算效率高，因此被广泛应用。研究人员也提出了很多时间序列的相似性度量方法。

欧氏距离具有直观、高效的优点，但对数据的平移非常敏感，且计算精度不高[6]。吴虎胜等[7]提出了一种基于二维奇异值分解的相似匹配方法，其本质是用二维奇异值分解对序列进行特征描述，然后计算欧氏距离。Berndt和Chen等[8-9]将动态弯曲距离用于时间序列的相似性度量，克服了欧氏距离无法反映数据整体发展趋势的缺点，并且可以处理不同长度的时间序列，但是存在复杂度较高的问题。刘彤彤等[10]提出了基于窗口斜率表示的相似性算法，以每个窗口内最大最小幅值差与窗口宽度的比值作为序列的特征信息，进行相似性分析。李海林等[11]提出的基于多维形态表示的时间序列相似性度量方法，利用正交多项式的基向量形成的特征空间对序列进行特征表示，进而计算相似度。但特征空间的选择对相似性度量结果影响较大。董晓莉等[12]提出的七元模式形态距离虽然保留了时间序列的分段趋势信息，但本质上是基于对序列分段模式的有限划分，因此，任意两个序列对应分段间的距离值都是离散的，相似匹配的精确程度依赖于模式划分粒度。

针对现有方法的一些不足，文中提出一种基于经验模态分解的相似性度量算法。用经验模态分解方法提取时间序列的趋势信息，并在此基础上进行时间序列的分段线性表示，然后用分段向量距离方法计算趋势分段序列的相似性。基于趋势的分段能有效降低噪声影响，加权向量距离从数据趋势上区分差异，比基于点距离的方法更稳定，同时修正了用户间可能存在的度量标准不统一的问题。

1 相关工作

因为时间序列具有数据量巨大、增长速度快、含有大量噪声等特点，因此在分析时间序列数据之前需要进行维度约简。由Keogh等[13]提出的PLR分段线性表示方法具有良好的数据压缩作用。PLR方法的基本思想是选取序列中的局部极值点或拐点，若该点与端点的比值大于参数ε，则该点被认为是重要点。将所有重要点用直线连接，即可得到基于重要点的分段时间序列。参数ε的大小决定了分段表示的划分粒度。

2 基于EMD的相似度量方法

2.1EMD方法提取序列趋势

经验模态分解方法(Empirical Mode Decomposition，EMD)是Hilbert-Huang等提出的适用于非平稳时间信号分析的方法。它的核心思想是将被分析的数据分解成多个具有不同特征的数据序列组合，每个数据序列具有一个本征模函数(Intrinsic Mode Function,IMF)信号。Huang等定义IMF必须满足以下两个条件[14]：

(1)序列数据的极值点个数和过零点个数相差不超过1；

(2)由极大值点构成的上包络线和由极小值点构成的下包络线关于时间轴对称。

满足以上条件的信号即为IMF信号。如果信号不满足上述条件，则需要进行分解操作，进行平稳化处理，将原始信号分解成多个满足IMF的子信号。

若原始序列信号用X(t)表示，则分解过程主要分为以下三个步骤：

步骤1：找出原始序列中的局部极大值和局部极小值，通过三次样条插值分别得到由极大值构成的上包络线U(t)和由极小值构成的下包络线L(t)，将序列中的所有信号点都包含在两条包络线之间，上包络线和下包络线的平均值为m1(t)。原始序列和上下包络线的平均值包络线差值为h1，如果序列h1不满足IMF的条件或者给定阈值，执行步骤2，否则执行步骤3。

步骤2：将h1作为原始信号重复执行步骤1，直至执行结果满足IMF条件或给定阈值。

h11(t)=h1(t)-m11(t)

(1)

设重复执行i次后，结果满足IMF或阈值内的误差。

h1i(t)=h1(i-1)(t)-m1i(t)

(2)

步骤3：如果序列h1i(t)满足IMF条件，则将其表示为：

c1(t)=h1i(t)

(3)

r1=X(t)-c1(t)

(4)

其中，r1为残留分量。将r1作为原始序列重复步骤1的筛选过程，直至满足下列条件之一：

(1)rn或者cn小于给定阈值；

(2)rn成为单调函数，无法再从分解中得到IMF。

最后得到：

(5)

其中，X(t)表示原始时间序列信号；Ci(t)表示满足IMF的子信号；rn(t)为趋势序列。

因为EMD分解过程是依据原始数据信息进行的，因此分解的信号隐含数据的真实信息，rn(t)体现了序列的真实趋势。

图1为一个经验模态分解过程。其中，Signal是原始序列信号；imf1-imf5是分解过程的细节；res是分解后得到的趋势序列。将imf信号累加可以基本拟合原始序列。

图1 经验模态分解过程

图2为原始序列与分解后的趋势拟合序列对比图。

图2 原始序列与趋势拟合序列对比

直接对原始序列进行分段表示的计算量较大，而且容易受噪声影响。拟合序列能在保留基本趋势的基础上过滤噪声，降低数据维度。对拟合序列使用PLR分段表示方法，提取到的分段序列趋势特征更准确，能够提高相似性度量的准确性。

2.2基于EMD的向量距离

(6)

分段向量距离区间为[0,2],不同分段向量之间夹角越大，向量距离越大，相似度越低；夹角越小，向量距离越小，相似度越高。当向量距离为0时，表示两个向量方向完全一致，即两个分段的趋势完全相同；向量距离为2时，表示两个分段趋势完全相反。通过分段相似度可以得到两个序列的整体相似度：

(7)

为了提高计算结果的准确性，在相似度公式中引入权重(ti+1-ti)/tn，表示分段i的相似性si在整体相似性中所占的权重。其中，tn表示整个序列的长度，ti+1-ti表示分段i的长度。(ti+1-ti)/tn越大，对整体相似度的影响越大，加权后得到的结果能够更精确地反映相似度。

2.3基于EMD的相似性度量算法

输入：原始时间序列S1=，S2=。

Step1：使用EMD方法对原始序列进行经验模态分解；

Step2:拟合原始序列的趋势序列；

Step3：对趋势拟合序列进行分段，得到分段序列；

Step4：对不同序列的分段序列进行等长处理；

Step5：计算分段序列的向量序列；

Step6：计算不同向量序列之间的相似度。

输出：S1和S2的相似度Sim。

使用EMD提取序列趋势之后进行分段表示，减少了噪声的影响，能够更准确地反映序列的形态变化特征，使分段表示提取的趋势特征更准确。向量距离根据不同分段的发展趋势区分差异，比基于点距离的方法精确，比基于形态距离的方法灵活。

3 实 验

实验选取Intel Core(TM) i5-3210M CPU@2.50 GHz，内存为4 GB的电脑，操作系统为Microsoft Windows7，开发工具为MATLAB。采用三种股票在2005年至2010年之间的每日收盘价格时间序列进行实验。第一组数据S1是标普500指数数据(S&P500)，第二组数据S2是沪深300指数数据，第三组数据S3是上证指数数据，每条时间序列包含1 500个数据点。图3是三种时间序列原始数据的走势图。为防止度量标准不统一对结果造成影响，在预处理过程中会将数据统一映射到[0,1]区间。

图3 三种股票数据的走势图

对比方法采用欧氏距离方法和形态距离方法。欧氏距离方法和形态距离方法直接使用PLR分段方法，将预处理后的序列分别压缩至50、100和150段，然后进行距离计算。文中方法先利用EMD进行数据分解，拟合原始序列，再使用PLR方法对拟合序列进行压缩分段表示，最后使用加权向量距离计算相似度。实验结果如表1～3所示。

表1 文中方法的实验结果

表2 形态距离法的实验结果

表3 欧氏距离法的实验结果

实验结果表明，加权向量距离和形态距离方法结果一致，无论将数据压缩到50段、100段还是150段，结果均是S2与S3的距离最小，没有受压缩程度的影响，欧氏距离方法在压缩到150段时认为S1与S3最相似。对比图3中的数据形态走势图可以发现，加权向量距离和形态距离结果正确，但是欧氏距离在150段时没有正确区分序列的趋势差异，计算结果出现误差。虽然本次实验中形态距离和向量距离结果均正确，但是形态距离方法的划分粒度不同，度量结果也会有差异，因此不够稳定。基于EMD的向量距离方法虽然多了提取序列趋势的步骤，但是减少了分段表示的计算量，而且计算结果稳定有效，适用于序列的相似分析和相关研究。

4 结束语

针对现有方法的一些不足，提出了基于EMD的向量距离相似性度量方法。实验结果表明，该方法能够在降低噪声影响的同时提取序列的趋势信息，向量距离能够有效度量时间序列的形态趋势相似度，而且不需要划分形态模式，避免了形态距离方法划分标准不统一、度量结果不稳定的问题，同时克服了欧氏距离对数据平移敏感的缺陷。下一步工作主要是考虑如何减少计算时间，并将该度量方法应用到时间序列的聚类分析中。

[1] 张海涛,李志华,孙 雅,等.时间序列的层次分段及相似性度量[J].计算机工程与应用,2015,51(10):147-151.

[2] 朱扬勇,戴东波,熊 赟.序列数据相似性查询技术研究综述[J].计算机研究与发展,2010,47(2):264-276.

[3] 涂 辉,刘 丽,张正金.改进DTW算法的心电信号相似性度量[J].计算机工程与应用,2015,51(16):215-218.

[4] 刘永志,皮德常,陈传明.基于关键点的不同长度时间序列相似性度量[J].计算机工程与应用,2014,50(20):1-4.

[5] 尚福华,马 楠,杜睿山.基于形态特征的测井曲线相似性搜索研究[J].计算机应用研究,2013,30(4):1076-1078.

[6] 张 勇,王元珍,曹忠升.基于形态拟合的时间序列距离计算[J].华中科技大学学报：自然科学版,2012,40(8):72-76.

[7] 吴虎胜,张凤鸣,钟 斌.基于二维奇异值分解的多元时间序列相似匹配方法[J].电子与信息学报,2014,36(4):847-854.

[8] Berndt D J,Clifford J.Using dynamic time warping to find patterns in time series[C]//Working notes of the knowledge discovery in databases workshop.[s.l.]:[s.n.],1994:359-370.

[9] Chen Y,Hu B,Keogh E,et al.DTW-D:time series semi-supervised learning from a single example[C]//ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2013:383-391.

[10] 刘彤彤,戴 敏,李忠义.基于窗口斜率表示法的心电波形相似性分析[J].计算机应用,2012,32(10):2969-2972.

[11] 李海林,郭崇慧.基于多维形态特征表示的时间序列相似性度量[J].系统工程理论与实践,2013,33(4):1024-1034.

[12] 董晓莉,顾成奎,王正欧.基于形态的时间序列相似性度量研究[J].电子与信息学报,2007,29(5):1228-1231.

[13] Keogh E J,Pazzani M J.An enhanced representation of time series which allows fast and accurate classification,clustering and relevance feedback[C]//International conference on knowledge discovery & data mining.[s.l.]:[s.n.],1998:27-31.

[14] Huang N E,Shen Z,Long S R,et al.The empirical mode decomposition and the hilbert spectrum for nonlinear and non-stationary time series analysis[J].Proceedings of the Royal Society A Mathematical Physical & Engineering Sciences,1998,454(1971):903-995.

ASimilarityMeasureAlgorithmforTimeSeriesBasedonEMD

JIA Rui-yu，WANG Rui

(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

The time series itself has characteristics of high dimension and high noise.It is necessary to represent the sequence before the similarity measure.When using piecewise linear representation method for feature representation,piecewise fitting results depend on the partition granularity.If the segmentation number and segmentation points are not proper selection,which may lead to poor fitting and could not accurately reflect the overall trend of the sequence form.Therefore,aiming at the problem,a new method of similarity measurement based on the trend is proposed which combines the empirical mode decomposition with piecewise linear representation.Firstly,filtering details by empirical mode decomposition,extracting main morphological trend of the sequence,the trend fitting sequence is gained.On this basis,use of piecewise linear representation for fitting the trend sequence,the dependence of the fitting result on the partition granularity is reduced.Finally,the calculation method of piecewise vector distance is given.The similarity between different sequences can be obtained by calculating the weighted vector distance of the trend segment sequence.Simulation results show that the proposed algorithm is stable and effective,and not sensitive to noise.

time series;similarity;trend;vector distance

2016-11-03

2017-03-15 < class="emphasis_bold">网络出版时间

时间：2017-08-01

国家自然科学基金资助项目(61202227)

贾瑞玉(1965-)，女，副教授，硕士研究生导师，研究方向为数据挖掘、智能软件；王 瑞(1991-)，女，硕士研究生，研究方向为数据挖掘、智能数据处理。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1550.026.html

TP301

A

1673-629X(2017)11-0071-04

10.3969/j.issn.1673-629X.2017.11.015