Using Graph Spectral to solve Change Point Detection Problems

• Luis Gustavo C. Uzai UTFPR
• André Y. Kashiwabara UTFPR

DOI: https://doi.org/10.5753/eniac.2018.4461

Resumo

Time series are sequence of values distributed over time. Analyzing time series is important in many areas including medical, financial, aerospace, commercial and entertainment. Change Point Detection is the problem of identifying changes in meaning or distribution of data in a time series. This article presents Spec, a new algorithm that uses the graph spectrum to detect change points. The Spec was evaluated using the UCR Archive which is a large da- tabase of different time series. Spec performance was compared to the PELT, ECP, EDM, and gSeg algorithms. The results showed that Spec achieved a better accuracy compared to the state of the art in some specific scenarios and as efficient as in most cases evaluated.

Referências

Aminikhanghahi, S. and Cook, D. J. (2016). A survey of methods for time series change point detection. Knowledge and Information Systems, pages 1–29.

Basseville, M. and Nikiforov, I. (1993). Detection of abrupt changes. Theory and application, volume 2.

Bonsal, B. R., Zhang, X., Vincent, L. A., and Hogg,W. D. (2001). Characteristics of daily and extreme temperatures over Canada. Journal of Climate, 14(9):1959–1976.

Bosc, M., Heitz, F., Armspach, J. P., Namer, I., Gounot, D., and Rumbach, L. (2003). Automatic change detection in multimodal serial MRI: Application to multiple sclerosis lesion evolution. NeuroImage, 20(2):643–656.

Casaca, W. C. d. O. (2014). Graph laplacian for spectral clustering and seeded image segmentation. PhD thesis, Universidade de São Paulo.

Cheboli, D. (2010). Anomaly detection on time series. 2010 IEEE International Conference on Progress in Informatics and Computing, 1:603–608.

Chen, H. and Zhang, N. (2015). Graph-based change-point detection. Annals of Statistics, 43(1):139–176.

Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., and Batista, G. (2015). The ucr time series classification archive. www.cs.ucr.edu/~eamonn/time_series_data/.

Cook, D. and Krishnan, N. (2015). Activity Learning, volume 1.

de Abreu, N. M. M., Del-Vecchio, R., Trevisan, V., and Vinagre, C. T. M. (2014). Teoria Espectral de Grafos - Uma Introdução. page 201.

Ducré-Robitaille, J. F., Vincent, L. A., and Boulet, G. (2003). Comparison of techniques for detection of discontinuities in temperature series. International Journal of Climatology, 23(9):1087–1101.

Fritscher, E. (2011). Propriedades espectrais de um grafo.

Fujita, A., Takahashi, D. Y., Balardin, J. B., Vidal, M. C., and Sato, J. R. (2017). Correlation between graphs with an application to brain network analysis. Computational Statistics and Data Analysis, 109:76–92.

Gower, J. C. (1982). Euclidean distance geometry. Math. Sci, 7(1):1–14.

Itoh, N. and Kurths, J. (2010). Change-Point Detection of Climate Time Series by Nonparametric Method. In Proceedings of theWorld Congress on Engineering and Computer Science, volume I, pages 20–23.

James, N. A., Kejariwal, A., and Matteson, D. S. (2016). In Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016, pages 3499–3508.

Keogh, E. and Kasetty, S. (2003). On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Mining and knowledge discovery, 7(4):349–371.

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.

Lai, T. L. (2014). Sequential changepoint detection in quality control and dynamical systems. Journal of the Royal Statistical Society, 47(3):429–437.

Li, S., Xu, L. D., and Zhao, S. (2015). The internet of things: a survey. Information Systems Frontiers, 17(2):243–259.

Luxburg, U. V. (2007). A Tutorial on Spectral Clustering. pages 1–32.

Malladi, R., Kalamangalam, G. P., and Aazhang, B. (2013). Online Bayesian change point detection algorithms for segmentation of epileptic activity. In Conference Record - Asilomar Conference on Signals, Systems and Computers, pages 1833–1837.

Matteson, D. S. and James, N. A. (2014). Journal of the American Statistical Association, 109(505):334–345.

Moreira, F. d. S. (2011). Detecção de pontos de mudança em séries temporais utilizando uma formulação Neural/Fuzzy/Bayesiana: Aplicaçao na detecção de falhas. DissertaçãoMestrado - UFMG, page 69.

Neto, J. (2013). Spectral clustering. http://www.di.fc.ul.pt/~jpn/r/spectralclustering/spectralclustering.html.

Ng, A. Y., Jordan, M. I., and Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pages 849–856.

Page, E. S. (1955). A Test for a Change in a Parameter Occurring at an Unknown Point. Biometrika, 42(3/4):523.

Rakthanmanon, T., Campana, B., Mueen, A., Batista, G., Westover, B., Zhu, Q., Zakaria, J., and Keogh, E. (2013). Addressing big data time series: Mining trillions of time series subsequences under dynamic time warping. ACM Transactions on Knowledge Discovery from Data (TKDD), 7(3):10.

Reeves, J., Chen, J., Wang, X. L., Lund, R., and Lu, Q. Q. (2007). A review and comparison of changepoint detection techniques for climate data. Journal of Applied Meteorology and Climatology, 46(6):900–915.

Spielman, D. A. (2007). Spectral graph theory and its applications. In Foundations of Computer Science, 2007. FOCS’07. 48th Annual IEEE Symposium on, pages 29–38. IEEE.

Staudacher, M., Telser, S., Amann, A., Hinterhuber, H., and Ritsch-Marte, M. (2005). A new method for change-point detection developed for on-line analysis of the heart beat variability during sleep. Physica A: Statistical Mechanics and its Applications, 349(3-4):582–596.

Vidal, M. C., Sato, J. R., Balardin, J. B., Takahashi, D. Y., and Fujita, A. (2017). Anocva in r: A software to compare clusters between groups and its application to the study of autism spectrum disorder. Frontiers in neuroscience, 11:16.

Yang, P., Dumont, G., and Ansermino, J. M. (2006). Adaptive change detection in heart rate trend monitoring in anesthetized children. IEEE Transactions on Biomedical Engineering, 53(11):2211–2219.

Yonetanil, T. and Mccabe, G. J. (1994). Abrupt changes in regional temperature in the conternimous United States, 1895-1989. Climate Research, 4:13–23.