# Efficient Time-Series Clustering through Sparse Gaussian Modeling
## 4 The Sparse Time-Series Clustering Framework  
The _Sparse Time-Series Clustering_ (STSC) framework consists of two stages, as outlined in Algorithm 1. The input instance consists of \((\mathcal{X},k)\), where \(\mathcal{X}\) is a set of \(N\) time series to be partitioned into \(k\) clusters. The first stage is to approximate each time series \(X_{j}\in\mathcal{X}\) with a sparse time series \(X^{\prime}_{j}\) consisting of \(m\) inducing data points by applying Sparse Gaussian Process Regression (see Section 4.1 and Algorithm 2). The second stage is to cluster the reduced instance \((\{X^{\prime}_{1},\dots,X^{\prime}_{N}\},k)\) using the \(k\)-means algorithm with the \(\beta\)-DTW distance, for some fixed parameter \(\beta\geq 0\), and the DTW Barycenter Averaging (DBA) algorithm (see Section 4.2 and Algorithm 3). The outcome of the second stage is a tuple with  
Figure 2: Sparse Gaussian Process Regression (SGPR) uses a predetermined number of inducing points (red dots) to compute a sparse approximate representation of a given time series (black stars). representative time series, which define a \(k\)-clustering of the reduced dataset \(\{X_{1}^{\prime},\ldots,X_{N}^{\prime}\}\) (and the corresponding \(k\)-clustering for the original dataset \(\mathcal{X}\)) by (1). ```
1:Input : Instance \(\mathcal{X}=(X_{1},\ldots,X_{N})\) with \(N\) time series, number of clusters \(k\)
2:Output: \(k\) cluster representatives \((C_{1},\ldots,C_{k})\) (which \(k\)-cluster \(\mathcal{X}\) into \((\mathcal{X}_{1},\ldots,\mathcal{X}_{k})\). 3:framework(\(\mathcal{X}\), \(m\), seed):
4:for\(j\in[N]\)do
5:\(X_{j}^{\prime}\leftarrow\texttt{modeling}(X_{j},m)\)\(\triangleright\) SGPR with \(m\) inducing points on each \(X_{j}\)\(\triangleleft\)
6:endfor
7:\((C_{1},\ldots,C_{k})\leftarrow\texttt{clustering}(\{X_{1}^{\prime},\ldots,X_{N}^ {\prime}\},k,\text{seed})\)
8:\(\triangleright\)\(k\)-means clustering of reduced instance \(\triangleleft\)
9:return\((C_{1},\ldots,C_{k})\)
```  
**Algorithm 1** Sparse Time-Series Clustering Framework  
```
1:Input : time series \(X=((x_{1},t_{1}),\ldots,(x_{T},t_{T}))\), number of inducing points \(m\)
2:Output: approximate time series \(X^{\prime}=((x_{1}^{\prime},\tau_{1}),\ldots,(x_{m}^{\prime},\tau_{m}))\) with \(m\) inducing points
3:\(\texttt{modeling}\left(X=((x_{1},t_{1}),\ldots,(x_{T},t_{T})),m\right)\):
4:\(\texttt{model}\leftarrow\texttt{train\_SGPR}(X,m)\)
5:\(\triangleright\) apply SGPR for the given number \(m\) of inducing points \(\triangleleft\)
6:\((x_{1}^{\prime},\tau_{1}),\ldots,(x_{m}^{\prime},\tau_{m}))\leftarrow\texttt{ extract\_induced\_points}(\texttt{model},m)\)
7:return\(X^{\prime}=((x_{1}^{\prime},\tau_{1}),\ldots,(x_{m}^{\prime},\tau_{m}))\)
```  
**Algorithm 2** Modeling through Sparse Gaussian Process Regression  
```
1:Input : dataset \(\mathcal{X}=(X_{1},\ldots X_{N})\) with \(N\) time series, number \(k\) of clusters, seed for initialization
2:Output: \(\mathcal{C}=(C_{1},\ldots,C_{k})\) with \(k\) cluster representatives
3:clustering(\(\mathcal{X},k,\text{seed}\)):
4:for\(j\in[k]\)do
5:\(r\leftarrow\texttt{random\_generator}(\text{seed},N)\)
6:\(\triangleright\) randomly choose initial cluster representatives \(\triangleleft\)
7:\(C_{j}^{(0)}\gets X_{r}\)
8:endfor
9:for\(i\in[100]\)do
10:\((C_{1}^{(i)},\ldots,C_{k}^{(i)})\leftarrow\texttt{DBA}(\mathcal{X},k,(C_{1}^{(i- 1)},\ldots,C_{k}^{(i-1)}))\)
11:\(\triangleright\) update representatives with DBA \(\triangleleft\)\(\triangleright\)
12:if\((C_{1}^{(i)},\ldots,C_{k}^{(i)})\approx(C_{1}^{(i-1)},\ldots,C_{k}^{(i-1)})\)then
13:break\(\triangleright\)\(k\)-means converged to a \(k\)-clustering \(\triangleleft\)
14:endif
15:endfor
16:return\((C_{1},\ldots,C_{k})\)
```  
**Algorithm 3**\(k\)-Means Clustering  
In the following (and unless stated otherwise), we consider a dataset \(\mathcal{X}=\{X_{1},\ldots,X_{N}\}\) of \(N\) univariate time series, where each time series \(X=((x_{1},t_{1}),\ldots,(x_{T},t_{T}))\in\mathcal{X}\) consists of \(T\) data points.