article

Performing event detection in time series with SwiftEvent: an algorithm with supervised learning of detection criteria

Authors:

André Gensler,

Bernhard SickAuthors Info & Claims

Pattern Analysis & Applications, Volume 21, Issue 2

Pages 543 - 562

https://doi.org/10.1007/s10044-017-0657-0

Published: 01 May 2018 Publication History

Abstract

The automated detection of points in a time series with a special meaning to a user, commonly referred to as the detection of events, is an important aspect of temporal data mining. These events often are points in a time series that can be peaks, level changes, sudden changes of spectral characteristics, etc. Fast algorithms are needed for event detection for online applications or applications with huge time series data sets. In this article, we present a very fast algorithm for event detection that learns detection criteria from labeled sample time series (i.e., time series where events are marked). This algorithm is based on fast transformations of time series into low-dimensional feature spaces and probabilistic modeling techniques to identify criteria in a supervised manner. Events are then found in one, single fast pass over the signal (therefore, the algorithm is called SwiftEvent) by evaluating learned thresholds on Mahalanobis distances in the feature space. We analyze the run-time complexity of SwiftEvent and demonstrate its application in some use cases with artificial and real-world data sets in comparison with other state-of-the-art techniques.

References

[1]

Abonyi J, Feil B, Nemeth S, Arva P (2005) Modified Gath---Geva clustering for fuzzy segmentation of multivariate time-series. Fuzzy Sets Syst 149(1):39---56

Digital Library

[2]

Al-Shoshan AI (2006) Handwritten signature verification using image invariants and dynamic features. In: Proceedings of the 3rd international conference on computer graphics, imaging and visualisation (CGIV06), Sydney, Australia, pp 173---176

Digital Library

[3]

Amft O, Junker H, Tröster G (2005) Detection of eating and drinking arm gestures using inertial body-worn sensors. In: Proceedings of the 9th IEEE international symposium on wearable computers (ISWC05), Osaka, Japan, pp 160---163

Digital Library

[4]

Bishop CM (2006) Pattern recognition and machine learning, vol 4. Springer, New York

Digital Library

[5]

Blondell D, Hoang P, Powell J, Shi J (2002) Detection of financial time series turning points: a new CUSUM approach applied to IPO cycles. Rev Quant Finance Account 18(3):293---315

[6]

Brault J, Plamondon R (1993) Segmenting handwritten signatures at their perceptually important points. IEEE Trans Pattern Anal Mach Intell 15(9):953---957

Digital Library

[7]

Chen C, Tiao GC (1990) Random level-shift time series models, ARIMA approximations, and level-shift detection. J Bus Econ Stat 8(1):83---97

[8]

Chiu B, Keogh E, Lonardi S (2003) Probabilistic discovery of time series motifs. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining (KDD03), Washington, USA, pp 493---498

Digital Library

[9]

Chu CSJ (1995) Time series segmentation: a sliding window approach. Inf Sci 85(1):147---173

Digital Library

[10]

Chung FL, Fu TC, Luk R, Ng V (2001) Flexible time series pattern matching based on perceptually important points. In: International joint conference on artificial intelligence workshop on learning from temporal and spatial data, pp 1---7

[11]

Chung FL, Fu TC, Ng V, Luk RWP (2004) An evolutionary approach to pattern-based time series segmentation. IEEE Trans Evol Comput 8(5):471---489

Digital Library

[12]

Costa BSJ, Angelov PP, Guedes LA (2015) Fully unsupervised fault detection and identification based on recursive density estimation and self-evolving cloud-based classifier. Neurocomputing 150(Part A):289---303

Digital Library

[13]

Dobos L, Abonyi J (2012) On-line detection of homogeneous operation ranges by dynamic principal component analysis based time-series segmentation. Chem Eng Sci 75:96---105

[14]

Esling P, Agon C (2012) Time-series data mining. ACM Comput Surv (CSUR) 45(1):12---48

Digital Library

[15]

Feng L, Ju K, Chon KH (2005) A method for segmentation of switching dynamic modes in time series. IEEE Trans Syst Man Cybern Part B Cybern 35(5):1058---1064

Digital Library

[16]

Fu T (2011) A review on time series data mining. Eng Appl Artif Intell 24(1):164---181

Digital Library

[17]

Fu TC, Chung Fl, Ng V, Luk R (2001) Pattern discovery from stock time series using self-organizing maps. In: Workshop notes of KDD2001 workshop on temporal data mining. Citeseer, pp 26---29

[18]

Fu TC, Chung FL, Tang PY, Luk R, Ng CM (2005) Incremental stock time series data delivery and visualization. In: Proceedings of the 14th ACM international conference on information and knowledge management. ACM, pp 279---280

Digital Library

[19]

Fuchs E (1999) On discrete polynomial least-squares approximation in moving time windows. In: Gautschi W, Golub GH, Opfer G (eds) Applications and computation of orthogonal polynomials, international series of numerical mathematics. Birkhäuser, Basel, pp 93---107

[20]

Fuchs E (1999) Schnelle Quadratmittelapproximation in gleitenden Zeitfenstern mit diskreten orthogonalen Polynomen. Ph.D. thesis, University of Passau

[21]

Fuchs E, Gruber T, Nitschke J, Sick B (2009) On-line motif detection in time series with SwiftMotif. Pattern Recognit 42(11):3015---3031

Digital Library

[22]

Fuchs E, Gruber T, Nitschke J, Sick B (2010) Online segmentation of time series based on polynomial least-squares approximations. IEEE Trans Pattern Anal Mach Intell 32(12):2232---2245

Digital Library

[23]

Fuchs E, Gruber T, Pree H, Sick B (2010) Temporal data mining using shape space representations of time series. Neurocomputing 74(1):379---393

Digital Library

[24]

Fuchs E, Hanning T, Schwarz O (2004) An update algorithm for Fourier coefficients. In: Proceedings of the 12th European signal processing conference, pp 1509---1512 (2004)

[25]

Fuchs E, Hanning T, Schwarz O (2004) An update algorithm for Fourier coefficients. In: Proceedings of the 12th European signal processing conference. Vienna, Austria, pp 1509---1512

[26]

Gensler A Waveform data set. http://ies-research.de/Software

[27]

Gensler A, Gruber T, Sick B Fast approximation library. http://ies-research.de/Software

[28]

Gensler A, Gruber T, Sick B (2013) Blazing fast time series segmentation based on update techniques for polynomial approximations. In: Proceedings of the IEEE 13th international conference on data mining workshops (ICDMW13), Dallas, USA, pp 1002---1011

Digital Library

[29]

Gensler A, Gruber T, Sick B (2015) Fast feature extraction for time series analysis using least-squares approximations with orthogonal basis functions. In: Proceedings of the international workshop on temporal representation and reasoning (TIME15), Kassel, Germany, pp 29---37

Digital Library

[30]

Gensler A, Sick B (2014) Novel criteria to measure performance of time series segmentation techniques. Proceedings of LWA/KDML: workshop on knowledge discovery, data mining and machine learning, Aachen, Germany, vol 2, pp 29---37

[31]

Gensler A, Sick B, Willkomm J (2014) Temporal data analytics based on eigenmotif and shape space representations of time series. In: Proceedings of the 2nd IEEE China Summit & international conference on signal and information processing (ChinaSIP14), pp 753---757

[32]

Goldberger AL, Amaral LAN, Glass L, Hausdorff JM, Ivanov PC, Mark RG, Mietus JE, Moody GB, Peng CK, Stanley HE (2000) PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals. Circulation 101(23):e215---e220

[33]

Guralnik V, Srivastava J (1999) Event detection from time series data. In: Proceedings of the 5th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, San Diego, USA, pp 33---42

Digital Library

[34]

Haber D, Thomik AAC, Faisal AA (2014) Unsupervised time series segmentation for high-dimensional body sensor network data streams. In: Proceedings of the 11th IEEE international conference on wearable and implantable body sensor networks (BSN14), Zurich, Switzerland, pp 121---126

Digital Library

[35]

Huang X, Matijas M, Suykens JAK (2013) Hinging hyperplanes for time-series segmentation. IEEE Trans Neural Netw Learn Syst 24(8):1279---1291

[36]

Hunter J, McIntosh N (1999) Knowledge-based event detection in complex time series data. In: Proceedings of the joint European conference on artificial intelligence in medicine and medical decision making (AIMDM99), Aalborg, Denmark, pp 271---280

Digital Library

[37]

Ihler A, Hutchins J, Smyth P (2006) Adaptive event detection with time-varying Poisson processes. In: Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining (KDD06), Philadelphia, USA, pp 207---216

Digital Library

[38]

Jacobsen E, Lyons R (2003) The sliding DFT. IEEE Signal Process Mag 20(2):74---80

[39]

Kattan A, Fatima S, Arif M (2015) Time-series event-based prediction: an unsupervised learning framework based on genetic programming. Inf Sci 301:99---123

Digital Library

[40]

Kawahara Y, Sugiyama M (2009) Change-point detection in time-series data by direct density-ratio estimation. In: Proceedings of the SIAM international conference on data mining (SDM09), Sparks, Nevada, vol 9, pp 389---400

Digital Library

[41]

Keogh E, Chakrabarti K, Pazzani M, Mehrotra S (2001) Dimensionality reduction for fast similarity search in large time series databases. Knowl Inf Syst 3(3):263---286

[42]

Keogh E, Chu S, Hart D, Pazzani M (2004) Segmenting time series: a survey and novel approach. Data Min Time Ser Databases 57:1---22

[43]

Keogh E, Kasetty S (2003) On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Min Knowl Discov 7(4):349---371

Digital Library

[44]

Keogh E, Lin J (2005) Clustering of time-series subsequences is meaningless: implications for previous and future research. Knowl Inf Syst 8(2):154---177

Digital Library

[45]

Kumar K, Wu B (2001) Detection of change points in time series analysis with fuzzy statistics. Int J Syst Sci 32(9):1185---1192

[46]

Laguna P, Mark RG, Goldberg A, Moody GB (1997) A database for evaluation of algorithms for measurement of QT and other waveform intervals in the ECG. Comput Cardiol 24:673---676

[47]

Lemos A, Caminhas W, Gomide F (2013) Adaptive fault detection and diagnosis using an evolving fuzzy classifier. Inf Sci 220:64---85

Digital Library

[48]

Lin J, Keogh E, Lonardi S, Patel P (2002) Finding motifs in time series. In: Proceedings of the 2nd workshop on temporal data mining (KDD02), Edmonton, Canada, pp 53---68

[49]

Liu H, Motoda H (1998) Feature extraction, construction, and selection: a data mining perspective. Kluwer Academic Publishers, Boston

Digital Library

[50]

Ma J, Perkins S (2003) Online novelty detection on temporal sequences. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining (KDD03), New York, USA, pp 613---618

Digital Library

[51]

Miao S, Vespier U, Cachucho R, Meeng M, Knobbe A (2016) Predefined pattern detection in large time series. Inf Sci 329:950---964

Digital Library

[52]

Mueen A, Keogh E (2010) Online discovery and maintenance of time series motifs. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining (KDD10), Washington, USA, pp 1089---1098

Digital Library

[53]

Nikiforov AF, Uvarov VB, Suslov SK (1991) Classical orthogonal polynomials of a discrete variable. Springer, Berlin, pp 18---54

[54]

Oliver JJ, Forbes CS (1997) Bayesian approaches to segmenting a simple time series, Technical Report 14/97, Monash University, Melbourne, Australia

[55]

Perng CS, Wang H, Zhang SR, Parker DS (2000) Landmarks: a new model for similarity-based pattern querying in time series databases. In: Proceedings of the 16th international conference on data engineering, San Diego, USA, pp 33---42

Digital Library

[56]

Povinelli RJ, Feng X (2003) A new temporal pattern identification method for characterization and prediction of complex time series events. IEEE Trans Knowl Data Eng (TKDE) 15(2):339---352

Digital Library

[57]

Prechelt L (1994) PROBEN1--a set of benchmarks and benchmarking rules for neural network training algorithms. Technical Report 21/94, Fakultät für Informatik, Universität Karlsruhe, Karlsruhe, Germany

[58]

Pree H, Herwig B, Gruber T, Sick B, David K, Lukowicz P (2014) On general purpose time series similarity measures and their use as kernel functions in support vector machines. Inf Sci 281:478---495

Digital Library

[59]

Preston D, Protopapas P, Brodley C (2009) Event discovery in time series. In: Proceedings of the SIAM international conference on data mining (SDM09), Sparks, Nevada, pp 1---12

[60]

Sadler BM, Pham T, Sadler LC (1998) Optimal and wavelet-based shock wave detection and estimation. J Acoust Soc Am 104(2):955---963

[61]

Same A, Govaert G (2012) Online time series segmentation using temporal mixture models and Bayesian model selection. In: Proceeding of the 11th international conference on machine learning and applications (ICMLA11), vol 1, pp 602---605

Digital Library

[62]

Serdio F, Lughofer E, Pichler K, Buchegger T, Pichler M, Efendic H (2014) Fault detection in multi-sensor networks based on multivariate time-series models and orthogonal transformations. Inf Fusion 20(1):272---291

[63]

Serdio F, Lughofer E, Zavoianu AC, Pichler K, Pichler M, Buchegger T, Efendic H (2017) Improved fault detection employing hybrid memetic fuzzy modeling and adaptive filters. Appl Soft Comput J 51:60---82

Digital Library

[64]

Shahabi C, Yan D (2003) Real-time pattern isolation and recognition over immersive sensor data streams. In: Proceedings of the 9th international conference on multi-media modeling, pp 93---113

[65]

Tanaka Y, Iwamoto K, Uehara K (2005) Discovery of time-series motif from multi-dimensional data based on MDL principle. Mach Learn 58(2---3):269---300

Digital Library

[66]

Van Laerhoven K, Berlin E, Schiele B (2009) Enabling efficient time series analysis for wearable activity data. In: Proceedings of the 15th IEEE international conference on machine learning and applications (ICMLA09), Miami, USA, pp 392---397

Digital Library

[67]

Wang ZJ, Willett P (2004) Joint segmentation and classification of time series using class-specific features. IEEE Trans Syst Man Cybern Part B Cybern 34(2):1056---1067

Digital Library

[68]

Wecker WE (1979) Predicting the turning points of a time series. J Bus 52(1):35---50

[69]

Weiss GM, Hirsh H (1998) Learning to predict rare events in event sequences. In: Proceedings of the 4th international conference on knowledge discovery and data mining, pp 359---363

Digital Library

[70]

Xie F, Song A, Ciesielski V (2012) Event detection in time series by genetic programming. In: Proceedings of the IEEE congress on evolutionary computation (CEC12), Brisbane, Australia, pp 2507---2514

Cited By

Li HYu Y(2021)Detecting a multigranularity event in an unequal interval time series based on self-adaptive segmentingIntelligent Data Analysis10.3233/IDA-20548025:6(1407-1429)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/IDA-205480
Ivanova IAndrić MMoaveninejad SJanes ARicci FLienhart RMoeslund TSaito H(2020)Video and Sensor-Based Rope Pulling Detection in Sport ClimbingProceedings of the 3rd International Workshop on Multimedia Content Analysis in Sports10.1145/3422844.3423058(53-60)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3422844.3423058
Hamidzadeh JMoradi M(2020)Incremental one-class classifier based on convex–concave hullPattern Analysis & Applications10.1007/s10044-020-00876-723:4(1523-1549)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1007/s10044-020-00876-7

Index Terms

Performing event detection in time series with SwiftEvent: an algorithm with supervised learning of detection criteria
1. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms

Index terms have been assigned to the content through auto-classification.

Recommendations

A generic framework for event detection in various video domains
MM '10: Proceedings of the 18th ACM international conference on Multimedia

Event detection is essential for the extensively studied video analysis and understanding area. Although various approaches have been proposed for event detection, there is a lack of a generic event detection framework that can be applied to various ...
Few-shot Incremental Event Detection
Event detection tasks can enable the quick detection of events from texts and provide powerful support for downstream natural language processing tasks. Most such methods can only detect a fixed set of predefined event classes. To extend them to detect a ...
Multimedia Event Detection Using Event-Driven Multiple Instance Learning
MM '15: Proceedings of the 23rd ACM international conference on Multimedia

A complex event can be recognized by observing necessary evidences. In the real world scenarios, this is a difficult task because the evidences can happen anywhere in a video. A straightforward solution is to decompose the video into several segments ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Pattern Analysis & Applications

Pattern Analysis & Applications Volume 21, Issue 2

May 2018

313 pages

ISSN:1433-7541

EISSN:1433-755X

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer-Verlag London Ltd., part of Springer Nature.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 May 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li HYu Y(2021)Detecting a multigranularity event in an unequal interval time series based on self-adaptive segmentingIntelligent Data Analysis10.3233/IDA-20548025:6(1407-1429)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/IDA-205480
Ivanova IAndrić MMoaveninejad SJanes ARicci FLienhart RMoeslund TSaito H(2020)Video and Sensor-Based Rope Pulling Detection in Sport ClimbingProceedings of the 3rd International Workshop on Multimedia Content Analysis in Sports10.1145/3422844.3423058(53-60)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3422844.3423058
Hamidzadeh JMoradi M(2020)Incremental one-class classifier based on convex–concave hullPattern Analysis & Applications10.1007/s10044-020-00876-723:4(1523-1549)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1007/s10044-020-00876-7

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents