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. M. Brand. Incremental singular value decomposition of uncertain data with missing values. In Proceedings of the 7th European Conference on Computer Vision, pages 707--720, London, UK, 2002. Springer-Verlag.
2. J. Chai and J. K. Hodgins. Performance animation from low-dimensional control signals. In SIGGRAPH '05: ACM SIGGRAPH 2005 Papers, pages 686--696, New York, NY, USA, 2005. ACM.
3. J. Gao, B. Ding, W. Fan, J. Han, and P. S. Yu. Classifying data streams with skewed class distributions and concept drifts. IEEE Internet Computing, 12(6):37--49, 2008.
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. Plankers, R. Boulic, and D. Thalmann. Skeleton-based motion capture for robust reconstruction of human motion. In CA '00: Proceedings of the Computer Animation, page 77, Washington, DC, USA, 2000. IEEE Computer Society.
6. E. Hsu, S. Gentry, and J. Popovic. Example-based control of human motion. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, pages 69--77, Aire-la-Ville, Switzerland, 2004. Eurographics Association.
7. A. Jain, E. Y. Chang, and Y.-F. Wang. Adaptive stream resource management using kalman filters. In SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 11--22, New York, NY, USA, 2004. ACM.
8. E. Keogh, T. Palpanas, V. B. Zordan, D. Gunopulos, and M. Cardle. Indexing large human-motion databases. In VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases, pages 780--791. VLDB Endowment, 2004.
9. N. D. Lawrence and A. J. Moore. Hierarchical gaussian process latent variable models. In ICML '07: Proceedings of the 24th international conference on Machine learning, pages 481--488, New York, NY, USA, 2007. ACM.
10. J.-G. Lee, J. Han, and X. Li. Trajectory outlier detection: A partition-and-detect framework. IEEE 24th International Conference on Data Engineering, pages 140--149, April 2008.
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. J. Lin, E. Keogh, S. Lonardi, and B. Chiu. A symbolic representation of time series, with implications for streaming algorithms. In DMKD '03: Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, pages 2--11, New York, NY, USA, 2003. ACM Press.
13. G. Liu and L. McMillan. Estimation of missing markers in human motion capture. Vis. Comput., 22(9):721--728, 2006.
14. S. Mehta, S. Parthasarathy, and R. Machiraju. On trajectory representation for scientific features. IEEE International Conference on Data Mining, 2006.
15. S. Papadimitriou, A. Brockwell, and C. Faloutsos. Adaptive, hands-off stream mining. In VLDB '2003: Proceedings of the 29th international conference on Very large data bases, pages 560--571. VLDB Endowment, 2003.
16. S. I. Park and J. K. Hodgins. Capturing and animating skin deformation in human motion. ACM Trans. Graph., 25(3):881--889, 2006.
17. J. Shieh and E. Keogh. isax: indexing and mining terabyte sized time series. In KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 623--631, New York, NY, USA, 2008. ACM.
18. N. Srebro and T. Jaakkola. Weighted low-rank approximations. In 20th International Conference on Machine Learning, pages 720--727. AAAI Press, 2003.
19. Y. Tao, C. Faloutsos, D. Papadias, and B. Liu. Prediction and indexing of moving objects with unknown motion patterns. In SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 611--622, New York, NY, USA, 2004. ACM Press.
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. B.-K. Yi, N. D. Sidiropoulos, T. Johnson, H. V. Jagadish, C. Faloutsos, and A. Biliris. Online data mining for co-evolving time sequences. In ICDE '00: Proceedings of the 16th International Conference on Data Engineering, page 13, Washington, DC, USA, 2000. IEEE Computer Society.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

    • Machine learning approaches

      • Markov decision processes

• Information systems

  • Information systems applications

    • Data mining

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes