# Data Reduction in the String Space for Efficient kNN Classification Through Space Partitioning
## 4 Experimentation
### Performance Measurement  
In order to assess and compare the different situations proposed in the experimentation, we evaluate both the classification rate achieved by each strategy as well as the resulting size of the dataset. Note that, in the context of a DR task, the former concept relates to the goodness of the reduction algorithm to extract a representative set of prototypes while the latter concepts associated with the reduction capabilities of the strategy.  
As of classification performance metric, we have considered the use of the _F-measure_ (F\({}_{1}\)) to avoid any bias towards any particular class in the case of a certain data imbalance. In a two-class classification task this metric is defined as a function of the successes and misclassifications of the algorithm as  
\[\text{F}_{1}=\frac{2\cdot\text{TP}}{2\cdot\text{TP}+\text{FP}+\text{FN}} \tag{2}\]  
where TP, FP, and FN stand for _True Positives_ or correctly classified elements, _False Positives_ or type I errors, and _False Negatives_ or type II errors, respectively.  
It must be noted that, due to the non-binary nature of our datasets, we consider the use of the macro-averaged F\({}_{1}\) score which extends the definition of the binary F\({}_{1}\) to multiclass scenarios. This measure is defined as the average of the F\({}_{1}\) scores obtained for each class, that is:  
\[\text{F}_{1}^{M}=\frac{1}{|\mathcal{Y}|}\cdot\sum_{i=1}^{|\mathcal{Y}|}\text{ F}_{1}^{(i)} \tag{3}\]  
where \(\mathcal{Y}\) represents the set of classes in the task and F\({}_{1}^{(i)}\) the value of the F\({}_{1}\) metric for class \(y_{i}\in\mathcal{Y}\).  
Reduction capabilities have been assessed comparing the resulting set sizes of the training data in the different situations proposed. Computation time was discarded as evaluation metric due to its variability depending on the load of the computing system.  
As commented, DR methods seek for simultaneously optimizing two contradictory goals, set size reduction and classification performance. Thus, it is not possible to retrieve a global optimum: some approaches will retrieve sharper reduction figures at the expense of a decrease of the classification rate while other will just show the opposite behavior.  
In this sense DR can be addressed as a Multi-objective Optimization Problem (MOP) in which the two objectives to be optimised are the aforementioned reduction capabilities and classification performance. The possible solutions under this framework are usually retrieved resorting to the concept of non-dominance: one solution is said to dominate another if it is better or equal in each goal function and, at least, strictly better in one of them. The resulting elements, typically known as non-dominated elements, constitute the so-called Pareto frontier in which all elements are optimal solutions of the problem without any hierarchy among them.  
Finally, in order to provide a single value which relates both the performance and reduction capabilities of the strategies considered, we also consider the _estimated profit per prototype_ measure defined as the ratio between the classification accuracy and the total number of distances computed [30]. It must be mentioned that, for its use in this work, this metric was slightly adapted from its original definition by considering the F\({}_{1}\) instead of the classification accuracy as well as the resulting set size instead of the number of distances computed.