A Sliding Window Filter for Time Series Streams

Abstract

The ever increasing number of sensor-equipped devices comes along with a growing need for data analysis techniques that are able to process time series streams in an online fashion. Although many sensorequipped devices produce never-ending data streams, most real-world applications merely require high-level information about the presence or absence of certain events that correspond to temporal patterns. Since online event detection is usually computational demanding, we propose a sliding window lter that decreases the time/space complexity and, therefore, allows edge computing on devices with only few resources. Our evaluation for online gesture recognition shows that the developed ltering approach does not only reduce the number of expensive dissimilarity comparison, but also maintains high precision.

Keywords

• Internet of Things
• Time Series Streams
• Sliding Window Technique
• Online Event Detection
• Computational Complexity

-

As time goes by things change, and those who understand change can adapt accordingly. This basic principle is also re ected in today's digital society, where sensor-equipped devices measure our environment and online algorithms process the generated data streams in quasi real-time to inform humans or cognitive systems about relevant trends and events that impact decision making.

Depending on the domain researchers either speak about events, patterns, or scenes that they aim to detect or recognize in time series, sensor, or data streams. Applications range from event detection for smart home control [ 17 ] over frequent pattern mining for engine optimization [ 16 ] to scene detection for video content [ 1 ] and gesture recognition for human-computer interaction [ 11 ].

Commonly online algorithms for data streams employ the popular sliding window technique [ 8 ], which observes the most recent sensor measurements and moves along the time axis as new measurements arrive. Usually each window is examined for a set of prede ned events, which requires the comparison of the current time series segment and all preliminary learned instances of the relevant temporal patterns. In general, the pairwise dissimilarity comparisons of temporal patterns are performed by time series distance measures [ 18 ].

The time and space complexity of the sliding window technique increases with decreasing step size as well as growing window size, measurement frequency, and number of preliminary learned instances. High computational demand and memory usage is especially problematic for embedded systems with only few resources [ 9,19 ], which applies to the greatest part of sensor-equipped devices within the typical Internet of Things (IoT) scenario.

Our aim is to reduce the number of computational expensive dissimilarity comparisons that are required by the sliding window technique. To this end we propose a sliding window lter [ 10 ], which is able to decide whether the current window should be passed to a time series classi er or not. Although the lter could be considered as a binary classi er itself, it merely employs statistical measures with linear complexity and, thereby, avoids using computationally more expensive dissimilarity comparisons in many cases. Our approach to mitigate the computational complexity of event detection in data streams is di erent from other techniques in that we refrain from accelerating time series distance measures [ 13,15 ] or reducing dataset numerosity [ 20 ].

We demonstrate the practical use of our proposed sliding window lter for gesture recognition in continuous streams of accelleration data [ 10,11 ], where a great amount of the necessary but expensive Dynamic Time Warping (DTW) distance calculations [ 7 ] is replaced by less demanding statistical measures, such as the complexity estimate [ 2 ] or sample variance [ 3 ]. Our experimental results show that the number of DTW distance calculations can be cut in half, while still maintaining the same high gesture recognition performance.

The rest of the paper is structured as follows. Chapter 2 introduces background and notation. Chapter 3 and 4 introduce and evaluate our proposed sliding window lter. We conclude with future work in Chapter 5. 2

Background and Notation

This section gives more background on the sliding window technique [ 8 ], DTW distance measure [ 7 ], and time series normalization [ 4 ], which are fundamental building blocks of our conducted online gesture recognition study [ 10 ]. Table 1 introduces the notation that we use for formal problem description. Symbol Description

Q a time series of size n with Q = (q1; q2; : : : ; qi; : : : ; qn) Q[i; j] a subsequence time series of Q with Q[i; j] = (qi; qi+1; : : : ; qj) t the current time the mean of a time series Q the standard deviation of a time series Q , z two di erent time series normalizations Given a continuous time series stream Q, the sliding window technique examines the w most recent data points and moves s steps along the time axis as new measurements arrive, where w and s are referred to as window and step size. This technique has the advantage that it does not need to store the never-ending stream of data, but it also implies that measurements can only be considered for further data analysis as long as they are located within the current window.

In most applications, each window is passed to a data processing unit, which performs some kind of time series classi cation, clustering, or anomaly detection. For example in online gesture recognition [ 10 ], one can employ a nearest neighbor classi er, which compares each window to a training set of preliminary learned time series instances. In case that the current window Q[t w; t] is similar to one of the known gestures, where similar means that the time series distance falls below a certain threshold, a corresponding action can be triggered. A popular distance measure for gestures [ 11 ] and other warped time series is described in the following subsection. 2.2

Dynamic Time Warping

Dynamic Time Warping (DTW) is a widely used and robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis [ 7 ]. Traditionally DTW computes a full distance matrix to nd an optimal warping path, where possible nonlinear alignments between a pair of time series include matches of early time points of the rst sequence with late time points of the second sequence. To prevent pathological alignments, the size of the warping window can be constraint, for instance, by the Sakoe-Chiba band [ 12 ] or the Itakura parallelogram [ 6 ]. Figure 1 illustrates the DTW distance measure using a Sakoe-Chiba band of 10%, where the percentage of the warping window refers to the length of the compared time series.

20 n ito 40 a r lcee 60 c a 80 0 10 20 time 30 40

C Q 50 40 30 20 10 0 Fig. 1. Time series Q and C compared by DTW with a Sakoe-Chiba band of 10% time series length. The left plot illustrates the nonlinear alignment between the two sequences and the right plot shows the optimal warping path within the speci ed band. 2.3

Time Series Normalization

Literature on time series mining [ 5,18 ] suggests to normalize all (sub-)sequences before measuring their pair-wise dissimilarity by means of a distance measure. There are multiple ways to normalize time series, where two common techniques [ 4 ] are compared in this study.

Given is a time series Q = (q1; : : : ; qn) of length n, we can compute its mean and standard deviation as followed:

n = 1 X q n i=1 i

n = 1 X(qi n i=1 This section does not only explain the concept of our proposed ltering approach, but also describes how to integrate our lter into the well-known and widely-used sliding window technique, as shown in Figure 2.

In general, the sliding window lter considers the most recent measurements in a data stream. The considered measurements are usually passed to a classi er, which aims at categorizing the current time series subsequence. In case that the current subsequence was assigned to a known category or class, a corresponding action is triggered and the next non-overlapping window, w steps along the time axis, is examined. If the current subsequence just contains noise and no category was assigned, the next overlapping window, s steps along the arrow of time, is processed. The main limitation of this traditional sliding window technique is its computational complexity, which increases with growing window size, shrinking step size, higher sample rate, and larger training set.

For instance, given a data stream of length l=10090, a window size of w=100, and a step size of s=10, we need to classify (l (w s))=s = 1000 windows. Moreover, assuming 20 training time series, classifying 1000 windows by means of the nearest neighbor approach requires exactly 20 1000 = 20K dissimilarity comparisons. In case that we employ unconstrained DTW as time series distance measure, we need to compute 20K full warping matrices, each of them containing w w = 10K cells, resulting in a total amount of 200M distance operations. sensors or devices

Continuous time series stream Q

Extract last subsequence Q[t w; t] from Q of size w, Q[t w; t]

Time series lter

no Sleep for s time yes no

Time series classi cator Q[t w; t] classi able?

yes Trigger event that Q[t w; t] has been classi ed and sleep for w time

In order to reduce the large number of computational expensive dissimilarity comparisons, we propose to employ a sliding window lter, which is capable of separating signal from noise, only passing promising time series subsequences to the classi er. In that sense, the proposed lter can also be considered as a binary classi er, which prunes windows that are likely to be noise and forwards subsequences that exhibit similar features as the training time series. Extracting characteristic time series features that can be used as a lter criterion should ideally exhibit linear complexity, because we aim at replacing more expensive dissimilarity comparisons. Suitable lter candidates include statistical measures, such as the sample variance [ 3 ] and length normalized complexity estimate [ 2 ], explained in more detail below.

Given is a time series Q = (q1; : : : ; qn) with length n, we can de ne the sample variance (V AR) and length normalized complexity estimate (LN CE) as follows:

LN CE(Q) =

n V AR(Q) = 1 X(qi

n n 1 i=1 vun 1 u2X(qi 1 t i=1 )2 qi+1)2

Having de ned the above statistical measures, we are able to compute the V AR and LN CE for all training time series and, subsequently, use the resulting range of statistical values to learn an appropriate lter interval. During testing, each window that exhibits a measured value within the learned interval is passed to the classi er or pruned otherwise. In order to avoid excessive pruning of relevant windows, we further more introduce a multiplication factor, which allows us to expend the interval boundaries by a certain percentage.

In general, we aim at designing a lter with high precision and recall. In our case, precision is the ratio between the number of relevant windows that were passed to the classi er (true positives) and the number of all windows that were passed to the classi er (true positives and false positives). Consequently, recall is the ratio between the number of relevant windows that were passed to the classi er (true positives) and the number of all relevant windows (true positives and false negatives). An exhaustive evaluation of our proposed sliding window lter in dependence of all model parameters is presented in the next section. 4

Evaluation

This chapter describes the data aggregation in Section 4.1, data preparation in Section 4.2, experimental setup in Section Section 4.3, and used performance measures in Section 4.4, before presenting our results in Section 4.5. 4.1

Data Aggregation

We employed a Wii RemoteTM Plus controller to record di erent gestures for multiple users. Each user performed 8 gestures, rst in a controlled environment to record clean training samples and afterwards in noisy environment to record a test time series stream, which includes all predetermined gestures as well as acceleration data that corresponds to other physical activities. All records are available for download on our project website [ 10 ]. A sample record containing both training and test gestures is illustrated in Figure 3. All of our data records are resampled and quantized before further analysis. In general, dimensionality and cardinality reduction of time series is performed to ease and accelerate data processing by providing a more compact representation of equidistant measurements [ 11 ].

Resampling: The recorded acceleration data was resampled by means of the moving average technique, using a window size of 50 ms and step size of 30 ms. Quantization: The resampled records were then converted into time series with integer values between -16 and 16, such as suggested in related work [ 11 ] and summarized in table 2. The proposed sliding window lter has several model parameters that need to be carefully tuned in order to achieve optimal performance. Depending on the application domain we need to select an appropriate window and step size, time series normalization, dissimilarity threshold, and lter criterion. In the following we describe all parameter settings that were assessed in our empirical study: { The window size determines the number of most recent measurements contained in the examined time series subsequences. We tested four di erent sizes that were learned from the training gesture, including min, max, and avg length as well as the mid-point of the range. { The step size de nes the gap between consecutive time series windows. As default setting we use one tenth of the window size. { For online gesture recognition we employ the nearest neighbor classi er in combination with the DTW distance, where we evaluate 34 di erent SakoeChiba band sizes, ranging from 1 % to 100 %. Prior to pair-wise comparing sliding windows and training gestures, the corresponding time series should be normalized. We evaluate , z, and no normalization. { The dissimilarity threshold de nes the time series distance at which a sliding window and a training gesture are considered to belong to the same class. We determine the threshold for an individual class by measuring the distances between all samples of that particular class and all instances of other classes. In our empirical study we evaluate the threshold in uence for: (i) one half of the minimum distance - HMinD, (ii) one half of the average distance - HAvgD, and (iii) one half of the midpoint distance - HMidD. { The lter criterion is an essential part of our proposed approach. In our empirical study we evaluate the performance of the two lter criteria, namely the sample variance VAR and the length normalized complexity estimate LNCE of a time series. Both lters are tested with di erent factors that increase the size of the lter interval from 100 % to 300 %. Fig. 4. Visualized results of online gesture recognition for a sample time series stream. We highlight true positives in green, false positives in red, false negatives in blue, and true negatives in transparent. Although we see short false detection intervals before or after true positives, seven out of eight gestures were assigned to the correct class label. Since our proposed sliding window lter is tested on time series streams that contain various di erent gestures, we need to treat the described online gesture recognition challenge as multi-class problem. Common performance measures for multi-class problems are P recision , Recall and F score [ 14 ]: F score = ( 2 + 1)P recision Recall 2P recision + Recall where is usually set to one and l denotes the number of classes that require separate computation of true positives (tp), false positives (f p), and false negatives (f n). These multi-class performance measures allow us to compare and rank the results for di erent parameter settings. For our evaluation we employ the F1score , which weights P recision and Recall equally. 4.5

Results

In order to evaluate the in uence of all model parameters that were described in Section 4.3, we performed a total number of 28152 experiments. Figure 5(a) illustrates the P recision and Recall values for all test runs. A top performance of around 0.7384 F1score was achieved by parameter con gurations that used time series normalization, DTW with a Sakoe-Chiba band of about 18 % time series length, mid window size, and HAvgD for threshold determination.

Given the best parameter con guration, we investigated the in uence of the individual parameters by changing only one at a time and xing the others, see Figure 5(b,c,d). As shown in Figure 5(e), we also evaluated the performance with V AR, LN CE, and no lter. The best results for each individual gesture is shown in Figure Figure 5(f). Further tests on the applicability of the sliding window lter as well as our interpretation of the results are presented below.

Normalization: The in uence of the time series normalization is illustrated in Figure 5(b). We compare , z, and no normalization, with mid window size and HAvgD dissimilarity threshold. The best F1score was achieved by means of the normalization, which corresponds to the data points shown in the magnifying glass. The point cloud in the lower left corner of plot 5(b) are parameter settings with rather small warping band.

Warping Band: The in uence of the Sakoe-Chiba band in combination with the DTW distance is shown below in Figure 6. For this experiment we selected only the dominating parameter settings, with normalization, mid window size, and and HAvgD dissimilarity threshold. The best F1score was achieved with a band with of 18 % time series length.

Dissimilarity Threshold: We evaluate three di erent ways of determining a dissimilarity threshold, namely HMinD, HAvgD, and HMidD. For our comparison in Figure 5(c), we used normalization, mid window size, and a warping band of 18 % time series length. The best F1score was achieved by means of HAvgD, shortly followed by the HMidD approach. Comparatively high P recision values were given by HMinD threshold.

Window Size: The in uence of the window size determination approach is shown in Figure 5(d). We compare min, max, avg, and mid window size, with normalization, HAvgD dissimilarity threshold, and a warping and of 18 % time series length. The highest P recision , Recall and F1score was achieved by the mid window size, shortly followed by the avg window size. Figure 5(d) furthermore suggests to refrain from using max and min window size determination.

Filtering Approach: Given the optimal parameter setting that was determined in the previous experiments, we are now in the position to assess the in uence of the ltering approach. Figure 5(e) shows the performance with V AR, LN CE, and no lter. Twenty simulations are reaching a F1score value greater or equal to 0.7.

Interestingly, top performance was achieved with and without lter. This lead is to the question of computational complexity, which is answered in following paragraph.

DientdeorwmiSniazteioDnetermination Filter Mecea asure ll R0:4 :06:4

20 40 60 80 100 band size in % depending on input time series Filter Interval: The lter interval does not only in uence the resulting F1score , but also the amount of time series dissimilarity comparisons. Figure 7 illustrates the in uence of the interval size in respect to performance and computational demand. With an appropriate lter interval of about 200 % we are able to reduce the number of dissimilarity comparisons by one half, while still achieving relatively high performance values.

Individual Gestures Finally, we have tested the performance for each of the examined gestures separately. Figure 5(e) shows the best P recision and Recall values that were achieved for each gesture. The results demonstrate that some gestures are easier to recognize than others. 5

Conclusion and Future Work

In this work we have proposed a novel sliding window lter for more e cient event detection in time series streams, which replaces computational expensive dissimilarity comparisons by less demanding statistical measures. Furthermore, we have demonstrated that the developed lter is able to recognize gestures in continuous streams of acceleration data with high accuracy, while cutting the number of distance calculations in half.

Possible applications do not only include event detection on mobile device with few hardware resources, but also distributed sensor networks with limited bandwidth that communicate high level information instead of transferring raw data. In future work we plan to investigate a larger variety of statistical measures that exhibit favorable ltering properties for online gesture recognition as well as data streams found in other domains.

References

1. E. Acar , S. Spiegel , and S. Albayrak . MediaEval 2011 A ect Task: Violent Scene Detection combining audio and visual Features with SVM . CEUR Workshop , 2011 .

2. G. Batista , X. Wang , and E. J. Keogh . A complexity-invariant distance measure for time series . ICDM, 2011 .

3. T. F. Chan , G. H. Golub , and R. J. LeVeque . Algorithms for computing the sample variance: Analysis and recommendations . The American Statistician , 1983 .

4. G. Das , K.-I. Lin , H. Mannila , G. Renganathan, and P. Smyth . Rule Discovery from Time Series . KDD, 1998 .

5. H. Ding , G. Trajcevski, P. Scheuermann , X. Wang , and E. Keogh . Querying and mining of time series data: experimental comparison of representations and distance measures . VLDB Endowment , 2008 .

6. F. Itakura . Minimum prediction residual principle applied to speech recognition . IEEE Transactions on Acoustics, Speech, and Signal Processing , 1975 .

7. E. Keogh . Exact indexing of dynamic time warping . VLDB Endowment , 2002 .

8. E. Keogh , S. Chu , D. Hart , and M. Pazzani . Segmenting time series: A survey and novel approach . Data mining in Time Series Databases , 2004 .

9. S. Kratz , M. Rohs , K. Wolf , J. Mueller , M. Wilhelm , C. Johansson , J. Tholander , J. Laaksolahti . Body, movement, gesture and tactility in interaction with mobile devices . MobileHCI , 2011 .

10. G. Lesti and S. Spiegel . The sliding window lter for time series streams website . https://gordonlesti.com /a-sliding-window- lter-for-time-series-streams/

11. J. Liu , L. Zhong , J. Wickramasuriya , and V. Vasudevan . uWave: Accelerometerbased personalized gesture recognition and its applications . PerCom , 2009 .

12. H. Sakoe and S. Chiba . Dynamic programming algorithm optimization for spoken word recognition . Transactions on acoustics, speech, and signal processing , 1978 .

13. D. Sart , A. Mueen , W. Najjar , E. Keogh, and V. Niennattrakul . Accelerating dynamic time warping subsequence search with GPUs and FPGAs . ICDM, 2010 .

14. M. Sokolova and G. Lapalme . A systematic analysis of performance measures for classi cation tasks . Information Processing and Management , 2009 .

15. S. Spiegel , B.-J. Jain , and S. Albayrak . Fast time series classi cation under lucky time warping distance . SAC , 2014 .

16. S. Spiegel . Discovery of driving behavior patterns . Smart Information Systems - Advances in Computer Vision and Pattern Recognition , 2015 .

17. S. Spiegel . Optimization of in-house energy demand . Smart Information Systems - Advances in Computer Vision and Pattern Recognition , 2015 .

18. S. Spiegel . Time series distance measures: segmentation, classi cation and clustering of temporal data . TU Berlin , 2015 .

19. M. Wilhelm , D. Krakowczyk , F. Trollmann , S. Albayrak . eRing: Multiple Finger Gesture Recognition with one Ring Using an Electric Field . iWOAR, 2015 .

20. X. Xi , E. Keogh , C. Shelton , L. Wei , C. A. Ratanamahatana . Fast time series classi cation using numerosity reduction . ICML, 2006 .