# Efficient Time-Series Clustering through Sparse Gaussian Modeling
## 5 Experimental Evaluation
### Computational Efficiency  
As noted in Section 4.3, an important contribution of our work is that the combined computational complexity of our Sparse Time-Series Clustering framework is \(O(NT\log^{2}T+INk\log^{2}T)\), where \(I\) is the iterations of \(k\)-means, \(N\) is the number of time series in the dataset and \(T\) is their length, compared against a running time of \(O(INKT^{2})\) of the standard \(k\)-means algorithm applied to the original dataset. Next, we evaluate the running time and the CPU utilization of our framework in practice..  
Figure 4: Spread diagrams with comparative ARI results of Sparse Time-Series Clustering against standard \(k\)-means overall datasets for the \((\alpha T/m)\)-DTW distance, with different values of \(\alpha\in\{0,10^{-4},10^{-3},10^{-2}\}\) and with \(m=2\log_{2}T\) inducing points. The average spread and the average loss of the sparse framework are reported in the caption and on the upper left corner of each plot. We observe a slight deterioration in clustering quality as \(\alpha\) increases and a small average loss in (**e**) and (**f**), where we keep the best ARI and the mean ARI in each dataset (both across all values of \(\alpha\in\{0,10^{-4},10^{-3},10^{-2}\}\)). Table 4 displays the CPU utilization times for our framework and standard \(k\)-means on all datasets. Specifically, we provide the following metrics: \(T_{k}\) is the CPU utilization time of the standard \(k\)-means algorithm applied to the original dataset; \(T_{a}\) is the CPU utilization time of the modeling phase, where Sparse Gaussian Process Regression is applied, in steps 4-6 of Algorithm 1; and \(T_{b}\) is the CPU utilization time of the \(k\)-means algorithm in step 7 of Algorithm 1, where Algorithm 3 is applied to the sparse time series produced by the Sparse Gaussian Process Regression. Moreover, \(T_{a}+T_{b}\) is the total CPU utilization of our method, \(\left(T_{a}+T_{b}\right)/T_{k}\) indicates the CPU utilization overhead due to the modeling process (which dominates the running time of our framework); \(T_{k}/T_{b}\) quantifies how much slower \(k\)-means become when applied to the original dataset compared against the same algorithm applied to the sparsified dataset; and \(T_{a}/N\) is the average running time of the modeling phase (Sparse Gaussian Process Regression) per time series in the particular dataset. Figure 5: Spread diagrams with comparative ARI results of Sparse Time-Series Clustering against standard \(k\)-means overall datasets for the \((\alpha T/m)\)-DTW distance, with different values of \(\alpha\in\{0,10^{-4},10^{-3},10^{-2}\}\) and with \(m=5\log_{2}T\) inducing points. The average spread and the average loss of the sparse framework are reported in the caption and on the upper left corner of each plot. In contrast to the case where \(m=2\log_{2}T\), in Figure 4, with \(m=5\log_{2}T\) inducing points, we observe a stable clustering quality, and even a slight improvement, as \(\alpha\) increases. This behavior is attributed to the fact that larger \(m\) makes \((\alpha T/m)\)-DTW less sensitive to an increase in \(\alpha\). We also observe a small average gain in (**e**), where we keep the best ARI, and a small average loss in (**f**), where we take the mean ARI in each dataset (both across all values of \(\alpha\in\{0,10^{-4},10^{-3},10^{-2}\}\)).