Early Prediction on Time Series: A Nearest Neighbor Approach

1 Introduction

Early classification of time series data is critical in some timesensitive applications such as health-informatics. For example, a retrospective study of the clinical data of infants admitted to a neonatal intensive care unit [Griffin and Moorman, 2001] found that the infants, who were diagnosed with sepsis disease, had abnormal heart beating time series patterns 24 hours preceding the diagnosis. Monitoring the heart beating time series data and classifying the time series data as early as possible may lead to earlier diagnosis and effective therapy.

However, early classification of time series data is very challenging. An early classifier is expected to meet two requirements. First, an early classifier should be able to affirm the earliest time of reliable classification so that the early predictions can be used for further actions. Second, an early classifier should retain an accuracy comparable to that of a classifier using the full length time series or some user-specified accuracy threshold.

In this paper, we tackle the problem of early classification on time series data. We introduce a novel concept of MPL (Minimum Prediction Length) and develop ECTS ( Early Classification on Time Series), an effective 1-nearest neighbor classification method which makes prediction early and at the same time retains an accuracy comparable to that of a

∗The research is supported in part by an NSERC Discovery grant, an NSERC Discovery Accelerator grant, and a Simon Fraser University Trust Endowment Fund.

Philip S. Yu

Department of Computer Science University of Illinois at Chicago psyu@cs.uic.edu

1NN classifier using the full-length time series. Our empirical study using benchmark time series data sets shows that ECTS works well where 1NN classification is effective.

2 ProblemDefinition and RelatedWork

A time series s is a sequence of pairs (timestamp, value). The data values are ordered in timestamp ascending order. We assume that all timestamps take positive integer values. We denote by s[i] the value of time series s at timestamp i.

To keep our discussion simple, in this paper, we assume that all time series in question are of length L, i.e., each time series s has a value s[i] at timestamp 1 ≤ i ≤ L. L is called the full length of the time series. In general, we can use techniques like dynamic time warping [Myers and Rabiner, 1981] to align time series of different lengths.

For a time series s of length L, s[i, j ] = s[i]s[i + 1] · · · s[j ] (1 ≤ i < j ≤ L) is the subsequence at timestamp interval [i, j ]. Subsequence s[1, l] (l ≤ L) is the length-l prefix of s.

For two time series s and s′ , dist(s, s′ ) denotes the distance between them. In this paper, we use the Euclidean distance dist(s, s′ ) = √∑Li=1 (s[i] - s′ [i])2 , which is a simple yet effective and popularly adopted choice.

The set of all possible time series of length L is RL and is called the full-length space, where R is the set of real numbers. The prefix space of length-l, denoted by Rl , is the set of length-l prefixes of all possible time series.

In time series classification, a training set T contains a set of time series and a set of class labels C such that each time series t ∈ T carries a class label t.c ∈ C. The time series classification problem is to learn from T a classifier C : RL → C such that for any time series s, C predicts the class label of s by C(s). The performance of a classifier is often evaluated using a test set T ′ , which is a set of time series such that each time series t′ ∈ T ′ also carries a class label t′ .c ∈ C. The accuracy of a classifier C is the percentage that the class labels generated by C match those carried by the time series in the test set, that is, Accuracy(C, T ′ ) = |{C(t′ )=t′ .c|t′∈T ′ }| |T ′ | . Often, we want the classifier C as accurate as possible.

For a time series s, an early classifier C can identify an integer l0 and make classification based on s[1, l0]. An early classifier is serial [Xing et al., 2008] if C(s[1, l0]) = C(s[1, l0 + i]) for any i > 0. In other words, C can classify s based on only the prefix s[1, l0], and the classification remains the same by using any longer prefixes. An early classifier is preferred to be serial so that the early classification is reliable and consistent. The minimum length l0 of the prefix based on which C makes the prediction is called the cost of the prediction, denoted by Cost(C, s) = l0. Trivially, for any finite time series s, Cost(C, s) ≤ |s|. The cost of the prediction is Cost(C, T ′ ) = 1 |T ′ | ∑t′∈T ′ Cost(C, t′ ).

Among many methods that can be used in time series classification, the 1-nearest neighbor (1NN) classifier has been found often accurate in practice [Keogh and Kasetty, 2002; Wei and Keogh, 2006]. The 1NN classification method is parameter-free and does not require feature selection and discretization. Theoretically, Cover and Hart [1967] showed that the error rate of the 1NN classifier is at most twice that of the optimal Bayes probability when an infinite sample set is used.

Due to the effectiveness and the simplicity of the 1NN classifier on time series data, in this paper, we focus on extending the 1NN classifier for early classification on time series data. We use the 1NN classifier on full length time series as the baseline for comparison. Ideally, we want to build a classifier which is as accurate as the baseline method and minimizes the expected prediction cost.

In our previous work [Xing et al., 2008], we formulated the early classification problem on symbolic sequence data. The major idea is to mine symbolic sequential patterns which have high utility in early prediction, and then form classification rules or decision trees using those patterns. Time series are numeric. To use our symbolic methods, time series have to be discretized properly. However, appropriate discretization often heavily relies on good background knowledge. Moreover, affected by the discretization granularity, the discretizationbased methods may lose important information in time series data. Our previous study [Xing et al., 2008] shows that the symbolic methods do not work well on numeric time series data. Thus, early prediction on time series data, a type of data prevalent in time-sensitive applications, remains open at large.

To the best our knowledge, [Rodriguez and Alonso, 2002] is the only existing study mentioning early classification on time series data, which refers to classification when only a partial time series is available. It focuses on how to make prediction on partial information but does not attempt to make reliable prediction using minimal partial information.

Generally, most existing sequence classification methods transform a sequence into a set of features and then apply conventional classification methods on the features. For example, Lesh et al. [1999] proposed a criterion for selecting features for sequence classification. Nanopoulos et al. [2001] extracted statistical features such as mean and deviation from time series, and built a neural network on the features to classify time series. Eads et al. [2005] employed grammar-guided feature extraction and proposed a SVM classifier.

Different from feature-based classifiers, instance based classifiers [Keogh and Kasetty, 2002; Wei and Keogh, 2006; Xi et al., 2006], such as the 1NN classifier, make predictions based on the similarities between the time series to be classified and the ones in the training set. The choice of distance metric is critical to the performance of 1NN classifiers. The Euclidean distance is shown [Keogh and Kasetty, 2002;

Wei and Keogh, 2006] superior on accuracy comparing to other similarity measurements. Xi et al. [2006] showed that, on small data sets, elastic measures such as dynamic time warping (DTW) can be more accurate than the Euclidean distance. However, on large data sets, the accuracy of elastic measures converges with the Euclidean distance. In this paper, we focus on extending the 1NN classifier with the Euclidean distance to achieve early classification. However, our principle can be applied to other instance-based methods using different distance metrics.

3 1NN Early Classification

Example 1. Consider a training set of time series T in Table 1, where each time series, written as a sequence of values in timestamp ascending order, has a length L = 3.

To classify a time series s1 = (1, 2, 1), the 1NN classifier using the full length time series finds t1 as the 1NN of s1 in space R3 , and outputs c1, the class label of t1.

The prediction on s1 can be made much earlier, since t1 is also the 1NN of prefixes s1[1] = (1) and s1[1, 2] = (1, 2). In other words, using the 1NN of the prefixes, we may make early prediction.

For a time series s and a training data set T , let NN l (s) = argmint∈T{dist(s[1, l], t[1, l])} be the set of the nearest neighbors of s in T in prefix space Rl . In Example 1, NN 1 (s1) = {t1} and NN 2 (s1) = {t1}.

In the full length space RL, using the 1NN classifier, a time series s is classified by the dominating label in NN L(s). Consider prefix space RL-1 . Let T [1, L - 1] = {t[1, L - 1]|t ∈ T} be the set of length-(L - 1) prefixes of all time series in the training set T . If the time series in NN L(s) are still the nearest neighbors of s[1, L - 1] in T [1, L - 1], i.e., NN L(s) = NN L-1(s), then we can use NN L-1(s) to make prediction on the class label of s at timestamp (L1) without compromise in accuracy. This immediately leads to early prediction, as observed in Example 1. The question is when the data points of s arriving in time ascending order, how we can know starting from which prefix length l, the nearest neighbors of s will remain the same.

Generally, the set of length-l prefixes (1 ≤ l ≤ L) of the time series in T is T [1, l] = {t[1, l]|t ∈ T}. For t ∈ T , the set of reverse nearest neighbors in prefix space Rl of t(1, l) is RNN l (t) = {t′ ∈ T | t ∈ NN l (t′ )}. That is, RNN l (t) is the set of time series in T that treat t as its nearest neighbor. In Example 1, since RNN 1(t1) = RNN 2 (t1) = RNN 3(t1) = {t2}, RNN 1(t2) = RNN 2(t2) = RNN 3(t2) = {t1}.

Suppose training set T is a sufficiently large and uniform sample of the time series to be classified. For a time series t ∈ T , if there exists a timestamp l < L such that RNN l (t) = RNN l+1 (t) = · · · = RNN L(t), then we can use t to make prediction early at timestamp l without loss in expected accuracy, since every time series s which uses t in RL to predict the class label also likely has t as the 1NN in prefix spaces Rl , Rl+1 , . . . , RL-1 . In Example 1, t1 can be used to make prediction at timestamp 1 since RNN 1(t1) = RNN 2(t1) = RNN 3(t1).

Definition 1 (Minimum prediction length). In a training data set T with full length L, for a time series t ∈ T , the minimum prediction length (MPL for short) of t, MPL(t) = k if for any l (k ≤ l ≤ L), (1) RNN l (t) = RNN L(t) ̸= ∅ and (2) RNN k-1 (t) ̸= RNN L(t). Specifically, if RNN L(t) = ∅, MPL(t) = L. We denote by MPP (t) = t[1, MP L(t)] the minimum prediction prefix of t.

Example 2. In Example 1, MPL(t1) = 1 andMPP (t1) = (1). Moreover, MPL(t2) = 1, MPL(t3) = MPL(t4) = 2. MPL(t5) = MPL(t6) = MPL(t7) = 3.

Given a training set T , a simple 1NN early classification method works as follows. We assume that the training set is a sufficiently large and uniform sample of the data to be classified. In the training phase, for each time series t ∈ T , we calculate the minimum prediction length MPL(t). In the classification phase, for a time series s to be classified, the values of s arrive in timestamp ascending order. At timestamp i, we return the dominating class label of time series in NN i (s) that have a MPL at most i. If no such a time series is found, we cannot make reliable prediction at the current timestamp, and have to wait for more values of s.

Example 3. In Example 1, it is easy to verify that s1 = (1, 2, 1) is classified as c1 using t1 at timestamp 1. Consider s2 = (6, 2, 3). NN 1(s2) = {t4, t7}, but the MPLs of t4 and t7 are greater than 1. Thus, s2 cannot be classified at timestamp 1. NN 2(s2) = {t3, t4}. The MPLs of t3 and t4 are 2. Thus, s2 can be assigned label c1 at timestamp 2.

The 1NN early classification method has two drawbacks. First, to make early prediction using a time series t in a training set T , the RNNs of t must be stable after timestamp MPL(t). This requirement is often too restrictive and limits the capability of finding shorter prediction length. In Example 1, the RNNs of t5, t6, t7 are not stable, and the MPLs of them are all 3. We cannot use those time series to classify s3 = (5, 8, 8) at timestamp 2.

Second, the 1NN early classification method may overfit a training set. The MPP of a time series is obtained by only considering the stability of its RNNs which often consist of a small number of time series. The learned MPL(t) may not be long and robust enough to make accurate classification if the training set is not big enough or is not a uniform sample of the time series to be classified.

4 The ECTS Method

To overcome the drawbacks in the 1NN early classification method, we develop the ECTS method which extends the 1NN early classification method by finding the MPL for a cluster of similar time series instead of a single time series.

Example 4. We cluster the time series in the training set T in Table 1 in the full space R3 and the prefix spaces R2 and R1 , as shown in Table 2.

Cluster S1 is stable in all three spaces, and thus can be used at early classification as early as timestamp 1. Clusters S2 and S3 are stable at timestamps 2 and 3 and thus can be used as early as at timestamp 2.

We need to address two issues. First, we need to use a clustering approach to obtain the clusters in the full-length space. Second, we need to compute the MPLs of clusters.

We adopt single link MLHC [Ding and He, 2005], an agglomerative hierarchical clustering method to cluster the training data set in full length space. It builds a hierarchical clustering tree level by level by merging all mutual nearest neighbor pairs of clusters at each level. Two clusters form a mutual nearest neighbor pair if they consider each other as the nearest neighbor. The distance between two clusters is measured by the minimum among all inter-cluster pair-wise distances. In the output hierarchical clustering tree (i.e., a dendrogram), a cluster represented by a leaf node is called a leaf-cluster, and a cluster represented by an internal node is called a sub-cluster. The whole training set is represented by the root, and thus is called the root-cluster.

A cluster S is called 1NN consistent [Ding and He, 2004] if for each object (a time series in our case) o ∈ S, the 1NN of o also belongs to S. Immediately, we have the following.

Lemma 1. The sub-clusters and the root-cluster generated by single link MLHC are 1NN consistent.

If all time series in a sub-cluster S carry the same label, S is called a discriminative cluster. We denote by S.c the common class label of the time series in S. A discriminative cluster can be used in classification.

Example 5. S1, S2 and S3 in space R3 in Table 2 are discriminative clusters and can be used in classification. For example, s3 = (5, 8, 8) finds t5 ∈ S3 as the 1NN in R3 . S3.c = c2 can be assigned to s3.

To explore the potential of a discriminative cluster S in early classification, we find the earliest prefix space in which S is formed and becomes stable since then. The corresponding prefix length is the minimum prediction length of S. In a prefix space, we check if the 1NN consistency property holds for S and the stability of the reverse neighbors of S.

For a sub-cluster S, in space Rl (1 ≤ l ≤ L), we define the reverse nearest neighbors of S as RNN l (S ) = ∪s∈SRNN l(s)\S. If S is well separated from other clusters, RNN l (S ) is empty. Often, some sub-clusters in a training set may not be well separated from others. In such a case, RNN l (S ) is the boundary area of S.

Definition 2 (MPLs of clusters). In a training data set T with full length L, for a discriminative cluster S, MPL(S ) =

k if for any l ≥ k, (1) RNN l (S ) = RNN L(S ); (2) S is 1NN consistent in space Rl ; and (3) for l = k - 1, (1) and (2) cannot be both satisfied.

Example 6. For discriminative clusters S1, S2 and S3, MPL(S1) = 1, MPL(S2) = 2 and MPL(S3) = 2. Take S3 as an example, in space R3 and R2 , S3 is 1NN consistent and RNN 3 (S3) = RNN 2(S3) = ∅. In space R1 , S3 is not 1NN consistent. Thus, MPL(S3) = 2.

In a discriminative cluster S, there may be another discriminative cluster S ′ ⊂ S. MPL(S ) may be longer or shorter than MPL(S ′). Moreover, for a time series t ∈ T , t itself is a leaf-cluster with MPL(t) (Definition 1). Among all the discriminative or leaf clusters containing t, we can use the shortest MPL to achieve the earliest prediction using t.

As one drawback of the 1NN early classification method, the MPL obtained from a very small cluster may cause overfitting. To avoid over-fitting, a user can specify a parameter minimum support to control the size of a cluster. We calculate the support of a cluster in a way that is aware of the population of the corresponding class.

Definition 3 (Support). In a training set T , let Tc = {s ∈ T |s.c = c} be the set of time series that have label c. For a discriminative cluster or a leaf cluster S such that S.c = c, Support(S ) = |S|

We only use clusters passing the user-specified minimum support threshold for early prediction. The ECTS method works in two phases. In the training phase, given a training set T with full-length L and a minimum support threshold p0, for a time series t ∈ T , let SS = {S|t ∈ S ∧ S is a discriminative or leaf cluster} be the set of discriminative or leaf clusters containing t. MPL(t) = minS∈SS,Support(S)≥p0 MP L(S ). The training process is to compute MPL(t) for all t ∈ T . The classification phase is the same as the 1NN early prediction method in Section 3.

Section 2 states that we want to build a classifier as accurate as the 1NN classifier using the full-length time series. The following result answers the requirement.

Theorem 1. In a training data set T of full length L, assuming for any t ∈ T and 1 ≤ l ≤ L, NN l (t) contains only one time series 1 , ECTS has the same leave-one-out accuracy on T as the 1NN classifier using the full-length time series. Moreover, ECTS is a serial classifier on the time series in T .

Proof sketch. Using Lemma 1, we can show that in any leaveone-out test, if ECTS assigns label c to a time series t ∈ T using prefix t(1, l), the 1NN classifier assigns to t the same class label using any longer prefix t(1, k), where l < k ≤ L. Limited by space, we omit the details here.

The only remaining question is how to compute the subclusters and the MPLs. Given a training set T , we first precompute the nearest neighbors for each time series in T in all prefix spaces. This pre-computation step takes time O(|T |2 · L) where L is the full length.

1 If multiple 1NNs exist, we can select the 1NN of the smallest index .

Input: a training data set T;

Output: MPL(t) for each t ∈ T ;

Method:

• 1: pre-compute 1NNs for each t ∈ T in all prefix spaces;
• 2: compute the MPLs of leaf clusters and update the MPL for each t ∈ T ;
• 3: n = |T |, the number of time series in T ;
• 4: while n > 1
• 5: compute the mutual nearest neighbor pairs;
• 6: for each mutual nearest neighbor pair (S1, S2)

7:

merge S1 and S2 into a parent cluster S, n

8:

=

if all time series in S carry the same label then

9:

compute the MPL of S;

• 10: update the MPL for each time series in S; end if end for
• 11: if no new discriminative clusters are generated in this round then break;

end while

Figure 1: The algorithm of the training phase in ECTS.

Then, we apply single link MLHC [Ding and He, 2005] to space RL, which takes time O(|T |2 ). For each discriminative sub-cluster S, using the pre-computed 1NN information in the prefix spaces, we check the 1NN consistency of S and the stability of RNN l (S ) for l < L in the value l descending order, until MPL(S ) is determined. The complexity of this step is O(|T|3 · L). The algorithm of the training phase is shown in Figure 1.

Is learning different MPLs for different time series necessary? Can we just learn a fixed MPL for all time series in a training set? Let us consider the following simple early classification method called 1NN fixed. Given a training set T of full length L, we calculate the 1NN classification accuracy p in the full space RL. Then, we check the prefix spaces RL-1 ,RL-2 , . . . until prefix space Rk such that the accuracies in spaces RL-1 , . . . ,Rk+1 are at least p, and the accuracy in space Rk is lower than p. We use (k +1) as theMPL for all time series. That is, in classification, we always read the length-(k + 1) prefix of a time series s to be classified, and find the 1NNs of s among the length-(k + 1) prefixes of the time series in T to classify s.

Interestingly, 1NN fixed is a simplified special case of ECTS in 2-class situations under the assumption that each class forms one discriminative cluster in the full length space RL. However, since 1NN fixed does not consider the different early classification capabilities of the clusters in the hierarchy, it may use longer prefixes for classifications. Furthermore, when there are multiple classes or multiple large discriminative clusters, the 1NN fixed method may not work well since it requires the overall accuracy to be high and cannot identify clusters which are separated from other clusters earlier than the overall accuracy is satisfied.

5 Experimental Results

The UCR time series archive [Keogh et al., 2006] provides 23 time series data sets which are widely used to evaluate time

n -

1;

series clustering and classification algorithms. In each data set, the time series have a fixed length. Each data set contains a training set and a testing set. The 1NN classification accuracies using the Euclidean distance on the testing sets are provided as well [Keogh et al., 2006].

Table 3 lists the results on all the 7 data sets in the archive where the full-length 1NN classifier using Euclidean distance achieves an accuracy of at least 85%. The 1NN classifier can be regarded effective on those data sets. The seven data sets cover cases of 2-class and more-than-two-class cases.

Table 3 compares 5 methods. We use the 1NN classifier using the full length (denoted by full 1NN) as the baseline. In addition to ETCS, we also report the results of the 1NN early classification method (Section 3, denoted by 1NN Early), the 1NN fixed method introduced at the end of Section 4, and the SCR method [Xing et al., 2008]. ECTS uses only an optional parameter, minimum support, to avoid overfitting. The results of ECTS in Table 3 are obtained by setting minimum support= 0. All the experiments were conducted using a PC computer with an AMD 2.2GHz CPU and 1GB main memory. The algorithms were implemented in C++ using Microsoft Visual Studio 2005.

On data sets Wafer and Gun-point, the average prediction lengths (Cost(C, T ′ ) defined in Section 2) of ECTS are shorter than half of the full lengths. On the other five data sets, the average prediction lengths of ECTS are from 71% to 89% of the full lengths.

Except for data sets Gun-point and Two-patterns, ECTS

has an accuracy almost the same or even slightly better than that obtained by the full-length 1NN method. On Gun-point and Two-patterns, ECTS is about 5% lower in accuracy. As explained before, when minimal support= 0, ECTS may over fit a training set and thus may slightly lose accuracy.

By increasing minimum support, overfitting can be reduced. Figure 2 shows the effect on the Gun-point data set. When minimum support increases, the accuracy of ECTS approaches the accuracy of the full length 1NN classifier quickly. As the tradeoff, the average prediction length increases, too. Similar results are observed on the Two-patterns data set. Limited by space, we omit the details here.

The above results clearly show that ECTS can achieve early classification and can retain an accuracy comparable to that of the full length 1NN classifier. Using parameter minimum support, ECTS can reduce overfitting effectively.

On all the 7 data sets, ECTS and the early 1NN method achieve very similar accuracies. ECTS always achieves a shorter average prediction length. This result confirms that finding MPLs through clusters helps to obtain shorter MPLs.

On data sets Wafer, ECG and Synthetic-control, ECTS using minimum support= 0 achieves a shorter average prediction length than the 1NN fixed method. The two methods have similar accuracies. Especially, for the 6 classes synthetic control data set, the 1NN fixed method has to use the full length. ECTS uses a shorter prediction length. The saving mainly comes from the class cyclic, which is classified using an average length of 45. To handle multi-class situations, the 1NN fixed method cannot classify one class earlier if the other classes are mixed together in the prefix spaces.

On data set Gun-point, by setting minimum support= 15% to reduce overfitting, ECTS obtains an accuracy comparable to the 1NN fixed method, but uses a remarkably shorter average prediction length. Similar results are observed on data set Two-patterns.

On data sets OliveOil and CBF, interestingly, the 1NN fixed method is less accurate than ECTS but can obtain shorter average prediction length. For example, on data set OliveOil, ECTS obtains an accuracy of 90% and 1NN fixed method makes only 83.33%. The 1NN fixed method obtains an average prediction length of 406 and ECTS gives a length of 497.63. By analyzing the training set of 30 time series, we find that, training samples 7 and 9 are the cause of the dropping accuracy in the 1NN fixed method, which means the MPLs (406) of those two samples learned by the 1NN fixed method are not long enough to make accurate classification. In ECTS, the learned MPLs vary from 117 to 570 for the training samples. For samples 7 and 9, the learned MPLs are 567 and 570, respectively. Why does ECTS learn longer MPLs for samples 7 and 9? In the full length space, training sample 9 has an empty RNN set. The RNN set of training sample 7 consists of samples from two classes. Those RNN sets suggest that samples 7 and 9 are likely on the decision boundary. In contrast to the 1NN fixed method, ECTS can find longer MPLs for samples likely on the decision boundary to reduce the possible misclassification led by such a sample.

We also compare ECTS with our previous symbolic method SCR [Xing et al., 2008]. Since SCR can only handle discrete values, k-means (k = 3) is used to discretize values in the time series into 3 values. SCR requires a parameter, expected classification accuracy, which is set to the full length 1NN accuracy. The other parameter of SCR, minimal support, is set to 0. Although SCR sometimes uses a shorter average prediction length, the accuracies are far away from the expected values. Comparing to SCR, ECTS makes early classification reliable in accuracy.

In terms of efficiency, ECTS is faster than SCR in training. The early 1NN method, the 1NN fixed method and the full 1NN method are substantially faster than ECTS and SCR in training due to their very simple model construction tasks. All the methods have very fast classification runtime.

6 Conclusions

In this paper, we develop ECTS, a method for early classification on time series data. ECTS makes early classification and retains an accuracy comparable to that of the full length 1NN method. As future work, it is interesting to extend ECTS for streaming data.