On the use of normalized edit distances and an efficient k-NN search technique (k-AESA) for fast and accurate string classification

Classification based on nearest neighbours (NN) is a uniformly good approach to many pattern recognition tasks. However, two important aspects need to be taken into account to actually achieve good performance in practice: 1) the metric or dissimilarity measure adopted to compare the considered patterns; and 2) the computational cost incurred by the NN searching operation. As it is shown in this paper, by using adequate techniques to cope with these two issues, the NN-based classification leads to better results than those obtained by other approaches that have been applied to a task of human banded chromosomes classification.