Editing for the k-nearest neighbors rule by a genetic algorithm

EEkNN: k-Nearest Neighbor Classifier with an Evidential Editing Procedure for Training Samples

The k-nearest neighbor (kNN) rule is one of the most popular classification algorithms applied in many fields because it is very simple to understand and easy to design. However, one of the major problems encountered in using the kNN rule is that all of the training samples are considered equally important in the assignment of the class label to the query pattern. In this paper, an evidential editing version of the kNN rule is developed within the framework of belief function theory. The proposal is composed of two procedures. An evidential editing procedure is first proposed to reassign the original training samples with new labels represented by an evidential membership structure, which provides a general representation model regarding the class membership of the training samples. After editing, a classification procedure specifically designed for evidently edited training samples is developed in the belief function framework to handle the more general situation in which the edited training samples are assigned dependent evidential labels. Three synthetic datasets and six real datasets collected from various fields were used to evaluate the performance of the proposed method. The reported results show that the proposal achieves better performance than other considered kNN-based methods, especially for datasets with high imprecision ratios.

A scalable memetic algorithm for simultaneous instance and feature selection

Instance selection is becoming increasingly relevant due to the huge amount of data that is constantly produced in many fields of research. At the same time, most of the recent pattern recognition problems involve highly complex datasets with a large number of possible explanatory variables. For many reasons, this abundance of variables significantly harms classification or recognition tasks. There are efficiency issues, too, because the speed of many classification algorithms is largely improved when the complexity of the data is reduced. One of the approaches to address problems that have too many features or instances is feature or instance selection, respectively. Although most methods address instance and feature selection separately, both problems are interwoven, and benefits are expected from facing these two tasks jointly. This paper proposes a new memetic algorithm for dealing with many instances and many features simultaneously by performing joint instance and feature selection. The proposed method performs four different local search procedures with the aim of obtaining the most relevant subsets of instances and features to perform an accurate classification. A new fitness function is also proposed that enforces instance selection but avoids putting too much pressure on removing features. We prove experimentally that this fitness function improves the results in terms of testing error. Regarding the scalability of the method, an extension of the stratification approach is developed for simultaneous instance and feature selection. This extension allows the application of the proposed algorithm to large datasets. An extensive comparison using 55 medium to large datasets from the UCI Machine Learning Repository shows the usefulness of our method. Additionally, the method is applied to 30 large problems, with very good results. The accuracy of the method for class-imbalanced problems in a set of 40 datasets is shown. The usefulness of the method is also tested using decision trees and support vector machines as classification methods.

OligoIS: Scalable Instance Selection for Class-Imbalanced Data Sets

In current research, an enormous amount of information is constantly being produced, which poses a challenge for data mining algorithms. Many of the problems in extremely active research areas, such as bioinformatics, security and intrusion detection, or text mining, share the following two features: large data sets and class-imbalanced distribution of samples. Although many methods have been proposed for dealing with class-imbalanced data sets, most of these methods are not scalable to the very large data sets common to those research fields. In this paper, we propose a new approach to dealing with the class-imbalance problem that is scalable to data sets with many millions of instances and hundreds of features. This proposal is based on the divide-and-conquer principle combined with application of the selection process to balanced subsets of the whole data set. This divide-and-conquer principle allows the execution of the algorithm in linear time. Furthermore, the proposed method is easy to implement using a parallel environment and can work without loading the whole data set into memory. Using 40 class-imbalanced medium-sized data sets, we will demonstrate our method's ability to improve the results of state-of-the-art instance selection methods for class-imbalanced data sets. Using three very large data sets, we will show the scalability of our proposal to millions of instances and hundreds of features.

Prototype selection for nearest neighbor classification: taxonomy and empirical study

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.

DIAGNOSE EFFECTIVE EVOLUTIONARY PROTOTYPE SELECTION USING AN OVERLAPPING MEASURE

Evolutionary prototype selection has shown its effectiveness in the past in the prototype selection domain. It improves in most of the cases the results offered by classical prototype selection algorithms but its computational cost is expensive. In this paper, we analyze the behavior of the evolutionary prototype selection strategy, considering a complexity measure for classification problems based on overlapping. In addition, we have analyzed different k values for the nearest neighbour classifier in this domain of study to see its influence on the results of PS methods. The objective consists of predicting when the evolutionary prototype selection is effective for a particular problem, based on this overlapping measure.

A Survey on Evolutionary Instance Selection and Generation

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.

Supervised pattern recognition for the prediction of contrast-enhancement appearance in brain tumors from multivariate magnetic resonance imaging and spectroscopy

OBJECTIVE

The purpose of this study was to develop a pattern classification algorithm for use in predicting the location of new contrast-enhancement in brain tumor patients using data obtained via multivariate magnetic resonance (MR) imaging from a prior scan. We also explore the use of feature selection or weighting in improving the accuracy of the pattern classifier.

METHODS AND MATERIALS

Contrast-enhanced MR images, perfusion images, diffusion images, and proton spectroscopic imaging data were obtained from 26 patients with glioblastoma multiforme brain tumors, divided into a design set and an unseen test set for verification of results. A k-NN algorithm was implemented to classify unknown data based on a set of training data with ground truth derived from post-treatment contrast-enhanced images; the quality of the k-NN results was evaluated using a leave-one-out cross-validation method. A genetic algorithm was implemented to select optimal features and feature weights for the k-NN algorithm. The binary representation of the weights was varied from 1 to 4 bits. Each individual parameter was thresholded as a simple classification technique, and the results compared with the k-NN.

RESULTS

The feature selection k-NN was able to achieve a sensitivity of 0.78+/-0.18 and specificity of 0.79+/-0.06 on the holdout test data using only 7 of the 38 original features. Similar results were obtained with non-binary weights, but using a larger number of features. Overfitting was also observed in the higher bit representations. The best single-variable classifier, based on a choline-to-NAA abnormality index computed from spectroscopic data, achieved a sensitivity of 0.79+/-0.20 and specificity of 0.71+/-0.11. The k-NN results had lower variation across patients than the single-variable classifiers.

CONCLUSIONS

We have demonstrated that the optimized k-NN rule could be used for quantitative analysis of multivariate images, and be applied to a specific clinical research question. Selecting features was found to be useful in improving the accuracy of feature weighting algorithms and improving the comprehensibility of the results. We believe that in addition to lending insight into parameter relevance, such algorithms may be useful in aiding radiological interpretation of complex multimodality datasets.

Inheritable Genetic Algorithm for Biobjective 0/1 Combinatorial Optimization Problems and its Applications

In this paper, we formulate a special type of multiobjective optimization problems, named biobjective 0/1 combinatorial optimization problem BOCOP, and propose an inheritable genetic algorithm IGA with orthogonal array crossover (OAX) to efficiently find a complete set of nondominated solutions to BOCOP. BOCOP with n binary variables has two incommensurable and often competing objectives: minimizing the sum r of values of all binary variables and optimizing the system performance. BOCOP is NP-hard having a finite number C(n, r) of feasible solutions for a limited number r. The merits of IGA are threefold as follows: 1) OAX with the systematic reasoning ability based on orthogonal experimental design can efficiently explore the search space of C(n, r); 2) IGA can efficiently search the space of C(n, r+/-1) by inheriting a good solution in the space of C(n, r); and 3) The single-objective IGA can economically obtain a complete set of high-quality nondominated solutions in a single run. Two applications of BOCOP are used to illustrate the effectiveness of the proposed algorithm: polygonal approximation problem (PAP) and the problem of editing a minimum reference set for nearest neighbor classification (MRSP). It is shown empirically that IGA is efficient in finding complete sets of nondominated solutions to PAP and MRSP, compared with some existing methods.

Comments on "Constraints on belief functions imposed by fuzzy random variables": some technical remarks on Romer/Kandel

First, we would like to thank V. Kratschmer for his validation of our results in the paper regarding the belief measure by using a topological approach. Though assertions (1) and (3) are presented in a weakened fashion, our results still remain valid, as he claims. It is true that assertion (2) has been proved by us only for Borel sets B, which have at most countable components. We were not able to prove the same result for Borel sets with uncountable components (such as the irrational numbers, for example) using our line of reasoning. We therefore applaud the proof presented by V. Kratschmer for the more general Borel sets using an interesting use of some topological properties induced by the Hansdorff metric defined on the space of closed intervals of the real numbers. This certainly makes our original approach to fuzzy data analysis combining fuzzy sets theory and Dempster-Shafer even more useful.