SAXJS: An Online Change Point Detection for Wearable Sensor Data
Resumo
Wearable electronics are devices used by humans that can continuously and uninterruptedly monitor human activity through sensor data. The data collected by them have several applications, such as recommending running techniques and helping to monitor health status. Segmenting such data into chunks containing only a single human activity is challenging due to the wide variability of underlying process characteristics presented in the data. To deal with this problem, we propose a new change point detection algorithm based on the Symbolic Aggregate approXimation (SAX) transformation, the probability of transition between symbols, and the Jensen-Shannon distance.
Referências
Adams, R. P. and MacKay, D. J. (2007). Bayesian online changepoint detection. arXiv preprint arXiv:0710.3742.
Alhammad, N. and Al-Dossari, H. (2021). Dynamic segmentation for physical activity recognition using a single wearable sensor. Applied Sciences, 11(6):2633.
Aminikhanghahi, S. and Cook, D. J. (2017). A survey of methods for time series change point detection. Knowledge and information systems, 51(2):339-367.
Aminikhanghahi, S., Wang, T., and Cook, D. J. (2018). Real-time change point detection with application to smart home time series data. IEEE Transactions on Knowledge and Data Engineering, 31(5):1010-1023.
Arlot, S., Celisse, A., and Harchaoui, Z. (2019). A kernel multiple change-point algorithm via model selection. Journal of machine learning research, 20(162).
Benson, L. C., Clermont, C. A., Osis, S. T., Kobsar, D., and Ferber, R. (2018). Classifying running speed conditions using a single wearable sensor: Optimal segmentation and feature extraction methods. Journal of biomechanics, 71:94-99.
Booth, N. and Smith, A. (1982). A bayesian approach to retrospective identification of change-points. Journal of Econometrics, 19(1):7-22.
Bulling, A., Blanke, U., and Schiele, B. (2014). A tutorial on human activity recognition using body-worn inertial sensors. ACM Computing Surveys (CSUR), 46(3):1-33.
Celisse, A., Marot, G., Pierre-Jean, M., and Rigaill, G. (2018). New efficient algorithms for multiple change-point detection with reproducing kernels. Computational Statistics & Data Analysis, 128:200-220.
Cleland, I., Donnelly, M. P., Nugent, C. D., Hallberg, J., Espinilla, M., and Garcia-Constantino, M. (2018). Collection of a diverse, realistic and annotated dataset for wearable activity recognition. In 2018 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops), pages 555-560. IEEE.
De Ryck, T., De Vos, M., and Bertrand, A. (2021). Change point detection in time series data using autoencoders with a time-invariant representation. IEEE Transactions on Signal Processing, 69:3513-3524.
Fida, B., Bernabucci, I., Bibbo, D., Conforto, S., and Schmid, M. (2015). Varying behavior of different window sizes on the classification of static and dynamic physical activities from a single accelerometer. Medical engineering & physics, 37(7):705-711.
Gao, W., Emaminejad, S., Nyein, H. Y. Y., Challa, S., Chen, K., Peck, A., Fahad, H. M., Ota, H., Shiraki, H., Kiriya, D., et al. (2016). Fully integrated wearable sensor arrays for multiplexed in situ perspiration analysis. Nature, 529(7587):509-514.
IDTechEx (2021). Wearable technology forecasts 2021-2031.
Ige, A. O. and Noor, M. H. M. (2022). A survey on unsupervised learning for wearable sensor-based activity recognition. Applied Soft Computing, page 109363.
Kanamori, T., Hido, S., and Sugiyama, M. (2009). A least-squares approach to direct importance estimation. The Journal of Machine Learning Research, 10:1391-1445.
Kawaguchi, N., Ogawa, N., Iwasaki, Y., Kaji, K., Terada, T., Murao, K., Inoue, S., Kawahara, Y., Sumi, Y., and Nishio, N. (2011a). Hasc challenge: gathering large scale human activity corpus for the real-world activity understandings. In Proceedings of the 2nd augmented human international conference, pages 1-5.
Kawaguchi, N., Yang, Y., Yang, T., Ogawa, N., Iwasaki, Y., Kaji, K., Terada, T., Murao, K., Inoue, S., Kawahara, Y., et al. (2011b). Hasc2011corpus: towards the common ground of human activity recognition. In Proceedings of the 13th international conference on Ubiquitous computing, pages 571-572.
Kawahara, Y. and Sugiyama, M. (2009). Change-point detection in time-series data by direct density-ratio estimation. In Proceedings of the 2009 SIAM international conference on data mining, pages 389-400. SIAM.
Kawahara, Y., Yairi, T., and Machida, K. (2007). Change-point detection in time-series data based on subspace identification. In Seventh IEEE International Conference on Data Mining (ICDM 2007), pages 559-564. IEEE.
Killick, R., Fearnhead, P., and Eckley, I. A. (2012). Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association, 107(500):1590-1598.
Ko, S. I., Chong, T. T., and Ghosh, P. (2015). Dirichlet process hidden markov multiple change-point model. Bayesian Analysis, 10(2):275-296.
Larzen, R. and Marx, M. (1981). An introduction to mathematical statistics and it's applications.
Lin, J. (1991). Divergence measures based on the shannon entropy. IEEE Transactions on Information theory, 37(1):145-151.
Lin, J., Keogh, E., Wei, L., and Lonardi, S. (2007). Experiencing sax: a novel symbolic representation of time series. Data Mining and knowledge discovery, 15(2):107-144.
Liu, S., Yamada, M., Collier, N., and Sugiyama, M. (2013). Change-point detection in time-series data by relative density-ratio estimation. Neural Networks, 43:72-83.
Nachiar, C. C., Ambika, N., Moulika, R., and Poovendran, R. (2020). Design of cost-effective wearable sensors with integrated health monitoring system. In 2020 Fourth International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud)(ISMAC), pages 1289-1292. IEEE.
Napier, C., Esculier, J.-F., and Hunt, M. A. (2017). Gait retraining: out of the lab and onto the streets with the benefit of wearables.
Ni, Q., Patterson, T., Cleland, I., and Nugent, C. (2016). Dynamic detection of window starting positions and its implementation within an activity recognition framework. Journal of biomedical informatics, 62:171-180.
Page, E. (1955). A test for a change in a parameter occurring at an unknown point. Biometrika, 42(3/4):523-527.
Patterson, T., Khan, N., McClean, S., Nugent, C., Zhang, S., Cleland, I., and Ni, Q. (2016). Sensor-based change detection for timely solicitation of user engagement. IEEE Transactions on Mobile Computing, 16(10):2889-2900.
Prajapati, D. and Mahapatra, P. (2009). A new x chart comparable to cusum and ewma charts. International Journal of Productivity and Quality Management, 4(1):103-128.
Press, W. H. and Teukolsky, S. A. (1990). Savitzky-golay smoothing filters. Computers in Physics, 4(6):669-672.
Saatçi, Y., Turner, R. D., and Rasmussen, C. E. (2010). Gaussian process change point models. In ICML.
Selles, R. W., Formanoy, M. A., Bussmann, J. B., Janssens, P. J., and Stam, H. J. (2005). Automated estimation of initial and terminal contact timing using accelerometers; development and validation in transtibial amputees and controls. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 13(1):81-88.
Shinmoto Torres, R. L., Ranasinghe, D. C., and Shi, Q. (2013). Evaluation of wearable sensor tag data segmentation approaches for real time activity classification in elderly. In International conference on mobile and ubiquitous systems: computing, networking, and services, pages 384-395. Springer.
Takeuchi, J.-i. and Yamanishi, K. (2006). A unifying framework for detecting outliers and change points from time series. IEEE transactions on Knowledge and Data Engineering, 18(4):482-492.
Thakur, D. and Biswas, S. (2022). Online change point detection in application with transition-aware activity recognition. IEEE Transactions on Human-Machine Systems, 52(6):1176-1185.
Traversaro, F., Redelico, F. O., Risk, M. R., Frery, A. C., and Rosso, O. A. (2018). Bandt-pompe symbolization dynamics for time series with tied values: A data-driven approach. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(7):075502.
Truong, C., Oudre, L., and Vayatis, N. (2020). Selective review of offline change point detection methods. Signal Processing, 167:107299.
Verdier, G. (2020). An empirical likelihood-based cusum for on-line model change detection. Communications in Statistics-Theory and Methods, 49(8):1818-1839.
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, e. a., and SciPy 1.0 Contributors (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272.
Yamanishi, K. and Takeuchi, J.-i. (2002). A unifying framework for detecting outliers and change points from non-stationary time series data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 676-681.
Zhang, S., Galway, L., McClean, S., Scotney, B., Finlay, D., and Nugent, C. D. (2010). Deriving relationships between physiological change and activities of daily living using wearable sensors. In International Conference on Sensor Systems and Software, pages 235-250. Springer.
Zunino, L., Olivares, F., Ribeiro, H. V., and Rosso, O. A. (2022). Permutation jensen-shannon distance: A versatile and fast symbolic tool for complex time-series analysis. Physical Review E, 105(4):045310.
Alhammad, N. and Al-Dossari, H. (2021). Dynamic segmentation for physical activity recognition using a single wearable sensor. Applied Sciences, 11(6):2633.
Aminikhanghahi, S. and Cook, D. J. (2017). A survey of methods for time series change point detection. Knowledge and information systems, 51(2):339-367.
Aminikhanghahi, S., Wang, T., and Cook, D. J. (2018). Real-time change point detection with application to smart home time series data. IEEE Transactions on Knowledge and Data Engineering, 31(5):1010-1023.
Arlot, S., Celisse, A., and Harchaoui, Z. (2019). A kernel multiple change-point algorithm via model selection. Journal of machine learning research, 20(162).
Benson, L. C., Clermont, C. A., Osis, S. T., Kobsar, D., and Ferber, R. (2018). Classifying running speed conditions using a single wearable sensor: Optimal segmentation and feature extraction methods. Journal of biomechanics, 71:94-99.
Booth, N. and Smith, A. (1982). A bayesian approach to retrospective identification of change-points. Journal of Econometrics, 19(1):7-22.
Bulling, A., Blanke, U., and Schiele, B. (2014). A tutorial on human activity recognition using body-worn inertial sensors. ACM Computing Surveys (CSUR), 46(3):1-33.
Celisse, A., Marot, G., Pierre-Jean, M., and Rigaill, G. (2018). New efficient algorithms for multiple change-point detection with reproducing kernels. Computational Statistics & Data Analysis, 128:200-220.
Cleland, I., Donnelly, M. P., Nugent, C. D., Hallberg, J., Espinilla, M., and Garcia-Constantino, M. (2018). Collection of a diverse, realistic and annotated dataset for wearable activity recognition. In 2018 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops), pages 555-560. IEEE.
De Ryck, T., De Vos, M., and Bertrand, A. (2021). Change point detection in time series data using autoencoders with a time-invariant representation. IEEE Transactions on Signal Processing, 69:3513-3524.
Fida, B., Bernabucci, I., Bibbo, D., Conforto, S., and Schmid, M. (2015). Varying behavior of different window sizes on the classification of static and dynamic physical activities from a single accelerometer. Medical engineering & physics, 37(7):705-711.
Gao, W., Emaminejad, S., Nyein, H. Y. Y., Challa, S., Chen, K., Peck, A., Fahad, H. M., Ota, H., Shiraki, H., Kiriya, D., et al. (2016). Fully integrated wearable sensor arrays for multiplexed in situ perspiration analysis. Nature, 529(7587):509-514.
IDTechEx (2021). Wearable technology forecasts 2021-2031.
Ige, A. O. and Noor, M. H. M. (2022). A survey on unsupervised learning for wearable sensor-based activity recognition. Applied Soft Computing, page 109363.
Kanamori, T., Hido, S., and Sugiyama, M. (2009). A least-squares approach to direct importance estimation. The Journal of Machine Learning Research, 10:1391-1445.
Kawaguchi, N., Ogawa, N., Iwasaki, Y., Kaji, K., Terada, T., Murao, K., Inoue, S., Kawahara, Y., Sumi, Y., and Nishio, N. (2011a). Hasc challenge: gathering large scale human activity corpus for the real-world activity understandings. In Proceedings of the 2nd augmented human international conference, pages 1-5.
Kawaguchi, N., Yang, Y., Yang, T., Ogawa, N., Iwasaki, Y., Kaji, K., Terada, T., Murao, K., Inoue, S., Kawahara, Y., et al. (2011b). Hasc2011corpus: towards the common ground of human activity recognition. In Proceedings of the 13th international conference on Ubiquitous computing, pages 571-572.
Kawahara, Y. and Sugiyama, M. (2009). Change-point detection in time-series data by direct density-ratio estimation. In Proceedings of the 2009 SIAM international conference on data mining, pages 389-400. SIAM.
Kawahara, Y., Yairi, T., and Machida, K. (2007). Change-point detection in time-series data based on subspace identification. In Seventh IEEE International Conference on Data Mining (ICDM 2007), pages 559-564. IEEE.
Killick, R., Fearnhead, P., and Eckley, I. A. (2012). Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association, 107(500):1590-1598.
Ko, S. I., Chong, T. T., and Ghosh, P. (2015). Dirichlet process hidden markov multiple change-point model. Bayesian Analysis, 10(2):275-296.
Larzen, R. and Marx, M. (1981). An introduction to mathematical statistics and it's applications.
Lin, J. (1991). Divergence measures based on the shannon entropy. IEEE Transactions on Information theory, 37(1):145-151.
Lin, J., Keogh, E., Wei, L., and Lonardi, S. (2007). Experiencing sax: a novel symbolic representation of time series. Data Mining and knowledge discovery, 15(2):107-144.
Liu, S., Yamada, M., Collier, N., and Sugiyama, M. (2013). Change-point detection in time-series data by relative density-ratio estimation. Neural Networks, 43:72-83.
Nachiar, C. C., Ambika, N., Moulika, R., and Poovendran, R. (2020). Design of cost-effective wearable sensors with integrated health monitoring system. In 2020 Fourth International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud)(ISMAC), pages 1289-1292. IEEE.
Napier, C., Esculier, J.-F., and Hunt, M. A. (2017). Gait retraining: out of the lab and onto the streets with the benefit of wearables.
Ni, Q., Patterson, T., Cleland, I., and Nugent, C. (2016). Dynamic detection of window starting positions and its implementation within an activity recognition framework. Journal of biomedical informatics, 62:171-180.
Page, E. (1955). A test for a change in a parameter occurring at an unknown point. Biometrika, 42(3/4):523-527.
Patterson, T., Khan, N., McClean, S., Nugent, C., Zhang, S., Cleland, I., and Ni, Q. (2016). Sensor-based change detection for timely solicitation of user engagement. IEEE Transactions on Mobile Computing, 16(10):2889-2900.
Prajapati, D. and Mahapatra, P. (2009). A new x chart comparable to cusum and ewma charts. International Journal of Productivity and Quality Management, 4(1):103-128.
Press, W. H. and Teukolsky, S. A. (1990). Savitzky-golay smoothing filters. Computers in Physics, 4(6):669-672.
Saatçi, Y., Turner, R. D., and Rasmussen, C. E. (2010). Gaussian process change point models. In ICML.
Selles, R. W., Formanoy, M. A., Bussmann, J. B., Janssens, P. J., and Stam, H. J. (2005). Automated estimation of initial and terminal contact timing using accelerometers; development and validation in transtibial amputees and controls. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 13(1):81-88.
Shinmoto Torres, R. L., Ranasinghe, D. C., and Shi, Q. (2013). Evaluation of wearable sensor tag data segmentation approaches for real time activity classification in elderly. In International conference on mobile and ubiquitous systems: computing, networking, and services, pages 384-395. Springer.
Takeuchi, J.-i. and Yamanishi, K. (2006). A unifying framework for detecting outliers and change points from time series. IEEE transactions on Knowledge and Data Engineering, 18(4):482-492.
Thakur, D. and Biswas, S. (2022). Online change point detection in application with transition-aware activity recognition. IEEE Transactions on Human-Machine Systems, 52(6):1176-1185.
Traversaro, F., Redelico, F. O., Risk, M. R., Frery, A. C., and Rosso, O. A. (2018). Bandt-pompe symbolization dynamics for time series with tied values: A data-driven approach. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(7):075502.
Truong, C., Oudre, L., and Vayatis, N. (2020). Selective review of offline change point detection methods. Signal Processing, 167:107299.
Verdier, G. (2020). An empirical likelihood-based cusum for on-line model change detection. Communications in Statistics-Theory and Methods, 49(8):1818-1839.
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, e. a., and SciPy 1.0 Contributors (2020). SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272.
Yamanishi, K. and Takeuchi, J.-i. (2002). A unifying framework for detecting outliers and change points from non-stationary time series data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 676-681.
Zhang, S., Galway, L., McClean, S., Scotney, B., Finlay, D., and Nugent, C. D. (2010). Deriving relationships between physiological change and activities of daily living using wearable sensors. In International Conference on Sensor Systems and Software, pages 235-250. Springer.
Zunino, L., Olivares, F., Ribeiro, H. V., and Rosso, O. A. (2022). Permutation jensen-shannon distance: A versatile and fast symbolic tool for complex time-series analysis. Physical Review E, 105(4):045310.
Publicado
22/05/2023
Como Citar
RIQUETI, Giovanna A.; BARROS, Pedro H.; BORGES, João B.; CUNHA, Felipe D.; ROSSO, Osvaldo A.; RAMOS, Heitor S..
SAXJS: An Online Change Point Detection for Wearable Sensor Data. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 41. , 2023, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 351-364.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2023.395.
