Fast Time Series Classification using Numerosity Reduction (2006)

by Xiaopeng Xi, Eamonn Keogh, Christian Shelton, Li Wei, and Chotirat Ann Ratanamahatana

Abstract: Many algorithms have been proposed for the problem of time series classification. However, it is clear that one-nearest-neighbor with Dynamic Time Warping (DTW) distance is exceptionally difficult to beat. This approach has one weakness, however; it is computationally too demanding for many real-time applications. One way to mitigate this problem is to speed up the DTW calculations. Nonetheless, there is a limit to how much this can help. In this work, we propose an additional technique, numerosity reduction, to speed up one-nearest neighbor DTW. While the idea of numerosity reduction for nearest-neighbor classifiers has a long history, we show here that we can leverage off an original observation about the relationship between dataset size and DTW constraints to produce an extremely compact dataset with little or no loss in accuracy. We test our ideas with a comprehensive set of experiments, and show that it can efficiently produce extremely fast accurate classifiers.

Download Information

Xiaopeng Xi, Eamonn Keogh, Christian Shelton, Li Wei, and Chotirat Ann Ratanamahatana (2006). "Fast Time Series Classification using Numerosity Reduction." Proceedings of the Twenty-Third International Conference on Machine Learning (pp. 1033-1040).

Bibtex citation

@inproceedings{XiKeoSheWeiCho06,
   author = "Xiaopeng Xi and Eamonn Keogh and Christian Shelton and Li Wei and Chotirat Ann Ratanamahatana",
   title = "Fast Time Series Classification using Numerosity Reduction",
   booktitle = "Proceedings of the Twenty-Third International Conference on Machine Learning",
   booktitleabbr = "{ICML}",
   year = 2006,
   pages = "1033--1040",
}