# Comparison of Instance Selection and Construction Methods with Various Classifiers
## 1 Introduction  
Classification is one of the basic machine learning problems, with many practical applications in industry and other fields. The typical process of constructing a classifier consists of data collection, data preprocessing, training and optimizing the prediction models and finally applying the best of the evaluated models. The described scheme is obvious, however we face two types of problems. The first one is that recently we more often start to construct classifiers with limited resources and the second one is that we want to interpret and understand the data and the constructed model easily. The first group of restrictions are mostly related to time and memory constraints, where machine learning algorithms are often trained on mobile devices or micro computers like Rasberry Pi and other similar devices. There are basically three approaches to overcome these restrictions:  
* using specially tailored algorithms which are designed to face those challenge
* limiting the size of the training data
* exporting the training process from the device to the cloud or other high performance environment  
In the paper we focus on the second approach where instead of redesigning the classification algorithm or sending the data to the cloud we analyze how the data filters or in other words how the training set reduction methods influence classification performance with the data processing pipeline depicted in Figure 1.  
The data filter has two goals: first it can improve the classifier performance by eliminating noisy samples from the training data thus allowing to achieve higher classification accuracy, and the second goal is training set compression. Training set size reduction allows to speed up classifier construction process but also it speeds up decision making when the classifier is already trained [1]. The speed up in classifier training is rather obvious when the size of the input data is smaller but the speed up in the prediction phase results from smaller number of support vectors of the support vector machine, shallow trees (earlier stopping of tree construction) and lower number of reference vectors in \(k\)NN. Moreover, it speeds up model selection and optimization. Here, the gain should be multiplied by the number of evaluated classifiers and their hyper-parameters, because the filtering stage is applied once and then the classifier selection and optimization is carried out. Training set compression can be also used for solving model interpretability where the so called prototype-based rules [2; 3] can be applied. These rules are also based on limiting the size of the data. And in this case, even if the original dataset is small, further limiting dataset size is still beneficial. The main purpose of the paper and the research objective is the analysis of both aspects of data filtering that is the influence on prediction accuracy of various classifiers and the influence on training set size reduction. In the study we evaluate a set of 20 most popular instance selection and construction methods used as data filters and 7 popular classifiers on 40 datasets in terms of classification performance and training set compression. The evaluated data filters are: condensed nearest neighbor (_CNN_), edited nearest neighbor (_ENN_), repeated-edited nearest neighbor (_RENN_), _All-kNN_, instance based learning version 2 (_IB2_), relative neighbor graph editing (_RNGE_), _Drop_ family, iterative case filtering (_ICF_), modified selective subset selection (_MSS_), hit-miss network editing (_HMN-E_), hit-miss network interactive editing (_HMN-EI_), class conditional instance selection (_CCIS_) as well as learning vector quantization version 1,2.1 (respectively _LVQ1_, _LVQ2.1_), generalized learning vector quantization (_GLVQ_), _k-Means_. These data filters are selected for the evaluation, because they are the most frequently used instance selection methods.