Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 1910-1915.DOI: 10.11772/j.issn.1001-9081.2018010106

Previous Articles     Next Articles

Time series classifier design based on piecewise dimensionality reduction and updated dynamic time warping

CHANG Bingguo, ZANG Hongying   

  1. College of Information Science and Engineering, Hunan University, Changsha Hunan 410082, China
  • Received:2018-01-15 Revised:2018-04-03 Online:2018-07-10 Published:2018-07-12
  • Supported by:
    This work is partially supported by the Key Research and Development Program of Hunan Province (2016GK2050).

基于分段降维和路径修正DTW的时序特征分类器设计

常炳国, 臧虹颖   

  1. 湖南大学 信息科学与工程学院, 长沙 410082
  • 通讯作者: 臧虹颖
  • 作者简介:常炳国(1963-),男,陕西榆林人,副教授,博士,主要研究方向:信息集成方法与应用;臧虹颖(1993-),女,湖南长沙人,硕士研究生,主要研究方向:时间序列数据挖掘、分类与预测。
  • 基金资助:
    湖南省重点研发计划资助项目(2016GK2050)。

Abstract: Since traditional Dynamic Time Warping (DTW) measurement method is prone to over-bending and has the shortcoming of high computation complexity and low efficiency, an Updated Dynamic Time Warping (UDTW) measurement method based on path correction was proposed. Firstly, the characteristic information of time series was extracted by Piecewise Local Max-smoothing (PLM) method (a dimensionality reduction method), so that the computational cost of UDTW was reduced. Secondly, considering the sequence similarity requirements of morphological characteristics, a dynamic penalty factor was set to correct the bending degree of the excessive bending path. Finally, based on updated distance metric, 1-nearest neighbor classification algorithm was used to classify time series data, which improved the accuracy and efficiency of the time series similarity measurement. The experimental results show that UDTW measurement method outperforms the traditional DTW measurement method among 15 UCR datasets, and the accuracy rate achieved 100% in 3 of them. In the comparison experiments with Derivative DTW (DDTW) measurement method, UDTW increases the classification accuracy by 71.8% at most, and the execution time of PLM-UDTW is reduced by 99% without decreasing classification accuracy.

Key words: time series classifier, feature representation, Dynamic Time Warping (DTW), penalty function, similarity measurement

摘要: 针对传统的动态时间弯曲(DTW)度量方法易出现过度弯曲现象且计算复杂度高、算法效率低等问题,提出一种基于路径修正的动态时间弯曲(UDTW)度量方法。首先通过分段降维方法——分段局部最大值平滑法(PLM)有效提取序列特征信息,减少UDTW的计算代价;其次,考虑了时间序列形态特征的相似性要求,给过度弯曲路径设置动态惩罚系数,以此修正路径的弯曲程度;最后,在改进度量距离基础上,采用1-近邻分类算法对时序数据进行分类,以提高时间序列相似性度量的准确率和效率。实验结果表明,在15个UCR数据集上,UDTW度量方法与传统DTW度量方法相比具有更高的分类准确率,UDTW在其中3个数据集上能实现100%分类正确;与导数DTW(DDTW)度量方法相比,UDTW分类准确率最多提高了71.8%,而PLM-UDTW在不影响分类准确率的前提下执行时间减小了99%。

关键词: 时间序列分类器, 特征表示, 动态时间弯曲, 惩罚函数, 相似性度量

CLC Number: