nach oben

Knowledge and Information Systems

Erschienen in:

08.09.2016 | Survey Paper

A survey of methods for time series change point detection

verfasst von: Samaneh Aminikhanghahi, Diane J. Cook

Erschienen in: Knowledge and Information Systems | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Change points are abrupt variations in time series data. Such abrupt changes may represent transitions that occur between states. Detection of change points is useful in modelling and prediction of time series and is found in application areas such as medical condition monitoring, climate change detection, speech and image analysis, and human activity analysis. This survey article enumerates, categorizes, and compares many of the methods that have been proposed to detect change points in time series. The methods examined include both supervised and unsupervised algorithms that have been introduced and evaluated. We introduce several criteria to compare the algorithms. Finally, we present some grand challenges for the community to consider.

Nächster Artikel Exceptionally monotone models—the rank correlation model class for Exceptional Model Mining

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Adams RP, MacKay DJC (2007) Bayesian online changepoint detection. arXiv:0710.3742. Accessed 7 Aug 2015

Alippi C et al (2015) Change detection in multivariate datastreams: likelihood and detectability loss. arXiv:1510.04850. Accessed 25 Oct 2015

CENSREC-4—speech resources consortium. http://research.nii.ac.jp/src/en/CENSREC-4.html. Accessed 16 Sept 2015

Hasc Challenge 2011. http://hasc.jp/hc2011/. Accessed 16 Sept 2015

Welcome to CASAS. http://casas.wsu.edu/datasets/. Accessed 16 Sept 2015

Welcome to the UCR time series classification/clustering page. http://www.cs.ucr.edu/~eamonn/time_series_data/. Accessed 16 Sept 2015

Aue A et al (2009) Break detection in the covariance structure of multivariate time series models. Ann Stat 37(6B):4046–4087. http://arxiv.org/pdf/0911.3796.pdf. Accessed 6 July 2015

Bach S, Maloof M (2010) A Bayesian approach to concept drift. In: Advances in neural information processing systems, pp 127–135. http://papers.nips.cc/paper/4129-a-bayesian-approach-to-concept-drift. Accessed 5 Nov 2015

Barry D, Hartigan JA (1993) A Bayesian analysis for change point problems. J Am Stat Assoc 88(421):309–319. http://www.jstor.org/stable/2290726?seq=1#page_scan_tab_contents. Accessed 7 Aug 2015

10.

Basseville M, Nikiforov IV (1993) Detection of abrupt changes—theory and application. Prentice Hall, Englewood Cliffs. http://people.irisa.fr/Michele.Basseville/kniga/. Accessed 6 July 2015

11.

Boettcher M (2011) Contrast and change mining. Wiley Interdiscip Rev Data Min Knowl Discov 1(3):215–230. doi:10.1002/widm.27. Accessed 7 June 2016

12.

Bosc M et al (2003) Automatic change detection in multimodal serial MRI: application to multiple sclerosis lesion evolution. NeuroImage 20(2):643–656. http://www.sciencedirect.com/science/article/pii/S1053811903004063. Accessed 23 Aug 2015

13.

Brahim-Belhouari S, Bermak A (2004) Gaussian process for nonstationary time series prediction. Comput Stat Data Anal 47(4):705–712. http://www.sciencedirect.com/science/article/pii/S0167947304000301. Accessed 14 Aug 2015

14.

Chandola V, Vatsavai R (2010) Scalable time series change detection for biomass monitoring using gaussian process. In: Conference on intelligent data understanding 2010—CIDU. http://www.researchgate.net/profile/Ranga_Vatsavai/publication/221601357_Scalable_Time_Series_Change_Detection_for_Biomass_Monitoring_Using_Gaussian_Process/links/0912f50a51e4e084ca000000.pdf. Accessed 14 Aug 2015

15.

Chandola V, Vatsavai RR (2011) A Gaussian process based online change detection algorithm for monitoring periodic time series | Varun Mithal - Academia.edu. In: SIAM international conference on data mining, pp 95–106. http://www.academia.edu/2691671/A_gaussian_process_based_online_change_detection_algorithm_for_monitoring_periodic_time_series. Accessed 6 Sept 2015

16.

Chen H, Zhang N (2014) Graph-based change-point detection. Ann Stat 43(1):139–176. arXiv:1209.1625. Accessed 29 July 2015

17.

Chib S (1998) Estimation and comparison of multiple change point models. J Econ 86(2):221–241. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.322.213&rep=rep1&type=pdf. Accessed 7 Aug 2015

18.

Cho H, Fryzlewicz P (2015) Multiple-change-point detection for high dimensional time series via sparsified binary segmentation. J R Stat Soc Ser B (Stat Methodol) 77(2):475–507. doi:10.1111/rssb.12079. Accessed 6 July 2015

19.

Chowdhury MFR, Selouani S-A, O’Shaughnessy D (2011) Bayesian on-line spectral change point detection: a soft computing approach for on-line ASR. Int J Speech Technol 15(1):5–23. doi:10.1007/s10772-011-9116-2. Accessed 9 Sept 2015

20.

Cleland I et al (2014) Evaluation of prompted annotation of activity data recorded from a smart phone. Sensors (Basel, Switz) 14(9):15861–15879. http://www.mdpi.com/1424-8220/14/9/15861/htm. Accessed 27 Aug 2015

21.

Cook DJ, Krishnan NC (2015) Activity learning: discovering, recognizing, and predicting human behavior from sensor data. Wiley. https://books.google.com/books?id=YPOSBgAAQBAJ&pgis=1. Accessed 27 Aug 2015

22.

Desobry F, Davy M, Doncarli C (2005) An online kernel change detection algorithm. IEEE Trans Signal Process 53(8):2961–2974. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=1468491. Accessed 27 Aug 2015

23.

Downey AB (2008) A novel changepoint detection algorithm. arXiv:0812.1237. Accessed 8 Sept 2015

24.

Ducre-Robitaille J-F, Vincent LA, Boulet G (2003) Comparison of techniques for detection of discontinuities in temperature series. Int J Climatol 23(9):1087–1101. doi:10.1002/joc.924. Accessed 9 Sept 2015

25.

Feuz KD et al (2014) Automated detection of activity transitions for prompting. IEEE Trans Hum Mach Syst 45(5):1–11. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6949090. Accessed 8 May 2015

26.

Friedman JH, Rafsky LC (1979) Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests. Ann Stat 7(4):697–717. http://projecteuclid.org/euclid.aos/1176344722. Accessed 5 Aug 2015

27.

Han M et al (2012) Comprehensive context recognizer based on multimodal sensors in a smartphone. Sensors 12(12):12588–12605. http://www.mdpi.com/1424-8220/12/9/12588/htm. Accessed 27 Aug 2015

28.

Harchaoui Z et al (2009) A regularized kernel-based approach to unsupervised audio segmentation. In: IEEE international conference on acoustics, speech and signal processing. IEEE, pp 1665–1668. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=4959921. Accessed 25 Aug 2015

29.

Harchaoui Z, Moulines E, Bach FR (2009) Kernel change-point analysis. In: Advances in neural information processing systems, pp 609–616. http://papers.nips.cc/paper/3556-kernel-change-point-analysis. Accessed 25 Aug 2015

30.

Harel M et al (2014) Concept drift detection through resampling. In: Proceedings of the 31st international conference on machine learning—ICML-14, pp 1009–1017. http://machinelearning.wustl.edu/mlpapers/papers/icml2014c2_harel14. Accessed 5 Nov 2015

31.

Hido S et al (2008) Unsupervised change analysis using supervised learning. In: Washio T et al (eds) Advances in knowledge discovery and data mining, vol 5012, pp 148–159. doi:10.1007/978-3-540-68125-0. Accessed 25 Feb 2016

32.

Itoh N, Kurths J (2010) Change-point detection of climate time series by nonparametric method. In: World Congress on Engineering and Computer Science 2010, vol I. http://www.iaeng.org/publication/WCECS2010/WCECS2010_pp445-448.pdf. Accessed 14 July 2015

33.

Jeske DR et al (2009) Cusum techniques for timeslot sequences with applications to network surveillance. Comput Stat Data Anal 53(12):4332–4344. http://www.sciencedirect.com/science/article/pii/S016794730900228X. Accessed 8 July 2015

34.

Kawahara Y, Sugiyama M (2009) Sequential change-point detection based on direct density-ratio estimation. In: SIAM international conference on data mining, pp 389–400

35.

Kawahara Y, Yairi T, Machida K (2007) Change-point detection in time-series data based on subspace identification. In: 7th IEEE international conference on data mining (ICDM 2007). IEEE, pp 559–564. http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4470290. Accessed 14 July 2015

36.

Keogh E et al (2001) An online algorithm for segmenting time series. In: IEEE international conference on data mining. IEEE Comput Soc pp 289–296. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=989531. Accessed 26 Aug 2015

37.

Keogh E Lin J (2004) Clustering of time-series subsequences is meaningless: implications for previous and future research. Knowl Inf Syst 8(2):154–177. doi:10.1007/s10115-004-0172-7. Accessed 9 July 2015

38.

Kuncheva LI (2013) Change detection in streaming multivariate data using likelihood detectors. IEEE Trans Knowl Data Eng 25(5):1175–1180. http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6060824. Accessed 13 July 2015

39.

Kuncheva LI, Faithfull WJ (2014) PCA feature extraction for change detection in multidimensional unlabeled data. IEEE Trans Neural Netw Learn Syst 25(1):69–80. http://www.ncbi.nlm.nih.gov/pubmed/24806645. Accessed 13 July 2015

40.

Lacasa L et al (2008) From time series to complex networks: the visibility graph. Proc Natl Acad Sci USA 105(13):4972–4975. http://www.pnas.org/content/105/13/4972. Accessed 15 June 2015

41.

Lau HF, Yamamoto S (2010) Bayesian online changepoint detection to improve transparency in human-machine interaction systems. In: 49th IEEE conference on decision and control (CDC). IEEE, pp 3572–3577. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=5717959. Accessed 7 Aug 2015

42.

Liu S et al (2013) Change-point detection in time-series data by relative density-ratio estimation. Neural Netw 43:72–83. arXiv:1203.0453. Accessed 7 July 2015

43.

Malladi R, Kalamangalam GP, Aazhang B (2013) Online Bayesian change point detection algorithms for segmentation of epileptic activity. In: Asilomar conference on signals, systems and computers. IEEE, pp 1833–1837. http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6810619. Accessed 7 Aug 2015

44.

Montanez GD, Amizadeh S, Laptev N (2015) Inertial hidden Markov models: modeling change in multivariate time series. In: AAAI conference on artificial intelligence. pp 1819–1825

45.

Moskvina V, Zhigljavsky A (2003) An algorithm based on singular spectrum analysis for change-point detection. Commun Stat Simul Comput 32(2):319–352. doi:10.1081/SAC-120017494. Accessed 20 Oct 2015

46.

Nordli Ø et al (2014) Long-term temperature trends and variability on Spitsbergen: the extended Svalbard Airport temperature series, 1898–2012. Polar Res 33. http://www.polarresearch.net/index.php/polar/article/view/21349/xml. Accessed 15 Sept 2015

47.

Radke RJ et al (2005) Image change detection algorithms: a systematic survey. IEEE Trans Image Process 14(3):294–307. http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1395984. Accessed 3 Aug 2015

48.

Rakthanmanon T et al (2011) Time series epenthesis: clustering time series streams requires ignoring some data. In: IEEE 11th international conference on data mining. IEEE, pp 547–556. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6137259. Accessed 9 July 2015

49.

Raykar VC (2007) Scalable machine learning for massive datasets: fast summation algorithms. University of Maryland, College Park

50.

Reddy S et al (2010) Using mobile phones to determine transportation modes. ACM Trans Sens Netw 6(2):1–27. http://dl.acm.org/citation.cfm?id=1689239.1689243. Accessed 14 Sept 2015

51.

Reeves J et al (2007) A review and comparison of changepoint detection techniques for climate data. J Appl Meteorol Climatol 46(6):900–915. doi:10.1175/JAM2493.1. Accessed 9 Sept 2015

52.

Rosenbaum PR (2005) An exact distribution-free test comparing two multivariate distributions based on adjacency. J R Stat Soc 67:515–530. http://www-stat.wharton.upenn.edu/~rosenbap/crossmatch.pdf. Accessed 5 Aug 2015

53.

Rybach D et al (2009) Audio segmentation for speech recognition using segment features. In: IEEE international conference on acoustics, speech and signal processing. IEEE, pp 4197–4200. http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4960554. Accessed 9 Sept 2015

54.

Saatçi Y, Turner RD, Rasmussen CE (2010) Gaussian process change point models. In: International conference on machine learning. pp 927–934. http://mlg.eng.cam.ac.uk/pub/pdf/SaaTurRas10.pdf. Accessed 17 Sept 2015

55.

Scholz M, Klinkenberg R (2007) Boosting classifiers for drifting concepts. Intell Data Anal 11(1):3–28

56.

Shieh J, Keogh E (2010) Polishing the right apple: anytime classification also benefits data streams with constant arrival times. In: IEEE international conference on data mining. IEEE, pp 461–470. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=5694000. Accessed 27 Oct 2015

57.

Shumway RH, Stoffer DS (2011) Time series analysis and its applications. Springer, New York. doi:10.1007/978-1-4419-7865-3. Accessed 31 July 2015

58.

Staudacher M et al (2005) A new method for change-point detection developed for on-line analysis of the heart beat variability during sleep. Phys A Stat Mech Appl 349(3–4):582–596. http://www.sciencedirect.com/science/article/pii/S0378437104013640. Accessed 9 Sept 2015

59.

Tan BA et al (2015) Change-point detection for recursive Bayesian geoacoustic inversions. J Acoust Soc Am 137(4):1962–1970. http://scitation.aip.org/content/asa/journal/jasa/137/4/10.1121/1.4916887. Accessed 26 Feb 2016

60.

Tran D-H (2013) Automated change detection and reactive clustering in multivariate streaming data. arXiv:1311.0505. Accessed 27 Aug 2015

61.

Wei L, Keogh E (2006) Semi-supervised time series classification. In: 12th ACM SIGKDD international conference on Knowledge discovery and data mining—KDD ’06. ACM Press, New York, p 748. http://dl.acm.org/citation.cfm?id=1150402.1150498. Accessed 7 July 2015

62.

Yamada M et al (2013) Change-point detection with feature selection in high-dimensional time-series data. In: International joint conference on artificial intelligence. AAAI Press. http://dl.acm.org/citation.cfm?id=2540128.2540390. Accessed 13 July 2015

63.

Yamanishi K, Takeuchi J (2002) A unifying framework for detecting outliers and change points from non-stationary time series data. In: 8th ACM SIGKDD international conference on Knowledge discovery and data mining—KDD ’02. ACM Press, New York, p 676. http://dl.acm.org/citation.cfm?id=775047.775148. Accessed 7 July 2015

64.

Yang P, Dumont G, Ansermino JM (2006) Adaptive change detection in heart rate trend monitoring in anesthetized children. IEEE Trans Biomed Eng 53(11):2211–2219. http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=1710162. Accessed 9 Sept 2015

65.

Zakaria J, Mueen A, Keogh E (2012) Clustering time series using unsupervised-shapelets. In: IEEE 12th international conference on data mining. IEEE, pp 785–794. http://dl.acm.org/citation.cfm?id=2471881.2472632. Accessed 27 Aug 2015

66.

Zhang J, Small M (2006) Complex network from pseudoperiodic time series: topology versus dynamics. Phys Rev Lett 96(23):238701. doi:10.1103/PhysRevLett.96.238701. Accessed 31 July 2015

67.

Zheng Y, Liu L et al (2008) Learning transportation mode from raw gps data for geographic applications on the web. In: 17th international conference on World Wide Web—WWW ’08. ACM Press, New York, p 247. http://dl.acm.org/citation.cfm?id=1367497.1367532. Accessed 28 May 2015

68.

Zheng Y, Li Q et al (2008) Understanding mobility based on GPS data. In: 10th international conference on Ubiquitous computing—UbiComp ’08. ACM Press, New York, p 312. http://dl.acm.org/citation.cfm?id=1409635.1409677. Accessed 28 May 2015

69.

Zheng Y et al (2010) Understanding transportation modes based on GPS data for Web applications—Microsoft research. ACM Trans Web 4(1). http://research.microsoft.com/apps/pubs/default.aspx?id=102101. Accessed 21 Oct 2015

70.

Zilberstein S, Russell S (1996) Optimal composition of real-time systems. Artif Intell 82(1):181–213. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.89. Accessed 8 Sept 2015

Titel: A survey of methods for time series change point detection
verfasst von: Samaneh Aminikhanghahi
Diane J. Cook
Publikationsdatum: 08.09.2016
Verlag: Springer London
Erschienen in: Knowledge and Information Systems / Ausgabe 2/2017
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI: https://doi.org/10.1007/s10115-016-0987-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2017

Measuring similarity of users with qualitative preferences for service selection

Weighted-object ensemble clustering: methods and analysis

EFIM: a fast and memory efficient algorithm for high-utility itemset mining

Constrained recommendations for query visualizations

Decision-making and opinion formation in simple networks

Indexed list-based high utility pattern mining with utility upper-bound reduction and pattern combination techniques