Finding Discriminative Subsequences Via a Coverage Measure and Mutual Information Selection Strategy for Multi-Class Time Series Classification

Abstract

Abstract Time series classification (TSC) has attracted considerable attention from the data mining community over the past decades. One of the effective ways to handle this task is to find discriminative subsequences in time series to train a classifier. Obviously, how to measure the discriminative power of subsequences and find the optimal combination of subsequences is crucial to the accuracy of TSC. In this paper, we introduce a new method, CRMI, to find high-quality discriminative subsequences for multi-class time series classification (MC-TSC). Different from existing methods, there are two significant innovations in the work. At first, we propose a novel measure, named coverage ratio, to evaluate the discriminative power of a subsequence based on a coverage matrix which is figured out by the clustering technique. Second, a heuristic algorithm based on mutual information (MI) is proposed to find the optimal combination of subsequence candidates. The calculation of MI is also based on the coverage matrix. Extensive experiments were conducted on 54 UCR time series datasets with at least 3 categories, and the results show that (1) the proposed algorithm achieves the highest average accuracy and outperforms most of the existing shapelet-based TSC algorithms; (2) compared with existing methods, the proposed algorithm performs better on datasets with a large number of categories.

Keywords

• Multi-class time series classification
• Discriminative subsequence
• Coverage ratio
• Mutual information
• Clustering