# A Framework for the Detection of Search and Rescue Patterns Using Shapelet Classification
## 2 Related Work
### GENetic DIscovery of Shapelets  
As described in the previous paragraphs, in the case of time series classification, shapelets can be considered as subseries that are discriminative for a certain class. Similarly, in vessel trajectories classification, shapelets are important sub-trajectories within a trajectory and in our case are the parts of trajectory that can be used for discriminating between the various SAR maneuvers. The projection of a dataset comprising normal and SAR trajectories to a new feature space, where each feature corresponds to the distance from a certain shapelet, allows any classifier to be used for this task. GENDIS (GENDIS is available as an open source Python project at [[https://github.com/IBCNServices/GENDIS](https://github.com/IBCNServices/GENDIS)]([https://github.com/IBCNServices/GENDIS](https://github.com/IBCNServices/GENDIS))) is an implementation of a genetic algorithm for extracting the most discriminating shapelets from a dataset comprising time-series from two or more classes. According to its author _\"The algorithm is insensitive to its parameters (such as population size, crossover and mutation probability,...) and can quickly extract a small set of shapelets that is able to achieve predictive performances similar (or better) to that of other shapelet techniques.\"_  
More specifically, GENDIS takes as input the training data, which comprises one set of time-series for each class and applies a genetic algorithm that extracts the representative shapelets per class. The genetic extractor starts with creating an initial population comprising randomly selected shapelets (i.e., sub-series) from the input time-series sets. The shapelets are then evaluated on their ability to separate instances from different classes using the cross-entropy loss fitness function. The best shapelets survive to the next generation, where cross-over and mutation is applied to fill the remaining places. Random shapelets are added and removed at each iteration and Gaussian noise is added to the randomly inserted shapelets in order to increase population variety. At the end of this training process (i.e., if the best fitness score remains the same for several iterations or if the maximum number of iterations has been met) the extracted model comprises the representative shapelets (for all classes) for the specific classification task. By applying the extracted model (shapelet feature set) on unknown time-series, GENDIS produces a distance matrix of size \(N\times M\), where \(N\) is the number of classes in the classification task and \(M\) is the number of the extracted shapelets. The matrix comprises the distances (using Euclidian distance) of every time series from every shapelet. Although the way this distance is calculated is not the subject of this research, it gives a strong evidence that modern and more sophisticated algorithmsfor this calculation can produce better results. The produced matrices are the representations of the time-series in the shapelet feature space and can be fitted into a plethora classifications machine learning algorithms. As discussed at Section 4 even with a simple classifier such as Logistic Regression, high accuracy scores can be achieved in a cross validation experiment on the training trajectory dataset. However, the use of more sophisticated classifiers will probably lead to even better classification models and will produce better results. An advantage of GENDIS over other algorithms that are used for time-series classification (a long list of algorithms and implementations can be found at the Timeseries Classification website: [[http://timeseriesclassification.com/code.php](http://timeseriesclassification.com/code.php)]([http://timeseriesclassification.com/code.php](http://timeseriesclassification.com/code.php))) is that it seems more appropriate for handling noisy time-series and time-series in which the same patterns is repeated at a different scale in time, as is the case with SAR maneuvers, which can vary in scale depending on the vessel type.