基于双曲正切函数约束的时间序列建模表示

曹洋洋，林 意，王智博，毕小红

江南大学 数字媒体学院，江苏 无锡 214122

1 引言

时间序列的数据挖掘是从大量时间序列数据中发现有价值的规律性的算法和实现的技术，广泛应用于经济、科学、工业等诸多领域[1-2]。但由于时间序列数据具有海量性，短期波动，噪声大等特点，直接在原始时间序列上进行相似性查询[3-4]、聚类[5-6]、模式挖掘[7-8]等不仅存储和计算效率低而且影响算法的准确性和可靠性，难以取得满意的效果。因此，数据的高级表示[9]是有效并高效的解决问题的关键。常见的时间序列降维方法包括傅里叶变换[10]、奇异值分解（SVD）[11]、符号映射[12]等，与此同时，许多研究人员忽略时间序列的细节变化，提出了线性表示来描述时间序列的主要特征，本文主要研究最常用的时间序列表示方法PLR。

PLR[13]方法是指将长度为n的时间序列用k个直线段近似表示。PLR中的分段数决定了原始时间序列的大致粒度，由于拟合误差与压缩率呈现反相关的关系，如何在考虑序列的时间特性确定合理分段数的基础上选择适当的分段点以保证拟合误差在合理的范围下压缩率尽可能低是分段问题的重点。目前已有的PLR算法大体上分为：（1）自定义分段数算法，如文献[14]提出了多尺度时间序列固定分段数线性表示方法（PLR_BTBU）。（2）自定义拟合误差算法，如滑动窗口（SW）、自底向上（BU）和自顶向下（TD）[15]。（3）选择有代表性的分段点的算法，如趋势转折点[16]、重要点[17]以及导数突变点[18]等来近似表示时间序列的算法。由于分段后k通常比n小得多，降维后的序列使得数据的存储、传输和计算效率有明显的提高。但应用于不同领域的时间序列数据往往具有明显的数据特征的差异，同一时间序列在不同的时间段所呈现的数据特征也不相同，传统的分段方法忽略了时间序列的时间特性和不断增长的性质，得到的分段结果不够精确，影响时间序列相似性度量和之后的预测工作。

文献[19]和[20]分别独立地提出了时间序列分段聚合近似算法。由于该算法简单直观，支持任意长度的时间序列的相似性查询、所有的Minkowski度量以及加权欧氏距离，而且能够用于索引提高查询效率，因此该算法具有通用性和普遍性，Keogh等人的实验结果表明将PAA方法用于时间序列的索引时，查询效率比DFT表示方法提高了1～2个数量级[19]，而且能够用于加权欧几里德距离的计算。虽然Keogh和Yi等人提出的PAA方法能够有效地划分时间序列，对时间序列进行降维，但是在时间序列数据不断增长的过程中，不同区段的时间序列数据对当前时间区段数据的影响是不同的，在当前时间序列区段的左端，越靠右的区段对当前时间序列段的影响越大，对时间序列的预测的参考价值越大。而靠左的区段施加的影响较小，对时间序列预测的参考价值也越小，所以在对时间序列进行分段时引入不同区段的时间影响因素是有必要的，但PAA对时间序列进行分段时，用均值来表示不同区段的数据，在计算不同区段数据的距离时同等对待，没有考虑时间序列特有的时间性质。王元珍[21]等考虑了时间序列的时间特性，提出一种PAA的改进方法RPAA，该方法将时间影响因子应用到时间序列的分段中，但RPAA方法将滑动窗口首先作用在时间序列的尾端，然后沿着时间轴逆方向以步长为w的大小移动，计算各区段的均值以及相应的影响因子，这使得RPAA不能满足动态增长的时间序列分段的需求，不能实时在线划分时间序列，对于时间序列数据实际情况是不利的。

针对上述的不足，文章结合PAA算法满足动态增长的时间序列的分段要求的优点，在RPAA算法的启发下提出了基于时间约束滑动窗口的分段线性表示算法（HTFPAA），由于时间序列的时间特性较为复杂，任何模型都不能真正反应序列时间的真实性能。于是在时间的非线性特征尚不十分清楚的情况下，可采用任何计算方便且行之有效地简化数学模型或物理模型来描述时间的非线性特征。因此HTFPAA算法构造了一种新的时间非线性模型，在考虑时间序列不断增长并且与时间高度相关的特性的基础上，引入的双曲正切函数，可以有效度量随着时间推移当前序列对后继时间序列段的影响，并且该方法继承了PAA支持时间序列在线划分的优点，函数模型形式简单，物理意义明确，且参数少，只需记录当前分段的位置，有利于数值及编程实现。大量的实验结果表明与其他PLR算法在相同的压缩率下进行比较，该算法能够得到更小的拟合误差和更好的分类聚类性能。

2 PAA和RPAA分段表示方法

2.1 相关定义

定义1（时间序列）给定一个属性集X，时间序列是由记录时间t和记录值Xi组成的有序集合：对于给定的时间序列，有限时间集为T、非空状态属性集A=及其对应值域Daj。

定义2（时间序列长度）对于有限长的时间序列X=x1,x2,…,xn，X的长度为组成时间序列X的实数的个数，记为|X |，即，对于无限长的时间序列，X的长度定义为文章主要讨论有限长时间序列的分段方法。

定义3（时间序列子序列段）给定长度为n的时间序列X,X的子序列段s是在X中从点xi开始，数量为w(1

定义4（滑动窗口）给定长度为n的时间序列X和一个用户自定义的区域长度w(1≤w≤n),X的所有子序列矩阵s可以通过在X上定义一个宽度为w的窗口，将每一个区段s放入s的第s行得到，s的大小为(n-w+1)×w，w为滑动窗口的大小。

2.2 PAA算法及问题描述

Keogh和Yi等人分别独立地提出了时间序列PAA表示算法，当使用PAA进行时间序列降维时，首先将长度为n的时间序列分成N个大小相同的帧，滑动窗口放在原始序列S的前端，然后沿着时间轴以w个步长移动，计算每个宽度为w的帧中数据点的平均值，并按照原始时间表的方向构成索引向量表示原始时间序列。 在N(1≤N≤n)维空间中将长度为n的时间序列S 表示为向量，其中第 i(1≤i≤N)元素计算为：

当N=n时向量表示即为原时间序列；N=1时向量表示原时间序列的均值。

PAA支持时间序列的在线划分，但由于忽略了不同区段帧的时间特性对于时间序列数据后续区段的影响是不同的，靠近当前区段的时间段的对当前区段的影响较大，远离当前区段的时间影响较小，序列划分不够精确，进而影响到序列的相似性度量以及预测的准确性，导致后续数据挖掘工作出现较大的误差。

2.3 RPAA算法及问题描述

王元珍等人[21]考虑了时间序列的时间特征，通过在PAA线性分段方法基础上引入影响因子ρ（其中0≤ρ≤1）提出了RPAA算法，为了避免加入影响因子后，这种按照时间轴方向的运算必须每次都计算当前区段与最后区段的位置距离(j-i)而导致ρj-i的多次重复计算，该方法首先将滑动窗口放置在时间序列X的末尾，然后沿时间轴的逆方向以w大小的步长移动并计算各个窗口（大小为w）内帧的平均值和相应的函数影响系数，公式为：

由于滑动窗口从原始时间序列的末尾逆向移动，势必导致RPAA算法无法实现时间序列的在线划分，不适用于动态增长的时间序列数据流和在线时间序列的划分。

2.4 欧几里德距离

欧几里德距离广泛应用于时间序列距离计算中，给定长度为n的时间序列C=c1,c2,…,cn和Q=q1,q2,…,qn，则C和Q之间的欧几里德距离为：

为了防止递加数过多，导致欧几里德距离过大，可以计算加权的欧几里德距离：

由于函数 f(x)=x2单调，所以在实际计算中，可以计算平方后的加权欧几里德距离：

PAA支持平方后的加权欧几里德距离的计算，将一个查询Q降维表示为：

则此时计算PAA表示平方后的欧几里德距离为：

3 时间序列的HTFPAA算法

3.1 时间序列的HTFPAA表示算法

考虑到时间序列不同区段间的影响，文章引入移动增强因子的概念，定义如下。

定义5（移动增强因子）移动增强因子g(x)是取值范围为[0，1]并且单调递增的函数。函数的意义为两相邻区段中前序时间区段对后继时间区段影响的量化值。

文中引入了双曲正切函数g(x)=tanh(x)=(ex-e-x)/(ex+e-x)(0≤x)（如图1）为移动增强因子。此函数关于原点（0，0）中心对称的，在对称的水平渐近线 y=1和y=-1处收敛，在定义域内有连续的导数，当x≥0时，g(x)∈(0,1)且g(x)在定义域的范围内单调递增，有较快的收敛速度又有较高的收敛精度，满足移动增强因子的条件。并且由图1可知，该函数的形状符合序列的时间特性并且函数的有界性满足时间窗的基本要求，因此可将双曲正切函数引入到时间序列分段聚合近似中。

图1 双曲正切函数图像

函数证明如下：

（1）当 x≥0时，双曲正切函数的函数值是（0，1），证明如下：

因此，当x→∞时，ex→∞则

（2）当x≥0时，双曲正切函数单调递增，证明如下：

首先对双曲正切函数求导：

由于时间序列是一维的并且随着时间的增长具有不可逆转性，所以只有前序数据对于后继数据施加影响，反之并不成立。

RPAA考虑了序列的时间特性但不支持时间序列的在线划分，PAA则恰好相反，因此文章受RPAA算法的启发，在时间序列PAA分段中引入双曲正切函数，不仅适用于动态增长的时间序列，而且兼顾了序列的时间特性，不会顾此失彼。

HTFPAA算法计算索引时首先将滑动窗口置于原始时间序列S的前端，然后沿着时间轴方向移动，计算各个窗口的平均值和g(x)的乘积，按照时间轴的方向组成索引向量，此时

同时也可如RPAA方法首先将滑动窗口置于时间序列末端，公式为：

HTFPAA算法支持序列的双向划分。算法步骤如下：

输入：长度为n的时间序列数据S=s1,s2,…,sn，滑动窗口的大小为w(1

输出：时间序列S的HTFPAA表示。

（1）用N=[n/w]计算时间序列总分段数，最后一段不足w，则所有数据作为一段。

（2）分段后的HTFPAA向量为S′=ϕ。

（3）循环计算不同时间序列段的影响因子：

（5）返回 S′。

3.2 距离计算

欧几里德距离是欧式空间中评定个体间差异大小的一种测度，其计算相似度是所有相似度计算里面最简单、最易理解的方法。HTFPAA算法中时间序列的距离计算仍然可以使用平方后加权欧几里德距离，不影响后续度量的准确性并且在机器学习社区中众所周知，加入的双曲正切函数作为权重可以大大提高分类精度，公式如下：

3.3 满足下界定理

对原始数据进行降维处理后，在索引空间的查找可能出现错查和漏查两类问题。

错查：在索引空间中的两点距离小于给定的阈值ε，但在原始数据中该两点的距离大于ε，即

对序列点出现错查的情况，一般通过对索引空间中的查询结果再次到原始数据空间中查询，剔除其中的D(si,sj)≥ε的点来解决。由于在索引空间中查询的结果只保留了原时间序列数据集合中一个很小的子集，所以再次在原始空间中查询不会耗费太多CPU运行时间。

漏查：在原始数据中两点距离小于给定的阈值ε，但在索引空间中该两点的距离却大于ε，即。

序列点的漏查问题则决定了是否能够对序列进行有效的相似性查找，为了能够解决这个问题，Faloutsos[23]给出维度下限下界定理，即 Dindex(C,Q)≤D(C,Q)。

证明HTFPAA算法满足下界定理。

证明由0

又

根据上面的证明得出DHTFPAA(C,Q)针对DPAA(C,Q)满足下界定理，又由于DPAA(C,Q)满足欧几里德距离的下界定理，因此得出DHTFPAA(C,Q)满足欧几里德距离的下界定理，得证。

4 实验

4.1 实验数据和平台

实验使用UCR数据集[24]以及Datamarket中的Time series Data Library提供的来自不同领域的数据集，与现有的分段算法在拟合误差，分类聚类性能上比较，评估HTFPAA算法的有效性。数据集长短不一并且充分考虑到序列中易出现小幅度波动数据和突变数据的情况，具有较好的广泛性和代表性。数据集的相关信息以及本文的实验平台如表1～表3所示。

表1 UCR数据集

4.2 拟合误差的比较

对Time series中的数据分别用HTFPAA算法与基于PAA的分段线性表示算法，基于时间特性的时间序列建模表示算法（RPAA）以及基于自适应窗口的分段线性表示算法（AW）[25]进行分段，比较各算法下数据近似质量。由于任何方法都可以通过改变参数改善拟合质量，为了公平起见，控制在压缩率相同的情况下比较各算法的拟合误差，拟合误差越小，算法的拟合效果越好。由于实验选自不同领域的数据集，取值范围相差较大，为了方便比较，首先将数据归一化处理，归一化公式为：

表2 Time series数据集

表3 实验平台

由于固定滑动窗口算法本身的特点，其压缩率只能是(1-1/w)×100%，参数w为正整数。4种PLR分段算法在同一压缩率下（文章取w=5即压缩率为80%），实验结果如表4所示。

表4 80%压缩率时几种PLR表示的拟合误差

表4中下划线并且加粗的数据表示该行中拟合误差的最小值。可以看出HTFPAA算法在7条时间序列上具有较小的拟合误差；而在其他3条时间序列上HTFPAA算法的拟合误差也接近最小值。而且从拟合误差的平均值来看，HTFPAA算法拟合误差的平均值远远小于其他3种算法，实验结果表明，HTFPAA算法在10条数据集上的拟合误差都比较小，算法有良好的适应性。

对上述拟合误差实验中表现较好的7条序列，考虑压缩率分别设置为75%、80%、85%、90%、95%时，HTFPAA分段算法拟合误差的大小以及趋势走向，结果如图2所示。

图2 4个数据集上拟合误差的趋势

从图2可以看出，HTFPAA分段算法在各数据集上的拟合误差都呈增加趋势，并且上升趋势大致相近。

表1中只有PAA算法、RPAA算法在某些数据分段上拟合质量优于HTFPAA。因此对Time series数据中较长的4条时间序列，分别考察压缩率为75%、80%、85%、90%、95%时PAA、RPAA与HTFPAA方法的拟合误差。实验结果如图3所示。

图3 3种分段方法不同压缩率下的拟合误差

由图3对比分析可知，与RPAA方法、PAA方法相比，本文所提方法的拟合误差在4条时间序列数据集上一直都是3种方法中拟合误差最小的，而且随着压缩率的提高，拟合误差增长比较平稳。通过数据集横向和纵向拟合误差的比较，说明了该算法在不同类型的时间序列上拟合效果有着较强的可靠性和稳定性。

4.3 分类效果对比实验

4.3.1分类效果评价标准

序列分类的准确率直接受分段结果准确率的影响，文中使用错误率作为分类效果的评价指标，错误率越小，分类效果越好，否则，分类效果越差。分类错误率定义如下：

错误率=（错误分类的数量/真实类别数）×100%

4.3.2 分类实验及耗时比较

为了进一步证明HTFPAA算法的可行性和优越性，对HTFPAA和分段聚合近似（PAA）、基于时间特性的时间序列建模（RPAA）算法进行分类实验，观察比较各算法的分类结果。利用HTFPAA和经典分段算法对测试集中的测试序列在训练集中查找最相似即欧几里德距离最小的序列实现最近邻分类，并通过判断测试序列与最相似序列标签的一致性度量分类效果的好坏，评估各算法的分段效果，同时记录各算法在对不同数据集分类时平均占用的CPU时间，实验结果如表5所示。

表5 算法的实验结果

表5中下划线并且加粗的数据表示各个算法在该数据集上错误率最小的实验结果。从表5中不难看出，HTFPAA算法在大部分数据集中分类错误率普遍较低，其中在Face（four）数据集上的错误率也接近最小值，错误率的平均值也是3个算法中最小的，说明该方法可以更准确地对时间序列进行索引，具有较好的学习效果。同时，由于PAA算法不考虑序列的时间特性只需计算各个窗口内数据的均值，因此在各个数据集上平均消耗时间最少，RPAA与HTFPAA算法占用的CPU时间则不相上下，HTFPAA算法只比PAA运行速度略低8.9%，在可以接受的范围。

图4是在分类效果最好的Face（all）数据集中任选的一条时间序列采用HTFPAA算法的分段效果图，可以看出HTFPAA算法较好地反映了原始时间序列的趋势走向。

图4 HTFPAA分段效果图

4.4 序列聚类实验

4.4.1 聚类结果评价标准

给定的一组时间序列数据集聚类的真实结果为G=G1,G2,…,Gk，在某种分段方法的基础上得到的聚类的结果为Q=Q1,Q2,…,Qk，则用式（12）作为评价指标来评估聚类效果的优劣[26]。CPE(G,Q)越大时，说明采用某种方法得到的聚类结果越合理，反之，聚类效果越差，则说明该方法分段结果与原始时间序列相差越大。

4.4.2 聚类实验

在时间序列数据挖掘中，序列匹配是基本也是最重要的问题，针对全序列匹配，给定查询序列x，需要在指定的序列库中找到和x最相似的序列或者与x距离小于某个阈值E的所有序列，实验分别在PAA、RPAA以及文章所提到的HTFPAA算法分段的基础上进行聚类实验，比较三种分段算法在全序列匹配上的性能。

在表1中给出的数据集上进行聚类实验，计算相应的CPE的值，并在其中的一个数据中（文中采用Fish数据集）任意选择10条等长的时间序列数据，根据不同的类别标签K，在PAA、RPAA、HTFPAA基础上进行层次聚类，详细观察聚类结果。选择的10条数据中已知1～5有相同的类别标签6～10有相同的类别标签，聚类结果分别如表6和图5～图7所示。

表6 各个数据集中聚类性能比较

图5 PAA方法聚类结果

图6 RPAA方法聚类结果

图7 HTFPAA方法聚类结果

结果显示，HTFPAA算法在7条数据集上的聚类效果明显好于PAA以及RPAA算法，而在另外三条数据集上结果仅次于RPAA算法。图5～图7更加直观地显示算法的聚类结果，可见在进行数据挖掘时将序列的时间特性考虑在内，明显提高了序列的聚类质量。

4.5 实验小结

综合以上三个实验，可得出结论：由于HTFPAA算法不仅考虑了序列的时间性质，有拟合误差小、算法易于实现的优点，而且HTFPAA算法相比PAA算法，能够保持原始序列的形态特征和整体特性，以极小的时间代价获得更好的分类聚类效果。同时，HTFPAA算法时间复杂度为O(n)，具有较强的通用性、普适应和稳定性。

5 结束语

针对传统的时间序列分段算法往往忽略序列的时间特性，导致分段不够精确的问题，提出了基于双曲正切函数约束的时间序列建模表示算法HTFPAA。HTFPAA继承了PAA方法支持时间序列在线划分的优点而且能够满足RPAA方法支持时间序列分段时的时间特性，更加符合实际情况。实验结果表明HTFPAA方法能够比较准确地表示时间序列的整体特征，参数的引用在兼顾时间特性的同时更准确地描述时间序列动态变化的过程。但时间特性对序列走势的影响以及如何找到更加合适的函数描述时间这一特殊的变量是有待进一步研究的课题。