A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> This paper introduces a hybrid learning methodology that integrates genetic algorithms (GAs) and decision tree learning (ID3) in order to evolve optimal subsets of discriminatory features for robust pattern classification. A GA is used to search the space of all possible subsets of a large set of candidate discrimination features. For a given feature subset, ID3 is invoked to produce a decision tree. The classification performance of the decision tree on unseen data is used as a measure of fitness for the given feature set, which, in turn, is used by the GA to evolve better feature sets. This GA-ID3 process iterates until a feature subset is found with satisfactory classification performance. Experimental results are presented which illustrate the feasibility of our approach on difficult problems involving recognizing visual concepts in satellite and facial image data. The results also show improved classification performance and reduced description complexity when compared against standard methods for feature selection. <s> BIB001 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> When using machine learning techniques for knowledge discovery, output that is comprehensible to a human is as important as predictive accuracy. We introduce a new algorithm, SET-GEN, that improves the comprehensibility of decision trees grown by standard C4.5 without reducing accuracy. It does this by using genetic search to select the set of input features C4.5 is allowed to use to build its tree. We test SET-GEN on a wide variety of real-world datasets and show that SET-GEN trees are significantly smaller and reference significantly fewer features than trees grown by C4.5 without using SET-GEN. Statistical significance tests show that the accuracies of SET-GEN'S trees are either not distinguishable from or are more accurate than those of the original C4.5 trees on all ten datasets tested. <s> BIB002 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> This paper describes a hybrid methodology that integrates genetic algorithms (GAs) and decision tree learning in order to evolve useful subsets of discriminatory features for recognizing complex visual concepts. A GA is used to search the space of all possible subsets of a large set of candidate discrimination features. Candidate feature subsets are evaluated by using C4.5, a decision tree learning algorithm, to produce a decision tree based on the given features using a limited amount of training data. The classification performance of the resulting decision tree on unseen testing data is used as the fitness of the underlying feature subset. Experimental results are presented to show how increasing the amount of learning significantly improves feature set evolution for difficult visual recognition problems involving satellite and facial image data. In addition, we also report on the extent to which other more subtle aspects of the Baldwin effect are exhibited by the system. <s> BIB003 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> From the Publisher: ::: With advanced computer technologies and their omnipresent usage, data accumulates in a speed unmatchable by the human's capacity to process data. To meet this growing challenge, the research community of knowledge discovery from databases emerged. The key issue studied by this community is, in layman's terms, to make advantageous use of large stores of data. In order to make raw data useful, it is necessary to represent, process, and extract knowledge for various applications. Feature Selection for Knowledge Discovery and Data Mining offers an overview of the methods developed since the 1970's and provides a general framework in order to examine these methods and categorize them. This book employs simple examples to show the essence of representative feature selection methods and compares them using data sets with combinations of intrinsic properties according to the objective of feature selection. In addition, the book suggests guidelines for how to use different methods under various circumstances and points out new challenges in this exciting area of research. Feature Selection for Knowledge Discovery and Data Mining is intended to be used by researchers in machine learning, data mining, knowledge discovery, and databases as a toolbox of relevant tools that help in solving large real-world problems. This book is also intended to serve as a reference book or secondary text for courses on machine learning, data mining, and databases. <s> BIB004 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Interactive Genetic Algorithms (IGAs) are subjective and interactive methods to evaluate the qualities of offspring generated by genetic operations. We adopt IGA in order to select relevant features in inductive learning problems. The method we propose is used to extract efficient decision knowledge from noisy questionnaire data in marketing data analysis domain. Unlike popular learning-from-example methods, in such tasks, we must interpret the characteristics of the data without clear features of the data nor pre-determined evaluation criteria. The problem is how domain experts get simple, easy-tounderstand, and accurate knowledge from noisy data. The proposed method has been qualitatively and quantitatively validated by a case study on consumer product questionnaire data: the acquired rules are simpler than the results from the direct application of inductive learning; a domain expert admits that they are easy to understand; and they are at the same level on the accuracy compared with the other statistical methods. 1 <s> BIB005 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Feature selection is a common and key problem in many classification and regression tasks. It can be viewed as a multiobjective optimisation problem, since, in the simplest case, it involves feature subset size minimisation and performance maximisation. This paper presents a multiobjective evolutionary approach for feature selection. A novel commonality-based crossover operator is introduced and placed in the multiobjective evolutionary setting. This specialised operator helps to preserve building blocks with promising performance. Selection bias reduction is achieved by resampling. We argue that this is a generic approach, which can be used in many modelling problems. It is applied to feature selection on different neural network architectures. Results from experiments with benchmarking data sets are given. <s> BIB006 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> This paper discusses a genetic-algorithm-based approach for selecting a small number of representative instances from a given data set in a pattern classification problem. The genetic algorithm also selects a small number of significant features. That is, instances and features are simultaneously selected for finding a compact data set. The selected instances and features are used as a reference set in a nearest neighbor classifier. Our goal is to improve the classification performance (i.e., generalization ability) of our nearest neighbor classifier by searching for an appropriate reference set. In this paper, we first describe the implementation of our genetic algorithm for instance and feature selection. Next we discuss the definition of a fitness function in our genetic algorithm. Then we examine the classification performance of nearest neighbor classifiers designed by our approach through computer simulations on artificial data sets and real-world data sets. <s> BIB007 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Feature Selection is a very promising optimisation strategy for Pattern Recognition systems. But, as an NP-complete task, it is extremely dificult to carry out. Past studies therefore were rather limited in either the cardinality of the feature space or the number of patterns utilised to assess the feature subset performance. ::: ::: This study examines the scalability of Distributed Genetic Algorithms to very large-scale Feature Selection. As domain of application, a classification system for Optical Characters is chosen. The system is tailored to classify hand-written digits, involving 768 binary features. Due to the vastness of the investigated problem, this study forms a step into new realms in Feature Selection for classification. ::: ::: We present a set of customisations of GAs that provide for an application of known concepts to Feature Selection problems of practical interest. Some limitations of GAs in the domain of Feature Selection are unrevealed and improvements are suggested. A widely used strategy to accelerate the optimisation process, Training Set Sampling, was observed to fail in this domain of application. ::: ::: Experiments on unseen validation data suggest that Distributed GAs are capable of reducing the problemcomplexity significantly. The results show that the classification accuracy can be maintained while reducing the feature space cardinality by about 50%. Genetic Algorithms are demonstrated to scale well to very large-scale problems in Feature Selection. <s> BIB008 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Variable and feature selection have become the focus of much research in areas of application for which datasets with tens or hundreds of thousands of variables are available. These areas include text processing of internet documents, gene expression array analysis, and combinatorial chemistry. The objective of variable selection is three-fold: improving the prediction performance of the predictors, providing faster and more cost-effective predictors, and providing a better understanding of the underlying process that generated the data. The contributions of this special issue cover a wide range of aspects of such problems: providing a better definition of the objective function, feature construction, feature ranking, multivariate feature selection, efficient search methods, and feature validity assessment methods. <s> BIB009 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> This paper addresses the issue of reducing the storage requirements on instance-based learning algorithms. Algorithms proposed by other researches use heuristics to prune instances of the training set or modify the instances themselves to achieve a reduced set of instances. This paper presents an alternative way. The presented approach proposes to induce a reduced set of prototypes (partially-defined instances) with evolutionary algorithms. Experiments were performed with GALE, a fine-grained parallel evolutionary algorithm, and other well-known reduction techniques on several data sets. Results suggest that GALE is competitive and robust for inducing sets of partially-defined instances. Moreover, it achieves better reduction rates in storage requirements without losses in generalization accuracy. Simultaneously, if the partially-defined instances induced by GALE are post-processed, results can also be used for attribute selection. <s> BIB010 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> To improve computer aided diagnosis (CAD) for CT colonography we designed a hybrid classification scheme that uses a committee of support vector machines (SVMs) combined with a genetic algorithm (GA) for variable selection. The genetic algorithm selects subsets of four features, which are later combined to form a committee, with majority vote for classification across the base classifiers. Cross validation was used to predict the accuracy (sensitivity, specificity, and combined accuracy) of each base classifier SVM. As a comparison for GA, we analyzed a popular approach to feature selection called forward stepwise search (FSS). We conclude that genetic algorithms are effective in comparison to the forward search procedure when used in conjunction with a committee of support vector machine classifiers for the purpose of colonic polyp identification. <s> BIB011 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> A nearest-neighbor classifier compares an unclassified object to a set of pre-classified examples and assigns to it the class of the most similar of them (the object's nearest neighbor). In some applications, many pre-classified examples are available and comparing the object to each of them is expensive. This motivates studies of methods to remove redundant and noisy examples. Another strand of research seeks to remove irrelevant attributes that compromise classification accuracy. The paper suggests to use the genetic algorithm to address both issues simultaneously. Experiments indicate considerable reduction of the set of examples, and of the set of attributes, without impaired classification accuracy. The algorithm compares favorably with earlier solutions. <s> BIB012 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Digital mammography is one of the most suitable methods for early detection of breast cancer. It uses digital mammograms to find suspicious areas containing benign and malignant microcalcifications. However, it is very difficult to distinguish benign and malignant microcalcifications. This is reflected in the high percentage of unnecessary biopsies that are performed and many deaths caused by late detection or misdiagnosis. A computer based feature selection and classification system can provide a second opinion to the radiologists in assessment of microcalcifications. The research proposes and investigates a neural-genetic algorithm for feature selection in conjunction with neural and statistical classifiers to classify microcalcification patterns in digital mammograms. The obtained results show that the proposed approach is able to find an appropriate feature subset and neural classifier achieves better results than two statistical models. <s> BIB013 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Publisher Summary ::: This chapter focuses on methods for discovering the genetic and environmental factors that are involved in multifactorial diseases .To do this, experiments performed at the Biological Institute of Lille, France, are used that have generated a large amount of data concerning the genetic and environmental factors associated with various common diseases. To exploit this data, advanced data-mining tools are required. The chapter describes and investigates one such tool: a two-phase optimization approach that uses an evolutionary algorithm. During the first step of this approach, significant features from a very large dataset are selected by using the evolutionary algorithm. Then, during the second step, the k-means clustering algorithm is used to pick out clusters of affected individuals according to the features selected in the first step. The specifics of the genetic factors involved in the diseases under study are described, and the evolutionary algorithm developed to address the associated feature selection problem is presented. Results on both artificial and real data are presented to validate the data. <s> BIB014 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Searching for a small subset of genes out of the thousands of genes in Microarray is a crucial problem for accurate cancer classification. In this paper, a novel gene selection method based on genetic algorithms (GAs) is proposed. In order to reduce the search space of GAs, a novel pre-selection procedure is also introduced. To evaluate the performance of the presented method, experiments on five open datasets are conducted, and the results show that it performs rather well. <s> BIB015 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> Exploiting the diversity of hypotheses produced by evolutionary learning, a new ensemble approach for Feature Selection is presented, aggregating the feature rankings extracted from the hypotheses. A statistical model is devised to enable the direct evaluation of the approach; comparative experimental results show its good behavior on non-linear concepts when the features outnumber the examples. <s> BIB016 </s> A Review of Evolutionary Algorithms for Data Mining <s> Genetic Algorithms for Attribute Selection <s> A common approach to evaluating competing models in a classification context is via accuracy on a test set or on cross-validation sets. However, this can be computationally costly when using genetic algorithms with large datasets and the benefits of performing a wide search are compromised by the fact that estimates of the generalization abilities of competing models are subject to noise. This paper shows that clear advantages can be gained by using samples of the test set when evaluating competing models. Further, that applying statistical tests in combination with Occam's razor produces parsimonious models, matches the level of evaluation to the state of the search and retains the speed advantages of test set sampling. <s> BIB017
In the attribute selection task the goal is to select, out of the original set of attributes, a subset of attributes that are relevant for the target data mining task BIB004 BIB009 . This Subsection assumes the target data mining task is classification -which is the most investigated task in the evolutionary attribute selection literature -unless mentioned otherwise. The standard individual representation for attribute selection consists simply of a string of N bits, where N is the number of original attributes and the i-th bit, i=1,. . . ,N , can take the value 1 or 0, indicating whether or not, respectively, the i-th attribute is selected. For instance, in a 10-attribute data set, the individual "1 0 1 0 1 0 0 0 0 1" represents a candidate solution where only the 1st, 3rd, 5th and 10th attributes are selected. This individual representation is simple, and traditional crossover and mutation operators can be easily applied. However, it has the disadvantage that it does not scale very well with the number of attributes. In applications with many thousands of attributes (such as text mining and some bioinformatics problems) an individual would have many thousands of genes, which would tend to lead to a slow execution of the GA. An alternative individual representation, proposed by BIB002 , consists of M genes (where M is a user-specified parameter), where each gene can contain either the index (id) of an attribute or a flag -say 0 -denoting no attribute. An attribute is considered selected if and only if it occurs in at least one of the M genes of the individual. For instance, the individual "3 0 8 3 0", where M = 5, represents a candidate solution where only the 3rd and the 8th attributes are selected. The fact that the 3rd attribute occurs twice in the previous individual is irrelevant for the purpose of decoding the individual into a selected attribute subset. One advantage of this representation is that it scales up better with respect to a large number of original attributes, since the value of M can be much smaller than the number of original attributes. One disadvantage is that it introduces a new parameter, M , which was not necessary in the case of the standard individual representation. With respect to the fitness function, GAs for attribute selection can be roughly divided into two approaches -just like other kinds of algorithms for attribute selection -namely the wrapper approach and the filter approach. In essence, in the wrapper approach the GA uses the classification algorithm to compute the fitness of individuals, whereas in the filter approach the GA does not use the classification algorithm. The vast majority of GAs for attribute selection has followed the wrapper approach, and many of those GAs have used a fitness function involving two or more criteria to evaluate the quality of the classifier built from the selected attribute subset. This can be shown in Table  1 , adapted from  , which lists the evaluation criteria used in the fitness function of a number of GAs following the wrapper approach. The columns of that table have the following meaning: Acc = accuracy; Sens, Spec = sensitivity, specificity; |Sel Attr| = number of selected attributes; |rule set| = number of discovered rules; Info. Cont. = information content of selected attributes; Attr cost = attribute costs; Subj eval = subjective evaluation of the user; |Sel ins| = number of selected instances. BIB001 yes yes BIB003 yes yes yes yes yes BIB002 yes yes yes BIB006 yes yes  yes yes  yes BIB007 yes yes yes BIB010 yes BIB011 yes BIB008 yes yes BIB015 ) yes  yes yes BIB012 yes yes yes BIB005 yes yes yes (Vafaie & DeJong 1998) yes  yes yes BIB013 ) yes A precise definition of the terms used in the titles of the columns of Table  1 can be found in the corresponding references quoted in that table. The table refers to GAs that perform attribute selection for the classification task. GAs that perform attribute selection for the clustering task can be found, e.g., in  BIB014 ). In addition, in general Table 1 refers to GAs whose individuals directly represent candidate attribute subsets, but GAs can be used for attribute selection in other ways. For instance, in BIB016 a GA is used for attribute ranking. Once the ranking has been done, one can select a certain number of top-ranked attributes, where that number can be specified by the user or computed in a more automated way. Empirical comparisons between GAs and other kinds of attribute selection methods can be found, for instance, in BIB017 Kudo & Skalansky 2000) . In general these empirical comparisons show that GAs, with their associated global search in the solution space, usually (though not always) obtain better results than local search-based attribute selection methods. In particular, (Kudo & Skalansky 2000) compared a GA with 14 nonevolutionary attribute selection methods (some of them variants of each other) across 8 different data sets. The authors concluded that the advantages of the global search associated with GAs over the local search associated with other algorithms is particularly important in data sets with a "large" number of attributes, where "large" was considered over 50 attributes in the context of their data sets.