A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <s> In this paper we describe a method for hybridizing a genetic algorithm and a k nearest neighbors classification algorithm. We use the genetic algorithm and a training data set to learn real-valued weights associated with individual attributes in the data set. We use the k nearest neighbors algorithm to classify new data records based on their weighted distance from the members of the training set. We applied our hybrid algorithm to three test cases. Classification results obtained with the hybrid algorithm exceed the performance of the k nearest neighbors algorithm in all three cases. <s> BIB001 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <s> Selecting a set of features which is optimal for a given task is a problem which plays an important role in wide variety of contexts including pattern recognition, adaptive control and machine learning. Experience with traditional feature selection algorithms in the domain of machine learning leads to an appreciation for their computational efficiency and a concern for their brittleness. The authors describe an alternative approach to feature selection which uses genetic algorithms as the primary search component. Results are presented which suggested that genetic algorithms can be used to increase the robustness of feature selection algorithms without a significant decrease in compuational efficiency. <s> BIB002 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <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> BIB003 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <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> BIB004 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <s> From the Publisher: ::: The book can be used by researchers and graduate students in machine learning, data mining, and knowledge discovery, who wish to understand techniques of feature extraction, construction and selection for data pre-processing and to solve large size, real-world problems. The book can also serve as a reference book for those who are conducting research about feature extraction, construction and selection, and are ready to meet the exciting challenges ahead of us. <s> BIB005 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <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> BIB006 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <s> The majority of ensemble creation algorithms use the full set of available features for its task. Feature selection for ensemble creation has not been carried out except for some work on random feature selection. In this paper we focus our attention on genetic based feature selection for ensemble creation. Our approach uses a genetic algorithm to search over the entire feature space. Subsets of features are used as input for ensemble creation algorithms. In this paper we compare boosting and bagging techniques for ensemble construction together with feature selection approaches. Also we compared the memory employed for the ensembles using the well-known C4.5 induction algorithm for ensemble construction. Our approach show more reliable ensembles with less than 50% of the total number of features employed. <s> BIB007 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <s> In this paper, we review the feature selection problem in mining issues. The application of soft computing techniques to data mining and knowledge discovery is now emerging in order to enhance the effectiveness of the traditional classification methods coming from machine learning. A survey of the approaches presented in the literature to select relevant features by using genetic algorithms is given. The different values of the genetic parameters utilized as well as the fitness functions are compared. A more detailed review of the proposals in the mining fields of databases, text and the Web is also given. <s> BIB008 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Genetic Algorithms (GAs) for Data Preprocessing <s> Abstract A comparative study of algorithms for large-scale feature selection (where the number of features is over 50) is carried out. In the study, the goodness of a feature subset is measured by leave-one-out correct-classification rate of a nearest-neighbor (1-NN) classifier and many practical problems are used. A unified way is given to compare algorithms having dissimilar objectives. Based on the results of many experiments, we give guidelines for the use of feature selection algorithms. Especially, it is shown that sequential floating search methods are suitable for small- and medium-scale problems and genetic algorithms are suitable for large-scale problems. <s> BIB009
As discussed in section 2.3.1, one of the key problems in preparing a data set for mining is the attribute selection problem. In the context of the classification task, this problem consists of selecting, among all available attributes, a subset of attributes relevant for predicting the value of the goal attribute. The use of GAs for attribute selection seems natural. The main reason is that the major source of difficulty in attribute selection is attribute interaction, and one of the strengths of GAs is that they usually cope well with attribute interactions. In addition, the problem definition lends itself to a very simple, natural genetic encoding, where each individual represents a candidate attribute subset (a candidate solution, in this problem). More precisely, we can represent a candidate attribute subset as a string with m binary genes, where m is the number of attributes and each gene can take on the values 1 or 0, indicating whether or not the corresponding attribute is in the candidate attribute subset. For instance, assuming a 5-attribute data set, the individual "0 1 1 0 0" corresponds to a candidate solution where only the second and third attributes are selected to be given to the classification algorithm. Then, a simple GA, using conventional crossover and mutation operators, can be used to evolve the population of candidate solutions towards a good attribute subset. The "trick" is to use a fitness function that is a direct measure of the performance achieved by the classification algorithm accessing only the attributes selected by the corresponding individual. With respect to the categorization of wrapper and filter approaches for attribute selection discussed in section 2.3.1, this approach is clearly an instance of the wrapper approach. Note that in the above simple encoding scheme an attribute is either selected or not, but there is no information about the relative relevance of each attribute. It is possible to use an alternative encoding scheme where highly relevant attributes will tend to be replicated in the genome. This replication will tend to reduce the probability that a highly relevant attribute be removed from the individual due, for instance, to a harmful mutation. Such an alternative encoding scheme was proposed by Cherkauer & Shavlik BIB003 . In their scheme, each gene of an individual contains either an attribute A i , i=1,...,m, or no attribute, denoted by 0. The length of the individual is fixed, but it is not necessarily equal to m, the number of attributes. An attribute is selected if it occurs at least once in the individual. For instance, assuming a 10-attribute data set and a 5-gene string, the individual "0 A 8 0 A 8 A 4 " represents a candidate solution where only attributes A 8 and A 4 are selected to be given to the classification algorithm. Note that this example suggests an intriguing possibility. Suppose we are interested not only in selecting a subset of attributes, but also in determining how relevant each of the selected attributes are. In the above example perhaps we could consider that A 8 is presumably more relevant than A 4 , since the former occurs twice in the genome of the individual, whereas the latter occurs just once. In any case it is possible to use a GA to optimize attribute weights directly (assigning to an attribute a weight that is proportional to its relevance), rather than to simply select attributes. This approach has been used particularly for optimizing attribute weights for nearest neighbor algorithms BIB001 ,  . Comprehensive comparisons between GA and other attribute-selection algorithms, across a number of data sets, are reported in BIB005 and BIB009 . In these projects GA was used as a wrapper to select attributes for a constructive neural network and a nearest neighbor algorithm, respectively. Overall, the results show that GA is quite competitive with other respectable attribute-selection algorithms. In particular, the results reported in BIB009 indicate that in large-scale attributeselection problems, where the number of attributes is greater than 100, GA becomes the only practical way to get reasonable attribute subsets. In BIB006 it is reported that the use of an interactive GA for attribute selection led to the discovery of rules that are easy-to-understand and simple enough to make practical decisions on a marketing application involving oral care products. A further discussion on the use of genetic algorithms in attribute selection can be found in BIB004 , BIB002 , BIB007 , BIB008 .