# Comparison of Instance Selection and Construction Methods with Various Classifiers
## 2 Research Background
### Instance Selection and Construction Methods Overview  
One of the most important properties of data filtering methods is the relation between instances in the original training set \(\mathbf{T}\) and the in the selected prototype set \(\mathbf{P}\). If \(\mathbf{P}\subset\mathbf{T}\) then the methods are called instance selection algorithms, because the prototypes \(\mathbf{P}\) are selected directly from the training set \(\mathbf{T}\). This property does not hold for prototype construction also called prototype generation methods. In this case the elements of \(\mathbf{P}\) are new vectors which can constitute completely new instances, which have never appeared in \(\mathbf{T}\). This property is important considering the comprehensibility of the selected samples. In the case of instance selection methods the instances can be mapped into real objects, while in the case of instance construction methods the direct mapping is not possible. This is especially important when working with prototype-based rules [2; 12], or other interpretable models. In the literature perhaps the best overview of instance selection methods can be found in Reference [13] where the authors provide a taxonomy of over 70 instance selection methods, and empirically compare half of them in terms of compression and prediction performance of 1-NN classifier. The same group of authors of Reference [14] perform a similar analysis for prototype generation methods where 32 methods are discussed and 18 of them are empirically compared in application only for 1-NN classifier. The taxonomy of data filtering methods can be presented in the following aspects:  
* **search direction*
* **incremental**, when given method starts from an empty set \(\mathbf{P}\) and iteratively adds new samples, such as in \(CNN\)[15] or \(IB2\)[16]
* **decremental**, when a given method starts from \(\mathbf{P}=\mathbf{T}\) and then samples from \(\mathbf{P}\) are iteratively removed such as in _HMN-E_ and _HMN-EI_[17], _MSS_[18], _Drop1_, _Drop2_, _Drop3_ and _Drop5_[19], _RENN_[20]. * **batch**, when the instances are removed at once after analysis of the input training set. An examples of such methods are _ENN_[21], _All-kNN_[20]_ RNGE_[22], _ICF_[23], _CCIS_[24]. * **fixed**, when a fixed number of prototypes is given as the hyperparamter of the method. This group includes _LVQ_ (_LVQ1_, _LVQ2.1_, _GLVQ_) family [25; 26], _k-Means_ and random sampling. * **type of selection*
* **condensation**, when the algorithm tries to remove samples, which are located far from the decision boundary, as in the case of \(IB2\), \(CNN\), _Drop1_ and _Drop2_, _MSS_. * **edition**, when the algorithm is designed for noise removal, such as _ENN_, _RENN_, _All-kNN_, _HMN-E_. * **hybrid**, when the algorithm performs both steps--condensation and edition. Usually these methods starts from noise removal, and then perform condensation. This group includes: _Drop3_, _Drop5_, _ICF_, _HMN-EI_. * **the evaluation method*
* **filters**, where the method uses internal heuristic independent to the final classifier. * **wrappers**, when external dedicated classifier is used to identify important samples. The decision of assigning an algorithm to the right evaluation method depends on the final prediction model applied after data filtering. If the instance selection or construction method is followed by 1-NN or _k_NN classifier they can be considered as wrappers, because internally all of them use a kind of nearest neighbor based approach to decide whether an instance should be selected or rejected. On the other hand they can be also considered as filters, when the data filter takes as input entire training set and returns selected subset which is then used to train any classifier, notonly the \(k\)NN. There are implementations which works as wrappers, so they allow to use all kind of classifiers such as in Reference [27], where instead of \(k\)NN any other classifier can be used, in particular the MLP neural network was used. The drawback of the wrappers is the increase of computational complexity.