RPM: Representative Pattern Mining for Efficient Time Series Classification

Abstract

Time series classication is an important problem that has received a great amount of attention by researchers and practitioners in the past two decades. In this work, we propose a novel algorithm for time series classication based on the discovery of class-specic representative patterns. We dene representative patterns of a class as a set of subsequences that has the greatest discriminative power to distinguish one class of time series from another. Our approach rests upon two techniques with linear complexity: symbolic discretization of time series, which generalizes the structural patterns, and grammatical inference, which automatically nds recurrent correlated patterns of variable length, producing an initial pool of common patterns shared by many instances in a class. From this pool of candidate patterns, our algorithm selects the most representative patterns that capture the class specicities, and that can be used to eectively discriminate between time series classes. Through an exhaustive experimental evaluation we show that our algorithm is competitive in accuracy and speed with the stateof-the-art classication techniques on the UCR time series repository, robust on shifted data, and demonstrates excellent performance on real-world noisy medical time series.