Symbolic Representation of Time Series: a Hierarchical Coclustering Formalization

Abstract

The choice of an appropriate representation remains crucial for mining time series, particularly to reach a good trade-o between the dimensionality reduction and the stored information. Symbolic representations constitute a simple way of reducing the dimensionality by turning time series into sequences of symbols. SAXO is a data-driven symbolic representation of time series which encodes typical distributions of data points. This approach was rst introduced as a heuristic algorithm based on a regularized coclustering approach. The main contribution of this article is to formalize SAXO as a hierarchical coclustering approach. The search for the best symbolic representation given the data is turned into a model selection problem. Comparative experiments demonstrate the benet of the new formalization, which results in representations that drastically improve the compression of data.

Keywords

• Time series
• symbolic representation
• coclustering

Introduction

The choice of the representation of time series remains crucial since it impacts the quality of supervised and unsupervised analysis [ 1 ]. Time series are particularly dicult to deal with due to their inherently high dimensionality when they are represented in the time-domain [ 2 ] [ 3 ]. Virtually all data mining and machine learning algorithms scale poorly with the dimensionality. During the last two decades, numerous high level representations of time series have been proposed to overcome this diculty. The most commonly used approaches are: the Discrete Fourier Transform [ 4 ], the Discrete Wavelet Transform [ 5 ] [ 6 ], the Discrete Cosine Transform [ 7 ], the Piecewise Aggregate Approximation (PAA) [ 8 ]. Each representation of time series encodes some information derived from the raw data4. According to [ 1 ], mining time series heavily relies on the choice of a representation and a similarity measure. Our objective is to nd a compact and informative representation which is driven by the data. The symbolic representations constitute a simple way of reducing the dimensionality of the data by turning time series into sequences of symbols [ 9 ]. In such representations, each symbol corresponds to a time interval and encodes information which summarize designates a time series represented in the time-domain by a vector of Copyright ⃝c2015 for this paper by its authors. Copying permitted for private and academic purposes. the related sub-series. Without making hypothesis on the data, such a representation does not allow one to quantify the loss of information. This article focuses on a less prevalent symbolic representation which is called SAXO 5. This approach optimally discretizes the time dimension and encodes typical distributions 6 of data points with the symbols [ 10 ]. SAXO oers interesting properties. Since this representation is based on a regularized Bayesian coclustering 7 approach called MODL8 [ 11 ], a good trade-o is naturally reached between the dimensionality reduction and the information loss. SAXO is a parameter-free and data-driven representation of time series. In practice, this symbolic representation proves to be highly informative for training classiers. In [ 10 ], SAXO was evaluated on public datasets and favorably compared with the SAX representation.

Originally, SAXO was dened as a heuristic algorithm. The two main contributions of this article are: i) the formalization of SAXO as a hierarchical coclustering approach; ii) the evaluation of its compactness in terms of coding length. This article is organized as follows. Section 2 briey introduces the symbolic representations of time series and presents the original SAXO heuristic algorithm. Section 3 formalizes the SAXO approach resulting in a new evaluation criterion which is the main contribution of this article. Experiments are conducted in Section 4 on real datasets in order to compare the SAXO evaluation criterion with that of the MODL coclustering approach. Lastly, perspectives and future works are discussed in Section 5. 2

Related work

Numerous compact representations of time series deal with the curse of dimensionality by discretizing the time and by summarizing the sub-series within each time interval. For instance, the Piecewise Aggregate Approximation (PAA) encodes the mean values of data points within each time interval. The Piecewise Linear Approximation (PLA) [ 12 ] is an other example of compact representation which encodes the gradient and the y-intercept of a linear approximation of sub-series. In both cases, the representation consist of numerical values which describe each time interval. In contrast, the symbolic representations characterize the time intervals by categorical variables [ 9 ]. For instance, the Shape Denition Language (SDL) [ 13 ] encodes the shape of sub-series by symbols. The most commonly used symbolic representation is the SAX 9 approach [ 9 ]. In this case, the time dimension is discretized into regular intervals, the symbols encode the mean values per interval. 5 SAXO Symbolic Aggregate approXimation Optimized by data . 6 The SAXO approach produces clusters of time series within each time interval which correspond to the symbols. 7 The coclustering problem consist in reordering rows and columns of a matrix in order to satisfy a homogeneity criterion. 8 Minimum Optimized Description Length 9 Symbolic Aggregate approXimation.

The symbolic representations appear to be really helpful for processing large datasets of time series owing to dimensionality reduction. However, these approaches suer several limitations.

Most of these representations are lossy compression approaches unable to quantify the loss of information without strong hypothesis on the data. The discretization of the time dimension into regular intervals is not data driven.

The symbols have the same meaning over time irrespectively of their rank (i.e. the ranks of the symbols may be used to improve the compression) . Most of these representations involve user parameters which aect the stored information (ex: for the SAX representation, the number of time intervals and the size of the alphabet must be specied) .

The SAXO approach overcomes these limitations by optimizing the time discretization, and by encoding typical distributions of data points within each time interval [ 10 ]. SAXO was rst dened as a heuristic which exploits the MODL coclustering approach.

Figure 1 provides an overview of this approach by illustrating the main steps of the learning algorithm. The joint distribution of the identiers of the time series C, the values X, and the timestamp T is estimated by a trivariate coclustering model. The time discretization resulting from the rst step is retained, and the joint distribution of X and C is estimated within each time interval by using a bivariate coclustering model. The resulting clusters of time series are characterized by piecewise constant distributions of values and correspond to the symbols. A specic representation allows one to re-encode the time series as a sequence of symbols. Then, the typical distribution that best represents the data points of the time series is selected within each time interval. Figure 2(a) plots an example of recoded time series. The original time series (represented by the blue curve) is recoded by the abba SAXO word. The time is discretized into four intervals (the vertical red lines) corresponding to each symbol. Within time intervals, the values are discretized (the horizontal green lines) : the number of intervals of values and their locations are not necessary the same. The symbols correspond to typical distributions of values: conditional probabilities of X are associated with each cell of the grid (represented by the gray levels) ; Figure 2(b) gives an example of the alphabet associated with the second time interval. The four available symbols correspond to typical distributions which are both represented by gray levels and by histograms. By considering Figures 2(a) and 2(b), b appears to be the closest typical distribution of the second sub-series. (a) (b)

As in any heuristic approach, the original algorithm nds a suboptimal solution for selecting the most suitable SAXO representation given the data. Solving this problem in an exact way appears to be intractable, since it is comparable to the coclustering problem which is NP-hard. The main contribution of this paper is to formalize the SAXO approach within the MODL framework. We claim this formalization is a rst step to improving the quality of the SAXO representations learned from data. In this article, we dene a new evaluation criterion denoted by Csaxo (see Section 3). The most probable SAXO representation given the data is dened by minimizing Csaxo. We expect to reach better representations by optimizing Csaxo, instead of exploiting the original heuristic algorithm. 3

Formalization of the SAXO approach This section presents the main contribution of this article: the SAXO approach is formalized as a hierarchical coclustering approach. As illustrated in Figure 3, the originality of the SAXO approach is that the groups of identiers (variable C) and the intervals of values (variable X) are allowed to change over time. By contrast, the MODL coclustering approach forces the discretization of C and X to be the same within time intervals. Our objective is to reach better models by removing this constraint.

A SAXO model is hierarchically instantiated by following two successive steps. First, the discretization of time is determined. The bivariate discretization C X is then dened within each time interval. Additional notations are required to describe the sequence of bivariate data grids.

X

SAXO C

T C

T

Notations for time series: In this article, the input dataset D is considered to be a collection of N time series denoted Si (with i 2 [1, N ]). Each time series consists of mi data points, which are couples of values X and timestamps T . The total number of data points is denoted by m = ∑N i=1 mi.

Notations for the t-th time interval of a SAXO model: kT : number of time intervals; kCt : number of clusters of time series; kXt : number of intervals of value; kC (i, t): index of the cluster that contains the sub-series of Si; fniC g: number of time series in each cluster itC ;

t mt: number of data point; mit: number of data points of each time series Si; mitC : number of data points in each cluster itC ; fmtjX g: number of data points in the intervals jX ; fmitCjX g: number of data points belonging to each cell (iC , jX ).

Eventually, a SAXO model M ′ is rst dened by a number of time intervals and the location of their bounds. The bivariate data grids C X within each time interval are dened by: i) the partition of the time series into clusters; ii) the number of intervals of values; iii) the distribution of the data points on the cells of the data grid; iv) for each cluster, the distribution of the data points on the time series belonging to the same cluster. Section 3.1 presents the prior distribution of the SAXO models. The likelihood of a SAXO model given the data is described in Section 3.2. A new evaluation criterion which denes the most probable model given the data is proposed in Section 3.3. 3.1

Prior distribution of the SAXO models The proposed prior distribution P (M ′) exploits the hierarchy of the parameters of the SAXO models and is uniform at each level. The prior distribution of the number of time intervals kT is given by Equation 1. The parameter kT belongs to [1, m], with m representing the total number of data points. All possible values of kT are considered as equiprobable. By using combinatorics, the number of possible locations of the bounds can be enumerated given a xed value of kT . Once again, all possible locations are considered as equiprobable. Equation 2 represents the prior distribution of the parameter fmtg given kT . Within each time interval t, the number of intervals of values kXt is uniformly distributed (see Equation 3) . The value of kXt belongs to [1, mt], with mt representing the number of data points within the t-th time interval. All possible values of kXt are equiprobable. The same approach is applied to dene the prior distribution of the number of clusters within each time interval (see Equation 4) . The value of kt C belongs to [1, N ], with N denoting the total number of time series. Once again, all possible values of kCt are equiprobable. The possible ways of partitioning the N time series into kCt clusters can be enumerated, given a xed number of clusters in the t-th time interval. The term B(N, kCt ) in Equation 5 represents the number of possible partitions of N elements into kCt possibly empty clusters 10. Within each time interval, all distributions of the mt data points on the cells of the bivariate data grid C X are considered as equiprobable. Equation 6 enumerates the possible ways of distributing fmtg data points on kXt .kCt cells. Given a time interval t and a cluster itC , all distributions of the data points on the time series belonging to the same cluster are equiprobable. Equation 7 enumerates the possible ways of distributing mit data points on niC time series. t P (kT ) = 1 m (1)

1 P (fmtgjkT ) = (m+kT −1) kT −1 (2)

kT 1 P (fkXt gjkT , fmtg) = ∏ t=1 mt P (fkCt gjkT ) = ∏kT 1 t=1 N (4)

P (kC (i, t)jkT , fkCt g)= ∏kT 1 t=1 B(N, kCt ) t kT 1 P (fmjC;jX gjkT , fmtg, fkXt g, fkCt g)= ∏ t=1 (mt+kCt:kXt −1) kCt:kXt −1 P (fmitgjkT , fkCt g, kC (i, t), fmtjC;jX g)= ∏kT ∏kCt 1 (7) t=1 i=1(mitC +nitC −1) nt iC −1

In the end, the prior distribution of the SAXO models M ′ is given by Equation 8.

P (M ′) = 1 m

1 (m+kT −1) kT −1 ∏kT [ 1

mt t=1 1 N

1 B(N, kCt )  elements into k clusters and B(N, kCt ) = ∑ik=Ct1 S{Ni }.

Likelihood of data given a SAXO model A SAXO model matches with several possible datasets. Intuitively, the likelihood P (DjM ′) enumerates all the datasets which are compatible with the parameters of the model M ′. The rst term of the likelihood represents the distribution of the ranks of the values of T . In other words, Equation 9 codes all the possible permutations of the data points within each time interval. The second term enumerates all the possible distributions of the m data points on the kT time intervals, which are compatible with the parameter fmtg (see Equation 10) . In the same way, Equation 11 enumerates the distributions of the mt data points on the kXt .kCt cells of the bivariate data grids C X within each time interval. The considered distributions are compatible with the parameter fmitC;jX g. For each time interval and for each cluster, Equation 12 enumerates all the possible distributions of the data points on the time series belonging to the same cluster. Equation 13 enumerates all the possible permutations of the data points in the intervals of X, within each time interval. This information must also be coded over all the time intervals, which is equivalent to enumerating all the possible fusions of kT stored lists in order to constitute a global stored list (see Equation 14). In the end, the likelihood of the data given a SAXO models M ′ is characterized by Equation 15.

1 ∏tk=T1 mt! (9) 1 m! ∏tk=T1 mt! (10) kT ∏ 1 mt! t=1 ∏ikCCt=1 ∏jkXXt=1 mitC;jX ! 1 kT ∏

kt t=1 ∏iCC=1 mitC ! ∏iN=1 mit! (12)

(13) kT ∏ t=1 ∏jkXXt=1 mtjX ! 1 1 m! ∏tk=T1 mt! P (DjM ′)= m1!2 ∏kT  ∏ikCCt=1 ∏jkXXt=1 mitC;jX !

 kt t=1 ∏jkXXt=1 mtjX ! ∏iCC=1 mitC !

i=1 mit!  ∏N  (11) (14) (15) 3.3

Evaluation criterion The SAXO evaluation criterion is the negative logarithm of P (M ′) P (DjM ′) (see Equation 16) . The rst three lines correspond to the prior term log(P (M ′)) and the last two lines represent the likelihood term log(P (M ′jD)). The most probable model given the data is found by minimizing Csaxo(M ′) over the set of all possible SAXO models denoted by M′.

Csaxo(M ′) = log(m) + log

kT kT +kT .log(N )+∑log(B(N, kCt ))+∑log t=1 t=1 (mt+kCt .kXt 1)

kCt .kXt 1 (m + kT kT 1 1)

kT + ∑ log(mt) t=1 + ∑kT ∑kCt log(mitC + nitC t=1 iC=1 nt 1

1) + 2.log(m!)

iC kT kCt ∑ ∑ kXt ∑ log(mitC;jX !) t=1 iC=1 jX =1 kT  kCt + ∑  ∑ log(mitC !) t=1 iC=1

N ∑ log(mit!) + i=1 kXt  ∑ log(mtjX !) jX =1 (16) Key ideas to retain: Rather than having a heuristic decomposition of the SAXO approach in a two-step algorithm, we propose a single evaluation criterion based on the MODL framework. Once optimized, this criterion should yield better representations of time series. We compare the ability of both criterion to compress data. We aim at evaluating the interest of optimizing Csaxo rather than the original trivariate coclustering criterion [ 14 ] (denoted by Cmodl). 4

Comparative experiments on real datasets According to the information theory and since both criteria are a negative logarithm of a probability, Csaxo and Cmodl represent the coding length of the models. In this section, both approaches are compared in terms of coding length. The 20 processed datasets come from the UCR Time Series Classication and Clustering repository [ 15 ]. Some datasets are relatively small, we have selected the ones which include at least 800 learning examples. Originally, these datasets are divided into training and test sets which have been merged in our experiments. The objective of this section is to compare Csaxo and Cmodl for each dataset. On the one hand, the criterion Cmodl is optimized by using the greedy heuristic and a neighborhood exploration mentioned described in [ 11 ]. The coding length of the most probable MODL model (denoted by M APmodl) is then calculated by using Cmodl. On the other hand, the criterion Csaxo is optimized by exploiting the original heuristic algorithm illustrated in Figure 1 [ 10 ]. The coding length of best SAXO model (denoted by M APsaxo) is given by the criterion Csaxo. Notice that both algorithms have a O(mpm log m) time complexity. The order of magnitude of the coding length depends on the size of the data set and can not be easily compared over all datasets. We choose to exploit the compression gain [ 16 ] which consists in comparing the coding length of a model M with the coding length of the simplest model Msim. This key performance indicator varies in the interval [ 0, 1 ]. The compression gain is similarly dened for the MODL and the SAXO approaches such that:

Gainmodl(M ) = 1 Gainsaxo(M ′) = 1

Cmodl(M )/Cmodl(Msim)

Csaxo(M ′)/Csaxo(Msim)

Our experiments evaluate the variation of the compression gain between the SAXO and the MODL approaches. This indicator is denoted by ∆G and represents the relative improvement of the compression gain provided by SAXO. The value of ∆G can be negative, which means that SAXO provides a worse compression gain than the MODL approach.

∆G = Gainsaxo(M APsaxo) Gainmodl(M APmodl)

Gainmodl(M APmodl)

Dataset

∆G

Dataset

Table 1 presents the results of our experiments and includes a particular case with a missing value for the dataset TwoPatterns. In this case, the rst step of the heuristic algorithm which optimizes Csaxo (see Figure 1) leads to the simplest trivariate coclustering model that includes a single cell. This is a side eect due to the fact that the MODL approach is regularized. A possible explanation is that the temporal representation of time series is not informative for this dataset. Other representations such as the Fourier or the wavelet transforms could be tried. In most cases, ∆G has a positive value which means SAXO provides a better compression than the MODL approach. This trend emerges clearly, the average compression improvement reaches 183%. We exploit the Wilcoxon signed-ranks test to reliably comparing both approaches over all datasets [ 17 ]. If the output value (denoted by z) is smaller than 1.96, the gap in performance is considered as signicant. Our experiments give z = 3.37 which is highly signicant. In the end, the compression of data provided by SAXO appears to be intrinsically better than the MODL approach. The prior term of Csaxo induces an additional cost in terms of coding length. This additional cost is far outweighed by a better encoding of the likelihood.

Conclusion and perspectives

SAXO is a data-driven symbolic representation of time series which extends SAX in three ways: i) the discretization of time is optimized by a Bayesian approach rather than considering regular intervals; ii) the symbols within each time interval represents typical distributions of data points rather than average values; iii) the number of symbols may dier per time interval. The parameter settings is automatically optimized given the data. SAXO was rst introduced as an heuristic algorithm. This article formalizes this approach within the MODL framework as a hierarchical coclustering approach (see Section 3). A Bayesian approach is applied leading to an analytical evaluation criterion. This criterion must be minimized in order to dene the most probable representation given the data. This new criterion is evaluated on real datasets in Section 4. Our experiments compare the SAXO representation with the original MODL coclustering approach. The SAXO representation appears to be signicantly better in terms of data compression. In future work, we plan to use the SAXO criterion in order to dene a similarity measure. Numerous learning algorithms, such as K-means and K-NN, could use such an improved similarity measure dened over time series. We plan to explore potential gains in areas such as: i) the detection of atypical time series; ii) the query of a database by similarity; iii) the clustering of time series.

References

1. T. Liao , Clustering of time series data: a survey, Pattern Recognition , vol. 38 , pp. 18571874 , 2005 .

2. D. Bosq , Linear Processes in Function Spaces: Theory and Applications (Lecture Notes in Statistics) . Springer, 2000 .

3. J. Ramsay and B. Silverman , Functional Data Analysis, ser . Springer Series in Statistics. Springer, 2005 .

4. M. Frigo and S. Johnson , The design and implementation of FFTW3, Proceedings of the IEEE , vol. 93 , no. 2 , pp. 216231 , 2005 , special issue on Program Generation, Optimization, and Platform Adaptation.

5. R. Polikar , Physics and Modern Topics in Mechanical and Electrical Engineering . World Scientic and Eng. Society Press, 1999 , ch. The story of wavelets.

6. K. Chan and W. Fu , Ecient Time Series Matching by Wavelets, in ICDE '99: Proceedings of the 15th International Conference on Data Engineering . IEEE Computer Society , 1999 .

7. N. Ahmed , T. Natarajan , and K. R. Rao , Discrete Cosine Transfom, IEEE Trans. Comput. , vol. 23 , no. 1 , pp. 9093 , 1974 .

8. C. Guo , H. Li , and D. Pan , An improved piecewise aggregate approximation based on statistical features for time series mining, in Proceedings of the 4th international conference on Knowledge science, engineering and management , ser . KSEM'10 . Berlin, Heidelberg: Springer-Verlag, 2010 , pp. 234244 .

9. J. Lin , E. Keogh , S. Lonardi , and B. Chiu , A Symbolic Representation of Time Series, with Implications for Streaming Algorithms , in 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery , San Diego, 2003 .

10. A. Bondu , M. BoullØ, and B. Grossin , SAXO : An Optimized Data-driven Symbolic Representation of Time Series , in IJCNN (International Joint Conference on Neural Networks). IEEE , 2013 .

11. M. BoullØ, Hands on pattern recognition . Microtome , 2010 , ch. Data grid models for preparation and modeling in supervised learning .

12. H. Shatkay and S. B. Zdonik , Approximate Queries and Representations for Large Data Sequences , in 12th International Conference on Data Engineering (ICDE) , 1996 , pp. 536545 .

13. R. Agrawal , G. Psaila , E. L. Wimmers , and M. Zait , Querying Shapes of Histories, in 21th International Conference on Very Large Data Bases (VLDB 95) , 1995 , pp. 502514 .

14. M. BoullØ , Functional data clustering via piecewise constant nonparametric density estimation , Pattern Recognition , vol. 45 , no. 12 , pp. 43894401 , 2012 .

15. E. Keogh , Q. Zhu , B. Hu , H. Y. , X. Xi , L. Wei , and C. A. Ratanamahatana , The UCR Time Series Classication/Clustering Homepage : www.cs.ucr.edu/ eamonn/time_series_data/, 2011 .

16. M. BoullØ , Optimum simultaneous discretization with data grid models in supervised classication: a Bayesian model selection approach , Advances in Data Analysis and Classication , vol. 3 , no. 1 , pp. 3961 , 2009 .

17. J. Dem †ar, Statistical Comparisons of Classiers over Multiple Data Sets , Journal of Machine Learning Research , vol. 7 , pp. 130 , Dec . 2006 .