A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery
---
paper_title: Predictive Data Mining: A Practical Guide

paper_content:

1 What is Data Mining? 2 Statistical Evaluation for Big Data 3 Preparing the Data 4 Data Reduction 5 Looking for Solutions 6 What's Best for Data Reduction and Mining? 7 Art or Science? Case Studies in Data Mining
---
paper_title: Genetic Algorithms Data Structures Evolution Programs

paper_content:

Thank you for reading genetic algorithms data structures evolution programs. Maybe you have knowledge that, people have look hundreds times for their chosen novels like this genetic algorithms data structures evolution programs, but end up in infectious downloads. Rather than enjoying a good book with a cup of coffee in the afternoon, instead they are facing with some harmful virus inside their laptop.
---
paper_title: Genetic Programming: On the Programming of Computers by Means of Natural Selection

paper_content:

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.
---
paper_title: Machine Learning, Neural and Statistical Classification

paper_content:

Survey of previous comparisons and theoretical work descriptions of methods dataset descriptions criteria for comparison and methodology (including validation) empirical results machine learning on machine learning.
---
paper_title: Construction and Assessment of Classification Rules

paper_content:

Basic Ideas Introduction Constructing Rules Fisher's LDA and Other Methods Based on Covariance Matrices Nonlinear Methods Recursive Partitioning Methods Nonparametric Smoothing Methods Evaluating Rules Aspects of Evaluation Misclassification Rate Evaluating Two Class Rules Practical Issues Some Special Problems Some Illustrative Applications Links and Comparisons Between Methods.
---
paper_title: Database management and analysis tools of machine induction

paper_content:

This paper surveys machine induction techniques for database management and analysis. Our premise is that machine induction facilitates an evolution from relatively unstructured data stores to efficient and correct database implementations.
---
paper_title: Knowledge acquisition via incremental conceptual clustering

paper_content:

Conceptual clustering is an important way of summarizing and explaining data. However, the recent formulation of this paradigm has allowed little exploration of conceptual clustering as a means of improving performance. Furthermore, previous work in conceptual clustering has not explicitly dealt with constraints imposed by real world environments. This article presents COBWEB, a conceptual clustering system that organizes data so as to maximize inference ability. Additionally, COBWEB is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
---
paper_title: Genetic Algorithms and Grouping Problems

paper_content:

From the Publisher: ::: A reader-friendly introduction to the exciting, vast potential of Genetic Algorithms. ::: The book gives readers a general understanding of the concepts underlying the technology, an insight into its perceived benefits and failings, and a clear and practical illustration of how optimization problems can be solved more efficiently using Falkenauer's new class of algorithms.
---
paper_title: Clustering with a Genetically Optimized Approach

paper_content:

Describes a genetically guided approach to optimizing the hard (J/sub 1/) and fuzzy (J/sub m/) c-means functionals used in cluster analysis. Our experiments show that a genetic algorithm (GA) can ameliorate the difficulty of choosing an initialization for the c-means clustering algorithms. Experiments use six data sets, including the Iris data, magnetic resonance, and color images. The genetic algorithm approach is generally able to find the lowest known J/sub m/ value or a J/sub m/ associated with a partition very similar to that associated with the lowest J/sub m/ value. On data sets with several local extrema, the GA approach always avoids the less desirable solutions. Degenerate partitions are always avoided by the GA approach, which provides an effective method for optimizing clustering models whose objective function can be represented in terms of cluster centers. A series random initializations of fuzzy/hard c-means, where the partition associated with the lowest J/sub m/ value is chosen, can produce an equivalent solution to the genetic guided clustering approach given the same amount of processor time in some domains.
---
paper_title: Understanding the crucial differences between classification and discovery of association rules: a position paper

paper_content:

The goal of this position paper is to contribute to a clear understanding of the profound differences between the association-rule discovery and the classification tasks. We argue that the classification task can be considered an ill-defined, nondeterministic task, which is unavoidable given the fact that it involves prediction; while the standard association task can be considered a well-defined, deterministic, relatively simple task, which does not involve prediction in the same sense as the classification task does.
---
paper_title: Discovering Informative Patterns and Data Cleaning

paper_content:

We present a method for discovering informative patterns from data. With this method, large databases can be reduced to only a few representative data entries. Our framework encompasses also methods for cleaning databases containing corrupted data. Both on-line and off-line algorithms are proposed and experimentally checked on databases of handwritten images. The generality of the framework makes it an attractive candidate for new applications in knowledge discovery.
---
paper_title: On Changing Continuous Attributes into Ordered Discrete Attributes

paper_content:

The large real-world datasets now commonly tackled by machine learning algorithms are often described in terms of attributes whose values are real numbers on some continuous interval, rather than being taken from a small number of discrete values. Many algorithms are able to handle continuous attributes, but learning requires far more CPU time than for a corresponding task with discrete attributes. This paper describes how continuous attributes can be converted economically into ordered discrete attributes before being given to the learning system. Experimental results from a wide variety of domains suggest this change of representation does not often result in a significant loss of accuracy (in fact it sometimes significantly improves accuracy), but offers large reductions in learning time, typically more than a factor of 10 in domains with a large number of continuous attributes.
---
paper_title: Supervised and unsupervised discretization of continuous features

paper_content:

An electric shock weapon is disclosed for use by officers in maintaining order at public gatherings and for other crowd control applications. The invention is embodied in an electrified stick or in an electrified garment worn by the user. The device comprises at least one pair of exposed conductors which are connected across a high voltage power supply and adapted to be simultaneously engaged with the anatomy of a would-be assailant and thus to ward off or cause retreat of such person. In order to give warning of the character of the device, and to lend a menacing appearance, a sparking device is disposed on the weapon and connected across the high voltage power supply to provide a spark discharge. In the embodiment of the invention in an electrified stick a grip portion is provided at the rear end and a slidable insulating sleeve is disposed over a portion of the conductors and movable to the forward end of the stick to provide an auxiliary gripping portion for two-handed use of the stick. The high voltage power supply preferably comprises a capacitor discharge system comprising a battery energized transistor inverter and a voltage doubler connected across a storage capacitor, with a self-switching discharge circuit connected with an induction coil which in turn is connected with the exposed conductors on the device. A timing circuit and a silicon controlled rectifier are employed in the self-switching discharge circuit.
---
paper_title: Data Preparation For Data Mining

paper_content:

Data Preparation for Data Mining addresses an issue unfortunately ignored by most authorities on data mining: data preparation. Thanks largely to its perceived difficulty, data preparation has traditionally taken a backseat to the more alluring question of how best to extract meaningful knowledge. But without adequate preparation of your data, the return on the resources invested in mining is certain to be disappointing.Dorian Pyle corrects this imbalance. A twenty-five-year veteran of what has become the data mining industry, Pyle shares his own successful data preparation methodology, offering both a conceptual overview for managers and complete technical details for IT professionals. Apply his techniques and watch your mining efforts pay off-in the form of improved performance, reduced distortion, and more valuable results.On the enclosed CD-ROM, you'll find a suite of programs as C source code and compiled into a command-line-driven toolkit. This code illustrates how the author's techniques can be applied to arrive at an automated preparation solution that works for you. Also included are demonstration versions of three commercial products that help with data preparation, along with sample data with which you can practice and experiment. * Offers in-depth coverage of an essential but largely ignored subject.* Goes far beyond theory, leading you-step by step-through the author's own data preparation techniques.* Provides practical illustrations of the author's methodology using realistic sample data sets.* Includes algorithms you can apply directly to your own project, along with instructions for understanding when automation is possible and when greater intervention is required.* Explains how to identify and correct data problems that may be present in your application.* Prepares miners, helping them head into preparation with a better understanding of data sets and their limitations.
---
paper_title: Integrating inductive and deductive reasoning for data mining

paper_content:

Database mining is the process of finding previously unknown rules and relations in large databases. Often, several database mining techniques must be used cooperatively in a single application. In this paper we present the Recon database mining framework, which integrates three database mining techniques: rule induction, rule deduction, and data visualization.
---
paper_title: Using general impressions to analyze discovered classification rules

paper_content:

One of the important problems in data mining is the evaluation of subjective interestingness of the discovered rules. Past research has found that in many real-life applications it is easy to generate a large number of rules from the database, but most of the rules are not useful or interesting to the user. Due to the large number of rules, it is difficult for the user to analyze them manually in order to identify those interesting ones. Whether a rule is of interest to a user depends on his/her existing knowledge of the domain, and his/her interests. In this paper, we propose a technique that analyzes the discovered rules against a specific type of existing knowledge, which we call general impressions, to help the user identify interesting rules. We first propose a representation language to allow general impressions to be specified. We then present some algorithms to analyze the discovered classification rules against a set of general impressions. The results of the analysis tell us which rules conform to the general impressions and which rules are unexpected. Unexpected rules are by definition interesting.
---
paper_title: On Objective Measures of Rule Surprisingness

paper_content:

Most of the literature argues that surprisingness is an inherently subjective aspect of the discovered knowledge, which cannot be measured in objective terms. This paper departs from this view, and it has a twofold goal: (1) showing that it is indeed possible to define objective (rather than subjective) measures of discovered rule surprisingness; (2) proposing new ideas and methods for defining objective rule surprisingness measures.
---
paper_title: Choosing among competing generalizations

paper_content:

In a learning situation with noisy data, a generalization procedure may find a sizeable collection of partial generalizations each of them covering a part of the positive examples and, in general, a few negative examples. The task is to choose a moderately sized sub-collection of partial generalizations that are sufficiently different from one another. The idea is that the user is less interested in all the “best” partial generalizations (according to a given criterion) if they are quite similar rather than in some diverse ones, even if they are, taken individually, less satisfactory. This vague goal concept is made more precise and a procedure is developed and examined that employs two notions: a measure for the quality of a single generalization (called evidence) and an asymmetric measure for the similarity of two generalizations (called affinity). These two co-operate in suppressing generalizations that are worse than, but not too different from, another generalization. The selection procedure works satisfactorily in different environments.
---
paper_title: Finding interesting rules from large sets of discovered association rules

paper_content:

Association rules, introduced by Agrawal, Imielinski, and Swami, are rules of the form “for 90% of the rows of the relation, if the row has value 1 in the columns in set W , then it has 1 also in column B”. Efficient methods exist for discovering association rules from large collections of data. The number of discovered rules can, however, be so large that browsing the rule set and finding interesting rules from it can be quite difficult for the user. We show how a simple formalism of rule templates makes it possible to easily describe the structure of interesting rules. We also give examples of visualization of rules, and show how a visualization tool interfaces with rule templates.
---
paper_title: Discovering Interesting Patterns for Investment Decision Making with GLOWER ☹—A Genetic Learner Overlaid with Entropy Reduction

paper_content:

Prediction in financial domains is notoriously difficult for a number of reasons. First, theories tend to be weak or non-existent, which makes problem formulation open ended by forcing us to consider a large number of independent variables and thereby increasing the dimensionality of the search space. Second, the weak relationships among variables tend to be nonlinear, and may hold only in limited areas of the search space. Third, in financial practice, where analysts conduct extensive manual analysis of historically well performing indicators, a key is to find the hidden interactions among variables that perform well in combination. Unfortunately, these are exactly the patterns that the greedy search biases incorporated by many standard rule learning algorithms will miss. In this paper, we describe and evaluate several variations of a new genetic learning algorithm (GLOWER) on a variety of data sets. The design of GLOWER has been motivated by financial prediction problems, but incorporates successful ideas from tree induction and rule learning. We examine the performance of several GLOWER variants on two UCI data sets as well as on a standard financial prediction problem (S&P500 stock returns), using the results to identify one of the better variants for further comparisons. We introduce a new (to KDD) financial prediction problem (predicting positive and negative earnings surprises), and experiment with GLOWER, contrasting it with tree- and rule-induction approaches. Our results are encouraging, showing that GLOWER has the ability to uncover effective patterns for difficult problems that have weak structure and significant nonlinearities.
---
paper_title: Discovering comprehensible classification rules by using Genetic Programming: a case study in a medical domain

paper_content:

This work it is intended to discover classification rules for diagnosing certain pathologies. These rules are capable of discriminating among 12 different pathologies, whose main symptom is chest pain. In order to discover these rules it was used genetic programming as well as some concepts of data mining, particularly the emphasis on the discovery of comprehensible knowledge.
---
paper_title: Data Mining Using Grammar Based Genetic Programming and Applications

paper_content:

From the Publisher: ::: Describes a framework, called GGP (Generic Genetic Programming), that integrates GP and ILP based on a formalism of logic grammers. Accelerates the learning speed and/or improves the quality of the knowledge induced.
---
paper_title: Representational semantics for genetic programming based learning in high-frequency financial data

paper_content:

A concealed storage fire escape ladder of the general type disclosed in U.S. Pat. No. 3,547,226, and having structural refinements affording greater strength during use and improved convenience in assembly. Retractable means including a nylon rope affords a shock-absorbing function when the ladder is dropped into position for use. The individual step elements of the ladder are nestable, and utilization of space within a lowermost tread when the device is stored within a storage cabinet permits storage of a chain interconnecting the ladder with the storage cabinet to be stored within said space.
---
paper_title: Niching methods for genetic algorithms

paper_content:

Niching methods extend genetic algorithms to domains that require the location and maintenance of multiple solutions. Such domains include classification and machine learning, multimodal function optimization, multiobjective function optimization, and simulation of complex and adaptive systems. ::: This study presents a comprehensive treatment of niching methods and the related topic of population diversity. Its purpose is to analyze existing niching methods and to design improved niching methods. To achieve this purpose, it first develops a general framework for the modelling of niching methods, and then applies this framework to construct models of individual niching methods, specifically crowding and sharing methods. ::: Using a constructed model of crowding, this study determines why crowding methods over the last two decades have not made effective niching methods. A series of tests and design modifications results in the development of a highly effective form of crowding, called deterministic crowding. Further analysis of deterministic crowding focuses upon the distribution of population elements among niches, that arises from the combination of crossover and replacement selection. Interactions among niches are isolated and explained. The concept of crossover hillclimbing is introduced. ::: Using constructed models of fitness sharing, this study derives lower bounds on the population size required to maintain, with probability $\gamma$, a fixed number of desired niches. It also derives expressions for the expected time to disappearance of a desired niche, and relates disappearance time to population size. Models are presented of sharing under selection, and sharing under both selection and crossover. Some models assume that all niches are equivalent with respect to fitness. Others allow niches to differ with respect to fitness. ::: Focusing on the differences between parallel and sequential niching methods, this study compares and further examines four niching methods--crowding, sharing, sequential niching, and parallel hillclimbing. The four niching methods undergo rigorous testing on optimization and classification problems of increasing difficulty; a new niching-based technique is introduced that extends genetic algorithms to classification problems.
---
paper_title: Learning to Predict Rare Events in Event Sequences

paper_content:

Learning to predict rare events from sequences of events with categorical features is an important, real-world, problem that existing statistical and machine learning methods are not well suited to solve. This paper describes timeweaver, a genetic algorithm based machine learning system that predicts rare events by identifying predictive temporal and sequential patterns. Timeweaver is applied to the task of predicting telecommunication equipment failures from 110,000 alarm messages and is shown to outperform existing learning methods.
---
paper_title: A knowledge-intensive genetic algorithm for supervised learning

paper_content:

Supervised learning in attribute-based spaces is one of the most popular machine learning problems studied and, consequently, has attracted considerable attention of the genetic algorithm community. The full-memory approach developed here uses the same high-level descriptive language that is used in rule-based systems. This allows for an easy utilization of inference rules of the well-known inductive learning methodology, which replace the traditional domain-independent operators and make the search task-specific. Moreover, a closer relationship between the underlying task and the processing mechanisms provides a setting for an application of more powerful task-specific heuristics. Initial results obtained with a prototype implementation for the simplest case of single concepts indicate that genetic algorithms can be effectively used to process high-level concepts and incorporate task-specific knowledge. The method of abstracting the genetic algorithm to the problem level, described here for the supervised inductive learning, can be also extended to other domains and tasks, since it provides a framework for combining recently popular genetic algorithm methods with traditional problem-solving methodologies. Moreover, in this particular case, it provides a very powerful tool enabling study of the widely accepted but not so well understood inductive learning methodology.
---
paper_title: Competition-Based Induction of Decision Models from Examples

paper_content:

Symbolic induction is a promising approach to constructing decision models by extracting regularities from a data set of examples. The predominant type of model is a classification rule (or set of rules) that maps a set of relevant environmental features into specific categories or values. Classifying loan risk based on borrower profiles, consumer choice from purchase data, or supply levels based on operating conditions are all examples of this type of model-building task. Although current inductive approaches, such as ID3 and CN2, perform well on certain problems, their potential is limited by the incremental nature of their search. Genetic algorithms (GA) have shown great promise on complex search domains, and hence suggest a means for overcoming these limitations. However, effective use of genetic search in this context requires a framework that promotes the fundamental model-building objectives of predictive accuracy and model simplicity. In this article we describe COGIN, a GA-based inductive system that exploits the conventions of induction from examples to provide this framework. The novelty of COGIN lies in its use of training set coverage to simultaneously promote competition in various classification niches within the model and constrain overall model complexity. Experimental comparisons with NewID and CN2 provide evidence of the effectiveness of the COGIN framework and the viability of the GA approach.
---
paper_title: Search-Intensive Concept Induction

paper_content:

This paper describes REGAL, a distributed genetic algorithm-based system, designed for learning first-order logic concept descriptions from examples. The system is a hybrid of the Pittsburgh and the Michigan approaches, as the population constitutes a redundant set of partial concept descriptions, each evolved separately. In order to increase effectiveness, REGAL is specifically tailored to the concept learning task; hence, REGAL is task-dependent, but, on the other hand, domain-independent. The system proved particularly robust with respect to parameter setting across a variety of different application domains. ::: ::: REGAL is based on a selection operator, called Universal Suffrage operator, provably allowing the population to asymptotically converge, on the average, to an equilibrium state in which several species coexist. The system is presented in both a serial and a parallel version, and a new distributed computational model is proposed and discussed. ::: ::: The system has been tested on a simple artificial domain for the sake of illustration, and on several complex real-world and artificial domains in order to show its power and to analyze its behavior under various conditions. The results obtained so far suggest that genetic search may be a valuable alternative to logic-based approaches to learning concepts, when no (or little) a priori knowledge is available and a very large hypothesis space has to be explored.
---
paper_title: Discovering interesting prediction rules with a genetic algorithm

paper_content:

In essence, the goal of data mining is to discover knowledge which is highly accurate, comprehensible and "interesting" (surprising, novel). Although the literature emphasizes predictive accuracy and comprehensibility, the discovery of interesting knowledge remains a formidable challenge for data mining algorithms. We present a genetic algorithm designed from the scratch to discover interesting rules. Our GA addresses the dependence modelling task, where different rules can predict different goal attributes. This task can be regarded as a generalization of the classification task, where all rules predict the same goal attribute.
---
paper_title: Using genetic algorithms for concept learning

paper_content:

In this article, we explore the use of genetic algorithms (GAs) as a key element in the design and implementation of robust concept learning systems. We describe and evaluate a GA-based system called GABIL that continually learns and refines concept classification rules from its interaction with the environment. The use of GAs is motivated by recent studies showing the effects of various forms of bias built into different concept learning systems, resulting in systems that perform well on certain concept classes (generally, those well matched to the biases) and poorly on others. By incorporating a GA as the underlying adaptive search mechanism, we are able to construct a concept learning system that has a simple, unified architecture with several important features. First, the system is surprisingly robust even with minimal bias. Second, the system can be easily extended to incorporate traditional forms of bias found in other concept learning systems. Finally, the architecture of the system encourages explicit representation of such biases and, as a result, provides for an important additional feature: the ability to dynamically adjust system bias. The viability of this approach is illustrated by comparing the performance of GABIL with that of four other more traditional concept learners (AQ14, C4.5, ID5R, and IACL) on a variety of target concepts. We conclude with some observations about the merits of this approach and about possible extensions.
---
paper_title: GA-MINER: Parallel Data Mining with Hierarchical Genetic Algorithms Final Report

paper_content:

Staple fibers made from crimped, in particular compression crimped, multicomponent filaments of the matrix/segment type, the cross section of which shows, in addition to the matrix, at least 6 peripheral wedge-shaped or lenticular segments, not completely covered by the matrix, are processed into a web, which is then mechanically bonded, preferably by needling. Subsequently, the fabric is subjected to a shrinkage process, by which its density is increased by more than 30%, themulticomponent fibers being completely or partly split up into their components. The difference in shrinkage between the components should be at least 10%. The liquids used for the shrinkage treatment are in particular organic liquids, such as methylene chloride, as well as other liquids producing a difference in shrinkage of at least 20%. The fabric is then impregnated with a solution of polyurethane on the basis of polyglycols, specifically polytetramethylene glycol, diisocyanates and low-molecular glycols as chain lengtheners, the jelling temperature of the solution being higher than the roomtemperature and higher than the temperature of the coagulation bath; the polyurethane is coagulated by cooling and/or treatment with a coagulation bath containing a non-solvent for polyurethane; then the fabric is washed, dried and ground on one or both sides. The suede-like product obtained combines great suppleness with high strength. It is an excellent material for making garments, such as coats, jackets or skirts, offering high wear comfort as well as high breathability.
---
paper_title: Using genetic algorithms for concept learning

paper_content:

In this article, we explore the use of genetic algorithms (GAs) as a key element in the design and implementation of robust concept learning systems. We describe and evaluate a GA-based system called GABIL that continually learns and refines concept classification rules from its interaction with the environment. The use of GAs is motivated by recent studies showing the effects of various forms of bias built into different concept learning systems, resulting in systems that perform well on certain concept classes (generally, those well matched to the biases) and poorly on others. By incorporating a GA as the underlying adaptive search mechanism, we are able to construct a concept learning system that has a simple, unified architecture with several important features. First, the system is surprisingly robust even with minimal bias. Second, the system can be easily extended to incorporate traditional forms of bias found in other concept learning systems. Finally, the architecture of the system encourages explicit representation of such biases and, as a result, provides for an important additional feature: the ability to dynamically adjust system bias. The viability of this approach is illustrated by comparing the performance of GABIL with that of four other more traditional concept learners (AQ14, C4.5, ID5R, and IACL) on a variety of target concepts. We conclude with some observations about the merits of this approach and about possible extensions.
---
paper_title: Discovery of Decision Rules from Databases: An Evolutionary Approach

paper_content:

Decision rules are a natural form of representing knowledge. Their extraction from databases requires the capability for effective search large solution spaces. This paper shows, how we can deal with this problem using evolutionary algorithms (EAs). We propose an EA-based system called EDRL, which for each class label sequentially generates a disjunctive set of decision rules in propositional form. EDRL uses an EA to search for one rule at a time; then, all the positive examples covered by the rule are removed from the learning set and the search is repeated on the remaining examples. Our version of EA differs from standard genetic algorithm. In addition to the well-known uniform crossver it employs two non-standard genetic operators, which we call changing condition and insertion. Currently EDRL requires prior discretization of all continuous-valued attributes. A discretization technique based on the minimization of class entropy is used. The performance of EDRL is evaluated by comparing its classification accuracy with that of C4.5 learning algorithm on six datasets from UCI repository.
---
paper_title: A knowledge-intensive genetic algorithm for supervised learning

paper_content:

Supervised learning in attribute-based spaces is one of the most popular machine learning problems studied and, consequently, has attracted considerable attention of the genetic algorithm community. The full-memory approach developed here uses the same high-level descriptive language that is used in rule-based systems. This allows for an easy utilization of inference rules of the well-known inductive learning methodology, which replace the traditional domain-independent operators and make the search task-specific. Moreover, a closer relationship between the underlying task and the processing mechanisms provides a setting for an application of more powerful task-specific heuristics. Initial results obtained with a prototype implementation for the simplest case of single concepts indicate that genetic algorithms can be effectively used to process high-level concepts and incorporate task-specific knowledge. The method of abstracting the genetic algorithm to the problem level, described here for the supervised inductive learning, can be also extended to other domains and tasks, since it provides a framework for combining recently popular genetic algorithm methods with traditional problem-solving methodologies. Moreover, in this particular case, it provides a very powerful tool enabling study of the widely accepted but not so well understood inductive learning methodology.
---
paper_title: Competition-Based Induction of Decision Models from Examples

paper_content:

Symbolic induction is a promising approach to constructing decision models by extracting regularities from a data set of examples. The predominant type of model is a classification rule (or set of rules) that maps a set of relevant environmental features into specific categories or values. Classifying loan risk based on borrower profiles, consumer choice from purchase data, or supply levels based on operating conditions are all examples of this type of model-building task. Although current inductive approaches, such as ID3 and CN2, perform well on certain problems, their potential is limited by the incremental nature of their search. Genetic algorithms (GA) have shown great promise on complex search domains, and hence suggest a means for overcoming these limitations. However, effective use of genetic search in this context requires a framework that promotes the fundamental model-building objectives of predictive accuracy and model simplicity. In this article we describe COGIN, a GA-based inductive system that exploits the conventions of induction from examples to provide this framework. The novelty of COGIN lies in its use of training set coverage to simultaneously promote competition in various classification niches within the model and constrain overall model complexity. Experimental comparisons with NewID and CN2 provide evidence of the effectiveness of the COGIN framework and the viability of the GA approach.
---
paper_title: Search-Intensive Concept Induction

paper_content:

This paper describes REGAL, a distributed genetic algorithm-based system, designed for learning first-order logic concept descriptions from examples. The system is a hybrid of the Pittsburgh and the Michigan approaches, as the population constitutes a redundant set of partial concept descriptions, each evolved separately. In order to increase effectiveness, REGAL is specifically tailored to the concept learning task; hence, REGAL is task-dependent, but, on the other hand, domain-independent. The system proved particularly robust with respect to parameter setting across a variety of different application domains. ::: ::: REGAL is based on a selection operator, called Universal Suffrage operator, provably allowing the population to asymptotically converge, on the average, to an equilibrium state in which several species coexist. The system is presented in both a serial and a parallel version, and a new distributed computational model is proposed and discussed. ::: ::: The system has been tested on a simple artificial domain for the sake of illustration, and on several complex real-world and artificial domains in order to show its power and to analyze its behavior under various conditions. The results obtained so far suggest that genetic search may be a valuable alternative to logic-based approaches to learning concepts, when no (or little) a priori knowledge is available and a very large hypothesis space has to be explored.
---
paper_title: Discovering interesting prediction rules with a genetic algorithm

paper_content:

In essence, the goal of data mining is to discover knowledge which is highly accurate, comprehensible and "interesting" (surprising, novel). Although the literature emphasizes predictive accuracy and comprehensibility, the discovery of interesting knowledge remains a formidable challenge for data mining algorithms. We present a genetic algorithm designed from the scratch to discover interesting rules. Our GA addresses the dependence modelling task, where different rules can predict different goal attributes. This task can be regarded as a generalization of the classification task, where all rules predict the same goal attribute.
---
paper_title: Using genetic algorithms for concept learning

paper_content:

In this article, we explore the use of genetic algorithms (GAs) as a key element in the design and implementation of robust concept learning systems. We describe and evaluate a GA-based system called GABIL that continually learns and refines concept classification rules from its interaction with the environment. The use of GAs is motivated by recent studies showing the effects of various forms of bias built into different concept learning systems, resulting in systems that perform well on certain concept classes (generally, those well matched to the biases) and poorly on others. By incorporating a GA as the underlying adaptive search mechanism, we are able to construct a concept learning system that has a simple, unified architecture with several important features. First, the system is surprisingly robust even with minimal bias. Second, the system can be easily extended to incorporate traditional forms of bias found in other concept learning systems. Finally, the architecture of the system encourages explicit representation of such biases and, as a result, provides for an important additional feature: the ability to dynamically adjust system bias. The viability of this approach is illustrated by comparing the performance of GABIL with that of four other more traditional concept learners (AQ14, C4.5, ID5R, and IACL) on a variety of target concepts. We conclude with some observations about the merits of this approach and about possible extensions.
---
paper_title: Discovery of Decision Rules from Databases: An Evolutionary Approach

paper_content:

Decision rules are a natural form of representing knowledge. Their extraction from databases requires the capability for effective search large solution spaces. This paper shows, how we can deal with this problem using evolutionary algorithms (EAs). We propose an EA-based system called EDRL, which for each class label sequentially generates a disjunctive set of decision rules in propositional form. EDRL uses an EA to search for one rule at a time; then, all the positive examples covered by the rule are removed from the learning set and the search is repeated on the remaining examples. Our version of EA differs from standard genetic algorithm. In addition to the well-known uniform crossver it employs two non-standard genetic operators, which we call changing condition and insertion. Currently EDRL requires prior discretization of all continuous-valued attributes. A discretization technique based on the minimization of class entropy is used. The performance of EDRL is evaluated by comparing its classification accuracy with that of C4.5 learning algorithm on six datasets from UCI repository.
---
paper_title: Learning disjunctive concepts by means of genetic algorithms

paper_content:

REGAL is a Distributed Genetic Algorithm designed for learning concept descriptions from examples, in First Order Logic. In particular, each individual in the population represents a conjunctive formula in VL2 language. In order to increase the efficiency of the generalization process, REGAL has been provided with a new selection operator, called Universal Suffrage operator, which guarantees (in probability) to maintain a population covering all the learning events. As generalization mostly takes place when two individuals covering different sets of examples are crossed, the global generalization capability of the system is increased. Moreover, in the case of disjunctive or multiple concepts, the universal suffrage algorithm allows the formation of different species, each one corresponding to a different disjunct. In this way, all the disjuncts can be learned in parallel obtaining, in average, more general solutions than by learning them one at a time. A formal analysis of the universal suffrage operator is presented, providing theoretical explanations of the experimentally observed behaviour. A comparison with the classical selection algorithm and with the sharing function method is also made. Finally, a long term control strategy, called “Tories and Whigs”, is proposed in order to overcome the problem of lethal matings between uncompatible disjuncts. The effectiveness of REGAL is demonstrated on several learning problems.
---
paper_title: Learning disjunctive concepts by means of genetic algorithms

paper_content:

REGAL is a Distributed Genetic Algorithm designed for learning concept descriptions from examples, in First Order Logic. In particular, each individual in the population represents a conjunctive formula in VL2 language. In order to increase the efficiency of the generalization process, REGAL has been provided with a new selection operator, called Universal Suffrage operator, which guarantees (in probability) to maintain a population covering all the learning events. As generalization mostly takes place when two individuals covering different sets of examples are crossed, the global generalization capability of the system is increased. Moreover, in the case of disjunctive or multiple concepts, the universal suffrage algorithm allows the formation of different species, each one corresponding to a different disjunct. In this way, all the disjuncts can be learned in parallel obtaining, in average, more general solutions than by learning them one at a time. A formal analysis of the universal suffrage operator is presented, providing theoretical explanations of the experimentally observed behaviour. A comparison with the classical selection algorithm and with the sharing function method is also made. Finally, a long term control strategy, called “Tories and Whigs”, is proposed in order to overcome the problem of lethal matings between uncompatible disjuncts. The effectiveness of REGAL is demonstrated on several learning problems.
---
paper_title: A parallel genetic algorithm for rule discovery in large databases

paper_content:

This paper presents GA-PVMINER, a parallel genetic algorithm that uses the Parallel Virtual Machine (PVM) to discover rules in a database. The system uses the Michigan's approach, where each individual represents a rule. A rule has the form "if condition then prediction". GA-PVMINER is based on the concept learning framework, but it performs a generalization of the classification task, which can be called dependence modeling (sometimes also called generalized rule induction). In this task, different discovered rules can predict the value of different goal attributes in the "prediction" part of a rule, whereas in classification all discovered rules predict the value of the same goal attribute. The global population of genetic algorithm individuals is divided into several subpopulations, each assigned to a distinct processor. For each subpopulation, all the individuals represent rules with the same goal attribute in the "prediction" part of the rule. Different subpopulations evolve rules predicting different goal attributes. The system exploits both data parallelism and function parallelism.
---
paper_title: A knowledge-intensive genetic algorithm for supervised learning

paper_content:

Supervised learning in attribute-based spaces is one of the most popular machine learning problems studied and, consequently, has attracted considerable attention of the genetic algorithm community. The full-memory approach developed here uses the same high-level descriptive language that is used in rule-based systems. This allows for an easy utilization of inference rules of the well-known inductive learning methodology, which replace the traditional domain-independent operators and make the search task-specific. Moreover, a closer relationship between the underlying task and the processing mechanisms provides a setting for an application of more powerful task-specific heuristics. Initial results obtained with a prototype implementation for the simplest case of single concepts indicate that genetic algorithms can be effectively used to process high-level concepts and incorporate task-specific knowledge. The method of abstracting the genetic algorithm to the problem level, described here for the supervised inductive learning, can be also extended to other domains and tasks, since it provides a framework for combining recently popular genetic algorithm methods with traditional problem-solving methodologies. Moreover, in this particular case, it provides a very powerful tool enabling study of the widely accepted but not so well understood inductive learning methodology.
---
paper_title: Search-Intensive Concept Induction

paper_content:

This paper describes REGAL, a distributed genetic algorithm-based system, designed for learning first-order logic concept descriptions from examples. The system is a hybrid of the Pittsburgh and the Michigan approaches, as the population constitutes a redundant set of partial concept descriptions, each evolved separately. In order to increase effectiveness, REGAL is specifically tailored to the concept learning task; hence, REGAL is task-dependent, but, on the other hand, domain-independent. The system proved particularly robust with respect to parameter setting across a variety of different application domains. ::: ::: REGAL is based on a selection operator, called Universal Suffrage operator, provably allowing the population to asymptotically converge, on the average, to an equilibrium state in which several species coexist. The system is presented in both a serial and a parallel version, and a new distributed computational model is proposed and discussed. ::: ::: The system has been tested on a simple artificial domain for the sake of illustration, and on several complex real-world and artificial domains in order to show its power and to analyze its behavior under various conditions. The results obtained so far suggest that genetic search may be a valuable alternative to logic-based approaches to learning concepts, when no (or little) a priori knowledge is available and a very large hypothesis space has to be explored.
---
paper_title: Interactive Genetic Algorithm Based Feature Selection and Its Application to Marketing Data Analysis

paper_content:

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
---
paper_title: Discovering interesting prediction rules with a genetic algorithm

paper_content:

In essence, the goal of data mining is to discover knowledge which is highly accurate, comprehensible and "interesting" (surprising, novel). Although the literature emphasizes predictive accuracy and comprehensibility, the discovery of interesting knowledge remains a formidable challenge for data mining algorithms. We present a genetic algorithm designed from the scratch to discover interesting rules. Our GA addresses the dependence modelling task, where different rules can predict different goal attributes. This task can be regarded as a generalization of the classification task, where all rules predict the same goal attribute.
---
paper_title: GA-MINER: Parallel Data Mining with Hierarchical Genetic Algorithms Final Report

paper_content:

Staple fibers made from crimped, in particular compression crimped, multicomponent filaments of the matrix/segment type, the cross section of which shows, in addition to the matrix, at least 6 peripheral wedge-shaped or lenticular segments, not completely covered by the matrix, are processed into a web, which is then mechanically bonded, preferably by needling. Subsequently, the fabric is subjected to a shrinkage process, by which its density is increased by more than 30%, themulticomponent fibers being completely or partly split up into their components. The difference in shrinkage between the components should be at least 10%. The liquids used for the shrinkage treatment are in particular organic liquids, such as methylene chloride, as well as other liquids producing a difference in shrinkage of at least 20%. The fabric is then impregnated with a solution of polyurethane on the basis of polyglycols, specifically polytetramethylene glycol, diisocyanates and low-molecular glycols as chain lengtheners, the jelling temperature of the solution being higher than the roomtemperature and higher than the temperature of the coagulation bath; the polyurethane is coagulated by cooling and/or treatment with a coagulation bath containing a non-solvent for polyurethane; then the fabric is washed, dried and ground on one or both sides. The suede-like product obtained combines great suppleness with high strength. It is an excellent material for making garments, such as coats, jackets or skirts, offering high wear comfort as well as high breathability.
---
paper_title: Comparison of algorithms that select features for pattern classifiers

paper_content:

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.
---
paper_title: Using Learning to Facilitate the Evolution of Features for Recognizing Visual Concepts

paper_content:

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.
---
paper_title: Feature selection mechanisms for ensemble creation: A genetic search perspective

paper_content:

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.
---
paper_title: A Hybrid Genetic Algorithm for Classification

paper_content:

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.
---
paper_title: A survey of genetic feature selection in mining issues

paper_content:

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.
---
paper_title: Interactive Genetic Algorithm Based Feature Selection and Its Application to Marketing Data Analysis

paper_content:

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
---
paper_title: Feature Extraction Construction and Selection: A Data Mining Perspective

paper_content:

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.
---
paper_title: Growing Simpler Decision Trees to Facilitate Knowledge Discovery

paper_content:

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.
---
paper_title: Robust feature selection algorithms

paper_content:

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.
---
paper_title: Boosting the margin: A new explanation for the effectiveness of voting methods

paper_content:

One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and often is observed to decrease even after the training error reaches zero. In this paper, we show that this phenomenon is related to the distribution of margins of the training examples with respect to the generated voting classification rule, where the margin of an example is simply the difference between the number of correct votes and the maximum number of votes received by any incorrect label. We show that techniques used in the analysis of Vapnik's support vector classifiers and of neural networks with small weights can be applied to voting methods to relate the margin distribution to the test error. We also show theoretically and experimentally that boosting is especially effective at increasing the margins of the training examples. Finally, we compare our explanation to those based on the bias-variance
---
paper_title: Genetic Programming: On the Programming of Computers by Means of Natural Selection

paper_content:

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.
---
paper_title: Genetic programming for knowledge discovery in chest-pain diagnosis

paper_content:

Explores a promising data mining approach. Despite the small number of examples available in the authors' application domain (taking into account the large number of attributes), the results of their experiments can be considered very promising. The discovered rules had good performance concerning predictive accuracy, considering both the rule set as a whole and each individual rule. Furthermore, what is more important from a data mining viewpoint, the system discovered some comprehensible rules. It is interesting to note that the system achieved very consistent results by working from "tabula rasa," without any background knowledge, and with a small number of examples. The authors emphasize that their system is still in an experiment in the research stage of development. Therefore, the results presented here should not be used alone for real-world diagnoses without consulting a physician. Future research includes a careful selection of attributes in a preprocessing step, so as to reduce the number of attributes (and the corresponding search space) given to the GP. Attribute selection is a very active research area in data mining. Given the results obtained so far, GP has been demonstrated to be a really useful data mining tool, but future work should also include the application of the GP system proposed here to other data sets, to further validate the results reported in this article.
---
paper_title: Feature Extraction Construction and Selection: A Data Mining Perspective

paper_content:

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.
---
paper_title: A Hybrid Decision Tree/genetic Algorithm for Coping With the Problem of Small Disjuncts in Data Mining

paper_content:

The problem of small disjuncts is a serious challenge for data mining algorithms. In essence, small disjuncts are rules covering a small number of examples. Due to their nature, small disjuncts tend to be error prone and contribute to a decrease in predictive accuracy. This paper proposes a hybrid decision tree/genetic algorithm method to cope with the problem of small disjuncts. The basic idea is that examples belonging to large disjuncts are classified by rules produced by a decision-tree algorithm, while examples belonging to small disjuncts (whose classification is considerably more difficult) are classified by rules produced by a genetic algorithm specifically designed for this task.
---

Title: A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery

Section 1: Introduction
Description 1: Introduce the motivation behind the study of evolutionary algorithms in data mining and knowledge discovery, and outline the main goals and structure of the paper.

Section 2: An Overview of Data Mining and Knowledge Discovery
Description 2: Provide a general overview of data mining and knowledge discovery, including their importance and processes involved.

Section 3: Genetic Algorithms (GAs) for Rule Discovery
Description 3: Discuss the use of genetic algorithms for discovering classification rules, including individual representation, genetic operators, and fitness functions.

Section 4: Genetic Algorithms (GAs) for the Knowledge Discovery Process
Description 4: Explore how genetic algorithms can be used for data preprocessing and discovered-knowledge postprocessing in the knowledge discovery process.

Section 5: Genetic Programming (GP) for Rule Discovery
Description 5: Examine the application of genetic programming for discovering classification rules and discuss methods to ensure the discovered rules are comprehensible.

Section 6: Genetic Programming (GP) for Data Preprocessing
Description 6: Discuss the use of genetic programming for attribute construction during the data preprocessing phase.

Section 7: Discussion and Research Directions
Description 7: Present a discussion on the findings, the significance of evolutionary algorithms in data mining and knowledge discovery, and suggest potential research directions.