2024年4月17日发(作者：奕奇志)

时间序列相似性度量方法

王燕;安云杰

【摘 要】在时间序列相似性度量中,符号聚合近似(symbolic aggregate

approximation,SAX)方法没有将符号化后的模式序列进一步处理,导致存在一定误

差,为此提出将算术编码技术引用到SAX中,即将符号化序列转换为编码序列,实现

时间序列在概率区间上的分析与度量;在计算序列间的相似度时采用分层欧式距离

算法,综合考虑序列的统计距离和形态距离,由粗到细地进行筛选,达到序列整体趋势

匹配以及细节拟合的目标.实验结果表明,该方法在不同的数据集上都有一定的可行

性,具有较高的准确度和较好的鲁棒性.

【期刊名称】《计算机工程与设计》

【年(卷),期】2016(037)009

【总页数】6页(P2520-2525)

【关键词】时间序列;相似性度量;关键点对等;算术编码技术;符号化;分层欧式距离

【作 者】王燕;安云杰

【作者单位】兰州理工大学计算机与通信学院,甘肃兰州730050;兰州理工大学计

算机与通信学院,甘肃兰州730050

【正文语种】中 文

【中图分类】TP311

时间序列是对某一物理过程中的某一变量A(t)分别在时刻t1,t2,…,tn(t1

进行观察测量而得到的离散有序的数据集合，但由于时间序列数据的复杂，多种类、

高维度等特性，为处理这些数据的分析带来了很大的困难，因此时间序列数据挖掘

工作变得尤为重要[1]。

在整个时间序列数据挖掘过程中，相似性度量技术是许多其它工作(比如聚类、分

类、关联规则等)的基础，吸引了大量学者的深入研究[2-6]。其中，基于特征的符

号聚合近似(SAX)[7]方法成为了最流行的相似性度量方法。例如，Antonio

Canelas等用SAX方法处理时间序列[8]，具有简单易用、不依赖具体实验数据、

并能准确表示时间序列统计特征的优点，但该方法弱化了序列的形态变化信息；张

海涛等提出基于趋势的时间序列相似性度量[9]，能够客观的描述序列形态变化，

但由于选择的符号数太多，丧失了处理意义，使度量算法变的繁琐；肖瑞等提出了

编码匹配算法在不确定时间序列相似性度量上的应用[10]；Yan Wang将关键点提

取和序列对等技术应用到了SAX算法中[11]，为时间序列相似性度量提供了可以

借鉴和参考的方向。虽然学者们对基于特征的相似性度量方法提出了一些改进，但

是缺少对符号化后的模式序列进行处理，使得相似性度量的准确率较低。

为此本文提出对符号化序列用算术编码技术做进一步处理，使其既便于理解又提高

了相似性度量的准确率。在计算序列间相似度时采用分层欧式距离算法，综合考虑

均值距离和斜率距离，使度量结果更加准确、高效。

时间序列存在噪声干扰、短期起伏性、非稳态及长期性等特点，如果直接对原始序

列进行研究，难以获得令人满意的结果[4]。所以需要对原始时间序列进行预处理，

为了减少分段误差，预处理中采用先规范化再分段的方法。

规范化是将时间序列数据转化为均值为0，标准差为1的标准正态分布序列。即原

始时间序列A={A1,A2,…,An}转化为由S={S1,S2,…,Sn}表示，其数据规范化如式

(1)所示

表1为时间序列分段与对等过程中所涉及到的符号的定义。

对于时间序列的分段，本文采用关键点分段技术。现阶段关键点的提取方法有多种，

例如：基于极值点、弧度、曲率、夹角等。本文为了达到对时间序列进行有效压缩

和保留序列重要特征的目的，采用基于极值点的关键点选取方法。具体的选取原则

请参考文献[11]。将标准时间序列S分段得到子段})其中每个子段中包含k(k值不

等)个数据点，即,}(i≤w)。如图1所示：两条时间序列SX和SY利用关键点分段技

术可得到。

关键点是时间序列中的重要节点，利用关键点分段技术得到的子段可以保持原序列

的基本形态，为计算序列间的相似度提供了方便。但通常情况下，任意两条时间序

列SX和SY在采用关键点分段后各端点不会完全对齐。为了计算序列间相似性的

方便，需对分段后的序列进行关键点对等。对于上述SX和SY经过关键点对等后

表示为：,tx6),。

SAX是时间序列相似性度量中应用最为广泛的方法。但是SAX方法最大的缺陷是

只采用均值信息直接衡量序列间的相似性。本文提出在计算时间序列相似性时，应

用算术编码技术对符号化序列进一步处理，使得到的编码序列能够准确的反映出序

列的变化特征，并为相似性度量奠定了可靠的基础。

时间序列符号化是通过离散化方法将连续实数值的时间序列或者时间序列的某段时

间内的波形映射到有限的符号集上，从而实现时间序列模式转换[12]。将时间序列

映射到不同区域上，同一区域映射为一个字符。对于字符集大小的选择问题，若太

大会丧失符号化的意义，太小又起不到一定的效果，一般情况下，符号集大小选为

2。因此，本文采用两个字符{0,1}和一个划分点O对时间序列进行符号化表示。子

段的均值ai按照式(2)来计算，斜率ki按照式(3)计算

算术编码是一种对数据进行的无损压缩的方式，是一种在给定符号集合和符号概率

集合的情况下进行的编码方式。该编码方式的效果接近最优，能够精确表示出数据

的关键信息[10]。本文的符号集为符号化的取值{0,1}，符号概率集为{0.5,0.5}。具

体编码过程如下：

(1)输入时间序列S的均值和斜率符号化序列，符号集{0,1}，符号概率集{0.5,0.5}。

首次编码区间定为[0,1]，则对于首次编码符号为0时，编码区间为[0,0.5]；首次

编码符号为1时，编码区间为[0.5,1]。

(2)根据(1)的首次编码区间对时间序列S的均值符号序列和斜率符号序列进行算术

编码。现以均值序列编码为例：设子段(1

对于下一个子段(i+1≤w)时，若为字符0，则对应的编码为[a,(a+b)/2]；若为字符

1，则对应的编码为[(a+b)/2,b]；若i=w，编码结束，输出所有的均值编码区间值。

(3)每一个均值编码区间的均值编码值的计算公式如下

(4)最后输出时间序列S的均值编码序列Sa和斜率编码序列Sk。

对于图1中的时间序列SX按照上述算术编码规则得到均值编码区间序列为

[0.5,1];[0.5,0.75];[0.625,0.75];[0.625,0.6875];[0.625,0.65625];[0.640625,0.6562

5];[0.640625,0.648437]。与此同时，均值编码序列为：

0.75;0.625;0.6875;0.65625;0.640625;0.648437;0.644531。对于SX和SY的均

值编码和斜率编码如图2所示。

在图2中，标注出的关键点的前一个数字代表本段的均值编码值，后一个数字代

表斜率编码值。对于编码的两条时间序列计算相似性距离时，需要计算出两条时间

序列每段均值编码差和斜率编码差。以时间序列段之间的均值编码差为例，按式(5)

计算得出第i个子段的均值编码差。斜率编码差的计算公式与均值编码差的相似，

此处不再列出

本文采用分层欧氏距离(HE)算法对编码序列计算相似度。主要思想是：利用均值编

码对待度量序列进行粗度量，对于满足要求的序列形成候选集；接下来在候选集中

利用斜率编码进行细度量。这样有层次的进行相似性搜索，逐步缩小搜索范围，使

转换后的新序列与原始序列的拟合度更高，相似性度量效率也更高。具体的过程如

下：

(1)均值编码粗度量：在待度量序列中,对经过符号化和算术编码后的均值序列用欧

氏距离计算两条时间序列在统计特征上的相似度。对满足式(6)的序列形成候选集

序列

(2)斜率编码细度量：对候选集中的时间序列比较形态距离。给定的斜率编码阈值

λ，斜率编码距离的计算如式(8)

本文将分层的思想运用到计算序列间相似性问题中，可以达到在统计距离和形态距

离上的相似，从而提高相似性度量的准确率。本文的时间序列相似性度量流程如图

3所示。

其主要算法为：

输入：待度量时间序列，角度阈值θ，时间阈值η，均值编码阈值ε，斜率编码阈

值λ；

输出：相似的结果集；

步骤1 将时间序列规范化，得到标准时间序列S；

步骤2 利用关键点和对等技术分段，得到w个子段S′；

步骤3 对每个子段S′的均值与斜率进行符号化；

步骤4 对符号化后的均值和斜率序列进行算术编码，得到每个子段的均值编码序

列Sa′和斜率编码序列Sk′；

步骤5 计算两条时间序列对应的每段的均值编码差和斜率编码差。

步骤6 对编码后的序列采用基于分层欧式距离算法进行度量，首先进行均值编码

粗度量，形成候选集，再进行斜率编码细度量，最终得到相似序列。

实验的环境为：Windows 7，Inter(R) Core(TM)2 Duo CPU T5870 2.00 GHz，

Memory 2.00 GB，MatlabR 2010b。为了突出本文方法比Euclid、分层动态时

间弯曲(HD)、传统SAX方法在相似性度量方面的优势，采用相同的且已知分类结

果的一元时间序列数据集UCI进行实验并对比。表2对UCI中的3组数据集进行

了介绍。

实验1：本文参考文献[13]提出的把实验数据分为测试集和训练集两个已知的集合

的方法，利用所选的度量算法衡量测试集中的样本与训练集中的样本的相似度。即

给定相似度距离阈值，若测试集样本和训练集样本之间的相似度距离低于给定阈值，

则判定这两条时间序列相似，高于则为非相似序列，完成某一算法在测试集中所有

序列的相似性度量后，把这些结果的平均值作为此算法在这个数据集上的实验结果

[13]。实验结果用正确率和误检率来衡量。正确率指的是原本就相似的时间序列，

经相似性度量后依旧判定为相似序列的条数与原相似序列总数的比值。误检率是指

原本不相似的序列，经相似性度量后错误的判断为相似序列的条数与原不相似序列

总数的比值。例如在Synthetic control数据集中有6类数据，计算正确率时是在

每一类中随机选取一条数据与训练集中同类的50条数据进行度量，计算经过实验

判定为相似的序列条数与实验总数之比；在计算误检率时是在6类测试集中选中

一类中任意一条和训练集中不同类的250条数据进行实验，计算误认为相似的条

数与进行实验总数之比。为了体现本文方法的优越性，表3显示了传统SAX方法

与本文方法在相同的数据集上得到结果的对比。

表3显示出了本文方法和传统SAX方法在正确率和误检率方面的对比。可以看出

本文方法的正确率明显高于传统SAX方法，误检率可以达到传统SAX误检率的一

半。其主要原因有如下两点：①是传统的SAX方法采用PAA分段，用平均值表示

每个分段，而均值并不能完全的表示出时间序列的重要信息,忽略了原始序列的形

态特征。本文用关键点技术分段，既能提取序列的重要特征点，又能有效的压缩序

列并降低维数，可以更加准确代表原始序列。本文综合考虑了形态特征和统计特征，

不但拥有传统SAX方法的简单方便的特点，而且有效地描述了时间序列的形态变

化。②是在计算相似性距离之前没有对SAX序列充分处理，导致传统SAX方法在

度量上有一定的误差。而本文采用基于均值和斜率特征的基础上应用算术编码对字

符串进一步处理，将序列转换到概率区间上，使度量结果更加准确。

实验2：分层欧式距离(HE)和分层动态时间弯曲(HD)算法在数据集synthetic

control上随机抽取5组时间序列数据，每组数据抽取60条序列，分别属于6个

不同的类别，每个类别10条。图4显示出HE和HD在每组数据的相似性距离运

算时间的对比。

由图4可以很容易得到：分层欧式距离(HE)比分层动态时间弯曲(HD)算法的时间

消耗小的多。由于两种分层思想是基于传统算法的，传统的动态时间弯曲(DTW)

的时间代价很大[14],限制了HD使用范围。而传统的欧式距离算法运算速度快，

复杂度比较低，所以计算相似性距离时运用HE算法可以达到较高的效率。

实验3：对比传统欧氏距离(Euclid)与分层欧式距离(HE)在数据集coffee中随机抽

取10组数据进行实验的结果，表4显示了两种算法在计算序列间相似性度量精度

方面的对比。

表4显示出了Euclid和HE在每组数据集上得到的时序相似性度量在精度方面的

对比，可以得出Euclid在不同数据集上的度量精度波动很大，而HE除了在第10

组数据之外，其它9组的相似性度量精度都高于传统欧式距离并且十分稳定。从

两种算法在10组数据的相似性度量平均值上可以看出HE比Euclid要高出将近

10%。本文HE算法综合考虑了序列的统计差异和形态差异，即便两条时间序列的

斜率距离为0均值距离不同，其差异也会体现出来，因此更加符合时间序列的相

似性度量的要求。由此可得出HE比Euclid在计算时间序列相似性度量方面具有

较高的精度和较好的稳定性。

本文针对时间序列符号化相似性度量结果存在误差的问题，提出一种基于符号化与

算术编码相结合的相似性度量方法，它通过分层欧式距离算法结合均值编码距离和

斜率编码距离计算时序间的相似性，从而实现了时间序列在概率区间上的准确分析。

本文方法可以对时间序列提供更多的描述信息，提高了相似性度量的准确性和可靠

性，因而它在时间序列的相似性度量中获得更加出色的表现。接下来我们着力研究

的方向是实现构造数据索引。

2024年4月17日发(作者：奕奇志)

时间序列相似性度量方法

王燕;安云杰

【摘 要】在时间序列相似性度量中,符号聚合近似(symbolic aggregate

approximation,SAX)方法没有将符号化后的模式序列进一步处理,导致存在一定误

差,为此提出将算术编码技术引用到SAX中,即将符号化序列转换为编码序列,实现

时间序列在概率区间上的分析与度量;在计算序列间的相似度时采用分层欧式距离

算法,综合考虑序列的统计距离和形态距离,由粗到细地进行筛选,达到序列整体趋势

匹配以及细节拟合的目标.实验结果表明,该方法在不同的数据集上都有一定的可行

性,具有较高的准确度和较好的鲁棒性.

【期刊名称】《计算机工程与设计》

【年(卷),期】2016(037)009

【总页数】6页(P2520-2525)

【关键词】时间序列;相似性度量;关键点对等;算术编码技术;符号化;分层欧式距离

【作 者】王燕;安云杰

【作者单位】兰州理工大学计算机与通信学院,甘肃兰州730050;兰州理工大学计

算机与通信学院,甘肃兰州730050

【正文语种】中 文

【中图分类】TP311

时间序列是对某一物理过程中的某一变量A(t)分别在时刻t1,t2,…,tn(t1

进行观察测量而得到的离散有序的数据集合，但由于时间序列数据的复杂，多种类、

高维度等特性，为处理这些数据的分析带来了很大的困难，因此时间序列数据挖掘

工作变得尤为重要[1]。

在整个时间序列数据挖掘过程中，相似性度量技术是许多其它工作(比如聚类、分

类、关联规则等)的基础，吸引了大量学者的深入研究[2-6]。其中，基于特征的符

号聚合近似(SAX)[7]方法成为了最流行的相似性度量方法。例如，Antonio

Canelas等用SAX方法处理时间序列[8]，具有简单易用、不依赖具体实验数据、

并能准确表示时间序列统计特征的优点，但该方法弱化了序列的形态变化信息；张

海涛等提出基于趋势的时间序列相似性度量[9]，能够客观的描述序列形态变化，

但由于选择的符号数太多，丧失了处理意义，使度量算法变的繁琐；肖瑞等提出了

编码匹配算法在不确定时间序列相似性度量上的应用[10]；Yan Wang将关键点提

取和序列对等技术应用到了SAX算法中[11]，为时间序列相似性度量提供了可以

借鉴和参考的方向。虽然学者们对基于特征的相似性度量方法提出了一些改进，但

是缺少对符号化后的模式序列进行处理，使得相似性度量的准确率较低。

为此本文提出对符号化序列用算术编码技术做进一步处理，使其既便于理解又提高

了相似性度量的准确率。在计算序列间相似度时采用分层欧式距离算法，综合考虑

均值距离和斜率距离，使度量结果更加准确、高效。

时间序列存在噪声干扰、短期起伏性、非稳态及长期性等特点，如果直接对原始序

列进行研究，难以获得令人满意的结果[4]。所以需要对原始时间序列进行预处理，

为了减少分段误差，预处理中采用先规范化再分段的方法。

规范化是将时间序列数据转化为均值为0，标准差为1的标准正态分布序列。即原

始时间序列A={A1,A2,…,An}转化为由S={S1,S2,…,Sn}表示，其数据规范化如式

(1)所示

表1为时间序列分段与对等过程中所涉及到的符号的定义。

对于时间序列的分段，本文采用关键点分段技术。现阶段关键点的提取方法有多种，

例如：基于极值点、弧度、曲率、夹角等。本文为了达到对时间序列进行有效压缩

和保留序列重要特征的目的，采用基于极值点的关键点选取方法。具体的选取原则

请参考文献[11]。将标准时间序列S分段得到子段})其中每个子段中包含k(k值不

等)个数据点，即,}(i≤w)。如图1所示：两条时间序列SX和SY利用关键点分段技

术可得到。

关键点是时间序列中的重要节点，利用关键点分段技术得到的子段可以保持原序列

的基本形态，为计算序列间的相似度提供了方便。但通常情况下，任意两条时间序

列SX和SY在采用关键点分段后各端点不会完全对齐。为了计算序列间相似性的

方便，需对分段后的序列进行关键点对等。对于上述SX和SY经过关键点对等后

表示为：,tx6),。

SAX是时间序列相似性度量中应用最为广泛的方法。但是SAX方法最大的缺陷是

只采用均值信息直接衡量序列间的相似性。本文提出在计算时间序列相似性时，应

用算术编码技术对符号化序列进一步处理，使得到的编码序列能够准确的反映出序

列的变化特征，并为相似性度量奠定了可靠的基础。

时间序列符号化是通过离散化方法将连续实数值的时间序列或者时间序列的某段时

间内的波形映射到有限的符号集上，从而实现时间序列模式转换[12]。将时间序列

映射到不同区域上，同一区域映射为一个字符。对于字符集大小的选择问题，若太

大会丧失符号化的意义，太小又起不到一定的效果，一般情况下，符号集大小选为

2。因此，本文采用两个字符{0,1}和一个划分点O对时间序列进行符号化表示。子

段的均值ai按照式(2)来计算，斜率ki按照式(3)计算

算术编码是一种对数据进行的无损压缩的方式，是一种在给定符号集合和符号概率

集合的情况下进行的编码方式。该编码方式的效果接近最优，能够精确表示出数据

的关键信息[10]。本文的符号集为符号化的取值{0,1}，符号概率集为{0.5,0.5}。具

体编码过程如下：

(1)输入时间序列S的均值和斜率符号化序列，符号集{0,1}，符号概率集{0.5,0.5}。

首次编码区间定为[0,1]，则对于首次编码符号为0时，编码区间为[0,0.5]；首次

编码符号为1时，编码区间为[0.5,1]。

(2)根据(1)的首次编码区间对时间序列S的均值符号序列和斜率符号序列进行算术

编码。现以均值序列编码为例：设子段(1

对于下一个子段(i+1≤w)时，若为字符0，则对应的编码为[a,(a+b)/2]；若为字符

1，则对应的编码为[(a+b)/2,b]；若i=w，编码结束，输出所有的均值编码区间值。

(3)每一个均值编码区间的均值编码值的计算公式如下

(4)最后输出时间序列S的均值编码序列Sa和斜率编码序列Sk。

对于图1中的时间序列SX按照上述算术编码规则得到均值编码区间序列为

[0.5,1];[0.5,0.75];[0.625,0.75];[0.625,0.6875];[0.625,0.65625];[0.640625,0.6562

5];[0.640625,0.648437]。与此同时，均值编码序列为：

0.75;0.625;0.6875;0.65625;0.640625;0.648437;0.644531。对于SX和SY的均

值编码和斜率编码如图2所示。

在图2中，标注出的关键点的前一个数字代表本段的均值编码值，后一个数字代

表斜率编码值。对于编码的两条时间序列计算相似性距离时，需要计算出两条时间

序列每段均值编码差和斜率编码差。以时间序列段之间的均值编码差为例，按式(5)

计算得出第i个子段的均值编码差。斜率编码差的计算公式与均值编码差的相似，

此处不再列出

本文采用分层欧氏距离(HE)算法对编码序列计算相似度。主要思想是：利用均值编

码对待度量序列进行粗度量，对于满足要求的序列形成候选集；接下来在候选集中

利用斜率编码进行细度量。这样有层次的进行相似性搜索，逐步缩小搜索范围，使

转换后的新序列与原始序列的拟合度更高，相似性度量效率也更高。具体的过程如

下：

(1)均值编码粗度量：在待度量序列中,对经过符号化和算术编码后的均值序列用欧

氏距离计算两条时间序列在统计特征上的相似度。对满足式(6)的序列形成候选集

序列

(2)斜率编码细度量：对候选集中的时间序列比较形态距离。给定的斜率编码阈值

λ，斜率编码距离的计算如式(8)

本文将分层的思想运用到计算序列间相似性问题中，可以达到在统计距离和形态距

离上的相似，从而提高相似性度量的准确率。本文的时间序列相似性度量流程如图

3所示。

其主要算法为：

输入：待度量时间序列，角度阈值θ，时间阈值η，均值编码阈值ε，斜率编码阈

值λ；

输出：相似的结果集；

步骤1 将时间序列规范化，得到标准时间序列S；

步骤2 利用关键点和对等技术分段，得到w个子段S′；

步骤3 对每个子段S′的均值与斜率进行符号化；

步骤4 对符号化后的均值和斜率序列进行算术编码，得到每个子段的均值编码序

列Sa′和斜率编码序列Sk′；

步骤5 计算两条时间序列对应的每段的均值编码差和斜率编码差。

步骤6 对编码后的序列采用基于分层欧式距离算法进行度量，首先进行均值编码

粗度量，形成候选集，再进行斜率编码细度量，最终得到相似序列。

实验的环境为：Windows 7，Inter(R) Core(TM)2 Duo CPU T5870 2.00 GHz，

Memory 2.00 GB，MatlabR 2010b。为了突出本文方法比Euclid、分层动态时

间弯曲(HD)、传统SAX方法在相似性度量方面的优势，采用相同的且已知分类结

果的一元时间序列数据集UCI进行实验并对比。表2对UCI中的3组数据集进行

了介绍。

实验1：本文参考文献[13]提出的把实验数据分为测试集和训练集两个已知的集合

的方法，利用所选的度量算法衡量测试集中的样本与训练集中的样本的相似度。即

给定相似度距离阈值，若测试集样本和训练集样本之间的相似度距离低于给定阈值，

则判定这两条时间序列相似，高于则为非相似序列，完成某一算法在测试集中所有

序列的相似性度量后，把这些结果的平均值作为此算法在这个数据集上的实验结果

[13]。实验结果用正确率和误检率来衡量。正确率指的是原本就相似的时间序列，

经相似性度量后依旧判定为相似序列的条数与原相似序列总数的比值。误检率是指

原本不相似的序列，经相似性度量后错误的判断为相似序列的条数与原不相似序列

总数的比值。例如在Synthetic control数据集中有6类数据，计算正确率时是在

每一类中随机选取一条数据与训练集中同类的50条数据进行度量，计算经过实验

判定为相似的序列条数与实验总数之比；在计算误检率时是在6类测试集中选中

一类中任意一条和训练集中不同类的250条数据进行实验，计算误认为相似的条

数与进行实验总数之比。为了体现本文方法的优越性，表3显示了传统SAX方法

与本文方法在相同的数据集上得到结果的对比。

表3显示出了本文方法和传统SAX方法在正确率和误检率方面的对比。可以看出

本文方法的正确率明显高于传统SAX方法，误检率可以达到传统SAX误检率的一

半。其主要原因有如下两点：①是传统的SAX方法采用PAA分段，用平均值表示

每个分段，而均值并不能完全的表示出时间序列的重要信息,忽略了原始序列的形

态特征。本文用关键点技术分段，既能提取序列的重要特征点，又能有效的压缩序

列并降低维数，可以更加准确代表原始序列。本文综合考虑了形态特征和统计特征，

不但拥有传统SAX方法的简单方便的特点，而且有效地描述了时间序列的形态变

化。②是在计算相似性距离之前没有对SAX序列充分处理，导致传统SAX方法在

度量上有一定的误差。而本文采用基于均值和斜率特征的基础上应用算术编码对字

符串进一步处理，将序列转换到概率区间上，使度量结果更加准确。

实验2：分层欧式距离(HE)和分层动态时间弯曲(HD)算法在数据集synthetic

control上随机抽取5组时间序列数据，每组数据抽取60条序列，分别属于6个

不同的类别，每个类别10条。图4显示出HE和HD在每组数据的相似性距离运

算时间的对比。

由图4可以很容易得到：分层欧式距离(HE)比分层动态时间弯曲(HD)算法的时间

消耗小的多。由于两种分层思想是基于传统算法的，传统的动态时间弯曲(DTW)

的时间代价很大[14],限制了HD使用范围。而传统的欧式距离算法运算速度快，

复杂度比较低，所以计算相似性距离时运用HE算法可以达到较高的效率。

实验3：对比传统欧氏距离(Euclid)与分层欧式距离(HE)在数据集coffee中随机抽

取10组数据进行实验的结果，表4显示了两种算法在计算序列间相似性度量精度

方面的对比。

表4显示出了Euclid和HE在每组数据集上得到的时序相似性度量在精度方面的

对比，可以得出Euclid在不同数据集上的度量精度波动很大，而HE除了在第10

组数据之外，其它9组的相似性度量精度都高于传统欧式距离并且十分稳定。从

两种算法在10组数据的相似性度量平均值上可以看出HE比Euclid要高出将近

10%。本文HE算法综合考虑了序列的统计差异和形态差异，即便两条时间序列的

斜率距离为0均值距离不同，其差异也会体现出来，因此更加符合时间序列的相

似性度量的要求。由此可得出HE比Euclid在计算时间序列相似性度量方面具有

较高的精度和较好的稳定性。

本文针对时间序列符号化相似性度量结果存在误差的问题，提出一种基于符号化与

算术编码相结合的相似性度量方法，它通过分层欧式距离算法结合均值编码距离和

斜率编码距离计算时序间的相似性，从而实现了时间序列在概率区间上的准确分析。

本文方法可以对时间序列提供更多的描述信息，提高了相似性度量的准确性和可靠

性，因而它在时间序列的相似性度量中获得更加出色的表现。接下来我们着力研究

的方向是实现构造数据索引。