基于导数序列的时间序列同构关系发现

邹蕾　高学东

摘要：

时间序列子序列匹配作为时间序列检索、聚类、分类、异常监测等挖掘任务的基础被广泛研究。但传统的时间序列子序列匹配都是对精确相同或近似相同的模式进行匹配，为此定义了一种全新的具有相似发展趋势的序列模式——时间序列同构关系，经过数学推导给出了时间序列同构关系判定的法则，并基于此提出了同构关系时间序列片段发现的算法。该算法首先对原始时间序列进行预处理，然后分段拟合后对各时间序列分段进行同构关系判定。针对现实背景数据难以满足理论约束的问题，通过定义一个同构关系容忍度参数使实际时间序列数据的同构关系挖掘成为可能。实验结果表明，该算法能有效挖掘出满足同构关系的时间序列片段。

关键词：

时间序列；数据挖掘；子序列匹配；分段；模式发现

中图分类号：

C931.6TP301.6

文献标志码：A

Abstract：

As the basis of time series data mining tasks， such as indexing， clustering， classification， and anomaly detection， subsequence matching has been researched widely. Since the traditional time series subsequence matching only aims at matching the exactly same or approximately same patterns， a new sequence pattern with similar tendency， called time series homogeneous pattern， was defined. With mathematical derivation， the time series homogeneous pattern judgment rules were given， and an algorithm on time series homogeneous pattern discovery was proposed based on those rules. Firstly， the raw time series were preprocessed. Secondly， the homogeneous patterns were matched with segmentation and fitting subsequences. Since practical data can not satisfy the theoretical constraints， a parameter of homogeneous pattern tolerance was defined to make it possible for the practical data homogeneous patterns mining. The experimental results show that the proposed algorithm can effectively mine the time series homogeneous patterns.

英文關键词Key words：

time series； data mining； subsequence matching； segmentation； pattern discovery

0引言

时间序列数据挖掘的主要任务包括相似性检索、聚类、分类、模式发现、异常监测等，其中模式发现又分为序列模式发现、有趣模式发现、周期模式挖掘、异常模式发现等。序列模式发现最早由Agrawal等[1]提出，算法的输入是一系列序列数据集，算法的目标是找到满足用户定义的最小支持度的所有频繁序列模式；有趣模式发现[2]是指发现满足用户事先预期的、存在特定规律的模式行为；周期模式发现[3-7]根据周期特征的不同，分为完全周期模式挖掘、部分周期模式挖掘、同步周期模式挖掘、异步周期模式挖掘、近似周期模式挖掘等；异常模式发现[8]是指找出发生频率远不同于先前预期的模式行为。

已有的时间序列模式发现技术都是通过挖掘完全相同的序列模式，基于已知序列模式训练集的趋势从而进行未知序列模式的趋势预测。但现实的时间序列数据中，往往很难找到完全相同的时间序列模式，却存在类似发展趋势的时间序列模式。比如，各个国家钢铁产量时间序列、不同病人的心电图序列、不同地区降水量序列等，以上序列间虽不一定存在完全相同的序列模式，但由于内在的发展规律一致性，很可能存在同比发展趋势的序列模式。因此，如果能挖掘出有效的同比发展趋势的序列模式（如图1）也可以用于时间序列趋势预测。

本文基于以上问题定义了一种宽泛的时间序列相似关系，即时间序列同构关系。本文提出的时间序列同构关系与传统数据挖掘中的时间序列相似关系的区别在于：一是时间

序列的相似关系要求待比较序列间形状精确相同或近似相同，而本文提出的时间序列同构关系要求时间序列的变化趋势相似，因此，同构关系是一种更宽泛的相似关系；二是时间序列相似性度量需经过距离度量与主观设置的相似性阈值进行比较从而判定待比较时间序列是否相似，具有一定的主观性，而时间序列同构关系判定通过曲线间导数关系直接判断时间序列是否满足同构关系。

1本文后续章节的主要内容如下：第一章给出了时间序列同构关系的具体概念，并经过数学推导给出了同构关系判定的法则；第二章给出了具体的时间序列同构关系发现算法的步骤；第三章通过一个模拟手写签名曲线验证了本文算法对时间序列同构关系发现的有效性；最后一章是本文的结论部分。时间序列同构关系基本概念

时间序列同构关系具体概念

1.1时间序列

时间序列是由记录值和记录时间组成的元素的有序集合，记为X={x1=（v1，t1），x2=（v2，t2），…，xn=（vn，tn）}，元素xi=（vi，ti）表示时间序列在时刻ti的记录值为vi，记录时间是严格增加的（i

1.2时间序列关键点

时间序列关键点[10]即包含时间序列重要分段信息的点，比如极值点、拐点、最值点等，本文以极值点作为时间序列分段的关键点。

2.1时间序列数据预处理

由于原始时间序列可能波动过于频繁，如果对原始时间序列直接按极值点分段，则各分段时间区间过短，也难以形成趋势。因此，在数据预处理阶段首先对原始时间序列数据进行平滑预处理。本文采用平滑滤波[11]技术，平滑滤波技术是低频增强的空间域滤波技术。它的目的有两个：一个是模糊，一个是消除噪声。空间域的平滑滤波一般采用简单平均法进行，与滑动窗口平均法类似，不同的是，各个元素在平均时所占权重不同。

2.2时间序列分段同构关系发现

本文定义两时间序列同构时需满足两时间序列导数序列任意对应点处导数比相等，即两时间序列拟合后的多项式系数满足1.5节中定义的比例关系时，则认为两时间序列同构。由于在实际时间序列数据中，保证各多项式系数同时满足1.5节中定义的比例关系的条件较苛刻，可能很难达到，导致挖掘不出存在同构关系的时间序列分段。因此，为使算法可行，本文设置一个同构关系容忍度参数μ，当aibi∈[pωi-112（1-μ），pωi-112（1+μ）]（i∈[1，k]）时，也可认为两时间序列分段近似存在同构关系。

其中，在对各同构时间序列片段聚类时，由于严同构的时间序列片段间拟合多项式系数比严格满足比例关系，因此，各时间序列片段间的同构关系具有传递性。而对于宽同构的时间序列片段而言，由于各时间序列片段间拟合多项式系数比不严格满足比例关系，可能导致时间序列片段1与时间序列片段4间近似满足比例关系，时间序列片段1同时与时间序列片段7近似满足比例关系，但时间序列片段4与时间序列片段7间却不满足宽松比例关系，而无法聚到一个宽同构时间序列片段类。但本文定义当出现上述情况时，只要待聚类时间序列片段与已有类中任意时间序列片段存在宽同构关系，即认为该时间序列片段可聚到当前类中。因此，上述时间序列片段1、4、7可聚为一个宽同构时间序列片段类。

算法1时间序列同构关系发现。

输入：原始时间序列；

参数：同构关系容忍度μ；

输出：同构关系的时间序列片段。

步骤1原始时间序列平滑预处理，并按极值点进行分段。

步骤2对各时间序列片段进行最小二乘拟合，并记录各拟合多项式系数。

步骤3从第一个时间序列片段集中顺次取出一个时间序列片段，并将其从原时间序列片段集中删除，依次计算其与第二个时间序列片段集中各片段的拟合多项式对應项系数比。

步骤4如果拟合多项式对应项系数比满足1.5节中定义的比例关系，则将满足同构关系定义的原始时间序列片段放入同一同构时间序列片段类中；若与第二个时间序列片段

集中任意时间序列片段都不满足同构关系，则放入两个同构时间序列类。

步骤5若第一个时间序列片段集非空，顺次取出一个时间序列片段，并将其从原时间序列片段集中删除，依次与已有同构关系时间序列片段类中任一元素计算其拟合多项式对应项系数比，若与其中任一时间序列片段满足1.5节中定义的比例关系，则将该时间序列放入相应的同构关系时间序列类中。否则，依次与第二个时间序列片段集元素判断是否满足同构关系，若满足，则聚成一个同构关系时间序列片段类；否则，新生成一个时间序列片段类。重复步骤5直到第一个时间序列片段集为空。

步骤6算法结束，输出各同构关系时间序列片段类。

以图2为例，对序列1和2分别平滑预处理后按照极值点进行分段，序列1可分为7段，序列2可分为4段；因此，为了分段更明显，可以在原有曲线各分段上对应标上编号1～7（序列1）及1～4（序列2）；然后对各分段进行同构关系判定；最终发现序列1前4分段构成的子序列与序列2满足同构关系。

3实验分析

本文算法可以用于时间序列子序列匹配、手写签名识别、心电图异常检测等问题，其中，时间序列子序列匹配又可以作为时间序列聚类、分类、预测等的基础。由于以往的研究中没有涉及对时间序列同构关系发现的研究，因此，本文实验不设对比实验，仅通过一组模拟手写签名曲线匹配验证本文算法的合理性。

3.1实验参数说明

1）拟合多项式次数选择。

由于本文对原始时间序列进行平滑滤波处理后基于极值点进行分段，因此同一分段内曲线是单调变化的，基于这一特性，本文选择三次多项式对各分段进行最小二乘拟合。

2）同构关系容忍度参数。

由于实际背景的时间序列数据难以挖掘出有意义的同构关系时间序列片段，因此，有必要定义一个同构关系容忍度参数。经过多次实验，本文取同构关系容忍度参数为0.1，针对不同问题同构关系容忍度参数将根据具体情况而定。

3.2实验结果分析

采用本文算法对图3所示的两条模拟手写签名曲线进行匹配结果如下。对如图3所示序列1和2，由于两条曲线时间区间长度不同，因此，无法用传统的欧氏距离进行曲线间距离度量，而动态时间弯曲（Dynamic Time Warping， DTW）距离也难以得出两条曲线相似的结论；现有学者提出的基于相似性变换[12]、遗传算法[13]、演化计算[14-15]等的方法计算复杂性较大，【；采用本文算法后，图3中所示两条曲线的加粗部分均满足同构关系，因此，两条签名曲线可认为近似同构。因此本文算法通过比较导数直接判定两条曲线的关系，大大降低了问题的复杂性。实验结果如图3所示，两条曲线的加粗部分对应同构，两条签名曲线可认为满足宽同构关系。

4结语

本文针对时间序列子序列匹配问题，定义了一种全新的时间序列同构关系模式，并提出了有效的算法以实现对时间序列片段同构关系的挖掘。同时，针对实际背景数据难以满足理论约束时，通过定义一个同构关系容忍度参数，有效解决了宽同构关系时间序列片段的匹配问题。但针对时间序列同构关系模式的聚类、分类等问题的研究以及对时间序列同构关系模式的拓展应用仍有待于进一步研究。

参考文献：

[1]

AGRAWAL R， SRIKANT R. Mining sequential patterns [C]// ICDE 95： Proceedings of the 11th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 1995： 3-14.

[2]

FRADKIN D， MRCHEN F. Mining sequential patterns for classification [J]. Knowledge and Information Systems， 2015， 45（3）： 731-749.

[2]

RATANAMAHATANA C A， LIN J， GUNOPULOS D， et al. Data Mining and Knowledge Discovery Handbook [M]. Berlin： Springer， 2005： 1069-1103.

[3]

HAN J， DONG G， YIN Y. Efficient mining of partial periodic patterns in time series database [C]// Proceedings of the 1999 15th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 1999： 106-115.

[4]

SIRISHA G N V G， SHASHI M， RAJU G V P. Periodic pattern miningalgorithms and applications [J]. Global Journal of Computer Science and Technology， 2013， 13（13）： 18-28.

SIRISHA G N V G， SHASHI M， RAJU G V P. Periodic pattern mining—algorithms and applications [EB/OL]. [20151204]. http：//globaljournals.org/GJCST_Volume13/4PeriodicPatternMiningAlgorithms.pdf.

[5]

YU X， YU H. An asynchronous periodic sequential patterns mining algorithm with multiple minimum item supports [C]// Proceedings of the 2014 9th International Conference on P2P， Parallel， Grid， Cloud and Internet Computing. Washington， DC： IEEE Computer Society， 2014： 274-281.

[6]

董曉莉.时间序列数据挖掘相似性度量和周期模式挖掘研究[D].天津：天津大学，2007：20-25.（DONG X L. Similarity measure and periodic pattern mining of time series data mining [D]. Tianjin： Tianjin University， 2007： 20-25.）

[7]

AMIR A， APOSTOLICO A， EISENBERG E， et al. Detecting approximate periodic patterns [C]// Proceedings of the 1st Mediterranean Conference on Design and Analysis of Algorithms. Berlin： Springer， 2012： 1-12.

[8]

YANG J， WANG W， YU P S. Mining surprising periodic patterns [J]. Data Mining and Knowledge Discovery， 2004， 9（2）： 189-216.

[9]

肖辉.时间序列的相似性查询与异常检测[D].上海：复旦大学，2005：13.（XIAO H. Similarity search and outlier detection in time series [D]. Shanghai： Fudan University， 2005： 13.）

[10]

刘芬，郭躬德.基于符号化聚合近似的时间序列相似性复合度量方法[J].计算机应用，2013，33（1）：192-198.（LIU F， GUO G D. Composite metric method for time series similarity measurement based on symbolic aggregate approximation [J]. Journal of Computer Applications， 2013， 33（1）： 192-198.）