A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> A procedure is introduced to approximate nearest neighbor (INN) decision boundaries. The algorithm produces a selective subset of the original data so that 1) the subset is consistent, 2) the distance between any sample and its nearest selective neighbor is less than the distance from the sample to any sample of the other class, and 3) the subset is the smallest possible. <s> BIB001 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> As data warehouses grow to the point where one hundred gigabytes is considered small, the computational efficiency of data-mining algorithms on large databases becomes increasingly important. Using a sample from the database can speed up the data-mining process, but this is only acceptable if it does not reduce the quality of the mined knowledge. To this end, we introduce the "Probably Close Enough" criterion to describe the desired properties of a sample. Sampling usually refers to the use of static statistical tests to decide whether a sample is sufficiently similar to the large database, in the absence of any knowledge of the tools the data miner intends to use. We discuss dynamic sampling methods, which take into account the mining tool being used and can thus give better samples. We describe dynamic schemes that observe a mining tool's performance on training samples of increasing size and use these results to determine when a sample is sufficiently large. We evaluate these sampling methods on data from the UCI repository and conclude that dynamic sampling is preferable. <s> BIB002 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> In a previous paper the use of GAs as an editing technique for the k-nearest neighbor (k-NN) classification technique has been suggested. Here we are looking at different fitness functions. An experimental study with the IRIS data set and with a medical data set has been carried out. Best results (smallest subsets with highest test classification accuracy) have been obtained by including in the fitness function a penalizing term accounting tbr the cardinality of the reference set. (C 1997 Pattern Recognition Society. Published by Elsevier Science Ltd. k-Nearest Neighbors (k-NN) rule Genetic algorithms Fitness functions Editing strategies <s> BIB003 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> This paper presents an approach to select the optimal reference subset (ORS) for nearest neighbor classifier. The optimal reference subset, which has minimum sample size and satisfies a certain resubstitution error rate threshold, is obtained through a tabu search (TS) algorithm. When the error rate threshold is set to zero, the algorithm obtains a near minimal consistent subset of a given training set. While the threshold is set to a small appropriate value, the obtained reference subset may have reasonably good generalization capacity. A neighborhood exploration method and an aspiration criterion are proposed to improve the efficiency of TS. Experimental results based on a number of typical data sets are presented and analyzed to illustrate the benefits of the proposed method. The performances of the result consistent and non-consistent reference subsets are evaluated. <s> BIB004 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> We compare eleven methods for finding prototypes upon which to base the nearest prototype classifier. Four methods for prototype selection are discussed: Wilson+Hart (a condensation+error-editing method), and three types of combinatorial search—random search, genetic algorithm, and tabu search. Seven methods for prototype extraction are discussed: unsupervised vector quantization, supervised learning vector quantization (with and without training counters), decision surface mapping, a fuzzy version of vector quantization, c-means clustering, and bootstrap editing. These eleven methods can be usefully divided two other ways: by whether they employ pre- or postsupervision; and by whether the number of prototypes found is user-defined or “automatic.” Generalization error rates of the 11 methods are estimated on two synthetic and two real data sets. Offering the usual disclaimer that these are just a limited set of experiments, we feel confident in asserting that presupervised, extraction methods offer a better chance for success to the casual user than postsupervised, selection schemes. Finally, our calculations do not suggest that methods which find the “best” number of prototypes “automatically” are superior to methods for which the user simply specifies the number of prototypes. © 2001 John Wiley & Sons, Inc. <s> BIB005 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> This paper presents a new approach to the selection of prototypes for the nearest neighbor rule which aims at obtaining an optimal or close-to-optimal solution. The problem is stated as a constrained optimization problem using the concept of consistency. In this context, the proposed method uses tabu search in the space of all possible subsets. Comparative experiments have been carried out using both synthetic and real data in which the algorithm has demonstrated its superiority over alternative approaches. The results obtained suggest that the tabu search condensing algorithm offers a very good tradeoff between computational burden and the optimality of the prototypes selected. <s> BIB006 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> Evolutionary algorithms are adaptive methods based on natural evolution that may be used for search and optimization. As data reduction in knowledge discovery in databases (KDDs) can be viewed as a search problem, it could be solved using evolutionary algorithms (EAs). In this paper, we have carried out an empirical study of the performance of four representative EA models in which we have taken into account two different instance selection perspectives, the prototype selection and the training set selection for data reduction in KDD. This paper includes a comparison between these algorithms and other nonevolutionary instance selection algorithms. The results show that the evolutionary instance selection algorithms consistently outperform the nonevolutionary ones, the main advantages being: better instance reduction rates, higher classification accuracy, and models that are easier to interpret. <s> BIB007 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> Instance-based learning algorithms are often faced with the problem of deciding which instances to store for use during generalization. Storing too many instances can result in large memory requirements and slow execution speed, and can cause an oversensitivity to noise. This paper has two main purposes. First, it provides a survey of existing algorithms used to reduce storage requirements in instance-based learning algorithms and other exemplar-based algorithms. Second, it proposes six additional reduction algorithms called DROP1–DROP5 and DEL (three of which were first described in Wilson & Martinez, 1997c, as RT1–RT3) that can be used to remove instances from the concept description. These algorithms and 10 algorithms from the survey are compared on 31 classification tasks. Of those algorithms that provide substantial storage reduction, the DROP algorithms have the highest average generalization accuracy in these experiments, especially in the presence of uniform class noise. <s> BIB008 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> The basic nearest neighbour classifier suffers from the indiscriminate storage of all presented training instances. With a large database of instances classification response time can be slow. When noisy instances are present classification accuracy can suffer. Drawing on the large body of relevant work carried out in the past 30 years, we review the principle approaches to solving these problems. By deleting instances, both problems can be alleviated, but the criterion used is typically assumed to be all encompassing and effective over many domains. We argue against this position and introduce an algorithm that rivals the most successful existing algorithm. When evaluated on 30 different problems, neither algorithm consistently outperforms the other: consistency is very hard. To achieve the best results, we need to develop mechanisms that provide insights into the structure of class definitions. We discuss the possibility of these mechanisms and propose some initial measures that could be useful for the data miner. <s> BIB009 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> Storing and using specific instances improves the performance of several supervised learning algorithms. These include algorithms that learn decision trees, classification rules, and distributed networks. However, no investigation has analyzed algorithms that use only specific instances to solve incremental learning tasks. In this paper, we describe a framework and methodology, called instance-based learning, that generates classification predictions using only specific instances. Instance-based learning algorithms do not maintain a set of abstractions derived from specific instances. This approach extends the nearest neighbor algorithm, which has large storage requirements. We describe how storage requirements can be significantly reduced with, at most, minor sacrifices in learning rate and classification accuracy. While the storage-reducing algorithm performs well on several real-world databases, its performance degrades rapidly with the level of attribute noise in training instances. Therefore, we extended it with a significance test to distinguish noisy instances. This extended algorithm's performance degrades gracefully with increasing noise levels and compares favorably with a noise-tolerant decision tree algorithm. <s> BIB010 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> In this paper, we propose a new data reduction algorithm that iteratively selects some samples and ignores others that can be absorbed, or represented, by those selected. This algorithm differs from the condensed nearest neighbor (CNN) rule in its employment of a strong absorption criterion, in contrast to the weak criterion employed by CNN; hence, it is called the generalized CNN (GCNN) algorithm. The new criterion allows GCNN to incorporate CNN as a special case, and can achieve consistency, or asymptotic Bayes-risk efficiency, under certain conditions. GCNN, moreover, can yield significantly better accuracy than other instance- based data reduction methods. We demonstrate the last claim through experiments on five datasets, some of which contain a very large number of samples. <s> BIB011 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> Prototype selection problem consists of reducing the size of databases by removing samples that are considered noisy or not influential on nearest neighbour classification tasks. Evolutionary algorithms have been used recently for prototype selection showing good results. However, due to the complexity of this problem when the size of the databases increases, the behaviour of evolutionary algorithms could deteriorate considerably because of a lack of convergence. This additional problem is known as the scaling up problem. Memetic algorithms are approaches for heuristic searches in optimization problems that combine a population-based algorithm with a local search. In this paper, we propose a model of memetic algorithm that incorporates an ad hoc local search specifically designed for optimizing the properties of prototype selection problem with the aim of tackling the scaling up problem. In order to check its performance, we have carried out an empirical study including a comparison between our proposal and previous evolutionary and non-evolutionary approaches studied in the literature. The results have been contrasted with the use of non-parametric statistical procedures and show that our approach outperforms previously studied methods, especially when the database scales up. <s> BIB012 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> Artificial immune system (AIS)-based pattern classification approach is relatively new in the field of pattern recognition. The study explores the potentiality of this paradigm in the context of prototype selection task that is primarily effective in improving the classification performance of nearest-neighbor (NN) classifier and also partially in reducing its storage and computing time requirement. The clonal selection model of immunology has been incorporated to condense the original prototype set, and performance is verified by employing the proposed technique in a practical optical character recognition (OCR) system as well as for training and testing of a set of benchmark databases available in the public domain. The effect of control parameters is analyzed and the efficiency of the method is compared with another existing techniques often used for prototype selection. In the case of the OCR system, empirical study shows that the proposed approach exhibits very good generalization ability in generating a smaller prototype library from a larger one and at the same time giving a substantial improvement in the classification accuracy of the underlying NN classifier. The improvement in performance has been statistically verified. Consideration of both OCR data and public domain datasets demonstrate that the proposed method gives results better than or at least comparable to that of some existing techniques. <s> BIB013 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> The use of Evolutionary Algorithms to perform data reduction tasks has become an effective approach to improve the performance of data mining algorithms. Many proposals in the literature have shown that Evolutionary Algorithms obtain excellent results in their application as Instance Selection and Instance Generation procedures. The purpose of this paper is to present a survey on the application of Evolutionary Algorithms to Instance Selection and Generation process. It will cover approaches applied to the enhancement of the nearest neighbor rule, as well as other approaches focused on the improvement of the models extracted by some well-known data mining algorithms. Furthermore, some proposals developed to tackle two emerging problems in data mining, Scaling Up and Imbalance Data Sets, also are reviewed. <s> BIB014 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> Instance selection is becoming increasingly relevant because of the large amount of data that is constantly being produced in many fields of research. Two basic approaches exist for instance selection: instance selection as a method for prototype selection for instance-based methods (such as k-nearest neighbors) and instance selection for obtaining the training set for classifiers that require a learning process (such as decision trees or neural networks). In this paper, we review the methods that have been developed thus far for the latter approach within the field of evolutionary computation. Different groups of learning algorithms require different instance selectors to suit their learning/search biases. This requirement may render many instance selection algorithms useless if their philosophy of design is not suitable for the problem at hand. Evolutionary algorithms do not assume any structure of the data or any behavior of the classifier but instead adapt the instance selection to the performance of the classifier. They are therefore very suitable for training set selection. The main algorithms that have been developed for decision trees, artificial neural networks, and other classifiers are presented. We also discuss the relevant issue of the scalability of these methods to very large datasets. Although current algorithms are useful for fairly large datasets, scaling problems are found when the number of instances is in the hundreds of thousands or millions. © 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011 1 512–523 DOI: 10.1002/widm.44 <s> BIB015 </s> A survey on pre-processing techniques: Relevant issues in the context of environmental data mining <s> Wrapper instance selection <s> The nearest neighbor classifier is one of the most used and well-known techniques for performing recognition tasks. It has also demonstrated itself to be one of the most useful algorithms in data mining in spite of its simplicity. However, the nearest neighbor classifier suffers from several drawbacks such as high storage requirements, low efficiency in classification response, and low noise tolerance. These weaknesses have been the subject of study for many researchers and many solutions have been proposed. Among them, one of the most promising solutions consists of reducing the data used for establishing a classification rule (training data) by means of selecting relevant prototypes. Many prototype selection methods exist in the literature and the research in this area is still advancing. Different properties could be observed in the definition of them, but no formal categorization has been established yet. This paper provides a survey of the prototype selection methods proposed in the literature from a theoretical and empirical point of view. Considering a theoretical point of view, we propose a taxonomy based on the main characteristics presented in prototype selection and we analyze their advantages and drawbacks. Empirically, we conduct an experimental study involving different sizes of data sets for measuring their performance in terms of accuracy, reduction capabilities, and runtime. The results obtained by all the methods studied have been verified by nonparametric statistical tests. Several remarks, guidelines, and recommendations are made for the use of prototype selection for nearest neighbor classification. <s> BIB016
The selection criterion is based on the accuracy obtained by a model mined with the considered instances. Usually, those instances not contributing to the accuracy of the model are the candidates to be discarded from the training set. Most of the wrapper methods proposed in the literature are based on the k-NN classifier BIB016 . This is the case of Condensed Nearest Neighbor (CNN)  , one of the oldest, the SNN (Selective Nearest Neighbor rule) method BIB001 , and the Generalized Condensed Nearest Neighbor rule (GCNN) BIB011 . Other early instance selection methods focused on discarding noisy instances in the training set, like the Edited Nearest Neighbor method  and some variations like the all k-NN method  and the Multiedit method  . The IB2 and IB3 (Instance Based) methods were proposed by BIB010 , which are incremental methods. Other methods related to k-NN are those proposed by BIB008 : DROP1, DROP2, DROP5 (Decremental Reduction Optimization Procedure), which are based on the concept of associates. The associates of an instance i are those instances such that i is one of their k nearest neighbors. Another method related to the associates concept was the Iterative Case Filtering algorithm (ICF) proposed by BIB009 . In addition, evolutionary algorithms have been used for instance selection BIB005 BIB007 BIB014 BIB015 BIB003 . In BIB012 it was proposed a memetic algorithm, combining evolutionary algorithms and local search in the evolutive process, and BIB013 proposed the Clonal selection Algorithm (CSA), which is based on the artificial immune system approach. Finally, some authors proposed the taboo search for the selection of the instances BIB006 BIB004 . A special wrapper method is the Windowing method BIB002  , which uses a percentage of random instances to make the initial selection process, followed by feedback guidance; the selected data is mined (under a classifier/predictive model) and the inducted model is applied on the remaining data. Those which have not been correctly predicted are added to the selected dataset and the process is repeated. It could save up to 20% of the data.