摘要
动态时间规整算法(Dynamictimewarping,DTW)是时间序列相似性度量中的一种常用算法，它可以消除欧氏距离“点对点”匹配缺陷，通过“一对多”的匹配方式度量不同长度时间序列，获得较高匹配精度。算法对时间序列偏移、振幅变化等具有较强鲁棒性，在不同领域受到了广泛应用。但也有以下不足：算法计算量大、时间复杂度高，限制其在大规模数据上应用。此外，DTW在对齐过程中忽略序列的局部形状特征，容易导致不合理匹配，对复杂变化的时间序列度量精度降低。针对上述问题，本文对动态时间规整算法进行了不同方向的改进，主要工作如下： (1)对现有DTW算法计算量大、时间复杂度高的问题，在不降低原有算法相似分类准确率的情况下，提出基于时间序列极值点自适应加权的动态时间规整算法(EWDTW)。该算法首先利用局部极值近似表示原始序列，以降低原始序列的维数，然后在计算最佳动态弯曲路径的过程中，基于极值点的相位差、大小、类型等特征量为每个局部极值点设置自适应代价权重，在降低时间复杂度的同时有效改善序列的病态对齐现象。在部分UCR数据集上进行的实验结果表明，EWDTW算法提高了运算效率，同时算法的分类准确率高于已有的几种DTW及其衍生算法，此外对大部分不同类型的时间序列特别是长时间序列有良好的度量性能。 (2)LEDTW是一种有效提高DTW计算效率的改进算法。为保持前者高效的运算效率，改善其在短、中时间序列上度量精度偏低的问题，提出基于极值特征改进的LEDTW算法(FLEDTW)。算法标注原始时间序列局部极值点，根据极值点位置对时间序列分段，对相邻极值点进行线性拟合，之后选取极值点大小、极值点左拟合线段斜率、右拟合线段斜率和极值点位置作为四维特征量。提取所有局部极值点的四维特征构成极值特征矩阵，接着根据点的类型分别度量极大值特征矩阵和极小值特征矩阵的相似距离，以二者之和作为FLEDTW的度量结果。算法采用无参数度量的方法，在计算最佳动态弯曲路径的过程中，四维特征有效改善了序列因过度拉伸或压缩导致的度量精度低的问题，同时算法保持了LEDTW高效的计算效率。在UCR数据集的短、中、长三类时间序列上的实验结果表明，算法有效提高了LEDTW的分类准确率，且在中长时间序列上的时间复杂度与LEDTW相同。 (3)为改善DTW算法在复杂变化的时间序列上的度量效果，提出时间序列分解的动态时间规整算法(SFDTW)。算法将时间序列分解为滤波信号，斜率信号和波动信号。滤波信号反映时间序列的整体趋势，斜率信号反映时间序列的斜率变化特征，波动信号反映时间序列的局部波动情况。在后续相似度量的过程中，算法根据序列特点和实际需求调整分解信号的权重参数，得到更好的相似度量结果。通过调整滤波窗口长度和波动信号权重，算法能有效减少或消除噪声污染，有较强鲁棒性。实验结果表明，算法有效提高了时间序列的相似度量效果和分类性能，适用于不同类型的时间序列数据。
NETL