DynaMMo: mining and summarization of coevolving sequences with missing values

ABSTRACT

Given multiple time sequences with missing values, we propose DynaMMo which summarizes, compresses, and finds latent variables. The idea is to discover hidden variables and learn their dynamics, making our algorithm able to function even when there are missing values.

We performed experiments on both real and synthetic datasets spanning several megabytes, including motion capture sequences and chlorine levels in drinking water. We show that our proposed DynaMMo method (a) can successfully learn the latent variables and their evolution; (b) can provide high compression for little loss of reconstruction accuracy; (c) can extract compact but powerful features for segmentation, interpretation, and forecasting; (d) has complexity linear on the duration of sequences.

REFERENCES

• 1: 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
• 2: Jinxiang Chai , Jessica K. Hodgins, Performance animation from low-dimensional control signals, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 3: Jing Gao , Bolin Ding , Wei Fan , Jiawei Han , Philip S. Yu, Classifying Data Streams with Skewed Class Distributions and Concept Drifts, IEEE Internet Computing, v.12 n.6, p.37-49, November 2008 [doi>10.1109/MIC.2008.119]
• 4: Z. Ghahramani and M. I. Jordan. Supervised learning from incomplete data via an EM approach. In J. D. Cowan, G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, volume 6, pages 120--127. Morgan Kaufmann Publishers, Inc., 1994.
• 5: L. Herda , P. Fua , R. Plänkers , R. Boulic , D. Thalmann, Skeleton-Based Motion Capture for Robust Reconstruction of Human Motion, Proceedings of the Computer Animation, p.77, May 03-05, 2000
• 6: Eugene Hsu , Sommer Gentry , Jovan Popović, Example-based control of human motion, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028534]
• 7: Ankur Jain , Edward Y. Chang , Yuan-Fang Wang, Adaptive stream resource management using Kalman Filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007573]
• 8: 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
• 9: Neil D. Lawrence , Andrew J. Moore, Hierarchical Gaussian process latent variable models, Proceedings of the 24th international conference on Machine learning, p.481-488, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273557]
• 10: Jae-Gil Lee , Jiawei Han , Xiaolei Li, Trajectory Outlier Detection: A Partition-and-Detect Framework, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.140-149, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497422]
• 11: L. Li, J. McCann, C. Faloutsos, and N. Pollard. Laziness is a virtue: Motion stitching using effort minimization. In Short Papers Proceedings of EUROGRAPHICS, 2008.
• 12: Jessica Lin , Eamonn Keogh , Stefano Lonardi , Bill Chiu, A symbolic representation of time series, with implications for streaming algorithms, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882086]
• 13: Guodong Liu , Leonard McMillan, Estimation of missing markers in human motion capture, The Visual Computer: International Journal of Computer Graphics, v.22 n.9, p.721-728, September 2006 [doi>10.1007/s00371-006-0080-9]
• 14: Sameep Mehta , Srinivasan Parthasarathy , Raghu Machiraju, On Trajectory Representation for Scientific Features, Proceedings of the Sixth International Conference on Data Mining, p.997-1001, December 18-22, 2006 [doi>10.1109/ICDM.2006.120]
• 15: Spiros Papadimitriou , Anthony Brockwell , Christos Faloutsos, Adaptive, hands-off stream mining, Proceedings of the 29th international conference on Very large data bases, p.560-571, September 09-12, 2003, Berlin, Germany
• 16: Sang Il Park , Jessica K. Hodgins, Capturing and animating skin deformation in human motion, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 17: Jin Shieh , Eamonn Keogh, iSAX: indexing and mining terabyte sized time series, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401966]
• 18: N. Srebro and T. Jaakkola. Weighted low-rank approximations. In 20th International Conference on Machine Learning, pages 720--727. AAAI Press, 2003.
• 19: Yufei Tao , Christos Faloutsos , Dimitris Papadias , Bin Liu, Prediction and indexing of moving objects with unknown motion patterns, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007637]
• 20: M. E. Wall, A. Rechtsteiner, and L. M. Rocha. Singular value decomposition and principal component analysis. In D. P. Berrar, W. Dubitzky, and M. Granzow, editors, A Practical Approach to Microarray Data Analysis, pages 91--109, Norwell, MA, Mar 2003. Kluwel.
• 21: Online Data Mining for Co-Evolving Time Sequences, Proceedings of the 16th International Conference on Data Engineering, p.13, February 28-March 03, 2000

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms, Experimentation

Keywords:
bayesian network, expectation maximization (em), missing value, time series