Detecting a multigranularity event in an unequal interval time series based on self-adaptive segmenting

Abstract

Analyzing the temporal behaviors and revealing the hidden rules of objects that produce time series data to detect the events that users are interested in have recently received a large amount of attention. Generally, in various application scenarios and most research works, the equal interval sampling of a time series is a requirement. However, this requirement is difficult to guarantee because of the presence of sampling errors in most situations. In this paper, a multigranularity event detection method for an unequal interval time series, called SSED (self-adaptive segmenting based event detection), is proposed. First, in view of the trend features of a time series, a self-adaptive segmenting algorithm is proposed to divide a time series into unfixed-length segmentations based on the trends. Then, by clustering the segmentations and mapping the clusters to different identical symbols, a symbol sequence is built. Finally, based on unfixed-length segmentations, the multigranularity events in the discrete symbol sequence are detected using a tree structure. The SSED is compared to two previous methods with ten public datasets. In addition, the SSED is applied to the public transport systems in Xiamen, China, using bus-speed time-series data. The experimental results show that the SSED can achieve higher efficiency and accuracy than existing algorithms.

Keywords

Event detection multigranularity time series symbol sequence self-adaptive segment

ï»¿

1. Introduction

A time series, as a sequence consisting of an observed value and the recorded time, frequently appears in many domains, such as electric power [1, 2], finance [3], agriculture [4], and traffic [5]. Analyzing the time series data can be helpful to discover the temporal behaviors and reveal the hidden rules of the observed object. In recent years, time series analysis has focused on mining user patterns and the events the users are interested in rather than whole time series [6, 7, 8]. Detecting events has become a necessary step for other time series mining tasks, such as classification [9], prediction [10, 11], rule analysis [12], and anomaly detection [13, 14]. An event can be defined as a pattern that frequently occurs in the time-series data [15, 16]. For example, as shown in Fig. 1, segmentations $A$ , $B$ , and $C$ all belong to the same event.

Figure 1.

Example of an event.

Most existing works detect events based on directly calculating the similarity distance of the segmentation pairs, and these approaches are called exact methods. Exact methods first divide the original time series into several segmentations using a sliding window and then obtain the similarity distance between all pairs of segmentations using similarity distance measures such as the Euclidean distance and dynamic time warping (DTW) [17]. Finally, the segmentation pairs, for which the similarity distance is less than the threshold given by the user, will be marked as candidate events.

However, equal interval sampling is the default assumption in a time series analysis. In most application scenarios, it is difficult to guarantee that the sampling interval is equal because of the sampling error. For example, the largest challenge of the exact methods is the scalability of the detected events because fixed-granularity events can only be detected from equal interval time series. In time-series analysis, the time granularity denotes the time span of a segmentation [18, 19]. The typical way to solve this problem is to enumerate the range of granularity given by a user. However, enumerating granularity may cause not only a significant increase in execution time but also some important events to be missed.

To improve the accuracy, approximate methods are used to detect the events by transforming an original time series into a discrete-symbol sequence and then mapping back to the original time series segmentations. For example, SAX (symbolic aggregate approximation) [20] is widely used because of its simplicity and efficiency and can reduce the effects of noise. Through symbolic representation, the events within different lengths can be obtained in the solution. However, the time spans of the events are required to remain equal. Otherwise, the methods may obtain a lower accuracy, even compared to the exact methods [21].

To solve this problem, in this paper, a novel event detection method, SSED (self-adaptive segmenting-based event detection), is proposed. A self-adaptive segmenting algorithm is presented to divide a time series into unfixed-granularity segmentations according to the trend in the time series. All the segmentations are mapped to alphabetical symbols, and the original time series is represented as a sequence of symbols. Then, the SSED detects multigranularity events in the symbol sequence using a tree structure that adopts a novel symbolic representation. In summary, our work has two contributions: 1) a self-adaptive segmenting algorithm is proposed to improve the accuracy of identifying the events in an unequal interval time series; and 2) a novel symbolic representation based on the trend information is proposed that can detect the events with a wider range of granularity in linear time complexity. Compared with existing approximate methods, the SSED can achieve higher accuracy and efficiency than existing algorithms.

The main contributions of this work are summarized as follows.

Self-adaptive segmenting algorithm based on edge points is proposed to divide a time series into unfixed-length segmentations. At the stage of time series segmenting, based on the trend instead of fixed-length time window used in most of the existing methods, SSED divides time series into segmentations. This is because some important information on a curve, such as inflexion may be missed by using fixed-length time window. Therefore, self-adaptive segmenting algorithm can keep complete trends of time series as much as possible.

SSED uses a minimal set of five shape features to represent the maximum amount of change trend in the segmentation. Approximately representing the segmentations by extracting the features of each segmentation can eliminate the effect of noises on performance of clustering. In addition, five shape features reduce segmentation dimensions so that computational complexity can be highly reduced.

The rest of the paper is organized as follows. In Section 2, we present a survey of related work. In Section 3, we give the details of some definitions and notations that we address. Section 3 also presents a mathematical description of the problem. The details of SSED are presented in Section 4. The SSED has been evaluated using different data sets. The evaluation criteria, the design of the experiments, and the results are presented in Section 5. Finally, in Section 6, we present a summary and discuss what we intend to do in future work.

2. Related work

In time series analysis, event detection is an important research issue. It discovers sequence patterns [15] and reveals the temporal behavior of the objects that produce the data [22]. Therefore, event detection is applied to many domains, such as monitoring systems [17], healthcare [22] and geology [23], in which it is more helpful for discovering hidden knowledge.

Some researchers have focused on detecting events by directly calculating the similarity distance between segment pairs, called the exact method. The typical exact method is BF (brutal force) [24]. The main idea of BF is to find motifs by calculating the distance between segments obtained by the sliding window. BF tests all the combinations of segment pairs and records the locations of the pairs of segments with distances that are less than the threshold. In [25], Zhu et al. proposed an exact method based on DTW, which can quickly match the similarity segments by a warping matrix. In [26], Truong et al. proposed a novel clustering-based exact method, which can efficiently discover the subsequence pattern under DTW distance. Later, the NCM (normalized crossmatch) method was proposed in [27], which can discover frequent patterns by calculating the score matrix and the position matrix in the normalized time series data. Based on the matrix profile, which is a vector containing the distances between a subsequence and its nearest neighbor, a method called VLMOD (variable length motif discovery algorithm) was introduced in [28], which can find the exact fixed-length patterns by a fast similarity search algorithm introduced in [29]. In [30], the author proposed a efficiency fixed-length exact method called STOMP, which can optimize the time complexity to O ( $n^{2}\textit{Logn}$ ). In [31], Zhu et al. introduced a novel exact method to find the fixed-length patterns efficiently and effectively by a lower-bound matrix profile.

Differing from the above methods, to detect events more efficiently, some researchers have focused on approximate event detection by transforming the time series to a discrete symbol sequence. In [20], SAX was proposed to represent the segments as symbols by dividing a time series into equal-length segments, using the PAA (piecewise aggregate approximation) coefficients to represent each segment, and mapping the segments to symbol $a$ according to the breakpoints table, where $a\geqslant 2$ . Based on SAX, the repeated patterns or variable-length patterns are found [32, 33]. In [22], an algorithm called MDLats (motif discovery method for large-scale time series) was proposed to combine the advantages of the approximate methods and exact methods to efficiently find the frequent patterns of a time series. DTW (dynamic time warping) is often used to improve accuracy by removing false-positive events [23]. In [34], a method called SAX-ARM (symbolic aggregate approximation-association rule mining) is introduced that finds the deviant events from a multiple variate time series. In [35], an efficient framework was proposed to discover the arbitrary length frequency patterns of the host. Segmenting is an important step in finding the events in a time series. The fixed-granularity segmenting method, such as PAA [20], is widely used in time series mining tasks because of its simplicity. However, fixed-granularity segmentation lacks the contractility of the time series pattern. Variable-length segmentation is needed. In [36], edge points were detected and used as the segmentation points since they can avoid losing the key information of the raw time series to obtain better fitting performance.

Event detection, as an important research topic, is to discovery subsequence pattern from time series. In addition, there are other major research topics on time series, including forecast, correlation analysis, and sequential logic analysis, as shown in Table 1.

Table 1
Research topics on different domains

Research topics	Typical domains
Forecast	Seather [37], earthquake [38], finance [3], power system [10], mechanical vibration [39]
Subsequence pattern discovery	DNA sequencing [33], collaboration task [40, 41]
Correlation analysis	Collaboration task [42], finance [11]
Sequential logic analysis	Information security [43], software engineering [44]

As described above, to detect the events, dividing the time series into several equal-length segments is the first step in most methods. Exact methods directly calculate the similarity distance of the segment pairs, while approximate methods map segments to alphabetic symbols. If multigranularity events coexist in large-scale time series, iteratively invoking exact methods to detect all events will be a time-consuming task [23]. Approximate methods can efficiently detect the multigranularity events by transforming the sequences into discrete-symbol sequences. However, it achieves lower accuracy compared to exact methods [21]. Therefore, in time series analysis, a multigranularity event detection method with both accuracy and efficiency is required.

3. Problem statement

A time series represents a collection of values obtained from sequential measurements over time. Therefore, a time series can be defined as follows.

Definition 1. Time series: A time series $T=(t_{1},\ldots,t_{n})$ is a sequence of real values with length $n$ . The timestamp of the real value $t_{i}$ is denoted as $t_{i}.\textit{timestamp}$ , where the additional requirement $1\leqslant i\leqslant n$ is met.

When examining such time series, they are found to often contain events of interest. The goal of mining a time series is to extract these events. Segmenting an original time series or a datastream into events is an essential processing step. To clarify the presentation, the definition of segmentation is given.

Definition 2. Segmentation: Given a time series $T=(t_{1},\ldots,t_{n})$ , if a start position $i$ and an end position $j$ are specified, where $1\leqslant i<j\leqslant n$ , $S=(t_{i},t_{i+1},\ldots,t_{j})$ is called a segmentation. Specifically, for unequal sampling intervals, the granularities of segmentations are not equal, although both the start position and the end position are the same. The time granularity of $S$ is $t_{j}.\textit{timestamp}-t_{i}.\textit{timestamp}$ .

To obtain better fitting performance in a segmenting time series, edge points [36] are introduced as the intersections where the trend changes. For example, in the time series shown in Fig. 2, the left side of point $A$ has an upward trend, the right side has a downtrend; there is a downtrend on the left side of point $B$ and on the right side of point $B$ , the trend stabilizes. Therefore, points $A$ and $B$ are all edge points. The edge amplitude is the difference in trend between the adjacent segmentations on both sides of a point and is generally used to measure the possibility that a point is an edge point. If an edge amplitude is large enough, this point should be considered an edge point. We define the adjacent segment and edge amplitude as follows.

Figure 2.

Example of edge points.

Definition 3. Adjacent segmentation: For point $t_{i}$ in time series $T=(t_{1},\ldots,t_{n})$ , the adjacent segmentations with length $m$ can be divided into left adjacent segmentations $\textit{left}(S)_{i}=(t_{i-m},t_{i-m+1},\ldots,t_{i})$ and right adjacent segmentations $\textit{right}(S)_{i}=(t_{i},t_{i+1},\ldots,t_{i+m})$ , where $|\textit{left}(S)_{i}|=|\textit{right}({S})_{i}|={m}$ .

Definition 4. Edge amplitude: For point $t_{i}$ in time series $T=(t_{1},\ldots,t_{n})$ , the edge amplitude of $t_{i}$ represents the degree of the change in the trend between $\textit{left}(S)_{i}$ and $\textit{right}(S)_{i}$ , denoted as $EA_{i,m}$ , where $|\textit{left}(S)_{i}|=|\textit{right}(S)_{i}|=m$ .

The degree of change generally is the extent to which the level and trend are reflective of the difference between points in a time series.

Definition 5. Edge point: In time series $T=(t_{1},\ldots,t_{n})$ , $t_{i}$ can be used as an edge point, if $EA_{i,m}>d$ , where $d$ is the threshold of the edge amplitude, $1\leqslant i\leqslant n$ .

Generally, the degree of the change between any two points may be arbitrary, large or small. The smaller the value of $d$ , the greater the number of potential edge points. In this case, more noise points may be identified as edge points if partitioning time series. Conversely, if threshold $d$ is set to a very large value, real edge points could be lost. In most domains, according to practical needs, edge point can be identified better if the value of $d$ ranges from 1/4 and 3/4 of the maximum value of EA.

In a time series, an event is an important occurrence. Importance is application dependent. In a bus-speed time series, for instance, a traffic block is defined as an event. In this paper, we associate events with the frequent patterns in a time series. The more frequently a pattern appears in a time series, the more likely it is to be an event. The definition of an event is as follows.

Definition 6. Event: Given a time series $T=(t_{1},\ldots,t_{n})$ , a pattern $p$ is defined as an event $e$ if support ( $p$ ) $\geqslant$ minFreq, where support ( $p$ ) is the number of occurrences of $p$ , minFreq is the threshold of minimum frequency.

The occurrences of $p$ are obtained by directly counting subsequences of a time series, whether overlapping or not. Generally, the occurrences of $p$ cannot be directly counted from an original time series because the same subsequences are rare. In this paper, the symbolization processing is needed and is introduced in Section 4.2. As a pattern $p$ should be at least two occurrences, threshold minFreq can be set to a value greater than 2 according to the result.

Given a time series $T=(t_{1},\ldots,t_{n})$ , the problem we are interested in is to find an event set $E=\{e_{1},\ldots,e_{m}\}$ . For each $e_{i}\in E$ , there is a corresponding pattern. Depending on the segmentations, the pattern should meet minimum support.

4. Self-adaptive segmenting method

To detect the events with multigranularity, splitting the original time series into segmentations of different sizes is the first step in our work. Then, the symbolization processing of the segmentations is performed to reduce the complexity of the computation.

4.1 Self-adaptive segmenting based on edge points

To segment a time series into small sequences with different granularities, the method of extracting the edge points is the first crucial processing step. As described in Definition 5, whether a point can be identified as an edge point depends on the edge amplitude of the point. The rate of change in the time series is the degree to which the observed value changes with time. To measure the degree of the trend difference between two adjacent segmentations, the edge amplitude is used, as described in Definition 4. Therefore, for any two segmentations $S_{i}$ and $S_{j}$ in time series $T$ , the larger the difference in change rates between $S_{i}$ and $S_{j}$ , the greater the trend difference between them is. Given point $t_{i}$ and the adjacent segmentations with length $m$ , the edge amplitude $EA_{i}$ , as the difference in the change rate between $\textit{left}(S)_{i}$ and $\textit{right}(S)_{i}$ , is formulated as follows:

$\displaystyle{EA}_{i}=\left\{\begin{array}[]{ll}\left|\sum\limits^{i}_{j=1}{a_% {j}\omega_{j}-\sum\limits^{2i}_{j=i+1}{{a_{j}\omega}_{j}}}\right|&\text{if }1<% i<m;\\ \\ \left|\sum\limits^{i}_{j=i-m+1}{a_{j}{\omega}_{j}-\sum\limits^{i+m}_{j=i+1}{{a% _{j}\omega}_{j}}}\right|&\text{if }m\leqslant i\leqslant n-m;\\ \\ \left|\sum\limits^{i}_{j=2i-n+1}{a_{j}{\omega}_{j}-\sum\limits^{n}_{j=i+1}{{a_% {j}\omega}_{j}}}\right|&\text{if }n-m<i<n;\\ \end{array}\right.$ (1)

where ${\omega}_{j}$ represents the rate of change from point $t_{j-1}$ to point $t_{j}$ and $a_{j}$ is the weight value of $t_{j}$ . The following is considered, 1) as the behavior of segmentations in a time series changes with time, the adjacent points of $t_{i}$ have more similar characteristics with $t_{i}$ than those faraway points, and 2) the segmentations with different time intervals are also not identical. As the weight value is correlated to the time interval of the time series, ${\omega}_{j}$ and $a_{j}$ should be measured by a timestamp, as shown in Eqs (2) and (3).

$\displaystyle{\omega}_{j}=(t_{j}-t_{j-1})/(t_{j}.\textit{timestamp}-t_{j-1}.% \textit{timestamp})$ (2) $\displaystyle a_{j}=1/(|t_{j}.\textit{timestamp}-t_{i}.\textit{timestamp}|)$ (3)

Taking into account the timestamp, the process of extracting the edge points can support the unequal time intervals of a time series. Therefore, self-adaptive segmentations can be obtained via Eq. (1).

However, the adjacent points of which the edge amplitudes are greater than threshold $d$ may be close together. Therefore, it is possible that some consecutive points are chosen as edge points. For example, given a time series, as shown in Fig. 3, the edge amplitude of every point in the time series is calculated by Eq. (1). In the result, as shown in Fig. 4, the red horizontal line represents threshold $d$ , and the red points are the points of which the edge amplitude is greater than threshold $d$ . If the threshold is set to 2.3, seven points, $t_{16}$ , $t_{32}$ , $t_{33}$ , $t_{48}$ , $t_{49}$ , $t_{61}$ , and $t_{81}$ , are marked red. If these points are taken as edge points, two segmentations with a granularity of 1 would be generated. This outcome would cause too many small segmentations to be generated.

Figure 3.

Example of time series data.

Figure 4.

Edge amplitude of every point.

To improve the quality of segmenting, a self-adaptive segmenting algorithm is proposed to select the edge point with maximum edge amplitude if there are multiple consecutive edge points in a limited time span. Given two edge points $t_{i}$ and $t_{j}(i\neq j)$ , the additional requirement $t_{i}.\textit{timestamp}-t_{j}.\textit{timestamp}>r$ should be met, in which $r$ is the minimum granularity of segmentation. The pseudocode of the self-adaptive segmenting algorithm is shown in Algorithm 1.

Algorithm 1: DetectEdgePoints
Input: time series: $T$ ; threshold of edge amplitude: $d$ ; length of adjacent segment: $m$ ; minimum granularity of segment: $r$
Output: a sequence of edge points: SEP
1. $\textit{AEP}=\{\}$ //points of which the edge amplitudes are greater than threshold $d$
2. for $i$ in $\{1,\ldots,\text{len}(T)\}$
3. ${EA}_{i}=$ CalEdgeAmplitude ( $T[i],m$ ) //calculating edge amplitudes using Eq. (1)
4. if ${EA}_{i}>d$ thenAEP.add( $i$ )
5. end for
6. $\textit{SEP}=\textit{AEP}$
7. for $i$ in $\{2,\ldots,\text{len}(\textit{AEP})\}$
8. if $\textit{AEP}[i]\textit{.timestamp-lastep.timestamp}<=r$ //Compare the granularity scope with the adjacent points
9. if $\textit{AEP}[i]$ . $EA>\textit{lastep}$ . $E A$ //Save the point with the larger edge amplitude
10. SEP.remove(lastep); $\textit{lastep}=\textit{AEP}[i]$
11. else
12. SEP.remove(AEP[ $i$ ])
13. end if
14. else
15. $\textit{lastep}=\textit{AEP}[i]$
16. end if
17. end for
18. returnSEP

In the self-adaptive segmenting algorithm, the value of adjacent segmentation should be provided to calculate edge amplitude. This value depends on the degree of the change in a time series according to domain knowledge. For example, in public transportation domain, adjacent segmentation could be set to 30 seconds if sampling interval is 15 seconds, because velocity time series fluctuates greatly. In temperature forecast domain, as temperature time series is stable in most cases, adjacent segmentation could be set to a relatively large value, such as 4 hours or more.

4.2 Symbolizing segmentation

Generally, mapping a real-valued time series into a symbol sequence is a necessary step that can eliminate noise in the original time series data and reduce the computational complexity of detecting events. The segmentations resolved by Algorithm 1 in the last section are represented as symbol sequences.

To symbolize segmentation more accurately, we adopt a strategy in which all similar segmentations are mapped to one symbol sequence through clustering methods. The first step is to approximately represent the segmentations by extracting the shape features of each segmentation. The second step is to divide the segmentations into different sets by the clustering method and then represent them as symbols. The degree of similarity between any two segmentations is measured by the shape feature distances. This strategy can reduce the dimensions and eliminate the influence of noise.

To describe the trend of a time series, the five shape features of a segmentation include the mean value, average change rate, standard deviation, first point of segment and last point of segment in our work. Given a segmentation $S=({t}_{1},t_{2},\ldots,t_{n})$ with length $n$ , let the mean value be $\mu$ , average change rate be $\eta$ and standard deviation be $s d$ ; $\mu$ , $\eta$ , and $s d$ are calculated by the following equations.

$\displaystyle\mu=\left.\left(\sum^{n}_{h=1}{t_{h}}\right)\right/n$ (4) $\displaystyle\eta=(t_{n}-t_{1})/(t_{n}.\textit{timestamp}-t_{1}.\textit{% timestamp})$ (5) $\displaystyle sd=\sqrt{\left.\left(\sum^{n}_{h=1}{(t_{h}-\mu)^{2}}\right)% \right/n}$ (6)

In addition to the five features above, there are two points of any segmentation $S_{i}$ that are important, the first point and the last point, denoted as $fp_{i}$ and $lp_{i}$ , respectively. If two segmentations are identified as similar pairs, points $fp_{i}$ and $lp_{i}$ are used to further distinguish the pair.

Before clustering, the feature values should be normalized to eliminate their difference, as the five features have different units. In this paper, the z-score is used for normalization, which normalizes the value into numbers between $-$ 1 and 1. The z-score is formulated as follows.

$\displaystyle z=(x-\mu)/\sigma$ (7)

where $x$ is the feature value, $\sigma$ is the standard deviation, and $\mu$ is the mean value.

Given a segmentation set $SS=\{S_{1},\ldots,S_{k}\}$ , the features of each segmentation are mapped into numbers between $-$ 1 and 1 by Eq. (2). The tuple $(\mu^{*}_{{i}},\eta^{*}_{{i}},sd^{*}_{{i}},fp^{*}_{i},lp^{*}_{i})$ is used to represent the normalized feature of segmentation $S_{i}$ . Therefore, $S S$ can be represented as $FS=\{(\mu^{*}_{1},\eta^{*}_{{1}},sd^{*}_{{1}},fp^{*}_{1},\linebreak lp^{*}_{1}% ),\ldots,(\mu^{*}_{{k}},\eta^{*}_{{k}},sd^{*}_{{k}},fp^{*}_{k},lp^{*}_{k})\}$ .

Table 2

The shape features of the segmentations

Segment	$\mu$	$\eta$	$s d$	$f p$	$l p$
$S_{1}$	1.98	$-$ 0.01	0.32	1.76	1.53
$S_{2}$	8.94	0.97	4.78	1.53	17.08
$S_{3}$	17.07	0.00	0.24	17.08	17.13
$S_{4}$	9.56	$-$ 0.98	4.65	17.13	2.43
$S_{5}$	2.02	0.00	0.33	2.43	2.43
$S_{6}$	9.82	1.06	4.50	2.43	17.20

Figure 5.

An example of the symbolization of segments.

After normalizing the feature set, we use BIRCH (balanced iterative reducing and clustering using hierarchies) [16] to divide the $F S$ into several clusters. BIRCH is a well-known hierarchical clustering algorithm that obtains the initial clustering results by scanning a data set once according to a height-balance tree. BIRCH is very suitable for clustering large datasets and is a bounded-spherical clustering algorithm. It can ensure that the distances between the normalized feature tuple of segmentations within the same cluster are less than the given threshold $\delta$ , which can maintain that the segmentations within the same cluster are similar enough.

As there are five features used in a segmentation in $S S$ , and each feature of segmentation $S_{i}$ is normalized into numbers between $-$ 1 to 1, threshold $\delta$ ranges from 0 to the square root of 20. Threshold $\delta$ determines the number of clusters, in each of which all similar segmentations are mapped to one symbol sequence. Therefore, the number of symbol sequences is actually determined by threshold $\delta$ . The larger the value of threshold $\delta$ , the fewer symbols are obtained, and the more inaccurate the similarities between the original subsequences corresponding to the symbol sequences. In our method, the analysis of Calinski-Harabasz is applied to determine the value of threshold $\delta$ in Section 6.

Taking the segmentations as an example, the time series is split into six segmentations, from $S_{1}$ to $S_{6}$ . The shape features of the segmentations are shown in Table 2. If threshold $\delta$ is set to 1, the segmentations are divided into four clusters by clustering, as shown in Fig. 5. Segmentations $S_{1}$ and $S_{5}$ are divided into cluster $a$ , $S_{2}$ and $S_{6}$ are divided into cluster $b$ , and $S_{3}$ and $S_{4}$ are divided into cluster $c$ and $d$ , respectively. According to the clusters, all the segmentations within the same cluster center are symbolized with the same symbol. Finally, the time series is symbolized as a symbol sequence ( $a$ , $b$ , $c$ , $d$ , $a$ , $b$ ).

5. Detecting multigranularity events

If the identified events have different durations, this is so-called multigranularity events. For example, symbol sequences ( $a$ , $b$ , $c$ , $d$ , $a$ , $b$ ) can be identified as three events, ( $a$ ), ( $b$ ), and ( $a$ , $b$ ) that have different durations, as shown in Fig. 6.

Figure 6.

Multigranularity events.

In the symbol sequence representing the time series, each symbol corresponds to a set of segmentations with similar shapes. This correspondence means that each symbol has a high degree of support. If the degree of support is greater than minFreq, the symbol is an event we want to detect. In fact, the events in a time series may not be mutually exclusive and often show mutually inclusive relationships. For example, event ( $a$ ), ( $b$ ), and ( $a$ , $b$ ) that are identified from symbol sequences ( $a$ , $b$ , $c$ , $d$ , $a$ , $b$ ) all meet the support condition ( $p$ ) ${\geqslant}$ minFreq, if threshold minFreq is set to 2.

In our method, a tree structure called the suffix tree is adopted. In a suffix tree, the root node only serves to index the child nodes, while the nonroot node stores two kinds of information: a subsequence whose frequency is greater than minFreq and the set of starting positions of the subsequence in the symbol sequence. For the general definitions, a node in the tree is represented by $N_{i,j}$ , where $I$ denotes the depth of the node and $j$ the node number of the suffix tree, the subsequence stored in $N_{i,j}$ and the start position of the subsequence are represented by $N_{i,j}.\textit{sequence}$ and $N_{i,j}.\textit{startindex}$ , respectively.

Given a symbol sequence $CA=(c_{1},\ldots,c_{k})$ , minimum frequency threshold minFreq, and a suffix tree $T r$ built according to $C A$ , the suffix tree $T r$ should be compatible with the following conditions: 1) For a nonroot node $N_{i,j}$ in $T r$ , let $N_{i,j}.\textit{sequence}$ be ( $c_{h},\ldots,c_{h+i-1}$ ) where $h$ is the position index in $N_{i,j}.\textit{startindex}$ . The length of $N_{i,j}.\textit{sequence}$ is the depth of the node, i.e., $|N_{i,j}.\textit{sequence}|={I}$ , and the frequency of $N_{i,j}.\textit{sequence}$ in $C A$ is the size of $N_{i,j}.\textit{startindex}$ ; and 2) Given two nonroot nodes $N_{i,j}$ and $N_{i^{\prime}j^{\prime}}$ , $N_{i^{\prime}j^{\prime}}.\textit{sequence}$ is the suffix sequence of $N_{i,j}.\textit{sequence}$ and $N_{i^{\prime}j^{\prime}}.\textit{startindex}$ is the subset of $N_{i,j}.\textit{startindex}$ , if $N_{i,j}$ is the parent node of $N_{i^{\prime}j^{\prime}}$ .

To build the suffix tree, nine steps should be followed.

Step 1:

Scan symbol sequence $CA=(c_{1},\ldots,c_{k})$ , and obtain all the symbols and their positions in $C A$ ;

Step 2:

Initialize suffix tree $T r$ , generate new nodes according to the symbols and their positions, and then insert them into $T r$ ;

Step 3:

Take the new leaf nodes as the iterative node set INS;

Step 4:

Extract a leaf node $N_{i,j}$ from INS and obtain its suffix sequence set $\{(c_{h},\ldots,c_{h+i})|h\in N_{i,j}.\textit{startindex}\}$ ;

Step 5:

Filter the sequences with frequencies less than minFreq in the suffix sequence set; if the suffix sequence set is empty, go to step 7;

Step 6:

Generate new nodes according to the suffix sequence set and insert them into $T r$ ;

Step 7:

Remove $N_{i,j}$ from INS, and go back to step 3 if INS is not null;

Step 8:

Judge if there are new nodes generated in this iteration, go back to step 3;

Step 9:

Output the root node of the suffix tree.

The pseudocode of the building suffix tree is shown in Algorithm 2.

Algorithm 2: BuildSuffixTree
Input: a symbol sequence: $C A$ ; minimum number of occurrences of the events: minFreq;
Output: root node of the tree: rootNode
1. rootNode $=$ InitialTree() //Initialize the tree
2. symbolSet, positionSet $=$ getAllSymbol ( $C A$ ) //obtain all the symbols and their position indexes in $C A$
3. symbolSet, positionSet $=$ filterSequence(symbolSet, positionSet, minFreq) //filter the sequence whose frequency is less
than minFreq
4. cNodeSet $=$ createNewNode(symbolSet, positionSet) //create new node
5. InsertNode(cNodeSet) //insert new node into suffix tree
6. iteNode $=$ cNodeSet //take the newly generated node as the iterative node set
7. whileiteNode! $=$ NULL
8. $\{\textit{suffixSequenceSet},\textit{startPositionSet}\}$ $=$ getSuffixSequence(iteNode) //obtain the suffix sequence and its start
position index
9. $\{\textit{suffixSequenceSet},\textit{startPositionSet}\}$ $=$ filterSequence(suffixSequenceSet, startPositionSet, minFreq)
10. childNodeSet $=$ createNewNode(suffixSequenceSet, startPositionSet)
11. InsertNode(childNodeSet)
12. iteNode $=$ childNodeSet //Take the new generated nodes as the next iteration nodes
13. end while
14. returnrootNode

For example, given a symbol sequence ( $a$ , $b$ , $c$ , $a$ , $c$ , $c$ , $a$ , $b$ , $c$ , $c$ ), a suffix tree is built if threshold minFreq is set to 2, as shown in Fig. 7. Each subsequence stored by nonroot nodes in the suffix tree constitutes all events, and the occurrence frequency of the events is equal to the size of the starting position set. In building a suffix tree, the key process is to determine whether the nodes with the highest depth can generate child nodes. This process is repeated until no child nodes are generated in the current round of iteration. After the suffix tree is built, the events with multigranularity are resolved.

6. Performance evaluation

6.1 Experiment on public transport data

To evaluate the performance of SSED, we take the public transport system in Xiamen, China, as a case study to analyze our method. In this system, the speed value of buses is normally recorded every 15 seconds via GPS (global position system). Therefore, a speed time series is formed for each running bus. However, a large number of time series with unequal time intervals is found. Actually, a wide range of time intervals, from 1 to 32 seconds, is found in the original data because of the latency of the software platform or other reasons. This situation cannot be ignored.

We extract a part of the dataset including the speed time series of 29 buses belonging to line 953 during July 2018. The total length of the time series is 200657, and the sampling intervals vary from 1 second to 32 seconds. The format of the data is described in Table 3.

Table 3
Data format of the speed time series

Line number	Speed (km/h)	Time (Y/M/D h:m:s)
953	13	2018/7/1 15:42:15
953	15	2018/7/1 15:42:22
953	30	2018/7/1 15:42:37
953	27	2018/7/1 15:42:52
953	23	2018/7/1 15:42:56

Figure 7.

An example of a suffix tree.

The experiment has three steps: 1) dividing the time series into unfixed-granularity segmentations by a self-adaptive segmenting algorithm; 2) clustering the segmentations using BIRCH and symbolizing each cluster; and 3) detecting multigranularity events in the symbol sequence of the time series.

Step 1) Divide the time series into unfixed-granularity segmentations by a self-adaptive segmenting algorithm.

To use the self-adaptive segmenting algorithm, three parameters, window size $m$ , edge amplitude threshold $d$ and minimum granularity of segmentation $r$ , should be determined. In this experiment, according to Definition 3, the sample data at 15-seconds intervals should have segmentations with a length of at least 30 seconds. According to Definition 4 and 5, the value of EA is between 0 and 3. To obtain better edge point identifying effect, set $d=$ 1.5 according to the speed variation rate of the bus; set $m=$ 2 so that a complete solution is expected; and set $r=$ 15 seconds so that time intervals greater than 15 seconds are all considered. In the solution, the speed time series is divided into 93213 unfixed-granularity segmentations. A part of the segmentations in the original time series is shown in Fig. 8, in which the red points are the edge points.

Figure 8.

A part of the segmentations with edge points in speed time series.

Step 2) Clustering the segmentations using BIRCH and symbolizing each cluster.

To approximate the segmentations, we extract and normalize the shape feature. BIRCH clustering is used in our method. To obtain better clustering effect, the analysis of Calinski-Harabasz [45] is used to try the values of parameter $\delta$ from 0.6 to 1.0. With parameter $\delta=$ 0.75, there are 45 clusters in the result set, as shown in Table 4. Each cluster is identified by a unique symbol. Finally, the original time series is converted into a symbol sequence with length 93213.

Table 4

Cluster set

Cluster number	Mean value		Change rate		Standard deviation		First point value		Last point value
$C_{1}$	40	.08854	13	.15957	7	.236475	32	.43889	47	.5663
$C_{2}$	17	.15405	2	.452233	2	.437519	15	.67832	18	.53672
$C_{3}$	28	.63441	$-$ 1	.65372	10	.11407	21		10
$C_{4}$	35	.60406	$-$ 20	.4088	13	.50439	50	.48752	19	.8323
$C_{5}$	1	.739642	1	.057811	1	.620177	1	.428358	2	.685468
$C_{6}$	11	.51676	$-$ 6	.33558	12	.74343	34	.44283	1	.433333
$C_{7}$	38	.23081	$-$ 12	.1191	6	.980336	45	.54372	30	.70303
$C_{8}$	46	.45782	$-$ 1	.4819	2	.556453	47	.52758	44	.83737
$C_{9}$	30	.09507	15	.74606	14	.8697	11	.10323	48	.4271
$C_{10}$	26	.98878	$-$ 0	.99187	2	.98377	26	.75243	26	.18719
$C_{11}$	25	.74599	13	.59304	8	.112158	16	.87148	34	.41083
$C_{12}$	29	.1761	$-$ 47	.8019	24	.10101	53	.39623	4	.962264
$C_{13}$	36	.08409	1	.165393	2	.337695	34	.82955	36	.65127
$C_{14}$	45	.88886	1	.804261	8	.4479	23	.94186	45	.22093
$C_{15}$	35	.51893	8	.514023	9	.805874	21	.55245	46	.74514
$C_{16}$	46	.01636	$-$ 9	.48026	7	.266306	53	.58989	36	.52528
$C_{17}$	19	.2185	16	.81167	14	.69825	0	.527517	37	.19967
$C_{18}$	23	.30063	$-$ 7	.51021	12	.75906	34	.275	1	.041667
$C_{19}$	9	.190961	$-$ 14	.637	8	.202619	17	.96141	0	.678911
$C_{20}$	22	.86244	$-$ 21	.5762	18	.05239	44	.72026	0	.285714
$C_{21}$	13	.39396	21	.06911	11	.52449	1	.261613	25	.40093
$C_{22}$	23	.87827	$-$ 14	.2486	8	.521142	32	.84035	14	.51525
$C_{23}$	11	.54629	5	.53794	13	.65748	1	.096774	36	.9914
$C_{24}$	16	.69601	$-$ 26	.0257	13	.93364	31	.13253	2	.222901
$C_{25}$	20	.81844	37	.62952	18	.81476	2	.003676	39	.6332
$C_{26}$	48	.5	59		29	.5	19		78
$C_{27}$	13	.18592	2	.616157	9	.59798	15	.08333	30	.54167
$C_{28}$	27	.03085	16	.79566	18	.51381	0	.409692	49	.17621
$C_{29}$	36	.55666	$-$ 4	.12482	10	.82271	41	.25	12
$C_{30}$	25	.52293	$-$ 14	.7132	14	.25764	42	.71918	6	.478159
$C_{31}$	53	.5	$-$ 49		24	.5	78		29
$C_{32}$	45	.1275	29	.245	14	.6225	30	.505	59	.75
$C_{33}$	23	.12404	0	.057765	13	.58878	2	.375	2	.625
$C_{34}$	34	.77591	2	.971321	9	.241092	16	.06098	35	.63415
$C_{35}$	31	.4947	$-$ 9	.51624	5	.48156	36	.91525	25	.53276
$C_{36}$	16	.45121	28	.8839	14	.44195	2	.009253	30	.89316
$C_{37}$	35	.08039	8	.603377	6	.149788	27	.45651	41	.25871
$C_{38}$	27	.8499	6	.165472	13	.39068	1	.153285	36	.80693
$C_{39}$	26	.91883	25	.98682	12	.99341	13	.92542	39	.91224
$C_{40}$	19	.72419	$-$ 38	.0252	19	.01259	38	.73678	0	.711596
$C_{41}$	44	.86007	9	.055739	10	.87043	27	.7931	56	.98276
$C_{42}$	17	.14378	$-$ 9	.89259	5	.510336	22	.88509	11	.37255
$C_{43}$	30	.45791	$-$ 26	.3216	13	.16078	43	.61869	17	.29712
$C_{44}$	20	.27383	3	.883141	10	.17817	0	.606061	21	.75758
$C_{45}$	9	.603214	16	.88662	8	.86562	0	.577362	18	.71444

Step 3) Detecting the multigranularity events in the symbol sequence of the time series.

Algorithm 2 is used to detect the multigranularity events in the symbol sequence. In this experiment, considering the fact that buses generally run on a regular schedule in most cases, setting the minimum frequency of events to 10 can obtain a moderate degree of support. Of course, threshold minFreq can be set higher as well so that events with higher degree of support can be obtained. Then, the symbol sequence is mapped back to the segmentations of the original time series as the final event set. In the final event set, there are 3072 events together with a range of granularities from 15 seconds to 342 seconds. The four events with instances, each of which is composed of the segmentations of the time series, are provided, as shown in Fig. 9.

Figure 9.

Four events detected by SSED in speed time series.

To evaluate the results on the Xiamen bus data, the experiment is designed as follows. First, a typical event is detected from the time series on one bus stop. Then, the typical event, as a standard, is used to measure the percentage by which it is detected from the time series on another bus stops. The percentage $p$ is formulated as follows.

$\displaystyle p=\textit{numofdetected/allEvents}$ (8)

Considering that velocity time series during bus arrival and departure shows similar trends, two kinds of events are selected as the standards in this experiment. For example, event $A$ and $B$ describes the velocity time series of buses arrival and departure during off-peak hour and peak hour respectively, as shown in Fig. 10. The two kinds of events have typical characteristics of bus arrival and departure because buses almost have good pit stops during off-peak hour, while have difficult pit stops during peak hour. In this experiment, the two kinds of events are selected as standards from the time series on bus stop HUJING. Four bus stops, DIANQIAN, SM, School of Business Tourism and PINGYANGLI are selected to measure the percentage of event $A$ and $B$ kinds. The velocity time series are created by capturing every bus arrival and departure with durations between 30 and 80 seconds. Threshold minFreq are set to 50. In the final result, the percentage of event $A$ and $B$ kinds at the four bus stops are 71%, 78%, 71%, and 82%. These percentages show that the typical events can properly be identified by SSED. Therefore, it proves SSED is an effective method.

6.2 Experiment on another 10 public datasets

We applied the SSED on another 10 public datasets from the UCR Time Series Archive [46] to evaluate the scalability of SSED on a range of domains. The UCR Time Series Archive is a popular time series library that collects numerous datasets used in time series analysis research. As all required parameters cannot be directly learnt, the method of grid search is chosen to determine the most parameters as it is widely used for parameter optimization. The characteristics of the test datasets and recommended parameter settings are described in Table 5. In the experiment, we set $\textit{minFreq}=$ 2 for each dataset.

Table 5
Characteristics of the selected datasets and recommended parameters of SSED

Dataset number	Dataset name	Datasets length	Recommended parameter of SSED
1	CinC ECG Torso	65600	$m=$ 40, $d=$ 0.5, $r=$ 200, $\delta=$ 0.5
2	Coffee	8036	$m=$ 20, $d=$ 0.8, $r=$ 15, $\delta=$ 0.8
3	Cricket_X	117390	$m=$ 10, $d=$ 2, $r=$ 20, $\delta=$ 1
4	Cricket_Y	117390	$m=$ 10, $d=$ 2, $r=$ 20, $\delta=$ 1
5	Cricket_Z	117390	$m=$ 10, $d=$ 2, $r=$ 20, $\delta=$ 1
6	Gun Point	7550	$m=$ 20, $d=$ 0.8, $r=$ 20, $\delta=$ 0.5
7	MedicalImages	38100	$m=$ 8, $d=$ 2, $r=$ 8, $\delta=$ 0.75
8	ShapesAll	307800	$m=$ 30, $d=$ 0.8, $r=$ 30, $\delta=$ 0.8
9	ToeSegmentation1	11120	$m=$ 12, $d=$ 1, $r=$ 12, $\delta=$ 1.3
10	Yoga	128100	$m=$ 20, $d=$ 1, $r=$ 20, $\delta=$ 0.8

Figure 10.

Two events detected on the Xiamen bus data.

Figure 11.

Events detected by the SSED on the ten datasets.

Due to space limitations, we show only two events resolved on each dataset, as shown in Fig. 11. For example, Fig. 11(1) shows two movement events of cardiac action potential during each cardiac cycle; Fig. 11(2) shows two waves of spectral change that are used to distinguish between Robusta and Aribica coffee beans; Fig. 11(3)–(5) show that two kinds of accelerometer trends in three dimensions, X-, Y- and Z-axis directions, taken from actors performing cricket gestures; The events in the rest of figures are related to location changes or image pixel changes.

6.3 Results and discussions

For quantitative analysis, two methods, the GrammarViz method proposed in [47] and the STOMP method proposed in [30] are chosen for comparison.

The GrammarViz method is chosen for comparison, as GrammarViz and SSED are both approximate methods. GrammarViz has four steps: 1) dividing a raw time series into several overlapping segmentations with equal length by a sliding window; 2) symbolizing each segmentation by using SAX; 3) using the sequitur grammar inference algorithm to detect the multigranularity events in the symbol sequence; and 4) removing the trivial match in the candidate events.

The comparison is designed as follows. The ten public datasets from Section 6.2 are used. On the parameter settings, for the SSED, the parameters are the same as those given in Table 5. For GrammarViz, three parameters are required: sliding window $s$ , word size $w$ , and symbol size $a$ . A sliding window is used to divide the time series into overlapping segmentations with fixed granularity. Word size and symbol size are used to transform the segmentations into symbols.

The STOMP method is an advanced exact method, which is based on a fast algorithm for similarity search to get the matrix profile of the segmentations in time series and then to match the segmentations. As an exact method, two parameters are required: sliding window ( $s$ ) and radius ( $r$ ). A sliding window is used to divide a time series. A radius is a similarity degree which is used to find all neighbors of a segmentation. Considering that STOMP can only detect fixed-granularity event, to detect multigranularity events, sliding window $s$ should be iteratively set according to a range of granularities. The parameters of STOMP and GrammarViz used in this experiment are shown in Table 6.

Table 6
Parameter settings of GrammarViz and STOMP

Dataset number	Dataset name	Parameter of GrammarViz	Parameter of STOMP
1	CinC ECG Torso	$s=$ 150, $w=$ 3, $a=$ 3	$R=$ [1000, 4000], $m=$ 300, $r=$ 5
2	Coffee	$s=$ 200, $w=$ 4, $a=$ 3	$R=$ [100, 500], $m=$ 40, $r=$ 5
3	Cricket_X	$s=$ 150, $w=$ 3, $a=$ 6	$R=$ [100, 500], $m=$ 40, $r=$ 5
4	Cricket_Y	$s=$ 150, $w=$ 3, $a=$ 6	$R=$ [100, 500], $m=$ 40, $r=$ 5
5	Cricket_Z	$s=$ 150, $w=$ 5, $a=$ 6	$R=$ [100, 500], $m=$ 40, $r=$ 5
6	Gun Point	$s=$ 150, $w=$ 3, $a=$ 3	$R=$ [100, 500], $m=$ 40, $r=$ 5
7	MedicalImages	$s=$ 300, $w=$ 3, $a=$ 3	$R=$ [100, 400], $m=$ 30, $r=$ 5
8	ShapesAll	$s=$ 300, $w=$ 3, $a=$ 5	$R=$ [500, 2000], $m=$ 150, $r=$ 5
9	ToeSegmentation1	$s=$ 100, $w=$ 5, $a=$ 5	$R=$ [100, 300], $m=$ 30, $r=$ 5
10	Yoga	$s=$ 300, $w=$ 3, $a=$ 6	$R=$ [100, 400], $m=$ 30, $r=$ 5

The running environment of the computer includes an Intel(R) Core(TM) i5-6500 with 3.20 GHz, and 16 GB of RAM. The SSED is implemented in Python using PyCharm 2018.2.3.

We compare the accuracy and the efficiency of our method with the GrammarViz method and the STOMP method. The concrete indexes for accuracy and efficiency will be introduced in the following subsections.

6.3.1 Accuracy analysis

Error analysis, as an accuracy analysis, is often used to evaluate the performance of a method. Though the STOMP method is an exact method, errors can still exist as fixed time windows is used at the stage of segmenting. Therefore, the STOMP method cannot be used as a criterion.

To measure the accuracy of detecting events, we define error as the average similarity distance between the segmentations in the same clusters. The value of error can be calculated using the following equation.

$\displaystyle\textit{error}=\sum^{M}_{i=1}\textit{Avg}\left.\left(\frac{% \textit{Distance}(S_{ih},S_{ik})}{(S_{ih}.\textit{length}+S_{ik}.\textit{% length})/2}\right)\right/M\quad|1\leqslant h\leqslant|e_{i}|,1\leqslant k% \leqslant|e_{i}|$ (9)

where $M$ is the number of events and $|e_{i}|$ is the number of segmentation sets from the event in which $e_{i}$ is clustered. $S_{ih}$ and $S_{ik}$ are the $h$ -th and $k$ -th segmentation in the cluster, respectively. $\textit{Distance}(S_{ih},S_{ik})$ is the similarity distance between $S_{ih}$ and $S_{ik}$ . We use DTW to measure the distance. $\textit{AVG}\{*\}$ denotes the mean value of elements in the set.

Through calculating the events in the ten datasets using STOMP and SSED, it is observed that SSED has slightly higher error on eight datasets, as shown in Table 7. This is because STOMP is an exact algorithm that can obtain all similar subsequences. Despite this, SSED still has the same or lowest error on two datasets. This is because the five shape features of a segmentation, including the mean value, average change rate, standard deviation, first point of segment and last point of segment adopted by SSED can preserve the important properties of a time series as much as possible. This is an advantage of SSED.

Table 7

A comparison of the error and runtime (in seconds) of STOMP, GrammarViz and SSED on different data sets (The execution times is given in brackets)

Dataset	STOMP		GrammarViz		SSED
CinC ECG Torso	0.137	(958.979)	0.1797	(12.318)	0.1451	(0.5802)
Coffee	0.0291	(20.4269)	0.074	(1.5923)	0.0291	(0.1476)
Cricket_X	0.1964	(6616.554)	0.3632	(23.0610)	0.2635	(1.1085)
Cricket_Y	0.2391	(6414.247)	0.3615	(22.4237)	0.298	(1.1912)
Cricket_Z	0.2091	(6561.1479)	0.3833	(22.5009)	0.2023	(1.1431)
Gun Point	0.037	(19.7801)	0.0797	(1.4250)	0.0451	(0.0967)
MedicalImages	0.061	(314.1572)	0.3821	(7.6913)	0.1279	(0.3401)
ShapesAll	0.0764	(37008.442)	0.2231	(57.5801)	0.0805	(2.924)
ToeSegmentation1	0.0969	(18.9829)	0.3213	(2.43086)	0.1492	(0.1492)
Yoga	0.102	(7561.1479)	0.7996	(27.6176)	0.0929	(0.9564)
Average Error	0.1184	(6549.386)	0.3168	(17.864)	0.1434	(0.8637)

Through calculating the events in the ten datasets using GrammarViz and SSED, it is observed that GrammarViz has the highest error on all datasets, as shown in Table 7, because GrammarViz adopts SAX to symbolize the segmentations. SAX only uses the mean value to represent the segmentation and ignores the trend of the time series. It can result in the increasing possibility of producing false positives in detecting events. SSED achieves the lowest errors on all datasets, as the five shape features of a segmentation are considered to describe the trend of the time series. Therefore, we can conclude that the SSED can obtain higher accuracy than the other approximate methods.

6.3.2 Efficiency analysis

The efficiency represents the execution time of a method. To measure the efficiency of detecting events, we compare the execution time with two other methods, GrammarViz and STOMP.

For STOMP, two parameters are required, sliding window $s$ and radius $r$ , as shown in Table 6. A sliding window is used to divide the time series, and the radius is used to find the neighbors within a scope. Considering that STOMP can only detect the fixed-granularity events, we will iteratively set the sliding window according to granularity range $R$ and the step size of sliding window $m$ .

The efficiency of detecting the events in ten datasets is shown in Table 7. It is observed that the SSED has the highest efficiency compared to the other two methods because SSED detects the events in the symbol sequence rather than the original time series. This detection can dramatically decrease the computational cost. STOMP takes the longest time to enumerate the events in the ten datasets, although the number of iterations is reduced by enumerating within some ranges. In the largest dataset ShapesAll, STOMP requires nearly 10 hours to process the time series with a length of 307800, because more running time is needed for exact methods. The execution time for SSED is just 2.924 seconds.

GrammarViz is an approximate method and uses an inverted index to detect the events in a symbol sequence. Although the execution time of GrammarViz is faster than that of STOMP, it is still longer than that of SSED because GrammarViz obtains all the overlapping segmentations by using a sliding window in the discretization step to avoid losing segmentations. As a result, the dimensionality is almost unchanged after the discretization process. This outcome significantly increases the time consumption in symbolizing segmentations and detecting events. Moreover, GrammarViz requires extra time to eliminate the trivial match from the candidate sets. Therefore, we can conclude that the SSED can obtain higher efficiency than the approximate method and exact method.

6.3.3 Precision and recall

We use precision and recall to evaluate the performance of SSED. Precision is the fraction of identified events that are correct events. Assume that we have identified $m$ events, in which $n$ is the number of the events that are judged as correct. Recall is the fraction of all correct events that are successfully identified.

$\displaystyle\textit{precision}=n/m$ (10) $\displaystyle\textit{reacll}=n/\textit{number of all the correct events}$ (11) $\displaystyle\textit{F-measure}=2\times\textit{precision}\times\textit{recall}% /\textit{precision}+\textit{recall}$ (12)

The experiment is designed as follows. We create three events the trends of which are simple, medium and complex respectively, as shown in Fig. 12. Each event contains 100 instances. Three synthetic datasets in each of which there is a random walk time series with length 10000 are generated, denoted as dataset1, dataset2, and dataset3. The characteristics of synthetic datasets are shown in Table 8. The 100 event instances of Event $A$ , $B$ and $C$ are inserted into dataset1, dataset2 and dataset3 respectively. To better simulate a real working environment, a Gaussian noise with a mean of 0 and a standard deviation of 0.2 was added to each event instance.

Table 8

Characteristic of synthetic datasets

Dataset	Dataset length	Event type in the dataset	Number of event instances	Length of each event instances
dataset1	12800	Event $A$	100	28
dataset2	20000	Event $B$	100	100
dataset3	18500	Event $C$	100	85

Figure 12.

Three types of events used in synthetic experiments.

We compare the precision, recall and $F$ -measure with GrammarViz on the synthetic datasets as SSED and GrammarViz are approximate methods. The parameters used in SSED and GrammarViz, as shown in Table 9, all ensure the best results of SSED and GrammarViz. Results in Table 10 shows that, with GrammarViz, SSED has the better overall precision, recall and $F$ -measure. GrammarViz works better for simple events, but not for complex events. SSED can achieve stable and better performance.

Table 9

Parameter setting of GrammarViz and SSED on synthetic datasets

Dataset	Parameter of GrammarViz	Parameter of SSED
dataset1	$s=$ 15, $w=$ 3, $a=$ 5	$m=$ 10, $d=$ 3, $r=$ 5, $\delta=$ 0.75
dataset2	$s=$ 50, $w=$ 3, $a=$ 3	$m=$ 10, $d=$ 2, $r=$ 10, $\delta=$ 1
dataset3	$s=$ 30, $w=$ 3, $a=$ 3	$m=$ 10, $d=$ 5, $r=$ 5, $\delta=$ 1

Table 10

Comparison of precision and recall between GrammarViz and SSED on synthetic datasets

Dataset	GrammarViz			SSED
	Precision	Recall	$F$ -measure	Precision	Recall	$F$ -measure
dataset1	1.0	0.86	0.92	0.97	0.92	0.94
dataset2	0.89	0.47	0.61	0.91	0.80	0.85
dataset3	0.96	0.48	0.64	0.97	0.85	0.90

6.4 Time complexity of SSED

SSED calculates the edge amplitude of all points in the time series with length $n$ and divides the original time series into $m$ segments. To calculate the edge amplitude of all points, the time complexity is $O(n)$ . For BIRCH, to divide the segments into several clusters, the run time complexity is $O(m)$ . To detect events in the symbolic representation, the time complexity depends on the suffix trees. To build a suffix tree, the time complexity is $O(|E|)$ , where $|E|$ is the number of events. Thus, the overall time complexity of SSED is $O(n+m+|E|)$ .

7. Conclusion

In this paper, a novel method, SSED, is proposed to more efficiently detect the multigranularity events in a time series with unequal time intervals. In order to solve the noise problem caused by unequal interval time series, the five shape features extracted from the trend of a time series are used. Unlike the fixed-granularity detection methods, SSED can detect multigranularity events within a linear time complexity. Additionally, a novel symbolic representation based on the trend information is proposed that can detect events with a wider range of granularity with a linear time complexity. The SSED is of higher precision, efficiency and stronger anti-noise-interference ability.

In future work, considering that real-time data analysis instead of historical data is needed in some domains, we plan to extend the SSED as an incremental method to detect events from the data stream in real time.

Footnotes

Acknowledgments

The project is supported by the Fujian Province Science and Technology Plan, China (grant number 2019H0017); the Quanzhou City Science & Technology Plan, China (grant number 2018C110R). Thanks to Jiang Peizhou from the Xiamen GNSS Development & Application Co. Ltd.

References

Liu

Iftikhar

Huo

and Nielsen

P.S.

, Two approaches for synthesizing scalable residential energy consumption data, Future Generation Computer Systems (95) (2019), 586–600.

Yadav

Pradhan

A.K.

and Kamwa

, Real-time multiple event detection and classification in power system using signal energy transformations, IEEE Transactions on Industrial Informatics 15(3) (2018), 1521–1531.

Huang

C.F.

H.C.

Chen

P.C.

and Chang

B.R.

, Autonomous self-evolving forecasting models for price movement in high frequency trading: Evidence from Taiwan, Intelligent Data Analysis 24(5) (2020), 1175–1206.

Torbick

Chowdhury

Salas

and Qi

, Monitoring rice agriculture across myanmar using time series sentinel-1 assisted by landsat-8 and PALSAR-2, Remote Sensing 9(2) (2017), 119.

Mao

and Shang

, Multivariate singular spectrum analysis for traffic time series, Physica A: Statistical Mechanics and its Applications (526) (2019), 121063.

Gensler

and Sick

, Performing event detection in time series with SwiftEvent: An algorithm with supervised learning of detection criteria, Pattern Analysis and Applications 21(2) (2018), 543–562.

Andor

and Boh?k

, Identifying events in financial time series – A new approach with bipower variation, Finance Research Letters (22) (2017), 42–48.

Mehrmolaei

and Keyvanpour

M.R.

, An enhanced hybrid model for event prediction in healthcare time series, International Journal of Knowledge-Based and Intelligent Engineering Systems 23(3) (2019), 131–147.

Edali

Baydoğan

M.G.

and Yücel

, Classification of generic system dynamics model outputs via supervised time series pattern discovery, Turkish Journal of Electrical Engineering and Computer Sciences 27(2) (2019), 832–846.

10.

Galicia

Talavera-Llames

Troncoso

Koprinska

and Martínez-Álvarez

, Multi-step forecasting for big data time series based on ensemble learning, Knowledge-Based Systems (163) (2019), 830–841.

11.

Jeon

Hong

and Chang

, Pattern graph tracking-based stock price prediction using big data, Future Generation Computer Systems (80) (2018), 171–187.

12.

Funde

N.A.

Dhabu

M.M.

Paramasivam

and Deshpande

P.S.

, Motif-based association rule mining and clustering technique for determining energy usage patterns for smart meter data, Sustainable Cities and Society (46) (2019), 101415.

13.

Tong

Weng

Dong

and He

, Detecting a business anomaly based on QoS benchmarks of resource-service chains for collaborative tasks in the IoT, IEEE Access (7) (2019), 165509–165519.

14.

Wang

and Cao

, Anomaly detection in road networks using sliding-window tensor factorization, IEEE Transactions on Intelligent Transportation Systems 20(12) (2019), 4704–4713.

15.

Chen

and Shah

S.L.

, Detection of frequent alarm patterns in industrial alarm floods using itemset mining methods, IEEE Transactions on Industrial Electronics 65(9) (2018), 7290–7300.

16.

Afzalan

Jazizadeh

and Wang

, Self-configuring event detection in electricity monitoring for human-building interaction, Energy and Buildings (187) (2019), 95–109.

17.

Moser

and Schramm

, Multivariate dynamic time warping in automotive applications: A review, Intelligent Data Analysis 23(3) (2019), 535–553.

18.

Polato

Sperduti

Burattin

and de Leoni

, Time and activity sequence prediction of business process instances, Computing 100(9) (2018), 1005–1031.

19.

van Goethem

Staals

Löffler

Dykes

and Speckmann

, Multi-granular trend detection for time-series analysis, IEEE Transactions on Visualization and Computer Graphics 23(1) (2017), 661–670.

20.

Lin

Keogh

Lonardi

and Chiu

, A symbolic representation of time series, with implications for streaming algorithms, in: Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2003, pp. 2–11.

21.

X.M.T.

Tran

T.M.

and Nguyen

H.T.

, An improvement of SAX representation for time series by using complexity invariance, Intelligent Data Analysis 24(3) (2020), 625–641.

22.

Liu

Chen

Tan

Chen

and Zhou

, Efficient motif discovery for large-scale time series in healthcare, IEEE Transactions on Industrial Informatics 11(3) (2015), 583–590.

23.

Ruan

Hanson

P.C.

Dugan

H.A.

and Plale

, Mining lake time series using symbolic representation, Ecological Informatics (39) (2017), 10–22.

24.

Lin

Keogh

Lonardi

and Patel

, Finding motifs in time series, in: Proc of the 2nd Workshop on Temporal Data Mining, 2002, pp. 53–68.

25.

Zhu

Zhao

Chen

C.T.

and He

, Developing a pattern discovery method in time series data and its GPU acceleration, Big Data Mining and Analytics 1(4) (2018), 266–283.

26.

Truong

C.D.

and Anh

D.T.

, A novel clustering-based method for time series motif discovery under time warping measure, International Journal of Data Science and Analytics 4(2) (2017), 113–126.

27.

Gong

Fong

Wong

R.K.

Mohammed

Fiaidhi

and Vasilakos

A.V.

, Discovering sub-patterns from time series using a normalized cross-match algorithm, Journal of Supercomputing 72(10) (2016), 3850–3867.

28.

Linardi

Zhu

Palpanas

and Keogh

, Matrix profile goes MAD: Variable-length motif and discord discovery in data series, Data Mining and Knowledge Discovery (34) (2020), 1022–1071.

29.

Yang

and Alessandrini

, An ultra-fast way of searching weather analogs for renewable energy forecasting, Solar Energy (185) (2019), 255–261.

30.

Zhu

Zimmerman

Senobari

N.S.

Yeh

C.C.M.

Funning

Mueen

Brisk

and Keogh

, Matrix profile II: Exploiting a novel algorithm and GPUs to break the one hundred million barrier for time series motifs and joins, in: IEEE 16th International Conference on Data Mining, 2017, pp. 739–748.

31.

Zhu

Mueen

and Keogh

, Matrix profile IX: Admissible time series motif discovery with missing data, IEEE Transactions on Knowledge and Data Engineering (2019), 1–1.

32.

Al Aghbari

and Al-Hamadi

, Finding K Most Significant Motifs in Big Time Series Data, Procedia Computer Science (170) (2020), 595–601.

33.

Gao

and Lin

, HIME: Discovering variable-length motifs in large-scale time series, Knowledge and Information Systems 61(1) (2019), 513–542.

34.

Park

and Jung

J.Y.

, SAX-ARM: Deviant event pattern discovery from multivariate time series using symbolic aggregate approximation and association rule mining, Expert Systems with Applications (141) (2020), 112950.

35.

Chang

Sun

Chen

and Huang

, Developing an efficient pattern discovery method for CPU utilizations of computers, International Journal of Parallel Programming 45(4) (2017), 853–878.

36.

Yin

Yang

Zhu

and Zhang

, Symbolic representation based on trend features for knowledge discovery in long time series, Frontiers of Information Technology and Electronic Engineering 16(9) (2015), 744–758.

37.

Karevan

and Suykens

J.A.K.

, Transductive LSTM for time-series prediction: An application to weather forecasting, Neural Networks 125 (2020), 1–9.

38.

Barkat

Ali

Hayat

Crowley

Q.G.

Rehman

Siddique

Haidar

and Iqbal

, Time series analysis of soil radon in Northern Pakistan: Implications for earthquake forecasting, Applied Geochemistry 97 (2018), 197–208.

39.

Jiao

Niu

Zhang

M.J.

, Prediction of machining dimension in laser heating and ultrasonic vibration composite assisted cutting of tungsten carbide, Journal of Advanced Manufacturing Systems 17(1) (2018), 35–45.

40.

Chan

K.C.C.

Liang

, and Luo

, Composition of resource-service chain for cloud manufacturing, IEEE Transactions on Industrial Informatics 12(1) (2016), 211–219.

41.

Liang

and He

, Optimizing the composition of a resource service chain with inter-organizational collaboration, IEEE Transactions on Industrial Informatics 13(3) (2017), 1152–1161.

42.

and Tong

, A novel clustering algorithm for time-series data based on precise correlation coefficient matching in the IoT, Mathematical Biosciences and Engineering 16(6) (2019), 6654–6671.

43.

Qian

Liu

Zimmermann

and Wang

, Towards automated reentrancy detection for smart contracts based on sequential models, IEEE Access 8 (2020), 19685–19695.

44.

Zhang

Hou

Zeng

and Zhao

, Hardware acceleration implementation of sparse coding algorithm with spintronic devices, IEEE Transactions on Nanotechnology 18 (2019), 518–531.

45.

Gao

Wei

Wang

Fan

, Exploring the Spatial-Temporal Characteristics of Traditional Public Bicycle Use in Yancheng, China: A Perspective of Time Series Cluster of Stations, Sustainability 12 (2020), 6370.

46.

Dau

H.A.

Bagnall

Kamgar

Yeh

C.C.M.

Zhu

Gharghabi

Ratanamahatana

C.A.

and Keogh

, The UCR time series archive, IEEE/CAA Journal of Automatica Sinica 6(6) (2019), 1293–1305.

47.

Senin

Lin

Wang

Oates

Gandhi

Boedihardjo

A.P.

Chen

and Frankenstein

, GrammarViz 3.0: Interactive Discovery of Variable-LengthTime Series Patterns, Transactions on Knowledge Discovery from Data 12(1) (2018), 1–28.

Detecting a multigranularity event in an unequal interval time series based on self-adaptive segmenting

Abstract

Keywords

1. Introduction

Table 1 Research topics on different domains

4.1 Self-adaptive segmenting based on edge points

6.1 Experiment on public transport data

Table 3 Data format of the speed time series

Step 1) Divide the time series into unfixed-granularity segmentations by a self-adaptive segmenting algorithm.

Step 2) Clustering the segmentations using BIRCH and symbolizing each cluster.

Step 3) Detecting the multigranularity events in the symbol sequence of the time series.

Table 5 Characteristics of the selected datasets and recommended parameters of SSED

Table 6 Parameter settings of GrammarViz and STOMP

6.3.3 Precision and recall

7. Conclusion

Footnotes

Acknowledgments

References

Table 1
Research topics on different domains

Table 3
Data format of the speed time series

Table 5
Characteristics of the selected datasets and recommended parameters of SSED

Table 6
Parameter settings of GrammarViz and STOMP