A PCA-based similarity measure for multivariate time series

ABSTRACT

Multivariate time series (MTS) datasets are common in various multimedia, medical and financial applications. We propose a similarity measure for MTS datasets, <i>Eros</i> <i>E</i>xtended F<i>ro</i>beniu<i>s</i> norm), which is based on Principal Component Analysis (PCA). <i>Eros</i> applies PCA to MTS datasets represented as matrices to generate principal components and associated eigenvalues. These principal components and eigenvalues are then used to compare the similarity between MTS matrices. Though <i>Eros</i> in itself does not satisfy the triangle inequality, without which existing multidimensional indexing structures may not be utilized, the lower and upper bounds to satisfy the triangle inequality are obtained. In order to show the validity of <i>Eros</i> for similarity search on MTS datasets, we performed several experiments on three datasets (2 real-world and 1 synthetic). The results show the superiority of our approaches as compared to the traditional similarity measures for MTS datasets, such as Euclidean Distance (ED), Dynamic Time Warping (DTW), Weighted Sum SVD (WSSVD) and PCA similarity factor (S<sc>PCA</sc>) in precision/recall.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: J. Alon, S. Sclaroff, G. Kollios, and V. Pavlovic. Discovering clusters in motion time-series data. In IEEE CVPR, 2003.
• 3: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 4: Matthew Brand, Incremental Singular Value Decomposition of Uncertain Data with Missing Values, Proceedings of the 7th European Conference on Computer Vision-Part I, p.707-720, May 28-31, 2002
• 5: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 6: Andrea Corradini, Dynamic Time Warping for Off-Line Recognition of a Small Gesture Vocabulary, Proceedings of the IEEE ICCV Workshop on Recognition, Analysis, and Tracking of Faces and Gestures in Real-Time Systems (RATFG-RTS'01), p.82, July 13-August 13, 2001
• 7: Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Finding Similar Time Series, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.88-100, June 24-27, 1997
• 8: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 9: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 10: G. H. Golub and C. F. V. Loan. Matrix Computations. Johns Hopkins Univ Press, 1996.
• 11: C. Goutte, P. Toft, E. Rostrup, F. A. Nielsen, and L. K. Hansen. On clustering fmri time series. NeuroImage, 9(3), 1999.
• 12: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: S. Hettich and S. D. Bay. The UCI KDD Archive. http://kdd.ics.uci.edu, 1999.
• 14: F. Hoppner. Learning dependencies in multivariate time series. In Proc. of the ECAI'02 Workshop, 2002.
• 15: J. E. Jackson. A User's Guide to Principal Components. Wiley-Interscience, 1991.
• 16: Mohammed Waleed Kadous, Temporal classification: extending the classification paradigm to multivariate time series, 2002
• 17: E. Keogh. Exact indexing of dynamic time warping. In VLDB, 2002.
• 18: D. Kifer, S. Ben-David, and J. Gehrke. Detecting change in data streams. In Very Large Databases, 2004.
• 19: Deok-Hwan Kim , Chin-Wan Chung, QCluster: relevance feedback using adaptive clustering for content-based image retrieval, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872829]
• 20: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 21: W. Krzanowski. Between-groups comparison of principal components. JASA, 74(367), 1979.
• 22: T. K. Moon and W. C. Stirling. Mathematical Methods and Algorithms for Signal Processing. Prentice Hall, 2000.
• 23: C. Myers, L. R. Rabiner, and A. E. Rosenberg. Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE TASSP, ASSP-28(6), 1980.
• 24: Tim Oates, Identifying distinctive subsequences in multivariate time series by clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.322-326, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312268]
• 25: K. pong Chan and A. W.-C. Fu. Efficient time series matching by wavelets. In ICDE, 1999.
• 26: Cen Rao , Alexei Gritai , Mubarak Shah , Tanveer Syeda-Mahmood, View-invariant Alignment and Matching of Video Sequences, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.939, October 13-16, 2003
• 27: T. M. Rath and R. Manmatha. Lower-bounding of dynamic time warping distances for multivariate time series. Technical Report MM-40, University of Massachusetts Amherst, 2002.
• 28: D. Roverso. Plant diagnostics by transient classification: The aladdin approach. IJIS,Special Issue on Intelligent Systems for Plant Surveillance and Diagnostics, 2002.
• 29: H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE TASSP, ASSP-26(1), 1978.
• 30: Yasushi Sakurai , Masatoshi Yoshikawa , Ryoji Kataoka , Shunsuke Uemura, Similarity Search for Adaptive Ellipsoid Queries Using Spatial Transformation, Proceedings of the 27th International Conference on Very Large Data Bases, p.231-240, September 11-14, 2001
• 31: C. Shahabi. AIMS: An immersidata management system. In VLDB CIDR, 2003.
• 32: C. Shahabi and D. Yan. Real-time pattern isolation and recognition over immersive sensor data streams. In the 9th International Conference On Multi-Media Modeling, 2003.
• 33: D. Singhal, A.; Seborg. Clustering of multivariate time-series data. In Proceedings of the American Control Conference, volume 5, 2002.
• 34: Renato O. Stehling , Mario A. Nascimento , Alexandre X. Falcão, A compact and efficient image retrieval approach based on border/interior pixel classification, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584812]
• 35: Michael Steinbach , Pang-Ning Tan , Vipin Kumar , Steven Klooster , Christopher Potter, Discovery of climate indices using clustering, 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.956801]
• 36: Tanawongsuwan and Bobick. Performance analysis of time-distance gait parameters under different speeds. In 4th International Conference on Audio- and Video Based Biometric Person Authentication, Guildford, UK, June 2003.
• 37: A. Tucker, S. Swift, and X. Liu. Variable grouping in multivariate time series via correlation. IEEE TSMC, Part B, 31(2), 2001.
• 38: M. Vlachos, G. Kollios, and D. Gunopulos. Discovering similar multidimensional trajectories. In ICDE, 2002.
• 39: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, A comparison of DFT and DWT based similarity search in time-series databases, Proceedings of the ninth international conference on Information and knowledge management, p.488-495, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354857]
• 40: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001
• 41: X. L. Zhang, H. Begleiter, B. Porjesz, W. Wang, and A. Litke. Event related potentials during object recognition tasks. Brain Research Bulletin, 38(6), 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Multivariate statistics; Time series analysis

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
multivariate time series, nearest neighbor search, principal component analysis, similarity measure, singular value decomposition