Clustering is ubiquitous in data analysis, including analysis of time series. It is inherently subjective: different users may prefer different clusterings for a particular dataset. Semi-supervised clustering addresses this by allowing the user to provide examples of instances that should (not) be in the same cluster. This paper studies semi-supervised clustering in the context of time series. We show that COBRAS, a state-of-the-art active semi-supervised clustering method, can be adapted to this setting. We refer to this approach as COBRASTS. An extensive experimental evaluation supports the following claims: (1) COBRASTS far outperforms the current state of the art in semi-supervised clustering for time series, and thus presents a new baseline for the field; (2) COBRASTS can identify clusters with separated components; (3) COBRASTS can identify clusters that are characterized by small local patterns; (4) actively querying a small amount of semi-supervision can greatly improve clustering quality for time series; (5) the choice of the clustering algorithm matters (contrary to earlier claims in the literature).
In contrast to the wealth of papers on semi-supervised clustering of attribute-value data, only one method has been proposed specifically for semi-supervised time series clustering. cDTW SS @cite_14 uses pairwise constraints to tune the warping width parameter @math in constrained DTW. cDTW SS is also an active clustering method, as it comes with a strategy to select the pairwise queries that are most informative for tuning @math . We compare COBRAS TS to this method in the experiments.
@cite_14
2532798634
The research community seems to have converged in agreement that for time series classification problems, Dynamic Time Warping (DTW)-based nearest-neighbor classifiers are exceptionally hard to beat. Obtaining the best performance from DTW requires setting its only parameter, the warping window width (w). This is typically set by cross validation in the training stage. However, for clustering, by definition we do not have access to such labeled data. This issue seems to have been largely ignored in the literature, with many practitioners simply assuming that "the larger the better" for the value of w, and using as large a value of w as computational resources permit. In this work we show that this is a naive approach which in most circumstances produces inferior clusterings. To address this problem, we introduce a novel semi-supervised technique that allows us to set the best value of w. Unlike virtually all other semi-supervised techniques, our ideas are completely independent of the clustering algorithm used, and can be utilized to improve time series clustering under partitional, hierarchical, spectral or density-based clustering. Our approach requires very little human intervention; moreover, we show that in many cases, true human annotation efforts can be replaced with automatically-generated "pseudo" supervision information. We demonstrate our technique by testing with more than one hundred publicly available datasets.