Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm

Francois Petitjean, Germain Forestier, Geoffrey I. Webb, Ann E. Nicholson, Yanping Chen, Eamonn Keogh

    Research output: Contribution to journalArticleResearchpeer-review

    50 Citations (Scopus)

    Abstract

    A concerted research effort over the past two decades has heralded significant
    improvements in both the efficiency and effectiveness of time series classification. The consensus that has emerged in the community is that the best solution is a surprisingly simple one. In virtually all domains, the most accurate classifier is the nearest neighbor algorithm with dynamic time warping as the distance measure. The time complexity of dynamic time warping means that successful deployments on resource-constrained devices remain elusive. Moreover, the recent explosion of interest in wearable computing devices, which typically have limited computational resources, has greatly increased the need for very efficient classification algorithms. A classic technique to obtain the benefits of the nearest neighbor algorithm, without inheriting its undesirable time and space complexity, is to use the nearest centroid algorithm. Unfortunately, the unique properties of (most) time series data mean that the centroid typically does not resemble any of the instances, an unintuitive and underappreciated fact. In this paper we demonstrate thatwe can exploit a recent result by Petitjean et al. to allow meaningful averaging of “warped” time series, which then allows us to create super-efficient nearest “centroid” classifiers that are at least as accurate as their more computationally challenged nearest neighbor relatives.We demonstrate empirically the utility of our approach by comparing it to all the appropriate strawmen algorithms on the ubiquitous UCR Benchmarks and with a case study in supporting insect classification on resource-constrained sensors.
    Original languageEnglish
    Pages (from-to)1 - 26
    Number of pages26
    JournalKnowledge and Information Systems
    Volume47
    Issue number1
    DOIs
    Publication statusPublished - 2016

    Cite this

    @article{5302e958f291434782686e508bccc402,
    title = "Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm",
    abstract = "A concerted research effort over the past two decades has heralded significantimprovements in both the efficiency and effectiveness of time series classification. The consensus that has emerged in the community is that the best solution is a surprisingly simple one. In virtually all domains, the most accurate classifier is the nearest neighbor algorithm with dynamic time warping as the distance measure. The time complexity of dynamic time warping means that successful deployments on resource-constrained devices remain elusive. Moreover, the recent explosion of interest in wearable computing devices, which typically have limited computational resources, has greatly increased the need for very efficient classification algorithms. A classic technique to obtain the benefits of the nearest neighbor algorithm, without inheriting its undesirable time and space complexity, is to use the nearest centroid algorithm. Unfortunately, the unique properties of (most) time series data mean that the centroid typically does not resemble any of the instances, an unintuitive and underappreciated fact. In this paper we demonstrate thatwe can exploit a recent result by Petitjean et al. to allow meaningful averaging of “warped” time series, which then allows us to create super-efficient nearest “centroid” classifiers that are at least as accurate as their more computationally challenged nearest neighbor relatives.We demonstrate empirically the utility of our approach by comparing it to all the appropriate strawmen algorithms on the ubiquitous UCR Benchmarks and with a case study in supporting insect classification on resource-constrained sensors.",
    author = "Francois Petitjean and Germain Forestier and Webb, {Geoffrey I.} and Nicholson, {Ann E.} and Yanping Chen and Eamonn Keogh",
    year = "2016",
    doi = "10.1007/s10115-015-0878-8",
    language = "English",
    volume = "47",
    pages = "1 -- 26",
    journal = "Knowledge and Information Systems",
    issn = "0219-1377",
    publisher = "Springer-Verlag London Ltd.",
    number = "1",

    }

    Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm. / Petitjean, Francois; Forestier, Germain; Webb, Geoffrey I.; Nicholson, Ann E.; Chen, Yanping; Keogh, Eamonn.

    In: Knowledge and Information Systems, Vol. 47, No. 1, 2016, p. 1 - 26.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm

    AU - Petitjean, Francois

    AU - Forestier, Germain

    AU - Webb, Geoffrey I.

    AU - Nicholson, Ann E.

    AU - Chen, Yanping

    AU - Keogh, Eamonn

    PY - 2016

    Y1 - 2016

    N2 - A concerted research effort over the past two decades has heralded significantimprovements in both the efficiency and effectiveness of time series classification. The consensus that has emerged in the community is that the best solution is a surprisingly simple one. In virtually all domains, the most accurate classifier is the nearest neighbor algorithm with dynamic time warping as the distance measure. The time complexity of dynamic time warping means that successful deployments on resource-constrained devices remain elusive. Moreover, the recent explosion of interest in wearable computing devices, which typically have limited computational resources, has greatly increased the need for very efficient classification algorithms. A classic technique to obtain the benefits of the nearest neighbor algorithm, without inheriting its undesirable time and space complexity, is to use the nearest centroid algorithm. Unfortunately, the unique properties of (most) time series data mean that the centroid typically does not resemble any of the instances, an unintuitive and underappreciated fact. In this paper we demonstrate thatwe can exploit a recent result by Petitjean et al. to allow meaningful averaging of “warped” time series, which then allows us to create super-efficient nearest “centroid” classifiers that are at least as accurate as their more computationally challenged nearest neighbor relatives.We demonstrate empirically the utility of our approach by comparing it to all the appropriate strawmen algorithms on the ubiquitous UCR Benchmarks and with a case study in supporting insect classification on resource-constrained sensors.

    AB - A concerted research effort over the past two decades has heralded significantimprovements in both the efficiency and effectiveness of time series classification. The consensus that has emerged in the community is that the best solution is a surprisingly simple one. In virtually all domains, the most accurate classifier is the nearest neighbor algorithm with dynamic time warping as the distance measure. The time complexity of dynamic time warping means that successful deployments on resource-constrained devices remain elusive. Moreover, the recent explosion of interest in wearable computing devices, which typically have limited computational resources, has greatly increased the need for very efficient classification algorithms. A classic technique to obtain the benefits of the nearest neighbor algorithm, without inheriting its undesirable time and space complexity, is to use the nearest centroid algorithm. Unfortunately, the unique properties of (most) time series data mean that the centroid typically does not resemble any of the instances, an unintuitive and underappreciated fact. In this paper we demonstrate thatwe can exploit a recent result by Petitjean et al. to allow meaningful averaging of “warped” time series, which then allows us to create super-efficient nearest “centroid” classifiers that are at least as accurate as their more computationally challenged nearest neighbor relatives.We demonstrate empirically the utility of our approach by comparing it to all the appropriate strawmen algorithms on the ubiquitous UCR Benchmarks and with a case study in supporting insect classification on resource-constrained sensors.

    UR - http://link.springer.com/content/pdf/10.1007%2Fs10115-015-0878-8.pdf

    U2 - 10.1007/s10115-015-0878-8

    DO - 10.1007/s10115-015-0878-8

    M3 - Article

    VL - 47

    SP - 1

    EP - 26

    JO - Knowledge and Information Systems

    JF - Knowledge and Information Systems

    SN - 0219-1377

    IS - 1

    ER -