基于形状特征的DTW距离相似性搜索算法

褚蓉　钮焱

摘要：针对时间序列相似性研究中存在动态时间弯曲DTW复杂度过高与分段思想易造成特征丢失的问题，提出了一种基于形状和升降性提取序列数据重要特征点的DTW相似性搜索算法，利用关键特征点快速筛选相似候选子序列集合，计算各个原始子序列的DTW距离，与改进的分段DTW距离度量方法进行实验比较。结果表明，该方法提高了相似性搜索效率，并具备更高的相似度。

关键词：时间序列；相似性；序列特征；升降标识；动态时间弯曲

DOIDOI：10.11907/rjdk.172425

中圖分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）003007803

英文摘要Abstract：In the research of time series similarity， the similarity measurement method of DTW distance is with higher complexity and the idea of segmenting will cause characteristic losing. This paper presents a dynamic match DTW distance similarity searching method based on shape feature and lifting identification， which extracts series shape key points， computing the DTW distance by the similar subsequence screened by lifting identification. Compared with the improved similarity measurement method based on segmented DTW distance，the results show that the method proposed by this paper improves the searching efficiency largely with higher similarity accuracy.

英文关键词Key Words：time series； similarity； series feature； lifting identification； DTW

0引言

时间序列是按照时间顺序排列的一系列观测数据值，广泛应用于商业、经济、科学计算等多个热门领域[1，2]。目前，基于时间序列的相似性搜索已有大量研究，如时间序列傅里叶变换、小波变换、各种分段计算和时间序列降维等方法[38]。但是，上述相似性搜索方法都是使用欧式距离作为度量计算公式，需要两个相同长度的序列才能进行计算。动态时间弯曲（Dynamic Time Warping，DTW）技术的引入，开始广泛应用于相似性度量中，有效解决了欧式距离方法在时间轴伸缩和弯曲方面无法适用的弊端。

DTW技术最初广泛应用在语音识别领域，后来在时间轴上存在弯曲延伸的序列也可以利用该技术进行相似性距离计算。但是由于其核心计算方法为累积距离矩阵的动态规划，导致计算复杂度较高，因此该方法无法很好地适用于海量时间序列的相似性度量[9]。很多研究人员致力于研究和提出多种基于DTW距离的改进方法，用于提高DTW距离计算的查询效率。文献[10]首先对原始数据序列进行筛选，对筛选处理后的序列再进行DTW精确计算，筛选方法主要包括设定DTW下界距离计算公式，用于排除下界距离超过阈值的序列，但存在距离公式的过滤性能与时间复杂度相互制约的问题；文献[11]通过分段预处理各个原始数据序列，将各个分段的平均值作为时间弯曲距离，但存在序列搜索漏报和分段点特征不完整问题；文献[12]提出了快速相似性搜索（FTW）算法，该算法通过限制弯曲路径区域，结合动态规划方法，增强了计算近似距离的准确度；文献[13]综合符号化策略和原始序列分段技术，进一步提高了查询相似序列集合的效率，而且符号策略更好地保留了关键的序列特征，但该方法要求相比较的两个序列长度必须一致。

本文参考符号化思想[13，14]，提出基于序列形状特征和上下标识的DTW相似性搜索算法。该方法通过对提取的数据序列形状添加预标记，准确快速确定相似性子序列集合，对筛选出的相似子序列集合进行精确的DTW距离计算，极大提高了筛选相似序列的效率。该方法已经应用于海洋平台监测数据库的监测数据趋势相似性查询中。

1形状特征与特征标记预处理

形状特征和标记算法的基本思路为：通过分析序列点前后数据形状变化趋势，提取时间序列的关键特征点，为方便数据计算，对提取出来的关键特征点进行数字标记，获得原始时间序列数据的关键特征序列。

1.1关键形状特征序列

以时间点为基本顺序特点的序列X={〈t1，x1〉，〈t2，x2〉，…，〈ti，xi〉，…，〈tn，xn〉}，序列长度为n，ti是序列的某个时间戳，xi是对应时间戳序列点的具体数值。数据序列中一般包括两种关键形状特征点，其中，数据序列曲线有转折和拐弯的点，通过判断某个数据点两侧数据xi-1和xi+1大小值可得。如图1（a）所示，A和B两个点的序列变化趋势是不一样的，都是拐点。第二种是数据序列中数据变化斜度不一样的点，这一类数据点的重要特征是两侧的数据变化趋势差异非常明显。为判断某数据点是否为重要形状特征点，本文通过计算各个数据点两侧的数据倾斜度获得。如图1（b）所示，该数据点两侧的斜度变化比较明显，因此是可以反映数据形状变化的重要特征点。

由于第二类形状特征点不易识别，因此本文为了保证第二类关键特征点提取的完整性和准确性，对原始数据序列进行各个数据值的差分计算，获得数据连续的前后变化量Δ（xi-xi-1），再对获得的前后变化量进行二次差分Δi-Δi-1，获得二次差分变化序列T，对比变化序列数值与设定阈值δ的大小，进而识别该数据点是否可以列为二类关键形状特征点。

由于阈值δ的大小对形状特征点的提取有直接影响，同时更是判断其是否是第二类特征点的主要依据，因此必须保证阈值提取的完备性和准确性。根据差分数值接近于0的序列对差分变化序列影响极其微弱的特性，将接近于0的微弱数据点直接忽略和排除，在差分变化序列中选取峰值最小的绝对数值为阈值δ。提取方法如式（1）。差分变化序列中如果大于阈值，则对应的序列点xi为第二类关键特征点。

δ=MinMinPeak（Ti）Ti≥0

MaxPeak（Ti）Ti≤0（1）

1.2形状特征序列预标记

在篩选关键形状特征序列时，首先通过形状特征序列的上升和下降增减特征，对对应的子序列进行标记预处理，便于后续DTV数字化距离计算。使用数字（0、1）代表特征的趋势，0表示下降，1表示上升（见图2）。

算法详细思路：

①首先提取原始数据序列的差分变化子序列T，选定阈值δ；

②数据序列X中的逐个数据点xi，i=1…n，执行第③、④步；

③如果xi同时大于或小于xi-1和xi+1，说明该类数据点是第一类关键特征点；

④若xi不是第一类关键形状特征点，则提取差分变化子序列Ti，如果Ti≥δ即说明数据点xi为第二类关键形状特征点；

⑤根据特征点xi和xi+1的大小关系确定两个数据点之间的序列增减升降性，并标注1或0。

2基于序列特征与升降标记的DTW距离相似性算法

基于序列特征与升降标记序列匹配的DTW距离算法是指对原始数据R和待分析数据X分别进行关键特征形状的提取和标记，在关键标记特征序列中进行形状匹配，筛选与原始数据形状近似的候选子序列集合。计算筛选出候选子序列集合的DTW距离相似度，最终获得与原始数据序列相似度最高的子序列。

相似性搜索算法如下：通过对原始数据R和待分析数据X进行特征提取和预标记算法，获得原始特征序列R′、原始标记序列R′l、待分析特征序列X′和待分析标记序列X′l。同时构建一个大小为k的堆U，ui≤u2i且ui≤u2i+1，i=1…k.

对于X′l中，逐个计算与R′l匹配的序列f，对每一个与f时间轴同步的序列段X′f与R′进行DTW距离相似度计算v，并使uk=v，自上向下更新U。

参照U中的相似度，从而得到与待分析数据序列最相似的k个子序列（C1，C2，…，Ck）。

在时间序列相似性搜索时，基于分段DTW的算法代价为cssc-sc+1=ss-s+c，c为分段的平均长度，s为分段待分析序列长度，s为分段原始序列长度，该算法的复杂度为Ο（ss）。但是基于序列形状特征和标记的DTW距离方法的复杂度为Ο（′′fm），′为原始数据特征序列长度，f为待相似子序列的平均长度，m为待相似序列的个数。假设时间序列数据的压缩率相同，′=′s且′=s，则′′fm≤′′=ss。因此，本文提出的基于形状特征和标记的DTW距离算法比分段DTW距离算法的复杂度更低。

3实验验证

本文在海洋平台长时间监测的数据库中，选取9月19-25日一周的惯导系统传感器数据。由于海洋环境和平台本身的因素，平台自身存在一定规律的晃动和移动，而平台上安装的惯导系统传感器所测量的平台横纵摇两项关键平台姿态数据呈现一定的跳动规律。该传感器的工作频率为30HZ，选取一周的惯导数据作为待分析数据序列，设定两种算法的数据压缩率都为90%，对以上数据，利用本文提出的搜索算法和分段DTW距离算法进行实验对比分析。

3.1实例验证与相似度比较

在海洋平台数据中实际应用了该算法，经过算法应用进行相似性查询，获得了20、25日的最佳相似时间序列（见图3）。

针对搜索算法计算出的Top平均相似度，本文对两种算法进行了比较，如图4。共有7组平均相似度数据，基于分段DTW搜索算法的平均相似距离为0.20～0.34，而基于形状特征和标记的搜索算法的平均相似度为0.15～0.29，平均相似度整体提高约15%，从而证实本文相似性搜索算法具备更高的相似度。

3.2相似性序列筛选个数比较

为比较两种算法在同一相似性距离阈值下筛选出的相似性子序列个数，本文首先预设阈值1.0，图5展示了在同样的数据样本上对两种对比算法进行相似性序列集合个数的对比结果。可以得出本文的搜索算法明显要优于分段DTW算法。

3.3运行效率对比

通过对比本文搜索算法和分段DTW算法分别被预处理后实际搜索的执行时间和效率，得出本文的DTW相似性搜索算法平均执行时间更优的结论，进一步验证了算法复杂度结果。

4结语

针对DTW距离相似性计算算法复杂度过高和分段思想比较容易丢失特征的弊端，本文提出了基于形状特征和标记的DTW相似性搜索算法。该方法通过提取和标记原始数据序列的特征序列，对快速获取的相似子序列集合进行DTW距离计算，既可以保留原始数据特征完整，也可以提高相似性计算效率。并且基于大量真实的海洋平台监测数据，利用本文算法与分段的DTW距离算法进行多种性能比较实验，实验结果说明，本文提出的相似性搜索算法既可在计算效率上大大提高，也具备较高相似性准确度，该算法和研究还为今后海洋平台监测数据的相似性研究提供了新的方法和思路。

参考文献参考文献：

[1]FU T C.A review on time series data mining[J]. Engineering Applications of Artificial Intelligence，2011，24（1）：164181.

[2]MARTIN S， HANNES O， JOSEF J， et al. Trendbased similarity search in timeseries data[C].Advances in Databases Knowledge and Data Applications， Second International Conference on IEEE，2010：97106.

[3]SERR J， ARCOS J L. An empirical evaluation of similarity measures for time series classification[J].Knowledgebased Systems，2014，67（3）：305314.