Edit Distance-Based Classification of Symbol Sequences

There are many types of sequences on which classification algorithms are applied. Sequences of symbols with information on the relation between every two direct successors (referred to as link information) is one of these. A common approach for classification of such sequences is to only consider the symbols and disregard the link information. However, this can be at the expense of the quality of the classifications. In this thesis, we show how the edit distance can be used to classify sequences based on its symbols as well as its link information. The edit distance is an alignment-based pairwise dissimilarity metric. Its definition depends on the structural representation of the instances that are compared. The set of edit operations determines in which ways instances can be modified. Applying an edit operation comes with a certain edit cost that is given by its cost function. The edit distance between two instances is the least expensive sequence of edit operations that transforms the one into the other. The symbols, link information and order of a sequence can be represented by the attributed graph data structure. For every edit operation, a model of its impact has been presented. The cost function of an edit operation is based on the variable(s) on which the model of its impact relies. The cost functions are defined in the edit cost model. Using the parameters of the edit cost model, the definition of the cost functions can be controlled. The edit distance is optimized for classification by finding the values of the edit cost model's parameters that minimize the average intra-class dissimilarity and maximize the average inter-class dissimilarity. Results of experiments conducted on real and artificial data show that classifications based on the edit distance can outperform both models that only incorporate symbols and models that incorporate the symbols, link information and order of sequences. In addition, the results show that the classification performance is positively correlated with the length of the sequences. A limitation of the presented method is that optimization of the edit distance can be computationally expensive.Electrical Engineering, Mathematics and Computer ScienceIntelligent System