A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems that straddle the breakeven point for computational effort Boolean parity functions determining the architecture of the program the lawnmower problem the bumblebee problem the increasing benefits of ADFs as problems are scaled up finding an impulse response function artificial ant on the San Mateo trail obstacle-avoiding robot the minesweeper problem automatic discovery of detectors for letter recognition flushes and four-of-a-kinds in a pinochle deck introduction to biochemistry and molecular biology prediction of transmembrane domains in proteins prediction of omega loops in proteins lookahead version of the transmembrane problem evolutionary selection of the architecture of the program evolution of primitives and sufficiency evolutionary selection of terminals evolution of closure simultaneous evolution of architecture, primitive functions, terminals, sufficiency, and closure the role of representation and the lens effect. Appendices: list of special symbols list of special functions list of type fonts default parameters computer implementation annotated bibliography of genetic programming electronic mailing list and public repository. <s> BIB001 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> 1 Genetic Programming as Machine Learning 2 Genetic Programming and Biology 3 Computer Science and Mathematical Basics 4 Genetic Programming as Evolutionary Computation 5 Basic ConceptsThe Foundation 6 CrossoverThe Center of the Storm 7 Genetic Programming and Emergent Order 8 AnalysisImproving Genetic Programming with Statistics 9 Different Varieties of Genetic Programming 10 Advanced Genetic Programming 11 ImplementationMaking Genetic Programming Work 12 Applications of Genetic Programming 13 Summary and Perspectives A Printed and Recorded Resources B Information Available on the Internet C GP Software D Events <s> BIB002 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> The knowledge discovery and data mining (KDD) field draws on findings from statistics, databases, and artificial intelligence to construct tools that let users gain insight from massive data sets. People in business, science, medicine, academia, and government collect such data sets, and several commercial packages now offer general-purpose KDD tools. An important KDD goal is to "turn data into knowledge". For example, knowledge acquired through such methods on a medical database could be published in a medical journal. Knowledge acquired from analyzing a financial or marketing database could revise business practice and influence a management school's curriculum. In addition, some US laws require reasons for rejecting a loan application, which knowledge from the KDD could provide. Occasionally, however, you must explain the learned decision criteria to a court, as in the recent lawsuit Blue Mountain filed against Microsoft for a mail filter that classified electronic greeting cards as spam mail. We expect more from knowledge discovery tools than simply creating accurate models as in machine learning, statistics, and pattern recognition. We can fully realize the benefits of data mining by paying attention to the cognitive factors that make the resulting models coherent, credible, easy to use, and easy to communicate to others. <s> BIB003 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <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> BIB004 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> List of Figures. List of Tables. Preface. Foreword. 1. Basic Concepts. 2. Evolutionary Algorithm MOP Approaches. 3. MOEA Test Suites. 4. MOEA Testing and Analysis. 5. MOEA Theory and Issues. 3. MOEA Theoretical Issues. 6. Applications. 7. MOEA Parallelization. 8. Multi-Criteria Decision Making. 9. Special Topics. 10. Epilog. Appendix A: MOEA Classification and Technique Analysis. Appendix B: MOPs in the Literature. Appendix C: Ptrue & PFtrue for Selected Numeric MOPs. Appendix D: Ptrue & PFtrue for Side-Constrained MOPs. Appendix E: MOEA Software Availability. Appendix F: MOEA-Related Information. Index. References. <s> BIB005 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> The use of machine learning techniques to automatically analyse data for information is becoming increasingly widespread. In this paper we examine the use of Genetic Programming and a Genetic Algorithm to pre-process data before it is classified using the C4.5 decision tree learning algorithm. The Genetic Programming is used to construct new features from those available in the data, a potentially significant process for data mining since it gives consideration to hidden relationships between features. The Genetic Algorithm is used to determine which such features are the most predictive. Using ten well-known datasets we show that our approach, in comparison to C4.5 alone, provides marked improvement in a number of cases. <s> BIB006 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> For a given data set, its set of attributes defines its data space representation. The quality of a data space representation is one of the most important factors influencing the performance of a data mining algorithm. The attributes defining the data space can be inadequate, making it difficult to discover high-quality knowledge. In order to solve this problem, this paper proposes a Genetic Programming algorithm developed for attribute construction. This algorithm constructs new attributes out of the original attributes of the data set, performing an important preprocessing step for the subsequent application of a data mining algorithm. <s> BIB007 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> We present a novel evolutionary model for knowledge discovery from texts (KDTs), which deals with issues concerning shallow text representation and processing for mining purposes in an integrated way. Its aims is to look for novel and interesting explanatory knowledge across text documents. The approach uses natural language technology and genetic algorithms to produce explanatory novel hypotheses. The proposed approach is interdisciplinary, involving concepts not only from evolutionary algorithms but also from many kinds of text mining methods. Accordingly, new kinds of genetic operations suitable for text mining are proposed. The principles behind the representation and a new proposal for using multiobjective evaluation at the semantic level are described. Some promising results and their assessment by human experts are also discussed which indicate the plausibility of the model for effective KDT. <s> BIB008 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> In this paper we use genetic programming for changing the representation of the input data for machine learners. In particular, the topic of interest here is feature construction in the learning-from-examples paradigm, where new features are built based on the original set of attributes. The paper first introduces the general framework for GP-based feature construction. Then, an extended approach is proposed where the useful components of representation (features) are preserved during an evolutionary run, as opposed to the standard approach where valuable features are often lost during search. Finally, we present and discuss the results of an extensive computational experiment carried out on several reference data sets. The outcomes show that classifiers induced using the representation enriched by the GP-constructed features provide better accuracy of classification on the test set. In particular, the extended approach proposed in the paper proved to be able to outperform the standard approach on some benchmark problems on a statistically significant level. <s> BIB009 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> An Introduction to Multi-Objective Evolutionary Algorithms and Their Applications Optimal Design of Industrial Electromagnetic Devices: A Multiobjective Evolutionary Approach Using a Particle Swarm Optimizer with a Multi-Objective Selection Scheme to Design Combinational Logic Circuits Automatic Control System Design via a Multiobjective Evolutionary Algorithm Evolutionary Multi-Objective Optimization of Trusses A Multi-Objective Evolutionary Algorithm for the Covering Tour Problem Multiobjective Aerodynamic Design and Visualization of Supersonic Wings by Using Adaptive Range Multiobjective Genetic Algorithms Mutli-Objective Spectroscopic Data Analysis of Inertial Confinement Fusion Implosion Cores: Plasma Gradient Determination On Machine Learning with Multiobjective Genetic Optimization and other papers. <s> BIB010 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> A new approach to data clustering is proposed, in which two or more measures of cluster quality are simultaneously optimized using a multiobjective evolutionary algorithm (EA). For this purpose, the PESA-II EA is adapted for the clustering problem by the incorporation of specialized mutation and initialization procedures, described herein. Two conceptually orthogonal measures of cluster quality are selected for optimization, enabling, for the first time, a clustering algorithm to explore and improve different compromise solutions during the clustering process. Our results, on a diverse suite of 15 real and synthetic data sets – where the correct classes are known – demonstrate a clear advantage to the multiobjective approach: solutions in the discovered Pareto set are objectively better than those obtained when the same EA is applied to optimize just one measure. Moreover, the multiobjective EA exhibits a far more robust level of performance than both the classic k-means and average-link agglomerative clustering algorithms, outperforming them substantially on aggregate. <s> BIB011 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> In this paper, we present a general-purpose, systematic algorithm, consisting of a genetic programming module and a k-nearest neighbor classifier, to automatically create multiple artificial features (i.e., features that are computer-crafted and may not have a known physical meaning) directly from EEG signals, in a process that reveals patterns predictive of epileptic seizures. The algorithm was evaluated in three patients, with prediction defined over a horizon that varies between 1 and 5 minutes before unequivocal electrographic onset of seizure. For one patient, a perfect classification was achieved. For the other two patients, high classification accuracy was reached, predicting three seizures out of four for one, and eleven seizures out of fifteen for the other. For the latter, also, only one normal (non-seizure) signal was misclassified. These results compare favorably with other prediction approaches for patients from the same population. <s> BIB012 </s> A Review of Evolutionary Algorithms for Data Mining <s> Satisfying the Closure Property <s> Various methods have been proposed to utilize Genetic Algorithms (GA) in handling the clustering problem. GA work on encoded strings, namely chromosomes, and the representation of different clusters as a linear structure is an important issue about the usage of GA in this domain. In this paper, we present a novel encoding scheme that uses links to identify clusters in a partition. Particularly, we restrict the links so that objects to be clustered form a linear pseudo-graph. A one-to-one mapping is thus achieved between the genotype and phenotype spaces. The other feature of the proposed approach is the use of multiple objectives in the process. One of the two objectives we use is to minimize the Total Within Cluster Variation (TWCV), identical to the one used by other k-means clustering approaches. However, unlike other k-means methods, number of clusters is not required specified in advance. Combined with a second objective, minimizing the number of clusters in a partition, our approach obtains the optimal partitions for all the possible numbers of clusters in the Pareto Optimal set returned by a single GA run. The performance of the proposed approach has been tested using two well-known data sets, namely Iris Data and Ruspini Data. The obtained results are compared with the output of the classical Group Number Encoding and it has been observed that a clear improvement has been achieved with the new representation. <s> BIB013
GP algorithms for attribute construction have used several different approaches to satisfy the closure property (briefly mentioned in Section 2). This is an important issue, because the chosen approach can have a significant impact on the types (e.g., continuous or nominal) of original attributes processed by the algorithm and on the types of attributes constructed by the algorithm. Let us see some examples. A simple solution for the closure problem is used in the GAP algorithm BIB006 . Its terminal set contains only the continuous (realvalued) attributes of the data being mined. In addition, its function set consists only of arithmetic operators (+, -, *, %,) -where % denotes protected division, i.e. a division operator that handles zero denominator inputs by returning something different from an error BIB002 BIB001 ) -so that the closure property is immediately satisfied. BIB012 ) also uses the approach of having a function set consisting only of mathematical operators, but it uses a considerably larger set of mathematical operators than the set used by BIB006 . The GP algorithm proposed by BIB009 ) uses a terminal set including all original attributes (both continuous and nominal ones), and a function set consisting of arithmetical operators (+, -, *, %, log), comparison operators (<, >, =), an "IF (conditional expression)", and an "approximate equality operator" which compares its two arguments with tolerance given by the third argument. The algorithm did not enforce data type constraints, which means that expressions encoding the constructed attributes make no distinction between, for instance, continuous and nominal attributes. Values of nominal attributes, such as male and female, are treated as numbers. This helps to solve the closure problem, but at a high price: constructed attributes can contain expressions that make no sense from a semantical point of view. For instance, the algorithm could produce an expression such as "Gender + Age", because the value of the nominal attribute Gender would be interpreted as a number. The GP proposed by BIB007 ) uses a terminal set including only the continuous attributes of the data being mined. Its function set consists of arithmetic operators (+, -, *, %,) and comparison operators (≥, ≤). In order to satisfy the closure property, the algorithm enforces the data type restriction that the comparison operators can be used only at the root of the GP tree, i.e., they cannot be used as child nodes of other nodes in the tree. The reason is that comparison operators return a Boolean value, which cannot be processed by any operator in the function set (all operators accept only continuous values as input). Note that, although the algorithm can construct attributes only out of the continuous original attributes, the constructed attributes themselves can be either Boolean or continuous. A constructed attribute will be Boolean if its corresponding tree in the GP individual has a comparison operator at the root node; it will be continuous otherwise. In order to satisfy the closure property, GPCI  simply transforms all the original attributes into Boolean attributes and uses a function set containing only Boolean functions. For instance, if an attribute A is continuous (real-valued), such as the attribute Salary, it is transformed into two Boolean attributes, such as "Is Salary > t?" and "Is Salary ≤ t?", where tis a threshold automatically chosen by the algorithm in order to maximize the ability of the two new attributes in discriminating between instances of different classes. The two new attributes are named "positive-A" and "negative-A", respectively. Once every original attribute has been transformed into two Boolean attributes, a GP algorithm is applied to the Boolean attributes. In this GP, the terminal set consists of all the pairs of attributes "positive-A" and "negative-A" for each original attribute A, whereas the function set consists of the Boolean operators {AND, OR}. Since all terminal symbols are Boolean, and all operators accept Boolean values as input and produce Boolean value as output, the closure property is satisfied. Table 2 summarizes the main characteristics of the five GP algorithms for attribute construction discussed in this Section. There are many real-world optimization problems that are naturally expressed as the simultaneous optimization of two or more conflicting objectives BIB005  BIB010 . A generic example is to maximize the quality of a product and minimize its manufacturing cost in a factory. In the context of data mining, a typical example is, in the data preprocessing task of attribute selection, to minimize the error rate of a classifier trained with the selected attributes and to minimize the number of selected attributes. The conventional approach to cope with such multi-objective optimization problems using evolutionary algorithms is to convert the problem into a single-optimization problem. This is typically done by using a weighted formula in the fitness function, where each objective has an associated weight reflecting its relative importance. For instance, in the above example of twoobjective attribute selection, the fitness function could be defined as, say: "2/3 classification error + 1/3 Number of selected attributes". However, this conventional approach has several problems. First, it mixes non-commensurable objectives (classification error and number of selected attributes in the previous example) into the same formula. This has at least the disadvantage that the value returned by the fitness function is not meaningful to the user. Second, note that different weights will lead to different selected attributes, since different weights represent different trade-offs between the two conflicting objectives. Unfortunately, the weights are usually defined in an ad-hoc fashion. Hence, when the EA returns the best attribute subset to the user, the user is presented with a solution that represents just one possible trade-off between the objectives. The user misses the opportunity to analyze different trade-offs. Of course we could address this problem by running the EA multiple times, with different weights for the objectives in each run, and return the multiple solutions to the user. However, this would be very inefficient, and we would still have the problems of deciding which weights should be used in each run, how many runs we should perform (and so how many solutions should be returned to the user), etc. A more principled approach consists of letting an EA answer these questions automatically, by performing a global search in the solution space and discovering as many good solutions, with as much diversity among them, as possible. This can be done by using a multi-objective EA, a kind of EA which has become quite popular in the EA community in the last few years  BIB005 BIB010 . The basic idea involves the concept of Pareto dominance. A solution s 1 is said to dominate, in the Pareto sense, another solution s 2 if and only if solution s 1 is strictly better than s 2 in at least one of the objectives and solution s 1 is not worse than s 2 in any of the objectives. The concept of Pareto dominance is illustrated in Figure 4 . This figure involves two objectives to be minimized, namely classification error and number of selected attributes (No attrib). In that figure, solution D is dominated by solution B (which has both a smaller error and a smaller number of selected attributes than D), and solution E is dominated by solution C. Hence, solutions A, B and C are non-dominated solutions. They constitute the best "Pareto front" found by the algorithm. All these three solutions would be returned to the user. The goal of a multi-objective EA is to find a Pareto front which is as close as possible to the true (unknown) Pareto front. This involves not only the minimization of the two objectives, but also finding a diverse set of nondominated solutions, spread along the Pareto front. This allows the EA to return to the user a diverse set of good trade-offs between the conflicting objectives. With this rich information, the user can hopefully make a more intelligent decision, choosing the best solution to be used in practice. At this point the reader might argue that this approach has the disadvantage that the final choice of the solution to be used depends on the user, characterizing a subjective approach. The response to this is that the knowledge discovery process is interactive   , and the participation of the user in this process is important to obtain useful results. The questions are when and how the user should participate   ). In the above-described multi-objective approach, based on Pareto dominance, the user participates by choosing the best solution out of all the non-dominated solutions. This choice is made a posteriori, i.e., after the algorithm has run and has returned a rich source of information about the solution space: the discovered Pareto front. In the conventional approach -using an EA with a weighted formula and returning a single solution to the user -the user has to define the weights a priori, i.e., before running the algorithm, when the solution space was not explored yet. The multi-objective approach seems to put the user in the loop in a better moment, when valuable information about the solution space is available. The multi-objective approach also avoids the problems of ad-hoc choice of weights, mixing non-commensurable objectives into the same formula, etc. Table 3 lists the main characteristics of multi-objective EAs for data mining. Most systems included in Table 3 consider only two objectives. The exceptions are the works of  and BIB008 , considering 4 and 8 objectives, respectively. Out of the EAs considering only two objectives, the most popular choice of objectives -particularly for EAs addressing the classification task -has been some measure of classification accuracy (or its dual, error) and a measure of the size of the classification model (number of leaf nodes in a decision tree or total number of rule conditionsattribute-value pairs -in all rules). Note that the size of a model is typically used as a proxy for the concept of "simplicity" of that model, even though arguably this proxy leaves a lot to be desired as a measure of a model's simplicity BIB003  ). (In practice, however, it seems no better proxy for a model's simplicity is known.) Note also that, when the task being solved is attribute selection for classification, the objective related to size can be the number of selected attributes, as in BIB004 , or the size of the classification model built from the set of selected attributes, as in   . Finally, when solving the clustering task a popular choice of objective has been some measure of intra-cluster distance, related to the total distance between each data instance and the centroid of its cluster, computed for all data instances in all the clusters. The number of clusters is also used as an objective in two out of the three EAs for clustering included in Table 3 . A further discussion of multi-objective optimization in the context of data mining in general (not focusing on EAs) is presented in  Jin 2006) .  attribute selection for clustering Cluster cohesiveness, separation between clusters, number of clusters, number of selected attributes BIB011 clustering Intra-cluster deviation and connectivity BIB013 clustering Intra-cluster variance and number of clusters