Averaging a set of time series is a major topic for many temporal data mining tasks as summarization, extracting prototype or clustering. Time series averaging should deal with the tricky multiple temporal alignment problem; a still challenging issue in various domains. This work compares the major progressive and iterative averaging time series methods under dynamic time warping (dtw).
Time series centroid estimation is a major issue for many temporal data analysis and mining tasks as summarization, extracting temporal prototype or clustering. Estimating the centroid of a set of time series under time warp should deal with the tricky multiple temporal alignment problem [1{4]. Temporal warping alignment of time series has been an active research topic in many scienti c disciplines. To estimate the centroid of two time series under temporal metrics, as the dynamic time warping [5{7], one standard way is to embed the time series into a new Euclidean space de ned by their temporal warping alignment. In this space, the centroid can be estimated as the average of the linked elements. The problem becomes more complex where the number of the time series is more than two, as one needs to determine a multiple alignment that links simultaneously all the time series on their commonly shared similar elements.
A rst manner to determine a multiple alignment is to search, by dynamic programming, the optimal path within an n-dimensional grid that crosses the n time series. The complexity of this approach prevents its use, as it constitutes an NP-complete problem with a complexity of O(T n) that increases exponentially with the number of time series n and the time series length T . A second way, that identi es progressive approaches, is based on combining progressively pairwise time series centroids to estimate the global one. The progressive approaches may su er of the early error propagation through the set of pairwise centroid combinations. The third approach is iterative, it works similarly to the progressive approach, but mainly reduces the error propagation by repeatedly re ning the barycenter and realigning it to the initial time series. In general, the main progressive and iterative approaches are of heuristic nature limited to the dynamic time warping metric, that provide an estimation of the barycenter without guarantee of an optimal solution.
The main contribution of this work is to introduce some major progressive and iterative approaches for time series centroid estimation, prior to present their Copyright c 2015 for this paper by its authors. Copying permitted for private and academic purposes. characteristics, as well as an extensive comparison between the mentioned methods throughout real and synthetic datasets, where to the best of our knowledge this necessary study is never conducted before.
The rest of this paper is organized as follows: In the next section, di erent approaches are studied and Section 3 presents the conducted experimentation and discuss the results obtained. Lastly, Section 4 concludes the paper. 2
The progressive and iterative methods for averaging a set of time series are mostly derived from the multiple sequence alignment methods to address the tricky multiple temporal alignment problem. In the following, we review the major progressive and iterative approaches for time series averaging under time warp.
Gupta et al. in [
To avoid the bias induced by random selection, Niennattrakul et al. [
A direct manner to estimate the centroid proposed by Abdulla et al. [
All the methods de ne heuristic approaches, although with no guarantee of optimal solutions, the provided approximations are accurate particularly for time series that behave similarly within the set. However these approaches may fail principally for time series with similar global behavior and local temporal di erences, as one needs to deploy local instead of global averaging process. 3
The experiments are conducted to compare the above approaches on classes of
time series composing various datasets. The datasets can be divided into two
categories. The rst one is composed of time series that have similar global
behavior within the classes, where the time series of the second category may
have distinct global behavior, while sharing local characteristics [
The experiments are rst carried out on four well known public datasets cbf, cc,
digits and character traj. [
The four mentioned methods nlaaf, psa, cwrt and dba described in Section 2 is compared together. The performances of these approaches are evaluated through the centroid estimation of each class of the above described datasets. 1 http://ama.liglab.fr/ douzal/data Particularly, the e ciency of each approach is measured through: a) the reduction rate of the inertia criterion; the initial inertia being evaluated around the time series medoid that minimizes the distances to the rest of time series and b) the space and time complexity. The results reported hereafter are averaged through a bootstrap process, with 10 repetitions. Finally for all reported results, the best one which is signi cantly di erent from the rest(t -test at 1% risk) is indicated in bold.
Inertia reduction rate Time series averaging approaches are used to estimate centroid of the time series classes described above, then the inertia w.r.t. the centroids is measured. Lower is the inertia higher representative is the extracted PN centroid. Table 2, gives the obtained inertia reduction rates irr=1 PiNi==11DD((xxii;;mc)) , averaged per dataset; x1; :::; xN being the set of time series, D the metric, c the determined centroid and m the initial medoid. Table 2 shows that the dba provides the highest irr for the most datasets. Some negative rates observed indicate an inertia increase. Time and space complexity In Table 3 the studied approaches are compared w.r.t their space and time complexity. The results, averaged per dataset, reveal almost dba the faster method and psa the slowest one. The cwrt approach is not comparable to the rest of the methods as it performs directly an euclidean distance on the time series once the initial dtw matrix evaluated. Remark that for nlaaf and psa the centroid lengths are very large making these approaches unusable for large time series. The centroid lengths for the remaining methods are equal to the length of the initial medoid. The higher time consumptions observed for nlaaf and psa are mainly explained by the progressive increase of the centroid length during the pairwise combination process. From Table 2, we can see that dba and psa lead to the highest inertia reduction rates, where the best scores (indicated in bold) are reached by dba for almost all datasets. However it is signi cantly lower for some challenging datasets. Finally, cwrt has the lowest inertia reduction rates. The negative rates observed for cwrt indicate an inertia increase. As expected, the dba method that iteratively optimizes an inertia criterion, in general, reaches higher values than the noniterative methods (nlaaf, psa and cwrt).
From Table 3, the results reveal dba the fastest method and the psa the slowest one. For nlaaf and psa the estimated centroids have a drastically large dimension (i.e. a length around 104) making these approaches unusable for large time series datasets. The nlaaf and psa methods are highly time-consuming, largely because of the progressive increase of the centroid length during the pairwise combination process. The centroid lengths for the remaining methods are equal to the length of the initial medoid (Table 3). Finally, psa appears greatly slower than nlaaf; this is due to the hierarchical clustering on the whole time series. We nally visualize here some of the centroids obtained by the di erent methods to compare their shape to the one of the time series they represent. Figure (1) and (2) display the centroids obtained by the mentioned methods respectively for the class "funnel " of cbf and "cyclic" of data set cc. As one can note, for global datasets, almost all the approaches succeed in obtainging centroids more or less similar to the initial time series. However, we observe generally less representative centroids for nlaaf and psa. The dtw is among the most frequently used metrics for time series in several domains as signal processing, temporal data analysis and mining or machine learning. However, for time series clustering, approaches are generally limited to kmedoid to circumvent time series averaging under dtw and tricky multiple temporal alignments problem. The present study compares the major progressive and iterative time series averaging approaches under dynamic time warping. The experimental validation is based on global datasets in which time series share similar behaviors within classes, as well as on more complex datasets exhibiting time series that share only local characteristics, that are multidimensional and noisy. Both the quantitative evaluation, based on an inertia criterion and time and space complexity, and the qualitative one (consisting in the visualization of the centroids obtained by di erent methods) show the e ectiveness of dba approach. In particular, the dba method that iteratively optimizes an inertia criterion, not only, reaches higher values than the non-iterative methods (nlaaf, psa and cwrt), but also provides a fast time series averaging for global and local datasets.