摘要
动态时间规整（DTW）算法是一种时间序列对齐算法，已广泛应用于音频、视频和图形数据对齐。它可以获得一个使时间序列之间的总距离最小化的对齐路径，实现两个不同长度的时间序列对齐路径的全局最优解。DTW本质上是一种在约束条件下寻找最优对齐的相似性度量方法。但是，DTW往往不能保证局部匹配的合理性，限制了算法在实际环境中的应用。具体来说，DTW可能试图通过扭曲水平时间轴来解释序列数值的可变性，这可能会导致不直观的对齐，即一个时间序列上的一个点映射到另一个时间序列的多个点。对此，本文从增强时间序列的局部信息角度出发，结合最近邻算法的特性，对DTW算法展开相关研究，不仅提高了时间序列相似性度量的准确性，而且改善了时间序列分类的性能。本文的主要研究内容如下： （1）针对信号的局部扭曲、噪声干扰和高计算成本，DTW及其变体在分类精度或速度方面存在一些限制等问题，提出了基于局部极值形状的动态时间规整算法（ESDTW），实现了快速准确地时间序列对齐。ESDTW引入了局部极值来表示原始时间序列，并进一步使用DTW来对齐局部极值的形状描述符。通过考虑局部极值的位置信息，该方式避免了LEDTW中由局部极大值和局部极小值分别对齐而引起的不可靠时间序列对齐的问题。人工模拟的时间序列对的对齐实验表明，相比于对比算法ESDTW可以获得更准确的弯曲路径。结合最近邻分类器，ESDTW在84个UCR时间序列数据集上得到了比其他距离测量更高的分类准确率。此外，本文还证实了对于长时间序列数据集，ESDTW算法的计算效率显著提高。 （2）针对序列中存在的噪声容易导致时间序列匹配时局部出现过度拉伸和压缩问题，提出了一种噪声鲁棒的动态时间规整算法（NoiseDTW）。算法首先在原始的信号中引入额外噪声，抑制了序列对齐中存在的一个点对齐多个点的问题。然后，通过在两个时间序列之间多条可能的匹配路径中找到一条最优的匹配路径，减少噪声的随机性对时间序列相似性度量的影响。为了检测NoiseDTW算法的性能，结合最近邻算法，在8个时间序列数据集上与4个常用的相似性度量算法进行时间序列分类对比实验，实验结果表明，NoiseDTW具有较高的分类性能和时间效率，在时滞明显的时间序列数据中具有明显的效果。 （3）针对目前的 DTW 算法计算复杂度高和容易出现奇点问题，提出一种基于动态子窗口匹配的相似性度量算法（DSWM）。算法基于窗口约束DTW的思想，对原始时间序列引入了一些重叠的小窗口表示，来提高DTW算法的计算效率，并根据信号频率的大小选择子窗口的大小，可以有效避免窗口过大或者过小对算法性能的影响。该算法在提高计算效率的同时使相似性度量的准确率也得到了提升。实验表明DSWM算法在大多数公共数据集上都表现出良好的性能。
NETL