时间序列表示进展及比较研究时间序列挖掘建模环境

时间序列表示进展及比较研究:时间序列挖掘建模环境1李俊奎，王元珍，刘城成，曹忠升华中科技大学数据库与多媒体研究所(430074)email:[e-mail]摘要：时间序列表示是时间序列挖掘的一个基础和关键问题。对当前出现的各种典型的时间序列表示方法进行了综述，对各自的特点从多个角度进行了比较研究。结果说明，大部分时间序列表示方法将时间序列降维，且都与应用领域紧密相关，在实际构建系统时仍需对各种表示方法按照实际需求进行转化和改造。关键词：数据挖掘时间序列表示建模1．引言时间序列是一种重要的高维数据类型，它是按照时间顺序观察所得到的一串数据。时间序列的应用日益广泛，其涉及天文、地理、生物、物理、化学等自然科学领域，图像识别、语音处理、声纳技术、遥感技术、机械工程等工程技术领域，以及市场经济、金融分析、人口统计、地震检测等社会经济领域，当前对于时间序列挖掘的研究正得到越来越多的重视[18][15]。本文的背景是国家发展与改革委员会“安全智能整合平台开发及产业化”项目，该项目的一个重要目标是以人工智能、数理统计等先进的数据挖掘技术为基础，满足用户的智能化知识发现和趋势分析的需求，为用户战略决策提供服务。在项目进行中，构建时间序列挖掘子系统时，我们面临首先必须解决的一个重要而基础的问题是对时间序列进行建模表示。经过大量深入细致的相关研究和文献查阅，我们发现当前对于时间序列的表示问题虽然取得了部分进展，但是如果需要将研究成果应用于实际系统构建过程，仍然需要深入考察以及对各种表示方法进行实际转化和处理。本文综述了当前时间序列挖掘研究领域中出现的各种时间序列的建模表示方法，指出在构建实际系统时，这些表示方法都存在各自的问题。并且指出时间序列表示方法是一种与应用领域和应用需求相关的方法，为实际的时间序列表示和建模提供了参考。本文的其余部分如下组织：第2节讨论时间序列表示的相关背景；第3节对当前已经出现的时间序列的表示方法进行综述，陈述各自的不足；第4节对各种时间序列表示方法进行比较；第5节总结全文，并指出未来的进一步工作。2．时间序列表示的相关背景为了说明的严谨，我们首先给出时间序列的相关定义。定义1时间序列(TimeSeries)时间序列12,,...,nTttt=是一串有序的n实数变量。定义2时间序列长度(LengthofTimeSeries)对于有限长时间序列12,,...,nTttt=，T的长度为组成T的实数个数，记为||T，即||Tn=。对于无限长时间序列，T的长度定义为||T=∞。无限长时间序列一般在数据流的建模中使用，有限长时间序列则在时间序列数据库中使用。定义3时间序列区段(子序列)(Segment,Subsequence)给定长度为n的时间序列T，T1本课题得到国家发展与改革委员会“安全智能整合平台开发及产业化”项目(项目编号[2005]538号)资助开始，数量为(1)wwn≤≤个连续位置点所组成的T的一个抽样，即11,,...,sssswCttt++−=，其中11snw≤≤−+。时间序列区段一般通过在T上给定一个滑动窗口(窗口大小为w)获得。实际生活中的时间序列都具有很长的长度，一般对于长度为n的时间序列可以看作是n维向量空间中的一个点，为了便于查找，可以首先利用Rtree，R*tree,k-dtree，skylineindex[9]等多维索引机制将这些点索引，然后查找则首先在索引上进行。不幸的是，由于目前现存的多维索引方式普遍仅对8-10维空间中的点比较有效，对于更高维的数据索引则将会导致索引性能的急剧下降，即引发所谓的“维度灾难”(DimensionCurse)问题[4][16]。为了解决维度灾难问题，一般的做法是对时间序列数据进行降维处理，然后再对降维后的数据进行索引，对原始数据进行降维处理后，在索引空间的查找可能出现两类问题[25]：(1)漏查(FalseDismissal)：在原始数据(T)中两点距离小于给定的阈值ε，但是在索引空间(T)中的该两点距离却大于ε，从而对索引空间的点查询时发生漏查，即,,,,0,(,)(,)ijijijindexijttTttTDttDttεεε∃∈∈⇒≥(1)(2)错查(FalsePositive)：在索引空间(T)中的两点距离小于给定的阈值ε，但是在原始数据(T)中该两点距离却大于ε，从而对索引空间的点查询的结果中出现错查，即,,,,0,(,)(,)ijijindexijijttTttTDttDttεεε∃∈∈⇒≥(2)对于错查问题，可以通过针对索引空间中的查询结果再次到原始数据空间中查询，剔除其中(,)ijDttε≥的点来解决，由于在索引空间中查询时已经剔除了大量不符合条件的点，只保留了原时间序列数据集合中一个很小的子集，所以再次在原始数据空间中查询时的耗费是可以接受的。漏查问题则决定了是否能够对时间序列进行有效的相似性查找，为了能够解决这个问题，Faloutsos等人在文献[7]中给出了降维下界定理(LowerBounding)，即：(,)(,)indexDTCDTC≤.(3)于是很多时间序列表示方法都侧重于首先对时间序列进行降维处理。3各种典型的时间序列表示方法在研究初期提出对时间序列进行(DiscreteFourierTransform,DFT离散傅立叶)变换[1][13]，然后用DFT的前k个系数作为原时间序列的表示，其底层的理论依据是数字信号处理领域的Parseval定理，该定理保证了时间序列数据的DFT变换前几个系数中保存了序列中大部分能量。在实际应用中，DFT变换对于自然产生的时间序列信号较为适合，但是对于其他来源的时间序列数据则效果不佳。随后出现了DWT(DiscreteWaveletTransform，离散小波变换)[4][23]，其中研究最多的是Haar小波变换，并用Haar变换的系数作为时间序列的表示。Haar小波变换的基函数不平滑，对时间序列的表示近似类似于梯形的结构，导致其对于一段很短的时间序列数据进行变换都会产生大量的系数。(SingularValueDecomposition,SVD单值分解)变换技术[22]，采用KL分解的技术来实现时间序列数据的降维处理。这种技术的劣势在于其依赖于数据，由于使用数据集来产生新的基向量，因此数据项的任何改变都需要重新进行计算。(PiecewiseAggregateApproximation,PAA滑动平均聚集近似)方法[16][24]，在时间序列上滑动一个大小固定的滑动窗口，并计算滑动窗口中数据的均值作为整个窗口内数据的表示。这种方法利用了时间序列在短期内数据变化不大的特性，能够在一定程度上实现时间序列的有效降维。但这种方法具有如下的不足：1)滑动窗口的大小是一个关键的因素，实际中需要根据时间序列数据仔细选取；2)利用求均值的方法对时间序列进行平滑处理，可能会丢失时间序列中的极值等特征信息；3)PAA没有考虑到时间序列数据的随着时间推进对于未来数据大小的参考价值越来越大的性质，它对每段时间序列都同等对待[29]。APCA(AdaptiveAggregateConstantApproximation，自适应平均聚集常量近似)方法[17]，将时间序列分段成为一系列变长的子段，每一子段用该子段中数据均值以及时间点右端值组成的二元组表示。相比较PAA方法，它克服了要求滑动窗口大小唯一的限制。但它具有如下不足：1)同等条件下，它需要2倍于PAA方法的存储量；2)在进行查询时需要对查询串采取同样长度的分解；3)对长度为n的时间序列完成N段精确的APCA表示，需要2()ONn时间复杂度，优化以后仍需(log())Onn，在时间序列流的情形下则不适合。PiecewiseLinearApproximation,PLA（分段线性近似)[7][26]方法首先将时间序列分段，然后利用线性拟合函数进行近似表示。这种方法的缺陷主要是计算复杂性较高，对长度为n的时间序列完成N段最优的分段拟合需要2()OnN的时间复杂度。虽然有很多的优化方法[20]，但是仍难以满足实用的要求。文献[28]中提出一种维约简的方法(PiecewiseRegressionApproximation,PRA逐段回归近似)的方法，该方法对时间序列滑动窗口中的数据计算回归系数，并利用回归系数作为窗口内数据的表示。它的结果对均值平稳的独立噪声干扰不敏感，较PAA方法在进行相似性查找时准确度更高。但该方法的表示结果难以为人所直观理解。文献[27]中提出一种基于向量空间n{1,t,...,t}的多项式拟合的方法，利用拟合的系数作为时间序列表示，这种方法过于复杂，在实际应用中求解将会出现困难。普通的时间序列都是离散的数值型数据，研究过程中也出现了将数值型数据量化形成字符串形式，然后采用常用字符串匹配操作[2][3](如Hash，Markov模型，SuffixTree)等相对成熟技术的方法。文献[19]中提出一种ClipperData方法，将时间序列进行“过零”量化成一串对应的二进制数串，利用二进制的算术运算来完成比较。这种方法对时间序列的数值量化过于简单，虽然采用了二进制压缩技术，但是实际中仍会出现大量冗余数据。文献[11]中提出一种SAX(SymbolicAggregateapproXimation，符号聚集近似)的时间序列表示方法，该方法首先采用PAA对时间序列进行时间轴向分段，然后根据正态分布，对数据轴向量化，量化后的结果利用查表方法确定相应段的字符串，从而完成时间序列的符号化。该方法被应用于时间序列的模式抽取和可视化中[10][12]。不同于一般的等值量化方法，它假设数据呈现正态分布，采用的是不等值量化方法。但是这种方法有如下不足：1)采用PAA对时间序列进行分段，无法克服PAA方法的缺陷；2)对数据的随机分布具有硬性规定；3)实际应用中字符串编码规则仍然需要仔细确定。在时间序列相似问题的研究过程中，一些研究人员独辟蹊径，他们不是从整个时间序列出发，而是选取时间序列中的若干特殊的数据点，从而完成时间序列的表示。文献[6]中提出一种称为Landmarks的时间序列表示方法，将时间序列中的极值点、弯曲点识别出来，并在这些点上建立模型，从而完成原时间序列的近似表示。文献[21]中提出一种类似的Importantpoint的时间序列表示方法，定义时间序列的局部最大点和局部最小点，并用这些点的相邻连线作为时间序列的表示。这些取若干点的方法的问题主要是:1)需要被选中的点能够突出序列中数据的主要特征；2)选取的点的数量、范围以及特征要求比较严格。4各种时间序列表示的比较在这一节，我们对典型的时间序列表示方法进行比较。由于数据挖掘过程是一个需要用户参与的不断交互的过程，而且时间序列数据经常以流序列的形式存在，所以结合我们的项目需求，我们从以下方面进行：(1)是否进行时域-频域变换；(2)是否有效降维；(3)是否线性计算复杂度；(4)是否符号化；(5)能否处理变长序列；(6)能否动态插入/删除；(7)结果用户是否容易理解；(8)局部特征是否保持。比较结果如表1所示。表1时间序列表示方法比较(Y:Yes,N:No)表示方法(1)(2)(3)(4)(5)(6)(7)(8)DFTYYNNＹＮNNDWTYYNNＮＮNNSVDYYNNＹＮNNPAANYYNＹＹYNAPCANYNNＹYYNPLANYNNＹＹYNPRANYYNＹYNN多项式拟合NYNNＹNNNClipperDataNNＹYＹYYNSAXNYＹYＹYYNLandmarksNYＹNＹYYYImportantpointNYＹＮＹYYY5结论总结以上出现的时间序列不同表示方法，可以得出结论如下：1)由于实际中不同应用对于时间序列数据的关注角度不同，对于时间序列的表示的方