Ensemble - based shapelet approximation

Abstract

Similarity search and classification on time series databases have received great interest over the past decade. The definition of similarity between the series is a major problem in this context. Nearest-neighbor (NN) classifiers with alternative dissimilar ity measures are widely used because of their simplicity and known success. However, these approaches compute the similarity over the whole time series which might be problematic with the long time series and relatively short features of interest. More over, NN classifiers are not directly interpretable as they do not describe why a time series is assigned to a certain class. To overcome these problems, researchers focus on discovering discriminative subsequences, namely shapelets, from the time series. In stead of pairwise distance calculations between the whole time series, shapelet-based approaches map time series to a feature vector based on the existence of the shapelets. In the recent years, shapelet discovery approaches have focused on the evaluation of the segmented subsequences in terms of their discriminative power. As this approach may be time-consuming depending on the size of the time series database, recent attempts exploit the change of time-series representations for faster discovery of shapelets. In this sense, piecewise constant approximations are shown to provide significantly faster results with a low-dimensional representation. This study proposes a novel supervised piecewise approximation to identify shapelets related to the class. After utilizing a simple piecewise linear model to characterize the time series, the segments from the model are determined to be potential candidates for shapelets. Proposed piecewise approximation scheme is notably different than the traditional methods. Ensembles of regression trees are utilized to learn a piecewise approximation to identify the shapelets in a supervised manner. Experimental results show that proposed Ensemble-based Fast Shapelet Approximation (EFSA) provides fast and competitive results on benchmark datasets from different domains.