| Description: | Rakthanmanon and Keogh propose an extension of the decision tree shapelet approach that speeds up shapelet discovery. Instead of a full enumerative search at each node, the fast shapelets algorithm discretises and approximates the shapelets. Specifically, for each possible shapelet length, a dictionary of SAX words is first formed. The dimensionality of the SAX dictionary is reduced through masking randomly selected letters (random projection). Multiple random projections are performed, and a frequency count histogram is built for each class. A score for each SAX word can be calculated based on how well these frequency tables discriminate between classes. The $k$-best SAX words are selected then mapped back to the original shapelets, which are assessed using information gain in a way identical to that used in 'Time Series Shapelets'. Algorithm 9 gives a modular overview. |
