Interval and dynamic time warping-based decision trees

ABSTRACT

This work presents decision trees adequate for the classification of series data. There are several methods for this task, but most of them focus on accuracy. One of the requirements of data mining is to produce comprehensible models. Decision trees are one of the most comprehensible classifiers. The use of these methods directly on this kind of data is, generally, not adequate, because complex and inaccurate classifiers are obtained. Hence, instead of using the raw features, new ones are constructed.This work presents two types of trees. In interval-based trees, the decision nodes evaluate a function (e.g., the average) in an interval and the result is compared to a threshold. For DTW-based trees each decision node has a reference example. The distance from the example to classify to the reference example is calculated and then it is compared to a threshold.The method for obtaining these trees it is based on 1) to develop a method that obtains for a 2-class data set a classifier formed by a new feature (a function in an interval or the distance to a reference example) and a threshold, 2) to use the boosting method to obtain an ensemble of these classifiers, and 3) to use a method for constructing decision trees using as data set the features selected by boosting.

REFERENCES

• 1: author.
• 2: R. J. Alcock and Y. Manolopoulos. Time-series similarity queries employing a feature-based approach. In Proceedings of the 7th Hellenic Conference on Informatics, Ioannina, Greece, 1999.
• 3: Claus Bahlmann , Bernard Haasdonk , Hans Burkhardt, On-Line Handwriting Recognition with Support Vector Machines " A Kernel Approach, Proceedings of the Eighth International Workshop on Frontiers in Handwriting Recognition (IWFHR'02), p.49, August 06-08, 2002
• 4: P. Geurts. Contributions to decision tree induction: bias/variance tradeoff and time series classification. PhD thesis, Department of Electrical Engineering and Computer Science, University of Liège, Belgium, 2002. http://www.montefiore.ulg.ac.be/~geurts/thesis.html.
• 5: S. Hettich and S. D. Bay. The UCI KDD archive {http://kdd.ics.uci.edu}, 1999. Irvine, CA: University of California, Department of Information and Computer Science.
• 6: Mohammed Waleed Kadous, Temporal classification: extending the classification paradigm to multivariate time series, 2002
• 7: E. Keogh. Exact indexing of dynamic time warping. In 28th International Conference on Very Large Data Bases, 2002.
• 8: Mineichi Kudo , Jun Toyama , Masaru Shimbo, Multidimensional curve classification using passing—through regions, Pattern Recognition Letters, v.20 n.11-13, p.1103-1111, Nov. 1999 [doi>10.1016/S0167-8655(99)00077-X]
• 9: D. Roverso. Multivariate temporal classification by windowed wavelet decomposition and recurrent neural networks. In 3rd ANS International Topical Meeting on Nuclear Plant Instrumentation, Control and Human-Machine Interface, 2000. http://www.ife.no/media/383_NPIC049.pdf.
• 10: Naoki Saito , Ronald R. Coifman, Local feature extraction and its applications using a library of bases, 1994
• 11: R. E. Schapire. The boosting approach to machine learning: An overview. In MSRI Workshop on Nonlinear Estimation and Classification, 2002. http://www.cs.princeton.edu/~schapire/papers/msri.ps.gz.
• 12: Robert E. Schapire , Yoram Singer, Improved boosting algorithms using confidence-rated predictions, Proceedings of the eleventh annual conference on Computational learning theory, p.80-91, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279960]
• 13: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000