噪声鲁棒的动态时间规整算法

动态时间规整(DTW)算法通过寻找两个时间序列的最佳匹配衡量序列之间的相似性。针对序列中存在的噪声容易导致时间序列匹配时局部出现过度拉伸和压缩问题,提出了一种噪声鲁棒的动态时间规整(NoiseDTW)算法。首先,在原始的信号中引入额外噪声,解决序列对齐中存在的一个点对齐多个点的问题;然后,通过在两个时间序列之间多条可能的匹配路径中找到一条最优的匹配路径,减少噪声的随机性对时间序列相似性度量的影响;最后,将匹配路径映射到原始序列上。实验结果表明,相较于欧氏距离(ED)、DTW、Sakoe-Chiba窗口动态时间规整(Sakoe-Chiba DTW)和加权动态时间规整(WDTW)算法,所提算法结合K-近邻(KNN)分类器得到的分类准确率在8个时间序列数据集上分别比次优算法提高了1~15个百分点。可见所提算法具有较好的分类性能,且对噪声具有鲁棒性。

基于时间加权改进的LDTW算法

在时间序列相似性度量研究中,动态时间弯曲(dynamic time warping,DTW)是最为常用的算法之一,但其存在病态对齐问题且未考虑时间属性影响。限制对齐路径长度DTW(DTW under limited warping path length,LDTW)和时间加权DTW(time-weighed DTW,TDTW)分别尝试解决上述两个问题中的一个,但未能同时解决DTW两方面的不足。为此提出一种综合时间权重的LDTW(time-weighting LDTW,TLDTW)算法。首先通过测量两个时间序列中时间点对的距离构建时间权值矩阵;然后在LDTW累计成本矩阵递归填充过程中融合对应的时间权值,以实现在考虑时间因素影响的同时保留有效抑制病态对齐特性。基于UCR数据集进行1-NN分类实验,实验结果显示基于TLDTW相似度量的分类准确率优于其他对比算法,且进一步对比验证了其可靠性。