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

来源：计算机应用杂志2016年第6期北京时间：

作者：陈明威, 孙丽华, 徐健锋

单位：1. 南昌大学 软件学院, 南昌 330047;2. 同济大学 计算机科学与技术系, 上海 201804

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

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

基金资助：国家自然科学基金资助项目(61070139,61273304)。