0 引言

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

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

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

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

时间序列是由记录值和记录时间组成的元素的有序集合，记为X={x₁=(v₁, t₁), x₂=(v₂, t₂), …, x_n=(v_n, t_n)}, 元素x_i=(v_i, t_i)表示时间序列在时刻ti的记录值为v_i，记录时间是严格增加的(i < j ⇔ t_i < t_j)^[9]。

1.2 时间序列关键点

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

1.3 时间序列区间长度比

假设时间序列y_α的时间区间为[t_i, t_j]，时间序列y_β的时间区间为[t_m, t_n]，则时间序列y_α对时间序列y_β的区间长度比ω定义为：ω_αβ=(t_j-t_i)/(t_n-t_m)。假设时间序列y_α的任意一点为x，则时间序列y_β上的对应点X满足：x-t_i=ω_αβ(X-t_m)，即：

$ X = \frac{1}{{{\omega _{\alpha \beta }}}}x + \left( {{t_m} - \frac{1}{{{\omega _{\alpha \beta }}}}{t_i}} \right). $

1.4 时间序列导数序列

对原时间序列最小二乘拟合后得到的多项式函数对时间t求导，得到的序列即为时间序列的导数序列。

1.5 时间序列同构

若两时间序列导数序列任意对应点处导数比相等，则认为两时间序列同构。

假设两时间序列最小二乘拟合后，分别表示为：

$ \begin{gathered} {y_1} = {a_n}{x^n} + {a_{n - 1}}{x^{n - 1}} + \cdots + {a_1}x + {a_0};x \in \left[ {{t_i},{t_j}} \right] \hfill \\ {y_2} = {b_n}{x^n} + {b_{n - 1}}{x^{n - 1}} + \cdots + {b_1}x + {b_0};x \in \left[ {{t_m},{t_n}} \right] \hfill \\ \end{gathered} $

则导数序列分别表示为：

$ \begin{gathered} {y_1} = n{a_n}{x^{n - 1}} + \left( {n - 1} \right){a_{n - 1}}{x^{n - 2}} + \cdots + {a_1};x \in \left[ {{t_i},{t_j}} \right] \hfill \\ {y_1} = n{b_n}{x^{n - 1}} + \left( {n - 1} \right){b_{n - 1}}{x^{n - 2}} + \cdots + {b_1};x \in \left[ {{t_i},{t_j}} \right] \hfill \\ \end{gathered} $

则时间序列区间比ω₁₂=(t_j-t_i)/(t_n-t_m)，设两时间序列导数序列对应点处导数比，即同构比相等为p，则为保证两时间序列导数序列任意对应点处导数比相等，需满足：

$ {a_n}\omega _{12}^{n - 1} = p{b_n},{a_{n - 1}}\omega _{12}^{n - 2} = p{b_{n - 1}}, \cdots ,{a_1} = p{b_1} $

变形后表示为：

$ \frac{{{a_n}}}{{{b_n}}} = \frac{p}{{\omega _{12}^{n - 1}}},\frac{{{a_{n - 1}}}}{{{b_{n - 1}}}} = \frac{p}{{\omega _{12}^{n - 2}}}, \cdots ,\frac{{{a_1}}}{{{b_1}}} = p $

因此，验证两导数序列是否同构时，只需比较两时间序列拟合后的多项式系数是否满足上述比例关系，若满足，则认为两时间序列同构。

2 时间序列同构关系发现

给定时间序列X如下：

$ X = \left\{ {{x_1} = \left( {{v_1},{t_1}} \right),{x_2} = \left( {{v_2},{t_2}} \right), \cdots ,{x_n} = \left( {{v_n},{t_n}} \right)} \right\} $

则时间序列X的同构关系发现算法基本思想如下：首先，对原始时间序列进行分段；然后，对各分段进行最小二乘拟合；最后，对各分段进行同构关系挖掘。

2.1 时间序列数据预处理

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

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

本文定义两时间序列同构时需满足两时间序列导数序列任意对应点处导数比相等，即两时间序列拟合后的多项式系数满足1.5节中定义的比例关系时，则认为两时间序列同构。由于在实际时间序列数据中，保证各多项式系数同时满足1.5节中定义的比例关系的条件较苛刻，可能很难达到，导致挖掘不出存在同构关系的时间序列分段。因此，为使算法可行，本文设置一个同构关系容忍度参数μ，当$\frac{{{a_i}}}{{{b_i}}} \in \left[ {\frac{p}{{\omega _{12}^{i - 1}}}\left( {1 - \mu } \right),\frac{p}{{\omega _{12}^{i - 2}}}\left( {1 + \mu } \right)} \right]\left( {i \in \left[ {1,k} \right]} \right)$时，也可认为两时间序列分段近似存在同构关系。

其中，在对各同构时间序列片段聚类时，由于严同构的时间序列片段间拟合多项式系数比严格满足比例关系，因此，各时间序列片段间的同构关系具有传递性。而对于宽同构的时间序列片段而言，由于各时间序列片段间拟合多项式系数比不严格满足比例关系，可能导致时间序列片段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前4分段构成的子序列与序列2满足同构关系。

3 实验分析

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

3.1 实验参数说明

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

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

3.2 实验结果分析

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

4 结语

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