弹性粗粒度动态弯曲时序相似性算法

陈明威 孙丽华 徐健锋

摘 要：针对动态时间弯曲（DTW）算法在提高计算速度同时不能兼顾分类正确率的问题，提出了一种基于朴素粒计算思想的弹性粗粒度动态时间弯曲（CGDTW）算法。首先，通过计算时序方差特征的方法来获取较优的时序粒度，用粒度特征代替原始序列；其次，再代入执行DTW算法，允许动态调整被比较时序粒间的弹性大小，从而获得相对最优的时序对应粒；最后，在对应最优粒的情况下计算DTW距离。同时引入下界函数的提前终止策略进一步提高CGDTW算法效率。实验结果表明，所提算法要比经典算法运行速率提高21.4%左右，比降维策略算法正确率提高近32.3个百分点，尤其是长序列的分类，CGDTW能够在保持正确率的情况下兼顾较高的运行效率。CGDTW在实际应用中能适应不确定长序列分类。

关键词：时序；时间粒；动态弯曲；弹性

中图分类号： TP301.6 文献标志码：A英文标题