Semi-supervised time series classification

ABSTRACT

The problem of time series classification has attracted great interest in the last decade. However current research assumes the existence of large amounts of labeled training data. In reality, such data may be very difficult or expensive to obtain. For example, it may require the time and expertise of cardiologists, space launch technicians, or other domain specialists. As in many other domains, there are often copious amounts of unlabeled data available. For example, the PhysioBank archive contains gigabytes of ECG data. In this work we propose a semi-supervised technique for building time series classifiers. While such algorithms are well known in text domains, we will show that special considerations must be made to make them both efficient and effective for the time series domain. We evaluate our work with a comprehensive set of experiments on diverse data sources including electrocardiograms, handwritten documents, and video datasets. The experimental results demonstrate that our approach requires only a handful of labeled examples to construct accurate classifiers.

REFERENCES

• 1: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 2: Chapelle, O., Scholkopf, B., & Zien, A. (2006). Semi-Supervised Learning. In press. MIT Press.
• 3: Chen, L. & Kamel, M. S. (2005). Design of Multiple Classifier Systems for Time Series Data. Multiple Classifier Systems, pp. 216-225, 2005.
• 4: Lei Chen , M. Tamer Öszu , Vincent Oria, Using multi-scale histograms to answer pattern existence and shape match queries, Proceedings of the 17th international conference on Scientific and statistical database management, p.217-226, June 27-29, 2005, Santa Barbara, CA
• 5: Ira Cohen , Fabio G. Cozman , Nicu Sebe , Marcelo C. Cirelo , Thomas S. Huang, Semisupervised Learning of Classifiers: Theory, Algorithms, and Their Application to Human-Computer Interaction, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.12, p.1553-1567, December 2004 [doi>10.1109/TPAMI.2004.127]
• 6: Cohen, W. (1993). Efficient pruning methods for separate-and-conquer rule learning systems. In proceedings of the 13th International Joint Conference on Artificial Intelligence, Chambery, France. pp. 988--994, 1993.
• 7: Goldberger, A., Amaral, L., Glass, L., Hausdorff, J., Ivanov, P., Mark, R., Mietus, J., Moody, G., Peng, C., & He, S. (2000). PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. Circulation 101(23): pp. 215--220, 2000.
• 8: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 9: Eamonn Keogh , Shruti Kasetty, On the need for time series data mining benchmarks: a survey and empirical demonstration, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775062]
• 10: Eamonn Keogh , Jessica Lin , Ada Fu, HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence, Proceedings of the Fifth IEEE International Conference on Data Mining, p.226-233, November 27-30, 2005 [doi>10.1109/ICDM.2005.79]
• 11: Kibler, D. & Langley, P. (1988). Machine learning as an experimental science. In proceedings of the 3rd European Working Session on Learning. pp. 81--92, 1988.
• 12: Landford, J. P. & Quan, A. (2002). Evolution of knowledge-based applications for launch support. In proceedings of Ground System Architecture Workshop, El Segundo, CA, 2002.
• 13: Manmatha, R. & Rath, T. M. (2003). Indexing of Handwritten Historical Documents - Recent Progress. In: Proc. of the 2003 Symposium on Document Image Understanding Technology (SDIUT), Greenbelt, MD, pp. 77--85, April 9-11, 2003.
• 14: Alex Nanopoulos , Rob Alcock , Yannis Manolopoulos, Feature-based classification of time-series data, Information processing and technology, Nova Science Publishers, Inc., Commack, NY, 2001
• 15: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 16: Ratanamahatana, C. A. & Keogh. E. (2004). Everything you know about Dynamic Time Warping is wrong. In proceedings of the Third Workshop on Mining Temporal and Sequential Data, in conjunction with the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 22-25, 2004.
• 17: Rath, T. & Manmatha, R. (2003). Word image matching using dynamic time warping. In proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Vol. II, pp. 521--527, 2003.
• 18: Li Wei , Eamonn Keogh , Helga Van Herle , Agenor Mafra-Neto, Atomic Wedgie: Efficient Query Filtering for Streaming Times Series, Proceedings of the Fifth IEEE International Conference on Data Mining, p.490-497, November 27-30, 2005 [doi>10.1109/ICDM.2005.28]
• 19: Wei, L. (2006). http://www.cs.ucr.edu/~wli/selfTraining/
• 20: Zhu, X. (2005). Semi-supervised learning literature survey. Technical report, no. 1530, Computer Sciences, University of Wisconsin-Madison, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
classification, semi-supervised learning, time series