# Efficient Time-Series Clustering through Sparse Gaussian Modeling
## 2 Notation and Preliminaries
### Distance Functions
#### 2.2.2 Dynamic Time Warping Distance  
The _Dynamic Time Warping_ (DTW) distance is a so-called _elastic_ distance, which can deal with time series of different lengths, different sampling frequencies, and different time alignments. DTW seeks an optimal alignment (or warping) of the data points of two time series \(X\) and \(Y\) that minimizes the resulting pairwise Euclidean distance of the corresponding data points. DTW is regarded as one of the most robust and accurate distance functions for time series and has been extensively used in practice (see, e.g., [8; 9; 10; 22] and the references therein). The optimal alignment of two time series \(X\) and \(Y\), with \(X=((x_{1},t_{1}),\ldots,(x_{\mathcal{T}},t_{\mathcal{T}}))\) and \(Y=(y_{1},\tau_{1}),\ldots,(y_{V},\tau_{V}))\), which is used for the computation of DTW, is a sequence \(W=((T_{1},V_{1}),\ldots,(T_{l},V_{l}))\) with \(l\leq T+V\) index pairs that aligns the data points of \(X\) and \(Y\) such that (i) \((T_{1},V_{1})=(1,1)\) and \((T_{l},V_{l})=(T,V)\), i.e., the first and the last points of \(X\) and \(Y\) are aligned with each other; (ii) every point of \(X\) (resp. \(Y\)) is aligned with at least one point of \(Y\) (resp. \(X\)); and (iii) for every two consecutive index pairs \((T_{\ell},V_{\ell})\), \((T_{\ell+1},V_{\ell+1})\), \((T_{\ell}-T_{\ell+1},V_{\ell}-V_{\ell+1})\in\{(0,1),(1,0),(1,1)\}\), i.e., the alignment sequence is increasing and without cross-alignments (see also Figure 1b). Then, the DTW distance of two time series \(X\) and \(Y\) is defined as:  
\[D(X,Y)=\min_{X\text{-}Y\text{ warping }W}\sqrt{\sum_{(T_{\ell},V_{\ell})\in W}(x _{T_{\ell}}-y_{V_{\ell}})^{2}} \tag{4}\]  
We note that DTW is symmetric and satisfies \(D(X,X)=0\), but it does not satisfy the triangle inequality. The square of DTW can be computed in quadratic time \(\Theta(TV)\), using dynamic programming based on the recursion below, which is similar to the recursion used for computing the Edit Distance of two strings:  
\[D(X[i],Y[j])=\left\{ \begin{array}{ll}\sum_{\ell=1}^{j}(x_{1}-y_{\ell})^{2}& \text{if }i=1\\ \sum_{\ell=1}^{j}(x_{\ell}-y_{1})^{2}&\text{if }j=1\\ (x_{i}-y_{j})^{2}+\\ \min\{D(X[i-1],Y[j-1]),D(X[i-1],Y[j]),D(X[i],Y[j-1])\}&\text{otherwise}\end{array} \right.\]  
where \(X[i]=((x_{1},t_{1}),\ldots(x_{i},t_{i}))\) denotes the prefix of \(X\) consisting of \(X\)'s first \(i\) data points and \(Y[j]=((y_{1},\tau_{1}),\ldots(y_{j},\tau_{j}))\) denotes the prefix of \(Y\) consisting of \(Y\)' first \(j\) data points. We should note that the definition of DTW sometimes restricts the maximum number of data points that can be aligned with a single one, which leads to faster computation and possibly better practical results (see also [23]). In this work, we focus on a generalization of DTW, referred to as \(\beta\)-DTW, for some fixed parameter \(\beta\geq 0\), where the distance between two aligned data points \((x_{i},t_{i})\) and \((y_{j},t_{j})\) is computed as:  
\[\delta_{\beta}((x_{i},t_{i}),(y_{j},t_{j}))=(x_{i}-y_{j})^{2}+\beta(t_{i}-t_{j })^{2}\,, \tag{5}\]  
instead of simply \((x_{i}-y_{j})^{2}\). Then, \(\beta\)-DTW is computed by the dynamic programming above by replacing the distance function \((x_{i}-y_{j})^{2}\) with the more general \(\delta_{\beta}((x_{i},t_{i}),(y_{j},t_{j}))\). For \(\beta=0\), we obtain the standard DTW. As \(\beta\) grows larger, \(\beta\)-DTW penalizes the alignment of data points observed at quite different points in time. Using a moderate value of \(\beta\) proves useful in our Sparse Time-Series Clustering framework because the inducing points used for time-series representation can be located by Sparse Gaussian Process Regression at very different points in time. In fact, the locations of the inducing points highly depend on the shape and the variance of the regressed time series at different time intervals. Hence, the second term in \(\delta_{\beta}(\cdot)\) serves to penalize significant differences in how two time series evolve.