# Comparison of Instance Selection and Construction Methods with Various Classifiers
## 3 Experimental Design  
There are several factors which determine the applicability of given algorithms as a general purpose training set filter. Among the most important are compression level and prediction accuracy of the final classifier. The compression is defined as:  
\[comp=1-\frac{\left\|\mathbf{P}\right\|}{\left\|\mathbf{T}\right\|}, \tag{1}\]  
so that higher value of compression indicates that more samples were rejected and the resultant set \(\mathbf{P}\) is smaller and lower values (close to 0) indicates that the output training set is larger. The second property is the prediction accuracy of the classifier trained on \(\mathbf{P}\). This value is subjective to the applied classifier, so that for one classifier given set \(\mathbf{P}\) may result in high accuracy, while for the other the accuracy can be worse. Here a simple accuracy measure was evaluated:  
\[acc=\frac{\#\text{correctly classified samples}}{\#\text{all evaluated samples}}. \tag{2}\]  
In order to determine the applicability of instance selection and construction methods as universal training set filters we designed experiments which mimic typical use cases of training set filtering. The scheme of the data processing pipeline is presented in Figure 3  
It starts with data loading and attribute normalization, then the 10 fold cross-validation procedure is executed which wraps the data filtering stage (our instance selection or construction method) followed by classifier training and hyperparameter optimization procedure. Finally, the trained classifier is applied to the test set. During the process execution prediction accuracy and compression were recorded. In the experiments the most commonly used classifiers were evaluated. These are: the basic classifiers for which the evaluated data filters were designed such as 1-NN and \(k\)NN; simple classifiers like Naive Bayes or linear model (GLM); followed by kernel methods such as SVM with Gaussian kernel and finally the decision tree based methods including C4.5 and Random Forest. Many of these methods require careful parameter selection such as the value of \(k\) in \(k\)NN or C and \(\gamma\) in SVM or the number of trees in Random Forest. All of the evaluated parameters are presented in Table 1. It is important to note that each of the applied data filters was independently evaluated for each classifier, because a particular filter may be beneficial for one classifier and unfavorable for another. Figure 3: The pipeline of data processing used in the experiments. The entire group of instance selection and construction methods is very broad. As indicated in Section 2.2 some authors distinguish over 70 instance selection methods and over 32 prototype construction methods [13; 14]. From these groups we selected the most popular ones which can be found in many research papers as the reference methods [10; 11; 28; 29; 30]. These are _CNN_, _ENN_, _RENN_, _All-kNN_, _IB2_, _RNGE_, _Drop1_, _Drop2_, _Drop3_, _Drop5_, _ICF_, _MSS_, _HMN-E_, _HMN-EI_, _CCIS_, from the group of instance selection methods, and from the group of prototype generation methods we selected 3 algorithm from the family of _LVQ_ algorithms, these are _LVQ1_, _LVQ2.1_, as well as the _GLVQ_ algorithm. In the experiments we also evaluated _k-Means_ clustering algorithm which is most often used to reduce the size of the training set [31]. The _k-Means_ algorithm was independently applied to each class label, and then the obtained cluster centers were used as prototypes with appropriate class labels [32]. All of the prototype generation methods belong to the group of fixed methods, so they require to determine the compression manually. For that purpose the experiments were carried out for two different initial sets of prototypes: randomly selected 10% of the training samples used for initialization which corresponds to 90% compression and also 30% of the training samples which corresponds to 70% compression. The 90% compression is the lower bound of the compression obtained by most of instance selection methods.