时间序列特征表示与相似性度量研究综述

孙冬璞，曲 丽

哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080

当今社会是一个数据信息爆炸的时代，时间序列作为其中一种普遍的数据类型，在日常生活中无处不在。如今已经成为数据挖掘领域[1]研究的主要方向，广泛应用于金融、气象、医学[2]、电子科技、教育、工业等多个领域。人们可以通过时间序列的历史数据挖掘出其中的潜在价值信息并预测未来趋势。简言之，时间序列是一组根据时间先后顺序不断变化的数列，如果直接对原时间序列进行处理，无法避免产生耗时长，时间复杂度高，成本高的问题。因此，选择一种简单的转换方式，将数据量大、动态性强、易受噪声干扰的高维密集型时间序列转换为低维离散型时间序列，发现不同时间序列之间的关系，探索其中的规律，达到降低研究成本的目的，就变得尤为重要。

特征表示是一种将数量冗长的高维时间序列映射到低维数据空间的常用方法，在提取局部特征信息仍然能够反映整体时间序列信息的前提下，过滤掉低频信息，既保证了时间序列的基本信息和形态特征，又有效地实现了数据降维去噪。这种方法为提高数据挖掘效率奠定了良好基础。

相似性度量作为数据挖掘领域另一个重要的过程，应用于大部分时间序列的预处理阶段。一般情况下，在对时间序列进行分类、聚类、回归分析之前，如果通过相似性度量发现序列之间的内在规律，筛选出重要的时间序列，对于提高数据挖掘的效率非常有利。针对不同类型的时间序列，采取合适的相似性度量方法能够更加客观地反映时间序列之间的关系。除了基于形状的相似性度量、基于模型的相似性度量方法和基于数据压缩的相似性度量方法外，常用的相似性度量方法还有兴趣模式发现、异常模式处理、序列可视化[3-5]等。

本文主要从时间序列的特征表示和相似性度量方面对目前时间序列的研究现状进行总结。

首先，针对时间序列特征表示方法，本文从非数据适应性方法、数据自适应性方法、基于模型的方法三方面进行阐述说明，比较了多种常用方法的优缺点、时间复杂度、不同特征表示方法之间的区别以及适用条件。

其次，针对时间序列相似性度量，本文从基于形状的相似性度量、基于模型的相似性度量、基于数据压缩的相似性度量三方面进行系统描述。对各种方法是否支持去噪、是否满足三角不等式等方面进行了说明，并且对常用的经典模型如欧氏距离（Euclidean distance，ED）、隐马尔科夫模型（hidden Markov model，HMM）、最长公共子序列（longest common subsequence，LCSS）、自回归滑动平均模型（autoregressive moving average model，ARMA）等进行了系统的介绍。

最后，本文对时间序列未来研究发展方向进行了展望，提出了引入聚类算法、分类算法、预测算法、权值、斜率、鲁棒性技术等研究方法。这些方法能够一定程度地降低时间序列噪声，提高挖掘精度。

1 时间序列特征表示方法研究现状

时间序列特征表示是一种能够将原始高维时间序列转化为另一个低维领域的近似表示数据，进而对数据降维的常用方法。例如小波变换，通过对时间轴函数的伸缩平移区分高频和低频信号，然后投射到低维数据空间上，使投射后的时间序列尽可能地反映原始时间序列信息。有效的特征表示方法往往能以简洁的方式表达该时间序列的特征信息，起到对时间序列降维去噪，减少计算量的效果，为进一步提高数据挖掘效率奠定了良好基础。目前已经研究出多种关于时间序列特征表示的方法。根据时间序列数据的不同转换方式，大体将特征表示方法分为非数据适应性方法、数据自适应性方法、基于模型的方法三类。不同方法之间存在着一定的区别和联系，归类分析如图1 所示。

1.1 非数据适应性方法

非数据适应性方法能够将高维度时间序列数据转换到其他的低维度数据空间，且数据本身相对独立，和转换过程、特征系数选择无关。该方法适用于表示大小（等长）不变并且每条时间序列的转换参数一致的分段时间序列。基于不同非数据适应性方法特性的比较如表1 所示。

Fig.1 Classification of time series feature representation methods图1 时间序列特征表示方法分类

Table 1 Comparison of non-data adaptive methods表1 非数据适应性方法的比较

1993 年，Agrawal 等人[6]提出了一种使用傅里叶变换（discrete Fourier transform，DFT）将时间序列的特征域变换到频域的表示方法。其时间复杂度为O(nlb(n))。该方法通过将信号分解，形成频率幅度大小不同的频率谱，然后通过R*-tree 将其运用到索引和相似度查询中。该方法有效解决了时间序列数据挖掘中“特征抽取完备性”和“维度灾难”的问题。它的优点是没有错误的丢失值，数值相对精准。缺点是不支持时间扭曲查询，主要考虑低频率分量，忽略了高频率分量和时间局部化的重要特征。该方法经常被应用于例如声学、光学、海洋学、信号处理等领域。Keogh 等人[7]提出了分段聚合近似表示方法（piecewise aggregate approximation，PAA），该方法在满足下界定理的前提下，时间复杂度最快能达到O(n)，适用于处理短期平稳变化的时间序列。该方法通过在索引速度和灵活性等方面与传统的奇异值分解（singular value decomposition，SVD）和离散小波变换（discrete wavelet transform，DWT）进行比较，证明其在时间序列相似性度量和索引上更具有优势。Keogh 等人[8]还提出了一种基于逐段线性分割的方法（partial least squares regression，PLS），该方法不仅能够较为准确地确定时间序列的形状，而且能够快速地对时间序列进行聚类和分类分析。除此之外，频谱分析也是非数据适应性的一种常见方法。Chan 等人[9]提出的离散小波变换（discrete wavelet transform，DWT）经常被应用于处理平稳信号的时间序列信息，其时间复杂度为O(n)。该方法有效结合了泛函数、调和分析、数值分析等数学分析方法。优点是既能够表示时间序列中的时域信息，又能够表示频域信息。此特性被广泛应用于语音合成、图像处理等领域。相比较而言，DFT 只能表示频域信息并且要求信号数量为2 的指数倍，信号结果不够稳定，具有一定的局限性。继而，Popivanov 等人[10]对比了不同小波变换对时间序列相似性搜索的效率并得出结论，多贝西小波（Daubechies wavelet，DbN）比哈尔小波（Haar wavelet，Harr）的高效性、光滑性和拟合性都更好一些，并且使用小波变换后的时间序列更加接近初始的时间序列。但是，Haar 小波在时间序列结果的精度上优于Daubechies和Coiflet小波，并且计算成本低。除了一维时间序列外，通过Haar 变换得到的序列精度接近最优，其性能明显优于DFT。此外，PIP（perceptually important points）方法[11]通常用于非等长时间序列之间的比较，被广泛应用于金融领域当中。

Table 2 Comparison of data adaptive methods表2 数据自适应性方法的比较

由于国内对于时间序列特征表示方面的研究起步较晚，而且主要集中在国内的重点高校和科研所当中[12]。因此，研究成果与国外相比较还有一定的提升空间。

1.2 数据自适应性方法

数据自适应性是一种数据和参数随着时间变化而变换的方法。与非数据适应性方法不同，数据适应性方法允许各条时间序列的转换参数是不一致的，该方法既依赖于单条时间序列，又受整体时间序列数据集的影响，相对独立性较差。对于数据自适应性方法的比较如表2 所示。

Lin 等人[13]提出了一种符号聚集近似（symbolic aggregate approximation，SAX）表示方法，时间复杂度能达到O(n)的级别。该方法能够实现将高维非离散时间序列转化为低维离散符号化时间序列，有效达到降维去噪的效果。该方法优点是满足下界定理，可以将字母存储为位而不是双精度，并且允许维度减少，大大节省了空间。研究者根据该方法可以更好地进行字符串处理、生物信息学应用、股票数据聚类等操作。缺点是该方法只适用于能等分且服从高斯分布的离散型和字母型时序数据，并且符号化过程只采取时间序列的均值作为局部特征提取，只能反映原始时间序列的总体变化趋势，不能客观描述各段的局部信息，容易忽略时间序列形态变化和特征点等信息，造成数据中其他信息的缺失，而且当两个时间序列各段的均值一致而各段趋势不同时，SAX 的局限性更明显。

Lkhagva 等人[14]在SAX 基础上提出了扩展方法（extension of symbolic aggregate approximation，ESAX），考虑加入时间序列段的均值、极大值和极小值等特征点元素，能够更加准确地反映时间序列的形态，在进行相似性搜索时，该方法效率更高，但是下界性没有得到充分证明。除此之外，可转位符号聚合近似（indexable symbolic aggregate apprximation，iSAX）的多分辨率符号表示方法，能够实现快速精确搜索和超快速近似搜索。其中，iSAX 与SAX 的不同在于是否通过二进制形式替代字母形式表示每个分段。iSAX方法创建的层次结构索引不能包含重叠的区域，是一种支持大量数据集进行索引的表示方法，可以索引多达亿个数量级的时间序列[15]。奇异值分解（singular value decomposition，SVD）[16]表示方法也是一种数据适应性方法，因为运行时间复杂度高达O(Mn2)，代价成本较高，应用并不广泛，往往应用于文本处理领域，用来处理数据的底层结构。Ye 等人[17-18]提出的shapelets 子序列的概念，是一种能够最大限度突出时间序列主要特征的子序列表示方法，具有准确性高、分类速度快、可解释性强的特点。该方法搭建起了时间序列和形状之间相互表示的桥梁。Sun 等人[19]提出了一种基于趋势距离的符号聚合近似表示方法（SAX trend distance，SAX-TD），通过时间序列段的起点和终点构建趋势距离，是一种融合了SAX 距离和趋势距离的新距离度量表示方法。该方法的缺点是在构建距离时，难免伴随着存储维度和运行时间的增加。除此之外，分段多项式也是常见的数据自适应性方法。

1.3 基于模型的方法

基于模型的方法是提前假定时间序列数据是由某个模型产生，然后通过对该模型设定合适的参数或者系数，实现对时间序列的特征表示。

Azzouzi 等人[20]提出隐马尔科夫模型（HMM）来捕获时间序列变量间的依赖关系和测量值中的串行相关性。该模型被广泛应用于语音识别、音字转换等自然语言处理领域。Kalpakis 等人[21]提出了求和自回归移动平均模型（autoregressive integrated moving average model，ARIMA），该模型能够更加高效直观地表示时间序列特征信息，主要应用于医疗领域对流行病的预测和食品领域对食品安全性预测方面。Nanopoulos 等人[22]提出一种基于统计模型（含方差、均值等）的特征提取方法，采用局部特征表示整体时间序列。李爱国等人[23]提出了一种分段多项式回归模型，将时间序列分为多段表示。Fuchs等人[24-26]提出了一种基于正交多项式的时间序列表示方法，实现了正交多项式和最小二乘法的融合，运用正交基向量形成特征空间，并将数值较大的坐标系数作为特征序列。这类方法往往被用于在线分割。Sebastiani 等人[27]使用马尔科夫链模型（Markov chain model，MC）表示时间序列中的动态特征。马尔科夫链模型是一种对时间、状态离散化处理，带有记忆情况的随机过程模型，经常用于对人均GDP、股票和彩票预测、全国电信业务总量的预测。另外，主成分分析法也是常用的一种基于模型的方法。基于模型的表示方法往往具有较强的可解释性，若两条时间序列可以由具有相同参数的同一数据集模型表示，那么认为它们是相似的。此类方法的关键在于选择合适的模型和提前了解时间序列数据产生过程的信息。只有选择与产生过程相符合的模型才能获得更好的结果。基于模型的主要方法特性比较如表3所示。

Table 3 Characteristics comparison of model-based methods表3 基于模型方法的特性比较

主要的时间序列特征表示方法的时间复杂度如表4 所示。

Table 4 Time complexity of feature representation methods表4 特征表示方法的时间复杂度

2 时间序列相似性度量研究现状

时间序列相似性度量通常采用衡量两个不同时间序列之间距离远近程度的方式来验证两个序列是否相似。目前时间序列相似性度量研究主要通过在原有研究基础上提出新的时间序列相似性度量方法，评估该方法对时间序列数据挖掘精度的影响。时间序列相似性度量方法分为基于形状的相似性度量方法、基于模型的相似性度量方法和基于数据压缩的相似性度量方法等。不同相似性度量方法特性存在一定的差异性和联系，如表5 所示。

Table 5 Features comparison of similarity measurement methods表5 相似性度量方法特性比较

相似性度量在应用于时间序列数据挖掘领域时，一般与聚类算法相结合。通常此类方法首先将等长时间序列通过降维的方法处理为不等长的时间序列，然后进行等长处理，选取两个时间序列的公共点元素，构成新的时间序列集合，利用得到的时间点集合再对时间序列进行二次划分，最后得到新的等长时间序列。此过程虽然会提高计算的复杂性，但是便于操作，基本不会对结果造成较大的偏差。

2.1 基于形状的相似性度量

基于形状的相似性度量方法多种多样。表6 对主要方法的特性进行了分析比较。

Table 6 Comparison of similarity measurement methods based on shape表6 基于形状的相似性度量方法的比较

欧氏距离（ED）是一种基于形状相似性的常见锁步度量方式。当两个时间序列长度相等且均为数值型序列时，该方法通过公式计算两个序列上时间点的距离。在模糊距离中，汉明距离和灰色关联分析法也可以应用在字符串形状相似性度量中。其中汉明距离通过对等长字符串序列对应位进行异或运算，统计结果为1 的个数。1 的个数越多，相似性越低。汉明距离有一个鲜明的特点就是它比较的两个字符串必须等长，否则距离不成立。它的核心原理是如何通过字符替换（最初应用在通讯中实际上是二进制的0-1 替换），能将一个字符串替换成另外一个字符串。灰色关联分析法是通过对时间序列进行无量纲化处理，确定参数数据序列和若干比较数据序列的几何形状来判断相似程度，然后根据关联度和关联系数衡量关联性的强弱。灰色关联分析法的特点在于思路清晰，可以在很大程度上减少由于信息不对称带来的损失，并且对数据要求较低，工作量较少。其中LP 范式为最常见的距离度量形式，时间复杂度为O(n)，并且满足三角不等式，一般用于索引、聚类和分类上。该距离方法缺点是对相位漂移比较敏感，受噪音干扰较大，对于时间序列的形状缩放和位移无法准确识别，某种情况下，度量结果往往存在很大误差。因此，该度量方式通常依赖于数据的归一化处理。在经过特征表示之后再进行相似性搜索时，该空间下的距离度量需要满足下界定理[28-31]。动态时间弯曲（dynamic time warping，DTW）是一种通过对时间轴进行弯曲、拉伸或收缩来计算两个时间序列间相似性的方法。该方法既可以处理两个等长时间序列，也可以处理两个不等长的时间序列，而且允许时间序列的点自行拷贝之后再进行等长匹配，支持平移，能够很好地处理时间漂移问题，克服了欧氏距离对于序列变形后不能准确匹配的问题，具有效率优于欧氏距离和三角形相似性[30,32-35]的特点，并且允许不同时间轴上的时间序列进行相似性匹配。但是存在不支持噪声处理、本地时间转换和三角不等式，且时间复杂度较高等问题，随着时间序列维度的递增，算法的效率并不高。针对其不足，Sakoe 等人[36]和Itakura[37]分别提出Sakoe-Chiba 条形约束和平行四边形约束方法，通过在动态规划过程中引入全局约束的方法，一定程度上减少了计算量，来实现算法效率的提高。该方法将路径规划（也称路径弯曲）过程限制在一定区域内，不仅避免了不必要的路径规划，而且有效防止过度匹配导致准确率下降的问题。Keogh 等人将基于DTW 的精确索引应用于时间序列挖掘中[38]。除此之外，DTW 在计算多元时间序列最佳弯曲路径时，虽然能够较好地反映时间序列形态变化问题，但容易出现不合理的匹配导致产生多条匹配路径，从而无法选择最精准的路径的问题。Gorecki 等人[39]考虑到局部形态特征处理问题，提出了分别用动态时间弯曲和微分动态时间弯曲求取多元时间序列距离后再用参数线性组合度量的方法，但仅考虑一阶数值导数可能会失去全局形态或重要的特征。Keogh 等人[40]提出了一种扩展方法为DDTW（derivative dynamic time warping），根据时间序列中某个点的相邻信息选取适当的计算方式构造出新的时间序列，达到实现新的序列不再对异常值敏感的目的。在此基础上，自适应代价动态时间弯曲的多元时间序列度量方法（adaptive cost multivariate dynamic time warping，ACM-DTW）[41]，通过对时间序列点距离矩阵赋予权重，来达到较好的匹配效果，权重由自适应代价函数计算获取。

基于互相关的距离度量方法（cross-correlation based distance）具有降低噪声影响和概括时间结构的特点[42]。当两个时间序列大体形态都很相似，此时欧氏距离和动态时间弯曲方法都无法测量，仅仅在小范围内存在弯曲或断点时，可以采用最长公共子序列（LCSS）距离度量方法。该方法对于噪声的处理能力比较强，但是对于处理时间轴的伸缩和振幅平移问题有待于进一步提高，而且不支持三角不等式[43-45]。LCSS 方法采用将两个时间字符串最大的公共字符串长度与最长字符串相除的百分比作为衡量两时间序列相似性的度量标准[46]。实序列编辑距离（edit distance on real sequence，EDR）是一种能够有效对时间序列进行降噪，降低序列位移和误差敏感度的方法。该方法通过阈值模式将时间序列元素量化为0/1表示，降低了时间序列的噪声，对于异常数据的处理具有更好的鲁棒性，但是该方法并不满足三角不等式[47-48]。实补偿编辑函数（edit distance with real penalty，ERP）是一种允许在两条不同长度的序列间通过添加符号达到等长效果的度量方法[49-50]。该方法对数据的噪声、位移和缩放具有较强的鲁棒性，通过使用一个恒定的参考点来达到寻找弯曲路径中最小路径的目的。该方法满足三角不等式，并且能够有效处理本地时间转换问题[51-52]。动态时间弯曲、最长公共子序列、实序列编辑距离、实补偿编辑函数方法的时间复杂度均为O(n2)。

2.2 基于模型的相似性度量

Ge 等人[53-54]采用隐马尔科夫模型进行相似性度量，加入了分段线性表示来实现捕获变量之间的依赖关系，又能够衡量时间序列测量相关性。Panuccio等人[55]采取标准化的方法对HMM 距离进行处理，判断时间序列的拟合性能好坏。ARMA 模型[21]是一种通过模型参数或演变参数确定原始序列相似性关系的方法。ARIMA 模型[56]全称为自回归积分滑动平均模型，该模型首先判断序列的平稳性，若为非平稳序列，通过差分运算过滤掉非平稳趋势的点，然后确定时间序列的自回归参数和滑动平均参数。空间装配距离（spatial assembling distance，SpADe）[57]也是一种基于模型的相似性度量方法。基于模型的相似性度量与基于形状的相似性度量相比，优势在于可以提前将数据的知识通过计算结合进来。并且通过某个序列所建模型生成另外序列的概率值来衡量两个序列的相似度。

2.3 基于数据压缩的相似性度量

皮尔逊相关系数和相关距离（Perason's correlation coefficient and related distance）[58]是一种不随数据点的比例和位置而变化的相似性度量方法。基于分段正常化的相似性度量（piecewise normalization）[59]是一种涉及不同大小的时间间隔或“窗口”的相似性度量方法。基于倒频谱的相似性度量（cepstrum）[60]是一种频谱测量方法，能够短时间内实现对数振幅频谱的反傅里叶变换。

基于概率距离的相似性度量（probability-based distance）[61]能够将多种季节性模式融合汇总。基于条件Kolmogorov 复杂性的距离度量或数据压缩距离度量（compression-based distance measure，CDM）[62-63]通过数据压缩比率大小反映时间序列相似性。该方法压缩率越大，相似性越高，反之亦然。但是对算法的连接和压缩过程要求较高，适合处理较长的离散化时间序列。Lang 等人[64]提出了基于字典压缩的相似性度量（dictionary-based compression）方法，应用于相似性度量的字典压缩评分。类似的KL（Kullback-Leibler）距离相似性度量[65]、基于分段概率的相似性度量（piecewise probabilistic）[66]、基于余弦小波函数的相似性度量（cosine wavelets）[67]、基于自相关的相似性度量（autocorrelation）[68]也是比较常用的基于数据压缩的相似性度量方法。基于数据压缩的相似性度量来自于计算理论研究和生物信息学研究的一些结果，是一个比较新颖的想法。数据压缩是指在不丢失有用信息的前提下，缩减数据量以减少存储空间，或者按照一定的算法对数据进行重新组织，减少数据的冗余和存储空间的一种技术方法。现有的相似性度量方法对短时间序列有较好的效果，但是对于较长的时间序列，它们的评估成本会迅速下降。因此应该为数据选择压缩工具和压缩参数的最佳组合。例如，CDM 取决于特定压缩器（gzip、bzip2 等）的选择以及压缩参数。如今这些方法的应用范围也较广泛，如医学上的心电图测量、生物识别中的面部识别、物理学中的粒子跟踪等。除此之外，这些时间序列相似性度量方法对于查询数据库、分类和聚类十分有用。

3 未来研究方向

随着科技的不断发展，时间序列被广泛应用于多个领域，为社会的经济发展做出了巨大的贡献。例如在医学领域，时间序列用来检测病人群体中的异常个体；金融领域中检测异常收入支出，防止发生诈骗行为；工业领域检测设备异常，防患于未然等。

时间序列一般用作数据挖掘的预处理步骤，降低高维数据维度，达到提高数据挖掘精度的效果。

如今时间序列相似性度量发展蓬勃，但是仍然存在一些问题值得重视。因此，针对时间序列相似性度量的未来研究方向提出了几种规划：

（1）一般对于时间序列相似性的研究比较理想化，多数相似性度量方法均在假设获取的训练集是相对准确的前提下进行研究。但是在实际情况中，时间序列数据的采集和运行结果往往受到周围环境的影响，伴随着大量噪声的产生。因此，如何将相关鲁棒统计学的技术运用在相似性度量的学习方法中，达到更为理想的效果还有待于研究。

（2）同一数据集运用不同的相似性度量方法时，精度的结果测量往往存在很大差异。因此，为了更好地完成数据挖掘的各类任务，在此基础上，可以考虑融合数据挖掘聚类算法将时间序列数据进行分组，每个分组内的时间序列数据相似性越高，不同分组之间相似度越低，则聚类效果越好。因此，选择合适的数据挖掘算法融合相似性度量方法提高结果精确度是一个值得研究的课题。

（3）考虑在时间序列的相似性度量方法上融合机器学习的分类算法。比如支持向量机、朴素贝叶斯、决策树等，也可以达到提高相似性度量结果精确度的目的，可以作为未来研究的方向之一。

（4）如今定位技术和基于位置服务的应用发展迅速，过程中会有文本、图像数据等海量轨迹数据产生。因此，如果对不同时间点车辆运行的路段信息、轨迹方向信息、运行轨迹长度信息（包括运行轨迹存在交叉等情况）采用合适的距离度量函数进行计算，对轨迹相似性度量进行深入研究，将有益于城市规划、智慧出行的发展。

（5）目前为止，对于时间序列相似性度量研究主要为静态低维的时间序列。对于动态高维时间序列的研究成果较少，这就要求时间序列相似性度量方法具有高效、平稳、低成本的特点，因此通过相似性度量方法改进优化实现这些特点，值得进一步研究。

4 结束语

时间序列往往具有高维性、数据量大、随着时间变化而变化的特点。随着大数据时代的蓬勃发展，时间序列越来越普遍存在于人们的日常生活中。因此，根据时间序列的高维特性适当地降低维度，发现不同时间序列之间的关系，探索其中的规律，挖掘潜在价值就变得尤为重要。本文从时间序列的特征表示和相似性度量方面对目前时间序列的研究现状进行了阐述和总结，分析比较了各种方法的优缺点、时间复杂度及方法之间的区别和适用条件，最后对时间序列的未来研究方向提出了几点展望。