Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series

Hoang Anh Dau, Diego Furtado Silva, Francois Petitjean, Germain Forestier, Anthony Bagnall, Eamonn Keogh

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

While the Dynamic Time Warping (DTW)-based Nearest-Neighbor Classification algorithm is regarded as a strong baseline for time series classification, in recent years there has been a plethora of algorithms that have claimed to be able to improve upon its accuracy in the general case. Many of these proposed ideas sacrifice the simplicity of implementation that DTW-based classifiers offer for rather modest gains. Nevertheless, there are clearly times when even a small improvement could make a large difference in an important medical or financial domain. In this work, we make an unexpected claim; an underappreciated 'low hanging fruit' in optimizing DTW's performance can produce improvements that make it an even stronger baseline, closing most or all the improvement gap of the more sophisticated methods. We show that the method currently used to learn DTW's only parameter, the maximum amount of warping allowed, is likely to give the wrong answer for small training sets. We introduce a simple method to mitigate the small training set issue by creating synthetic exemplars to help learn the parameter. We evaluate our ideas on the UCR Time Series Archive and a case study in fall classification, and demonstrate that our algorithm produces significant improvement in classification accuracy.

Original languageEnglish
Title of host publicationProceedings - 2017 IEEE International Conference on Big Data
Subtitle of host publicationDec 11- 14, 2017 • Boston, MA, USA
EditorsJian-Yun Nie, Zoran Obradovic, Toyotaro Suzumura, Rumi Ghosh, Raghunath Nambiar, Chonggang Wang, Hui Zang, Ricardo Baeza-Yates, Xiaohua Hu, Jeremy Kepner, Alfredo Cuzzocrea, Jian Tang, Masashi Toyoda
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages917-922
Number of pages6
ISBN (Electronic)9781538627143, 9781538627150
ISBN (Print)9781538627167
DOIs
Publication statusPublished - 2017
EventIEEE International Conference on Big Data (Big Data) 2017 - Boston, United States of America
Duration: 11 Dec 201714 Dec 2017
Conference number: 5th
http://cci.drexel.edu/bigdata/bigdata2017/

Conference

ConferenceIEEE International Conference on Big Data (Big Data) 2017
Abbreviated titleBig Data 2017
CountryUnited States of America
CityBoston
Period11/12/1714/12/17
Internet address

Keywords

  • classification
  • Dynamic Time Warping
  • time series

Cite this

Dau, H. A., Silva, D. F., Petitjean, F., Forestier, G., Bagnall, A., & Keogh, E. (2017). Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series. In J-Y. Nie, Z. Obradovic, T. Suzumura, R. Ghosh, R. Nambiar, C. Wang, H. Zang, R. Baeza-Yates, X. Hu, J. Kepner, A. Cuzzocrea, J. Tang, ... M. Toyoda (Eds.), Proceedings - 2017 IEEE International Conference on Big Data: Dec 11- 14, 2017 • Boston, MA, USA (pp. 917-922). Piscataway NJ USA: IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/BigData.2017.8258009
Dau, Hoang Anh ; Silva, Diego Furtado ; Petitjean, Francois ; Forestier, Germain ; Bagnall, Anthony ; Keogh, Eamonn. / Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series. Proceedings - 2017 IEEE International Conference on Big Data: Dec 11- 14, 2017 • Boston, MA, USA. editor / Jian-Yun Nie ; Zoran Obradovic ; Toyotaro Suzumura ; Rumi Ghosh ; Raghunath Nambiar ; Chonggang Wang ; Hui Zang ; Ricardo Baeza-Yates ; Xiaohua Hu ; Jeremy Kepner ; Alfredo Cuzzocrea ; Jian Tang ; Masashi Toyoda. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2017. pp. 917-922
@inproceedings{4726caa4b4ca48ff83944e72f2cb0b1e,
title = "Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series",
abstract = "While the Dynamic Time Warping (DTW)-based Nearest-Neighbor Classification algorithm is regarded as a strong baseline for time series classification, in recent years there has been a plethora of algorithms that have claimed to be able to improve upon its accuracy in the general case. Many of these proposed ideas sacrifice the simplicity of implementation that DTW-based classifiers offer for rather modest gains. Nevertheless, there are clearly times when even a small improvement could make a large difference in an important medical or financial domain. In this work, we make an unexpected claim; an underappreciated 'low hanging fruit' in optimizing DTW's performance can produce improvements that make it an even stronger baseline, closing most or all the improvement gap of the more sophisticated methods. We show that the method currently used to learn DTW's only parameter, the maximum amount of warping allowed, is likely to give the wrong answer for small training sets. We introduce a simple method to mitigate the small training set issue by creating synthetic exemplars to help learn the parameter. We evaluate our ideas on the UCR Time Series Archive and a case study in fall classification, and demonstrate that our algorithm produces significant improvement in classification accuracy.",
keywords = "classification, Dynamic Time Warping, time series",
author = "Dau, {Hoang Anh} and Silva, {Diego Furtado} and Francois Petitjean and Germain Forestier and Anthony Bagnall and Eamonn Keogh",
year = "2017",
doi = "10.1109/BigData.2017.8258009",
language = "English",
isbn = "9781538627167",
pages = "917--922",
editor = "Jian-Yun Nie and Obradovic, {Zoran } and Suzumura, {Toyotaro } and Rumi Ghosh and Nambiar, {Raghunath } and Wang, {Chonggang } and Zang, {Hui } and Baeza-Yates, {Ricardo } and Xiaohua Hu and Kepner, {Jeremy } and Cuzzocrea, {Alfredo } and Tang, {Jian } and Toyoda, {Masashi }",
booktitle = "Proceedings - 2017 IEEE International Conference on Big Data",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
address = "United States of America",

}

Dau, HA, Silva, DF, Petitjean, F, Forestier, G, Bagnall, A & Keogh, E 2017, Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series. in J-Y Nie, Z Obradovic, T Suzumura, R Ghosh, R Nambiar, C Wang, H Zang, R Baeza-Yates, X Hu, J Kepner, A Cuzzocrea, J Tang & M Toyoda (eds), Proceedings - 2017 IEEE International Conference on Big Data: Dec 11- 14, 2017 • Boston, MA, USA. IEEE, Institute of Electrical and Electronics Engineers, Piscataway NJ USA, pp. 917-922, IEEE International Conference on Big Data (Big Data) 2017, Boston, United States of America, 11/12/17. https://doi.org/10.1109/BigData.2017.8258009

Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series. / Dau, Hoang Anh; Silva, Diego Furtado; Petitjean, Francois; Forestier, Germain; Bagnall, Anthony; Keogh, Eamonn.

Proceedings - 2017 IEEE International Conference on Big Data: Dec 11- 14, 2017 • Boston, MA, USA. ed. / Jian-Yun Nie; Zoran Obradovic; Toyotaro Suzumura; Rumi Ghosh; Raghunath Nambiar; Chonggang Wang; Hui Zang; Ricardo Baeza-Yates; Xiaohua Hu; Jeremy Kepner; Alfredo Cuzzocrea; Jian Tang; Masashi Toyoda. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2017. p. 917-922.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series

AU - Dau, Hoang Anh

AU - Silva, Diego Furtado

AU - Petitjean, Francois

AU - Forestier, Germain

AU - Bagnall, Anthony

AU - Keogh, Eamonn

PY - 2017

Y1 - 2017

N2 - While the Dynamic Time Warping (DTW)-based Nearest-Neighbor Classification algorithm is regarded as a strong baseline for time series classification, in recent years there has been a plethora of algorithms that have claimed to be able to improve upon its accuracy in the general case. Many of these proposed ideas sacrifice the simplicity of implementation that DTW-based classifiers offer for rather modest gains. Nevertheless, there are clearly times when even a small improvement could make a large difference in an important medical or financial domain. In this work, we make an unexpected claim; an underappreciated 'low hanging fruit' in optimizing DTW's performance can produce improvements that make it an even stronger baseline, closing most or all the improvement gap of the more sophisticated methods. We show that the method currently used to learn DTW's only parameter, the maximum amount of warping allowed, is likely to give the wrong answer for small training sets. We introduce a simple method to mitigate the small training set issue by creating synthetic exemplars to help learn the parameter. We evaluate our ideas on the UCR Time Series Archive and a case study in fall classification, and demonstrate that our algorithm produces significant improvement in classification accuracy.

AB - While the Dynamic Time Warping (DTW)-based Nearest-Neighbor Classification algorithm is regarded as a strong baseline for time series classification, in recent years there has been a plethora of algorithms that have claimed to be able to improve upon its accuracy in the general case. Many of these proposed ideas sacrifice the simplicity of implementation that DTW-based classifiers offer for rather modest gains. Nevertheless, there are clearly times when even a small improvement could make a large difference in an important medical or financial domain. In this work, we make an unexpected claim; an underappreciated 'low hanging fruit' in optimizing DTW's performance can produce improvements that make it an even stronger baseline, closing most or all the improvement gap of the more sophisticated methods. We show that the method currently used to learn DTW's only parameter, the maximum amount of warping allowed, is likely to give the wrong answer for small training sets. We introduce a simple method to mitigate the small training set issue by creating synthetic exemplars to help learn the parameter. We evaluate our ideas on the UCR Time Series Archive and a case study in fall classification, and demonstrate that our algorithm produces significant improvement in classification accuracy.

KW - classification

KW - Dynamic Time Warping

KW - time series

UR - http://www.scopus.com/inward/record.url?scp=85047762839&partnerID=8YFLogxK

U2 - 10.1109/BigData.2017.8258009

DO - 10.1109/BigData.2017.8258009

M3 - Conference Paper

SN - 9781538627167

SP - 917

EP - 922

BT - Proceedings - 2017 IEEE International Conference on Big Data

A2 - Nie, Jian-Yun

A2 - Obradovic, Zoran

A2 - Suzumura, Toyotaro

A2 - Ghosh, Rumi

A2 - Nambiar, Raghunath

A2 - Wang, Chonggang

A2 - Zang, Hui

A2 - Baeza-Yates, Ricardo

A2 - Hu, Xiaohua

A2 - Kepner, Jeremy

A2 - Cuzzocrea, Alfredo

A2 - Tang, Jian

A2 - Toyoda, Masashi

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - Piscataway NJ USA

ER -

Dau HA, Silva DF, Petitjean F, Forestier G, Bagnall A, Keogh E. Judicious setting of Dynamic Time Warping's window width allows more accurate classification of time series. In Nie J-Y, Obradovic Z, Suzumura T, Ghosh R, Nambiar R, Wang C, Zang H, Baeza-Yates R, Hu X, Kepner J, Cuzzocrea A, Tang J, Toyoda M, editors, Proceedings - 2017 IEEE International Conference on Big Data: Dec 11- 14, 2017 • Boston, MA, USA. Piscataway NJ USA: IEEE, Institute of Electrical and Electronics Engineers. 2017. p. 917-922 https://doi.org/10.1109/BigData.2017.8258009