Proper length motif discovery for time series data using MDL principle

Abstract

As one of the most essential data mining tasks, finding of frequently occurring patterns, i.e., motif discovery, has drawn a lot of attention in the past decade. Despite successes in speedup of motif discovery, most of the existing algorithms still require predefined parameters. The critical and most cumbersome one is time series motif length since it is difficult to manually determine the proper length of the motifs—even for the domain experts. In addition, with variability in the motif lengths, ranking among these motifs becomes another major problem, not to mention possible redundancy of sub-motifs. Ultimately, running all possible ranges of parameter is computationally expensive. There are some attempts to deal with the parameter issue. However, they cannot truly eliminate parameters. There is a work that is considered the first parameter-free motif discovery, but it is not as efficient due to scalability problem and solution quality. These problems inspired this work to introduce a novel parameter-free time series motif discovery based on MDL (Minimum Description Length) principle. This work requires no parameter as input. The output is ranked classes of motifs or “K-compression Motif,” that are based on MDL principle. The experiments have been designed to correspond to the objectives: parameter-freeness, correctness, and speed. The proposed algorithm manages to discover proper length of motifs with consistently high accuracy. In addition, the proposed algorithm manages to discover “unexpected” motifs of time series. As for speed, the proposed algorithm is a few magnitudes faster than previous work.