# Data Reduction in the String Space for Efficient kNN Classification Through Space Partitioning
## 1 Introduction  
In Pattern Recognition (PR), supervised classification is defined as the task of predicting the label of a given element out of a discrete set of categories based on the knowledge extracted from other labeled samples [1]. This discipline is largely applied in a wide variety of disciplines such as optical text or music recognition [2; 3], audio analysis [4], speech recognition [5] and image categorization [6], among many others. One of the crucial points in classification tasks is the representation considered for encoding the data. In this regard, two paradigms are typically differentiated in the literature [7]: on the one hand, the so-called _statistical representations_ represent the data as vectors of numerical descriptors which describe each element based on a collection of features; on the other hand, _structural representations_ consider powerful and flexible high-level symbolic data structures for representing the data, such as strings, trees or graphs. Thus, statistical representations show the clear advantage of being addressable by most classification algorithms while structural codifications generally exhibit superior accuracyrates but are only handled by a reduced set of algorithms [8], mainly distance-based classifiers as, for instance, the \(k\)-Nearest Neighbor rule or Support-Vector Machines (SVM) since they only require the definition of a dissimilarity measure among the data points [9]. For instance, works such as the one by [PERSON] and [PERSON] [10] for signature verification or the contribution by [PERSON] et al. [11] for handwritten music symbols recognition state the adequacy of structural approaches, and more precisely string codifications, over other data representations. As one of the most well known distance-based classifiers, the \(k\)-Nearest Neighbor (\(k\)NN) algorithm [12] is widely used in PR due to its conceptual simplicity and theoretical low errors properties [13]. This classifier assigns the most common label among the \(k\) closest elements to the input query obtained by performing pairwise dissimilarities to all the elements in the training set without deriving a classification model (lazy learning). Thus, unlike other distance-based classifiers as SVM, the \(k\)NN algorithm is usually related to low efficiency figures since the entire training data must be queried for classifying a new element [14]. Furthermore, this issue is especially noticeable in the structural space since dissimilarity metrics are generally quite complex and time-consuming. Therefore, distance-based classifiers like the \(k\)NN rule require strategies to reduce the complexity and cost of their computations, and particularly in structural domains such as string data. Data Reduction (DR) is one of the main proposals for overcoming the efficiency issues inherent to \(k\)NN [15]. This family of methods aims at obtaining a reduced set of the original training data so that the time consumption is severely reduced while the classification rate is, ideally, not affected. While several approaches have been proposed in the literature, two particular strategies stand out in the literature [16]: (i) Prototype Selection (PS) methods, which reduce the initial data by selecting a subset out of it; and (ii) Prototype Generation (PG) methods, which generate a new set of data by means of performing some transformations on the initial one. In general, PG methods obtain higher reduction figures than PS, but their applicability is severely limited by the data representation considered since the transformations required are not as straightforward to define as in statistical codifications. The difficulties associated with structural representations have hindered the development of PG methods as possible DR strategies for tackling the \(k\)NN efficiency issue in the structural space. Hence, most research efforts related to PG have been devoted to statistical representations.