Unsupervised Feature Learning from Time Series

1 Introduction

Time series classification has wide applications in finance [Ruiz et al., 2012], medicine [Hirano and Tsumoto, 2006] and trajectory analysis [Cai and Ng, 2004]. The main challenge of time series classification is to find discriminative features that can best predict class labels. To solve the challenge, a line of works have been proposed to extract discriminative features, which are often referred to as shapelets, from time series. Shapelets are maximally discriminative features of time series which enjoy the merit of high prediction accuracy and are easy to explain [Ye and Keogh, 2009]. Therefore, discovering shapelets has become an important branch in time series analysis.

The seminal work on shapelet discovery [Ye and Keogh, 2009] resorts to a full-scan of all possible time series segments where the segments are ranked according to a predefined distance metric and the segments which best predict the class labels are selected as shapelets. Based on the seminal work, a line of speed-up algorithms [Mueen et al., 2011] [Rakthanmanon and Keogh, 2013] [Chang et al., 2012] have been proposed to improve the performance. All these methods can be categorized as the search-based algorithms which scan a pool of candidate segments. For example, with the Synthetic Control dataset [Chen et al., 2015] which contains 600 time series examples of length 60, the number of candidates for all lengths is 1▷098⇥106 .

On the other hand, a recent work [Grabocka et al., 2014] proposes a new time series shapelet learning approach. Instead of searching for shapelets from a candidate pool, they use regression learning and aim to learn shapelets from time series. This way, shapelets are detached from candidate segments and the learnt shapelets may differ from all the candidate segments. More importantly, shapelet learning is fast to compute, scalable to large datasets, and robust to noise as shown in Fig. 1.

We present a new Unsupervised Shapelet Learning Model (USLM for short) that can auto-learn shapelets from unlabeled time series data. We first introduce pseudo-class label to transform unsupervised learning to supervised learning. Then, we use the popular regularized least-squares and spectral analysis approaches to learn both shapelets and classification boundaries. A new regularization term is also added to avoid similar shapelets being selected. A coordinate descent algorithm is used to iteratively solve the pseudo-class label, classification boundary and shapelets.

Compared to the search-based algorithms on unlabeled time series data [Zakaria et al., 2012], our method provides a new tool that learns shapelets from unlabeled time series data. The contributions of the work are summarized as follows:

• ÷ We present a new Unsupervised Shapelet Learning Model (USLM) to learn shapelets from unlabeled time series data. USLM combines pseudo-class label, spectral analysis, shapelets regularization and regularized least-squares for learning.
• ÷ We empirically validate the performance of USLM on both synthetic and real-world data. The results show promising results compared to the state-of-the-art unsupervised shapelets selection models.

The remainder of the paper is organized as follows: Section 2 surveys related work. Section 3 gives the preliminaries. Section 4 introduces the proposed unsupervised shapelet learning model USLM. Section 5 introduces the learning algorithm with analysis. Section 6 conducts experiments. We conclude the paper in Section 7.

2 RelatedWork

Shapelets [Ye and Keogh, 2009] are time series short segments that can best predict class labels. The basic idea of shapelets discovery is to consider all segments of training data and assess them regarding a scoring function to estimate how predictive they are with respect to the given class labels [Wistuba et al., 2015]. The seminal work [Ye and Keogh, 2009] builds a decision tree classifier by recursively searching for informative shapelets measured by information gain. Based on information gain, several new measures such as F-Stat, Kruskall-Wallis and Mood's median are used in shapelets selection [Hills et al., 2014] [Lines et al., 2012].

Since time series data usually have a large number of candidate segments, the runtime of brute-force shapelets selection is infeasible. Therefore, a series of speed-up techniques have been proposed. On the one hand, there are smart implementations using early abandon of distance computations and entropy pruning of the information gain heuristic [Ye and Keogh, 2009]. On the other hand, many speed-ups rely on the reuse of computations and pruning of the search space [Mueen et al., 2011], as well as pruning candidates by searching possibly interesting candidates on the SAX representation [Rakthanmanon and Keogh, 2013] or using infrequent shapelets [He et al., 2012]. Shapelets have been applied in a series of real-world applications.

Shapelet learning. Instead of searching for shapelets exhaustively, a recent work [Grabocka et al., 2014] proposes to learn optimal shapelets and reports statistically significant improvements in accuracy compared to other shapelet-based classifiers. Instead of restricting the pool of possible candidates to those found in the training data and simply searching them, they consider shapelets to be features that can be learnt through regression learning. This type of learning method does not consider a limited set of candidates but can obtain arbitrary shapelets.

Unsupervised feature selection. Many unsupervised feature selection algorithms have been proposed to select informative features from unlabeled data. A commonly used criterion in unsupervised feature learning is to select features best preserving data similarity or manifold structure constructed from the whole feature space[Zhao and Liu, 2007] [Cai et al., 2010], but they fail to incorporate discriminative information implied within data, which cannot be directly applied in our shapelet learning problem. Earlier unsupervised feature selection algorithms evaluate the importance of each feature individually and select features one by one [He et al., 2005] [Zhao and Liu, 2007], with a limitation that correlation among features is neglected [Cai et al., 2010]˜citezhao2010efficient [Zhang et al., 2015].

State-of-the-art unsupervised feature selection algorithms perform feature selection by simultaneously exploiting discriminative information and feature correlation. Unsupervised Discriminative Feature Selection (UDFS) [Yang et al., 2011] aims to select the most discriminative features for data representation, where manifold structure is also considered. Since the most discriminative information for feature selection is usually encoded in labels, it is very important to predict a good cluster indicators as pseudo labels for unsupervised feature selection.

Shapelets for clustering. Shapelets also have been utilized to cluster time series [Zakaria et al., 2012]. Zakaria et al. [Zakaria et al., 2012] have proposed a method to use unsupervised-shapelets (u-Shapelets) for time series clustering. The algorithm searches for u-Shapelets which can separate and remove a subset of time series from the rest of the dataset, then it iteratively repeats the search among the remaining data until no data remains to be separated. It is a greedy search algorithm which attempts to maximize the gap between the two groups of time series divided by a u-shapelet.

The k-shape algorithm is proposed in the work [Paparrizos and Gravano, 2015] to cluster time series. k-shape is a novel algorithm for shape-based time series clustering that is efficient and domain independent. k-shape is based on a scalable iterative refinement procedure which creates homogeneous and well-separated clusters. Specifically, k-Shape requires a distance measure that is invariant to scaling and shifting. It uses a normalized version of the cross-correlation measure as distance measure to consider the shapes of time series. Based on the normalized cross-correlation, the method computes cluster centroids in every iteration to update the assignment of time series to clusters.

Our work differs from the above research problems. We introduce a new approach for unsupervised shapelet learning to auto-learn shapelets from unlabeled time series by combining shapelet learning and unsupervised feature selection methods.

3 Preliminaries

In this paper, scalars are denoted by letters (a↪ b↪ ▷▷▷; ↵↪ β↪ ▷▷▷), vectors by lower-case bold letters (a↪ b↪ ▷▷▷)↪ and matrices by boldfaced upper-case letters (A↪ B↪ ▷▷▷)▷ We use a(k) to denote the k-th element of vector a, and A(ij) to denote the element locating at the ith-row and j-th column. A(i↪:) and A(:↪j) denote vectors of the i-th row and j-th column of the matrix respectively. In a time series example, ta↪b denotes a segment starting from a to b.

Consider a set of time series examples T = ¶t1↪ t2↪ ▷ ▷ ▷ ↪ tn♦. Each example ti (1  i  n) contains an ordered set of real values denoted as (ti(1)↪ ti(2)↪ ▷ ▷ ▷ ↪ ti(qi)), where qi is the length of ti. We wish to learn a set of top-k most discriminative shapelets S = ¶s1↪ s2↪ ▷ ▷ ▷ ↪ sk♦. Similar to the shapelet learning model [Grabocka et al., 2014], we set the length of shapelets to expand r different length scales starting at a minimum lmin, i.e. ¶lmin↪ 2 ⇥ lmin↪ ▷ ▷ ▷ ↪ r ⇥ lmin♦. Each length scale i ⇥ lmin contains ki shapelets and k = Pri=1 ki. Obviously, S 2 Sri=1 Rki⇥(i⇥lmin) and r ⇥ lmin ⌧ qi to keep the shapelets compact.

4 Unsupervised shapelet learning

In this section, we aim to formulate the Unsupervised Shapelet Learning Model (USLM) which is shown in Eq. (7). It combines with spectral regularization term, shapelet similarity regularization term and the regularized least square minimization term.

To introduce the USLM specifically, we introduce shapelet-transformed representation [Grabocka et al., 2014] of time series first, which transfer time series from original space to a shapelet-based space. Then we introduce the pseudo-class label and the three terms of the unsupervised shapelet learning model respectively.

Shapelet-transformed Representation Shapelet transformation was introduced by the work[Lines et al., 2012] to downsize a long time series into a short feature vector in the shapelets feature space. Time series are ordered sequences and shapelet-transformation can preserve the shape information for classification.

Given a set of time series examples T = ¶t1↪ t2↪ ▷ ▷ ▷ ↪ tn♦ and a set of shapelets S = ¶s1↪ s2↪ ▷ ▷ ▷ ↪ sk♦, we use X 2 Rk⇥n to denote the shapelet-transformed matrix, where each element X(si↪tj) denotes the distance between shapelet si and time series tj. For simplicity, we use X(ij) to represent X(si↪tj) which can be calculated as in Eq. (1),

where q = qj - li + 1 denotes the total number of segments with length li from series tj, and qj↪ li are the lengths of time series tj and shapelet si respectively.

Given a set of time series data S, X(ij) is a function with respect to all candidate shapelets S, i.e. X(S)(ij). For simplicity, we omit the variable S and still use X(ij) instead.

The distance function in Eq. (1) is not continuous and thus non-differential. Based on the work [Grabocka et al., 2014], we approximate the distance function using the soft minimum function as in Eq. (2),

Pseudo-class label Unsupervised learning faces the challenge of unlabeled training examples. Thus, we introduce the pseudo-class labels for learning. Consider that we cluster a time series data set into c categories, the pseudo-class label matrix Y 2 Rc⇥n contains c labels, where Y(ij) indicates the probability of the j-th time series example belonging to the ith category. Time series examples that share the same pseudoclass label fall into the same category. If Y(ij) > Y(i↪j)↪ 8i, then the time series example tj belong to the cluster i.

where dijq = 1 li Pli h=1 (tj(q+h-1) -si(h)), and ↵ controls the precision of the function. The soft minimum approaches the true minimum when ↵ ! -1. In our experiments, we set ↵ = -100.

Spectral Analysis Spectral analysis was introduced by [Donath and Hoffman, 1973] and has been widely used in unsupervised learning [Von Luxburg, 2007]. The principle behind is that examples that are close to each other are likely to share the same class label [Tang and Liu, 2014] [Von Luxburg, 2007]. Assume that G 2 Rn⇥n is the similarity matrix of time series based on the shapelet-transformed matrix X, then the similarity matrix can be calculated as in Eq. (3), where σ is the parameter of the RBF kernel.

Based on G, we expect the pseudo-class labels of similar data instances to be the same. Therefore, we can formulate a spectral regularization term as follows,

where LG = DG - G is the Laplacian matrix and DG is a diagonal matrix with its elements defined as DG(i↪ i) = Pnj=1 G(ij).

Least Square Minimization Based on the pseudo-class labels, we wish to minimize the least square error. Let W 2 Rk⇥c be the classification boundary under the pseudoclass labels, the least square error minimizes the following objective function,

Shapelet Similarity Minimization We wish to learn shapelets that are diverse in shape. Specifically, we penalize the model in case it outputs similar shapelets. Formally, we denote the shapelet similarity matrix as H 2 Rk⇥k , where each element H(si↪sj) represents the similarity between two shapelets si and sj. For simplicity, we use H(ij) to represent H(si↪sj) which can be calculated as in Eq. (6),

where dij is the distance between shapelet si and shapelet sj. dij can be calculated by following Eq. (2).

Unsupervised Shapelet Learning Model Eq. (7) gives the unsupervised shapelet learning model (USLM). It is a joint optimization problemwith respect to three variables, the classification boundary W, Pseudo-class label Y and candidate shapelets S.

In the objective function, the first term is the spectral regularization that preserves local structure information. The second term is the shapelet similarity regularization term that prefers diverse shapelets. The third and fourth terms are the regularized least square minimization.

Note that matrix LG in Eq. (4), matrix H in Eq. (6), and matrix X in Eq. (2) depend on the shapelets S. We explicitly write these matrices as variables with respect to shapelets S in Eq. (7), i.e. LG(S) , H(S) and X(S) respectively. Below, we propose a coordinate descent algorithm to solve the model.

5 The Algorithm

In this part, we first introduce a coordinate descent algorithm to solve the USLM, and then analyze its convergence and initialization methods.

5.1 Learning Algorithm

In the coordinate descent algorithm, we iteratively update one variable by fixing the remaining two variables. The steps will be repeated until convergence. Algorithm 1 summarizes the steps.

Algorithm 1. Unsupervised Shapelet Learning Algorithm (USLA)

• 1: Input:
• ÷ Time series T with c classes
• ÷ Number of internal iterations imax
• ÷ Length and number of shapelets: lmin, r, k
• ÷ Learning rate ⌘ and Parameters λ1↪ λ2↪ λ3 and ↵↪ σ
• 2: Output: Shapelets S⇤ and class labels Y⇤
• 3: Initialize: S0↪W0↪Y0
• 4: While Not convergent do 5: Calculate: Xt(T↪ St♣↵), LGt(T↪ St♣↵↪ σ) 6: and Ht(St♣↵) based on Eqs. (2), (4), and (6); 7: update Wt+1↪ Yt+1: 8: Yt+1 λ2WTt Xt(LGt +λ2I)-1 9: Wt+1 (λ2XtXTt +λ3I)-1 (λ2XtYTt+1 ). 10: update St+1: 11: for i = 1↪ ▷ ▷ ▷ ↪ imax do 12: Si+1 Si - ⌘rSi

÷ Update Y by fixing W and S By fixing W and S, the function in Eq. (7) degenerates to Eq. (8),

The derivative of Eq. (8) with respect to Y is,

Let Eq. (9) equal to 0, we can obtain the solution of Y as in Eq. (10),

where I is an identity matrix. Thus, the update of Y is

÷ Update W by fixing S and Y By fixing S and Y, Eq. (7) degenerates to Eq. (12) as below,

The derivative of Eq. (12) with respect to W is,

Let Eq. (13) equal to 0, we obtain the solution of W as in Eq. (14),

Thus, the update of W is

÷ Update S by fixing W and Y By fixing W and Y, Eq. (7) degenerates to Eq. (16) as below,

Eq. (16) is non-convex and we cannot explicitly solve S as in finding W and Y. Instead, we resort to an iterative algorithm by setting a learning rate ⌘, i.e. Si+1 = Si - ⌘rSi, where rSi = @F(Si) @S . The iterative steps will guarantee the convergence of the objective function. The derivative of Eq. (16) with respect to S(mp) is

where m = 1↪ ▷ ▷ ▷ ↪ k, and p = 1↪ ▷ ▷ ▷ ↪ lm.

Because LG = DG - G and DG(i↪ i) = Pnj=1 G(ij), the first term in Eq. (17) turns to calculating @G(ij)◁@S(mp) as shown in Eq. (18),

The second term in Eq. (17) turns to calculating Eq. (21),

where ˜ dij is the distance between shapelets si and sj. The calculation of ˜ dij and @ ˜ dij @S(mp) is similar to X(ij) and @X(ij) @S(mp) respectively.

To sum up, we can calculate the gradient rSi = @F(S) @Si by following Eqs. (17)-(21). In the following, we discuss the convergence of the coordinate descent algorithm in solving Eq. (7).

5.2 Convergence

The convergence of Algorithm 1 depends on stepwise descents. When updating Y or W, we know that Yt+1 = Y⇤ (Wt↪ St) and Wt+1 = W⇤ (Yt+1↪ St). When updating S, the objective function in Eq. (16) is not convex and a closedform derivative is difficult to obtain. Instead, we use a gradient descent algorithm. In the iterations, as long as we set an appropriate learning rate ⌘ that is usually very small, the objective function will decrease to convergence.

In addition, the objective function in Eq. (7) is non-convex but have a lower bound of 0 due to being non-negative, so Algorithm 1 converges to local optima. In our experiments we run the algorithm several times under different initializations and choose the best solution as output.

5.3 Initialization

Because the algorithm only outputs local optima, we discuss how to initialize the variables to improve the performance of the algorithm. The algorithm expects to initialize S0, Y0 and W0. We first initialize S0 by using the centroids of the segments having the same length with the shapelets length, because centroids represent typical patterns behind the data. Then, we use the results of the shapelet-transformed matrix of time series based on S0 to obtain X0. Next, the results obtained by k-means based on X0 is used to initialize W0 and Y0. The initialization enables fast convergence.

6 Experiments

We conduct experiments to validate the performance of USLM. All experiments are conducted on a Windows 8 machine with 3.00GHz CPU and 8GB memory. The Matlab source codes and data are available online 1 .

6.1 Datasets

Synthetic data: This dataset is generated by following the work [Shariat and Pavlovic, 2011] and [Zakaria et al., 2012]. The dataset consists of ten examples from two classes. The first class contains sinusoidal signals of length 200. The second class contains rectangular signals of length 100. We randomly embed Gaussian noise in the data. Heterogeneous noise is generated from five Gaussian processes with means ⌫ 2 [0↪ 2] and variances σ2 2 [0↪ 10] chosen uniformly at random.

Real-world data: We use seven time series benchmark datasets download from the UCR time series archive [Chen et al., 2015] [Cetin et al., 2015]. The datasets are summarized in Table 1. More details of the datasets can resort to their Website.

6.2 Measures

Existing measures used to evaluate the performance of time series clustering include Jaccard Score, Rand Index, Folkes and Mallow index [Halkidi et al., 2001] [Zakaria et al., 2012]. Among them, Rand index [Rand, 1971] is the most popular one, while the remaining measures can be taken as variants of Rand index. Therefore, we use Rand Index as the evaluation method.

To calculate Rand index, we compare the cluster labels Y⇤ obtained by the clustering algorithm with the genuine class labels Ltrue as in Eq. (22),

where TP is the number of time series pairs which belong to the same class in Ltrue and are assigned to the same cluster in Y⇤ , TN is the number of time series pairs which belong to different classes in Ltrue and are assigned to different clusters in Y⇤ , FP is the number of time series pairs which belong to different classes in Ltrue but are assigned to the same cluster in Y⇤ , and FN is the number of time series pairs which belong to the same class in Ltrue but are assigned to different clusters in Y⇤ . If Rand index is close to 1, it indicates a high quality clustering [Zakaria et al., 2012] [Paparrizos and Gravano, 2015].

1 https://github.com/BlindReview/shapelet

6.3 Time series with unequal lengths

Fig. 2 shows an example of two shapelets learnt by USLM. Shapelet 1 is a sharp spike of length 12 which matches the most prominent spikes of the rectangular signals. Shapelet 2 is a subsequence of length 30 which is very similar to the standard shape of the sinusoidal signals. From the results, we can observe that USLM can auto-learn representative shapelets from unlabeled time series data.

The results in Fig. 3 also show that USLM can handle time series and shapelets of unequal lengths, where we can obtain the best Rand index value of 1. In contrast, the work [Shariat and Pavlovic, 2011] obtains only 0.9 on the dataset even if they use class label information during training.

6.4 Running time

We test the running time of USLM by changing the number of shapelets k and the number of clusters c. The results are given in Fig. 3.

First, we vary the parameter k from 2 to 12 with a step size of 2. The remaining parameters are fixed as follows, λ1 = λ2 = λ3 = λ4 = 1↪ σ = 1, Imax = 50↪ ⌘ = 0▷01 and the length of the shapelets is set to 10. The running time is the average of ten executions.

From Fig. 3(a), we can observe that the running time generally increases linearly with respect to the number of shapelets. Thus, our approach scales well to large datasets.

Then, we let the number of clusters c change from 2 to 7. The length of shapelets is set to be 10% of the time series length. We set k = 2 which means that we only learn two shapelets of equal length. The remaining parameters are the same as above. Fig. 3(b)

6.5 Comparisons with k-Shape

The k-Shape algorithm is proposed in the work [Paparrizos and Gravano, 2015] to cluster unlabeled time series. In this part, we compare our algorithm with the k-Shape algorithm. The source codes for k-Shape are downloaded from the website of the original authors. Table 2 lists the results. We select the best results obtained by k-Shape after 100 times of repeats. We can observe that the results obtained by USLM are better.

Form Table 2, we can observe that USLM outperforms the k-Shape algorithm on all the seven datasets. The average improvement on the seven datasets is 14% and the best improvement is 26% on the 'CBF' dataset. To sum up, the results show that USLM gains higher accuracy than k-Shape.

7 Conclusions

In this paper, we investigated a new problem of feature learning from unlabeled time series data. To solve the problem, we proposed a new learning model USLM by combining the pseudo-class label, spectral analysis, shapelets regularization and regularized least-squares minimization. USLM can autolearn the most discriminative features from unlabeled times series data. Experiments on real-world time series data have shown that USLM can obtain an average improvement of 14% compared to k-Shape.

Acknowledgments

This work was supported by the Australian Research Council (ARC) Discovery Projects under Grant No. DP140100545 and DP140102206 and also been partially supported by grants from National Natural Science Foundation of China (Nos. 61472390 and 11271361). Y. Tian is the corresponding author.