英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
基于相似性度量的时间序列分段统计近似算法
Qinglin Cai, Ling Chen, Jianling Sun
浙江大学计算机科学与技术学院，杭州，310027
摘要
在时间序列分析的研究领域，动态时间弯曲距离（DTW）是一种普遍的相似性高精度度量算法。但是，DTW的计算复杂度很高，这使得它很难应用于高维时间序列。一个有效的解决方案是计算分段表示的DTW（PR-DTW），其采用时间序列的子序列的特征相似性度量。但是，大多数现有的分段表示所关注的特征是过于简单，只捕捉时间序列波动信息的一个方面，从而影响PR-DTW的精度。为了解决这个问题，我们提出了一种新的分段表示法模型，称之为分段统计近似（PSA），用于支持PR-DTW测量。PSA并非只专注于单一类型的特征，而是提取多个统计特征来捕获合成相似性度量的变化信息。此外，通过加权欧氏距离对于子程序中的子序列匹配，基于PSA的DTW（PSADTW）可以辨别多特征的表示。凭经验对45个实际数据集进行综合实验，证明PSA非常适合支持精确和有效的PR-DTW测量。
引言
在过去的二十年中，在时间序列分析的研究领域提出了许多主题 [1-3]，包括相似性搜索[4-6]，分类[7-9]，聚类[10,11]，预测[12,13]，异常检测[14]和模式识别[15]。 许多关于这些主题的方法，例如kNN分类或k-means聚类算法，都需要评估时间序列之间的相似性。研究人员通常采用相似性度量（例如Lp-norms距离[16]，动态时间弯曲距离（DTW）[4,17]和编辑变化距离（LCSS，EDR，ERP）[18]等）进行评估时间序列之间的相似性。DTW是时间序列中最流行的相似性度量之一[1,4,7,17]，具有很高的精度。 但是，DTW的计算复杂度是这大大限制了它在时间序列和动态数据流高维空间的应用。
已经提出了许多方法来减少DTW的计算复杂度，它们可以大致分为两种类型：（1）利用加速的方法改进DTW的基本算法的技术，例如动态的编程约束[17]，下界启发式[4];（2）在低维特征空间中计算DTW的方法。最近的结果表明我们处于超速DTW [17]的渐近极限。对于第二种类型，大量的数据表示模型可以用来构造特征空间，例如离散的傅里叶变换（DFT）[19]，离散小波变换（DWT）[3]，分段聚合近似（PAA）[11,20]，自适应分段常数近似（APCA）[21]，分段线性近似（PLA）[22,23]，袋模式表示[24,25]，shapelet变换[8]等。在这些模型中，分段表示是捕捉时间序列的局部特征的优秀代表。但是，大多数功能现有的分段聚焦的特征过于简单，这是仅反映时间序列波动信息的一个方面。例如，PAA [20]和APCA [21]只提取平均值，PLA [23]只提取线性拟合斜率，以及派生的时间序列近似（DSA）[6]只提取子序列的平均值，以及最新技术分段云近似（PWCA）[26]只提取了子序列的云模型等等。这个缺点会导致表示方法的弱表达，以及影响基于DTW分段表示的精度（PR-DTW）。
为了提高现有PR-DTW的精度，我们提出一种新的分段表示模型，叫做分段统计近似（PSA）和相应的相似性测量，即基于PSA的DTW（PSADTW）。 而不是专注于单一类型的特征，多种统计特征值（例如，平均值，标准差和偏度等）都从PSA中时间序列的子序列中提取出来，可以捕获合成相似性度量的时间序列波动信息。此外，在PSADTW中，我们采用加权欧几里德距离用于匹配提取的特征，通过权重表示特征可以明确区分这些特征，并让PSADTW对有效信息更加敏感。 由于PSADTW的子程序是建立在在子序列的匹配之上的，所以它可以克服子序列之间的相移问题。本文的发现列举如下：
（1）提出时间序列的PSA表示，这可以捕获用于相似性度量的时间序列的综合的波动信息。
（2）提出PSADTW进行时间序列相似性度量，这可以区分多个特征的表达并克服子序列之间的相移。
（3）进行全面的实验来评估PSADTW的性能。
本文的结构如下：关于数据表示和相似性测量的相关工作在第2节中给出； 第3部分给出了PSA表示的细节；第4节介绍PSADTW测量的细节；第5节提供了综合实验结果和分析；第6节总结本文。
2 相关研究
2.1 数据表示
在许多应用领域中，时间序列的维数很高限制了无数算法的性能。针对这个问题，大量的数据表示方法被提出来去降低时间序列的维数[1,2]。它们大致可以分为两类：一类是基于全局映射，其中将整个时间序列投影到低维特征空间; 另一种是基于局部映射，其将分割的子时间序列投影到特征空间。
基于全局映射的第一次尝试是DFT方法[19]，将时间序列投影到频域，并提取主频率的系数来减少原始数据的维度。同样，DWT[3]将原始数据投影到小波域，并提取小波系数作为特征。与DFT，DWT相比可以捕捉时间序列的多分辨率特征时间和频率域。最近，一个新的基于形式的全局映射表示形式称为shapelet变换[8]被提出，它将时间序列映射到shapelet空间并将时间序列和形状之间的距离作为特征。这种方法是易于理解的，可以提供洞察力进入问题领域。此外，另一个最近的研究方向就全局映射而言，就是采用“袋模式”文本挖掘和信息检索社区。首先尝试是模式表示法（BOP）[25]，其中将时间序列投影到本地模式的向量空间中。然后，Senin等人[27]通过使用tf-idf分数选择模式来改进了BOP模式。与BOP不同的是，Baydogan等人[24]提出特征包表示（TSBF）方法，它使用典型的子序列来组成紧凑的码本作为矢量空间。
在基于局部映射的方法中，分段表示方法是最普遍的。第一次尝试是PAA [20]，它将时间序列分成等长的子序列，并提取子序列的平均值作为特征近似原始数据。但是，提取的单一类特征仅指示子序列的高度，其中可能会导致本地信息丢失。连续地，PAA的一种适应性版本，叫做分段常数近似（APCA）[21]被提出，它可以将时间序列分割成具有自适应长度的子序列，因此可以以更少的错误近似时间序列。同样，PAA的多分辨率版本，命名为MPAA [11]，可以迭代分割时间序列成2i个子序列。然而，这两个变化继承了PAA的不良表现力。另一个分段表示犯方法是PLA [22,23]，它提取线性拟合子序列的斜率作为近似原始的特征数据。但是，拟合斜率只反映了运动趋势的子序列。对于时间序列高频率剧烈波动下，PLA对降维的作用不大明显。
此外，还提出了两种新的分段表示法最近。其中一个是DSA [6]表示，它将平均值时间序列的派生子序列的平均值作为特征，但是，它对噪声很敏感。另一个是PWCA [26]的代表，它使用云模型来拟合子序列的数据分布。但是，提取的特征仅反映数据分布特征并不能捕捉到时间序列的波动信息。
2.2 相似性度量
时间序列的相似性度量方法在很多场合[1,2,7,17,18,30,31]已经被详细研究，一个完整的所有方法的搜寻超出了本文的范围。我们会只关注两种流行的方法：锁步措施和弹性措施。
锁步测量[1,2,16]通过严格对齐计算时间序列的指数。 Lp-norms距离[16,30]最多流行的锁步措施，如曼哈顿距离，欧几里德距离，最大距离分别为p = 1，p = 2和p→infin;。 Lp-norms以其实现简单，计算复杂度低，即O（n），无参数，并满足三角不等式而闻名。但是，它的测量精度对噪声，异常值和基本的形状变化敏感。为了提高Lp-norms的测量精度，提出了加权欧几里德距离[22]，它引入权重来表示测量点的重要性。但是，它保留了Lp规范对基本形状变化的灵敏度。
为了克服锁步措施的缺点，提出了弹性测量，这是通过重新计算得出的时间序列的指标并且对基本的形状变化稳健。DTW [4,7,17]是最普遍的弹性测量，其中由动态编程计算。 尽管它对时间弯曲和相移很健壮，并且具有很高的测量精度，O（n）的计算复杂度很大地限制了DTW在高维时间序列中和高速数据流[4,32]的应用和。 此外，“奇点”问题[33]也可能存在于DTW中，其中一个单一的时间序列点可能映射到另一个序列的大部分。为了克服这个问题，Keogh等人[33]提出了衍生物动态时间规整距离（DDTW），这是计算派生时间序列的一种方法，并能够找到时间序列之间的自然对齐性。
最近，一个名为WDTW [34]的新的基于补偿的DTW被提出，这可以补偿与它们们的时间序列点相位差，从而防止最小距离失真由异常值引起。另一个名为CIDDTW的新型DTW[30]也被提出，它将整体变异正则化引入到入DTW中，并可以用来识别相似性复杂的时间序列，这两个新的方法保留了DTW的高计算复杂度。
为了提高DTW的高计算复杂度，许多已经提出的方法大致可以分为两类：改进DTW基本算法的方法，以及计算DTW的方法低维特征空间的DTW方法。
对于第一种类型，主要使用全局约束，例如Sakoe-Chiba段和Itakura平行四边形段[22]，这可以将DTW的计算限制在一个小范围的动态编程表内。此外，还有四个与DTW用于相似性搜索任务一样新的下界启发式[4]方法被提出，它可以在DTW下快速提高搜索效率，就像在大规模数据集上的欧几里德距离一样。虽然这种方法是有效的，但他们受加速DTW渐近状态的限制。
对于第二种类型，基于PAA表示的PDTW [35]和基于PLA表示的的SDTW [36]是早期的方法，并且基于DSA表示的DSADTW [6]是最先进的方法。 它们不是在原始数据空间中分别计算PAA，PLA和DSA空间中的DTW。由于分段数量远小于原始时间系列长度，这种类型的方法可以大大减少计算量DTW的复杂性。 尽管如此，他们的测量精度仍然取决于使用的表示方法，其中提取特征对测量精度至关重要。
3 分段统计近似
为了不失一般性，我们首先给出三个基本定义与时间序列有关如下。
定义1 时间序列。 一个变量在连续时刻的样本序列称为时间序列，记为T = {t1,t2,hellip;,tn}其中ti表示变量在第i个时刻的样本值。
定义2 子序列。 给定时间序列T = {t1,t2,hellip;,tn}，子序列S是由T中连续元素组成的子集{ti 1,ti 2,hellip;,ti l}其中0le;ile;n-l和0le;lle;n，S被称为T的子序列.
定义3 时间序列数据表示。 给定时间序列设定T = {t1,t2,hellip;,tn}和Visin; Rn，如果存在f：T→V，那么V被称为时间序列数据表示。
在开始时，有必要对原始时间进行z归一化，使其具有零均值和零标准差，作为一个预处理步骤[4]。
由于分段表示方法采用不相交窗口降低时间序列的维数[6,20,26]，时间序列的局部特征可以独立调查，并且时间序列的全局特征可以是从子序列的高层次角度进行探索。
我们会提取，而不是专注于PSA中的多个统计特征中一种功能，例如平均值，标准偏差和偏斜度等，来描述其特性时间序列，而是捕获来自不同的方面的综合波动信息。 如下所示，我们展示了重要性的六个一般统计特征[37]，即平均值mu;，方差D，标准偏差sigma;，色散因子CV，偏度SK和峰值K，并将它们计算为公式（1）-（6）。
平均值（l）是子序列的平衡点，它表明子序列的高度和中心趋势。
方差（D）或标准偏差（r）表示强度和子序列的分散。
色散因子（CV）表示相对色散子。
偏度（SK）或峰度（K）表示子序列数据分布。
理论上，LFV的尺寸不受限制。 其实与来自不同应用领域的时间序列，实用性在PSA中提取的特征是数据可靠的。 例如，在图1中标记的样本，时间序列是周期性的低频率，并具有运动模式，噪音较小。从而，子序列的线性拟合斜率更大比描述波动的其他特征更有效特点。在股市中，投资者更多有兴趣的开放价格，高价格，低价格，和在一段时间内收盘价，因此我们只需要提取第一个值，最后一个值，最大值和最小值随后构建LFV。
图1
全文共17822字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14804]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
