Detecting time series motifs under uniform scaling

ABSTRACT

Time series motifs are approximately repeated patterns foundwithin the data. Such motifs have utility for many data mining algorithms, including rule-discovery,novelty-detection, summarization and clustering. Since the formalization of the problem and the introduction of efficient linear time algorithms, motif discovery has been successfully applied tomany domains, including medicine, motion capture, robotics and meteorology.

In this work we show that most previous applications of time series motifs have been severely limited by the definition's brittleness to even slight changes of uniform scaling, the speed at which the patterns develop. We introduce a new algorithm that allows discovery of time series motifs with invariance to uniform scaling, and show that it produces objectively superior results in several important domains. Apart from being more general than all other motifdiscovery algorithms, a further contribution of our work isthat it is simpler than previous approaches, in particular we have drastically reduced the number of parameters that need to be specified.

REFERENCES

• 1: H. Abe and T. Yamaguchi. Implementing an integrated time-series data mining environment - a case study of medical kdd on chronic hepatitis-. 1st International Conference on Complex Medical Engineering (CME2005), 2005.
• 2: I. Androulakis. New approaches for representing, analyzing and visualizing complex kinetic mechanisms. In Proc. of the 15th European Symposium on Computer Aided Process Engineering, 2005.
• 3: I. Androulakis, J. Wu, J. Vitolo, and C. Roth. Selecting maximally informative genes to enable temporal expression profiling analysis. In Proc. of Foundations of Systems Biology in Engineering, 2005.
• 4: R. Andrzejak, K. Lehnertz, F. Mormann, C. R. P. David, and C. Elger. Indications of nonlinear deterministic and finite-dimensional structures in time series of brain electrical activity: dependence on recording region and brain state. Phys Rev E Stat Nonlin Soft Matter Phys, 64, 2001.
• 5: D. Arita, H. Yoshimatsu, and R. Taniguchi. Frequent motion pattern extraction for motion recognition in real-time human proxy. In Proc. of JSAI Workshop on Conversational Informatics, pages 25--30, 2005.
• 6: Jeremy Buhler , Martin Tompa, Finding motifs using random projections, Proceedings of the fifth annual international conference on Computational biology, p.69-76, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369172]
• 7: W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
• 8: B. Celly and V. Zordan. Animated people textures. In Proc. of 17th International Conference on Computer Animation and Social Agents (CASA), 2004.
• 9: Bill Chiu , Eamonn Keogh , Stefano Lonardi, Probabilistic discovery of time series motifs, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956808]
• 10: F. DuchÆene, C. Garbay, and V. Rialle. Apprentissage non supervise de motifs temporels, multidimensionnels et hétérogènes. application a la télésurveillance médicale. CAP, 2005.
• 11: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 12: Pascale Fung, A pattern matching method for finding noun and proper noun translations from noisy parallel corpora, Proceedings of the 33rd annual meeting on Association for Computational Linguistics, p.236-243, June 26-30, 1995, Cambridge, Massachusetts [doi>10.3115/981658.981690]
• 13: R. Hamid, S. Maddi, A. Johnson, A. Bobick, I. Essa, and C. Isbell. Unsupervised activity discovery and characterization from event-streams. In Proc. of the 21st Conference on Uncertainty in Artificial Intelligence (UAI05), 2005.
• 14: Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258656]
• 15: E. Keogh, S. Lonardi, V. Zordan, S. Lee, and M. Jara. Visualizing the similarity of human and chimp DNA. Multimedia Video, http://www.cs.ucr.edu/ eamonn/DNA/, 2005.
• 16: Eamonn Keogh , Themistoklis Palpanas , Victor B. Zordan , Dimitrios Gunopulos , Marc Cardle, Indexing large human-motion databases, Proceedings of the Thirtieth international conference on Very large data bases, p.780-791, August 31-September 03, 2004, Toronto, Canada
• 17: Eamonn Keogh , Li Wei , Xiaopeng Xi , Sang-Hee Lee , Michail Vlachos, LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 18: E. J. Keogh. Efficiently finding arbitrarily scaled patterns in massive time series databases. In PKDD, pages 253--265, 2003.
• 19: J. Lin, E. Keogh, S. Lonardi, and P. Patel. Finding motifs in time series. In Proc. 2nd Workshop on Temporal Data Mining (KDD'02), 2002.
• 20: J. Maizel and R. Lenk. Enhanced graphic matrix analysis of nucleic acid and protein sequences. In Proc. Natl. Acad. Sci. USA, volume 78, pages 7665--7669, 1981.
• 21: A. McGovern, D. Rosendahl, A. Kruger, M. Beaton, R. Brown, and K. Droegemeier. Understanding the formation of tornadoes through data mining. 5th Conference on Artificial Intelligence and its Applications to Environmental Sciences at the American Meteorological Society, 2007.
• 22: D. Minnen, T. Starner, I. Essa, and C. Isbell. Discovering characteristic actions from on-body sensor data. 10th International Symposium on Wearable Computers (ISWC06), 2006.
• 23: K. Murakami, S. Doki, S. Okuma, and Y. Yano. A study of extraction method of motion patterns observed frequently from time-series posture data. IEEE International Conference on Systems, Man and Cybernetics, 4:3610--3615, 2005.
• 24: Pavel A. Pevzner , Sing-Hoi Sze, Combinatorial Approaches to Finding Subtle Signals in DNA Sequences, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.269-278, August 19-23, 2000
• 25: D. Rogers. Corner tang knives across Texas. Personal Press, 2000.
• 26: S. Rombo and G. Terracina. Discovering representative models in large time series databases. In Proc. of the 6th International Conference On Flexible Query Answering Systems, pages 84--97, 2004.
• 27: T. Sauer. Time series prediction by using delay coordinate embedding. Time Series Prediction. Forecasting the Future and Understanding the Past, 59(8):175--193, August 1994.
• 28: Yoshiki Tanaka , Kazuhisa Iwamoto , Kuniaki Uehara, Discovery of Time-Series Motif from Multi-Dimensional Data Based on MDL Principle, Machine Learning, v.58 n.2-3, p.269-300, February 2005 [doi>10.1007/s10994-005-5829-2]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
motifs, random projection, time series, uniform scaling