Efficient Shapelet Discovery for Time Series Classification
Guozhong Li, Byron Choi, Jianliang Xu, Sourav S. Bhowmick, Kwok Pan Chun, Grace Lai‐Hung Wong
Abstract
Time-series shapelets are discriminative subsequences, recently found effective for time series classification ( <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">tsc</small> ). It is evident that the quality of shapelets is crucial to the accuracy of <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">tsc</small> . However, major research has focused on building accurate models from some shapelet candidates. To determine such candidates, existing studies are surprisingly simple, e.g., enumerating subsequences of some fixed lengths, or randomly selecting some subsequences as shapelet candidates. The major bulk of computation is then on building the model from the candidates. In this paper, we propose a novel <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">efficient shapelet discovery</i> method, called <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bspcover</small> , to discover a set of high-quality shapelet candidates for model building. Specifically, <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bspcover</small> generates abundant candidates via Symbolic Aggregate approXimation with sliding window, then prunes identical and highly similar candidates via <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Bloom filters</i> , and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">similarity matching</i> , respectively. We next propose a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><inline-formula><tex-math notation="LaTeX">$p$</tex-math><alternatives><mml:math><mml:mi>p</mml:mi></mml:math><inline-graphic xlink:href="li-ieq1-2995870.gif"/></alternatives></inline-formula>-Cover algorithm</i> to efficiently determine discriminative shapelet candidates that maximally represent each time-series class. Finally, any existing shapelet learning method can be adopted to build a classification model. We have conducted extensive experiments with well-known time-series datasets and representative state-of-the-art methods. Results show that <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bspcover</small> speeds up the state-of-the-art methods by more than 70 times, and the accuracy is often comparable to or higher than existing works.