Times series averaging and denoising from a probabilistic perspective on time-elastic kernels

• Autorzy: Marteau Pierre-Francois

Identyfikatory

DOI

10.2478/amcs-2019-0028

• Języki publikacji: EN

Abstrakty

EN

In the light of regularized dynamic time warping kernels, this paper re-considers the concept of a time elastic centroid for a set of time series. We derive a new algorithm based on a probabilistic interpretation of kernel alignment matrices. This algorithm expresses the averaging process in terms of stochastic alignment automata. It uses an iterative agglomerative heuristic method for averaging the aligned samples, while also averaging the times of their occurrence. By comparing classification accuracies for 45 heterogeneous time series data sets obtained by first nearest centroid/medoid classifiers, we show that (i) centroid-based approaches significantly outperform medoid-based ones, (ii) for the data sets considered, our algorithm, which combines averaging in the sample space and along the time axes, emerges as the most significantly robust model for time-elastic averaging with a promising noise reduction capability. We also demonstrate its benefit in an isolated gesture recognition experiment and its ability to significantly reduce the size of training instance sets. Finally, we highlight its denoising capability using demonstrative synthetic data. Specifically, we show that it is possible to retrieve, from few noisy instances, a signal whose components are scattered in a wide spectral band.

Słowa kluczowe

EN

time series averaging; time elastic kernel; dynamic time warping; hidden Markov model

PL

szereg czasowy; dopasowanie czasu dynamiczne; ukryty model Markowa

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2019
• Tom: Vol. 29, no. 2
• Strony: 375--392
• Opis fizyczny: Bibliogr. 34 poz., rys., tab., wykr.

Twórcy

autor

Marteau Pierre-Francois

• Institute for Research in Computer Science and Stochastic Systems (IRISA), University of Southern Brittany, Tohannic Campus, 56000 Vannes, France

Bibliografia

• [1] Abdulla, W., Chow, D. and Sin, G. (2003). Cross-words reference template for DTW-based speech recognition systems, Conference on Convergent Technologies for the Asia-Pacific Region TENCON 2003, Bangalore, India, Vol. 4, pp. 1576–1579.
• [2] Carrillo, H. and Lipman, D. (1988). The multiple sequence alignment problem in biology, SIAM Journal on Applied Mathematics 48(5): 1073–1082.
• [3] Chen, L. and Ng, R. (2004). On the marriage of Lp-norms and edit distance, Proceedings of the 30th International Conference on Very Large Data Bases, VLDB’04, Toronto, Canada, pp. 792–803.
• [4] Chudova, D., Gaffney, S. and Smyth, P. (2003). Probabilistic models for joint clustering and time-warping of multidimensional curves, Proceedings of the 9th Conference on Uncertainty in Artificial Intelligence, UAI’03, San Francisco, CA, USA, pp. 134–141.
• [5] Cuturi, M., Vert, J.-P., Birkenes, O. and Matsui, T. (2007). A kernel for time series based on global alignments, IEEE ICASSP 2007, Honolulu, HI, USA, Vol. 2, pp. II-413–II-416.
• [6] Fasman, K.H. and Salzberg, S.L. (1998). An introduction to biological sequence analysis, in S.L. Salzberg et al., Computational Methods in Molecular Biology, Elsevier, Amsterdam, pp. 21–42.
• [7] Fréchet, M. (1906). Sur quelques points du calcul fonctionnel, Thèse, Faculté des sciences de Paris, Paris.
• [8] Ghouaiel, N., Marteau, P.-F. and Dupont, M. (2017). Continuous pattern detection and recognition in stream—a benchmark for online gesture recognition, International Journal of Applied Pattern Recognition 4(2): 146–160.
• [9] Gupta, L., Molfese, D., Tammana, R. and Simos, P. (1996). Nonlinear alignment and averaging for estimating the evoked potential, IEEE Transactions on Biomedical Engineering 43(4): 348–356.
• [10] Gupta, M., Gao, J., Aggarwal, C.C. and Han, J. (2014). Outlier detection for temporal data: A survey, IEEE Transactions on Knowledge and Data Engineering 26(9): 2250–2267.
• [11] Hassan, U. and Anwar, M.S. (2010). Reducing noise by repetition: Introduction to signal averaging, European Journal of Physics 31(3): 453.
• [12] Hautamaki, V., Nykanen, P. and Franti, P. (2008). Time-series clustering by approximate prototypes, 19th International Conference on Pattern Recognition, ICPR 2008, Tampa, FL, USA, pp. 1–4.
• [13] Juang, B. (1985). On the hidden Markov model and dynamic time warping for speech recognition—A unified view, AT&T Bell Laboratories Technical Journal 63(7): 1213–1242.
• [14] Just, W. and Just, W. (1999). Computational complexity of multiple sequence alignment with SP-score, Journal of Computational Biology 8(6): 615–623.
• [15] Kaiser, R. and Knight,W. (1979). Digital signal averaging, Journal of Magnetic Resonance (1969) 36(2): 215–220.
• [16] Keogh, E.J., Xi, X.,Wei, L. and Ratanamahatana, C. (2006). The UCR time series classification-clustering datasets, Repository, http://www.cs.ucr.edu/˜eamonn/time_series_data/.
• [17] Lichman, M. (2013). UCI Machine Learning Repository, http://archive.ics.uci.edu/ml.
• [18] Marteau, P.-F. (2007). Pulse width modulation data sets, http://people.irisa.fr/Pierre-Francois.Marteau/PWM/.
• [19] Marteau, P.-F. (2009). Time warp edit distance with stiffness adjustment for time series matching, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(2): 306–318.
• [20] Marteau, P.-F. and Gibet, S. (2014). On recursive edit distance kernels with application to time series classification, IEEE Transactions on Neural Networks and Learning Systems 26(6): 1121–1133.
• [21] Nakagawa, S. and Nakanishi, H. (1989). Speaker-independent English consonant and Japanese word recognition by a stochastic dynamic time warping method, Journal of Institution of Electronics and Telecommunication Engineers 34(1): 87–95.
• [22] Niennattrakul, V. and Ratanamahatana, C. (2007). Inaccuracies of shape averaging method using dynamic time warping for time series data, in Y. Shi et al. (Eds.), Computational Science—ICCS 2007, Lecture Notes in Computer Science, Vol. 4487, Springer, Berlin/Heidelberg, pp. 513–520.
• [23] Niennattrakul, V. and Ratanamahatana, C. (2009). Shape averaging under time warping, 6th International Conference on Electronics, Computer, Telecommunications and Information Technology, ECTI-CON 2009, Pattaya, Chonburi, Thailand, Vol. 02, pp. 626–629.
• [24] Petitjean, F., Forestier, G., Webb, G., Nicholson, A., Chen, Y. and Keogh, E. (2014). Dynamic time warping averaging of time series allows faster and more accurate classification, Proceedings of the 14th IEEE International Conference on Data Mining, Shenzhen, China, pp. 470–479.
• [25] Petitjean, F. and Gançarski, P. (2012). Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment, Journal of Theoretical Computer Science 414(1): 76–91.
• [26] Petitjean, F., Ketterlin, A. and Gançarski, P. (2011). A global averaging method for dynamic time warping, with applications to clustering, Pattern Recognition 44(3): 678–693.
• [27] Rabiner, L.R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition, Proceedings of the IEEE 77(2): 257–286.
• [28] Saito, N. (1994). Local Feature Extraction and Its Applications Using a Library of Bases, PhD thesis, Yale University, New Haven, CT.
• [29] Sakoe, H. and Chiba, S. (1971). A dynamic programming approach to continuous speech recognition, Proceedings of the 7th International Congress of Acoustic, Budapest, Hungary, pp. 65–68.
• [30] Soheily-Khah, S., Douzal-Chouakria, A. and Gaussier, E. (2016). Generalized k-means-based clustering for temporal data under weighted and kernel time warp, Pattern Recognition Letters 75: 63–69.
• [31] Velichko, V.M. and Zagoruyko, N.G. (1970). Automatic recognition of 200 words, International Journal of Man-Machine Studies 2: 223–234.
• [32] Wang, L. and Jiang, T. (1994). On the complexity of multiple sequence alignment, Journal of Computational Biology 1(4): 337–348.
• [33] Zhou, F. and De la Torre, F. (2009). Canonical time warping for alignment of human behavior, in Y. Bengio et al. (Eds.), Advances in Neural Information Processing Systems 22, Curran Associates, Inc., Vancouver, pp. 2286–2294.
• [34] Zhou, F. and De la Torre, F. (2016). Generalized canonical time warping, IEEE Transactions on Pattern Analysis and Machine Intelligence 38(2): 279–294.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).