# Comparison of Instance Selection and Construction Methods with Various Classifiers
## 2 Research Background  
### Problem Statement  
From the statistical point of view, reduction of the training set size will not affect prediction accuracy of the final classifier when the conditional probability \(P(c|\mathbf{x})\) of predicting class \(c\) for given  
Figure 1: The pipeline of prediction model construction with data filtering.  
vector \(\mathbf{x}\) remains unchanged when estimated from the original training set \(\mathbf{T}\) and from the set of prototypes \(\mathbf{P}\) obtained from the data filtering process.  
In the literature one of popular multidimensional probability estimation methods is based on the nearest neighbor approach [4]. Similarly, for \(k\)NN many data filtering methods were developed in order to select a suitable subset of the training set. These methods are called instance selection methods and instance construction or prototype generation methods, and mostly they were designed to overcome weaknesses of the \(k\)NN classifier. In instance selection, usually the performance of \(k\)NN or even 1-NN classifier is used to identify those training samples which are important for the classification. These are mostly border samples close to the decision boundary. Instances which represent larger groups of instances from the same class and noise samples are usually filtered out because they reduce the performance of \(k\)NN. On the other hand, instance construction methods tend to find optimal position of the stored samples by 1-NN, so they do not need to represent samples from the original training set, these are usually new samples. An example effect of applying instance selection methods to the training set is presented on Figure 2.  
The idea of applying instance selection and prototype generation methods as data filters is not new and it is often considered a standard preprocessing step. In particular in Reference [5] some of the instance selection methods evaluated in our study were considered as the most effective preprocessing methods.  
For example we have applied instance selection in the optimization of metallurgical processes for data size limitation and rule extraction [6; 7], but instance selection methods were also applied in haptic modeling [8] as well as for automatic machine learning [9]. However, we cannot find in the literature any comprehensive study analyzing the influence of the instance selection methods on various classifiers. Most of the authors when presenting new algorithms indicate only the performance of 1-NN, \(k\)NN with fixed \(k\) parameter, and sometimes other classifiers but usually also with fixed hyperparameters. Such a comparison can be considered unfair, because the training set is being changed during the data filtering so different parameters are required by the classifiers. Unfortunately, such a comparison requires much larger computational time especially when using grid search with internal cross-validation procedure, so the process is usually simplified and only classifiers with fixed parameters are used. Only in References [10; 11] some broader comparison is available but the experiments were conducted on only few (6 and 8) datasets. To fill that gap we provide a detailed analysis of the influence of the data based on instance selection and construction methods applied to 40 datasets.  
Figure 2: Example effect of artificial 2D training set compression using _Drop3_ instance selection methods.  
(a) Original training set with additional noise (b) Training set after compression.