A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB001 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB002 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB003 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB004 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB005 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB006 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Michigan versus Pittsburgh Approach. <s> 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. <s> BIB007
Genetic algorithms (GAs) for rule discovery can be divided into two broad approaches, based on how rules are encoded in the population of individuals ("chromosomes"). In the Michigan approach each individual encodes a single prediction rule, whereas in the Pittsburgh approach each individual encodes a set of prediction rules. It should be noted that some authors use the term "Michigan approach" in a narrow sense, to refer only to classifier systems  , where rule interaction is taken into account by a specific kind of credit assignment method. However, we use the term "Michigan approach" in a broader sense, to denote any approach where each GA individual encodes a single prediction rule. The choice between these two approaches strongly depends on which kind of rule we want to discover. This is related to which kind of data mining task we are addressing. Suppose the task is classification. Then we usually evaluate the quality of the rule set as a whole, rather than the quality of a single rule. In other words, the interaction among the rules is important. In this case, the Pittsburgh approach seems more natural. On the other hand, the Michigan approach might be more natural in other kinds of data mining tasks. An example is a task where the goal is to find a small set of high-quality prediction rules, and each rule is often evaluated independently of other rules BIB004 . Another example is the task of detecting rare events BIB003 . Turning back to classification, which is the focus of this chapter, in a nutshell the pros and cons of each approach are as follows. The Pittsburgh approach directly takes into account rule interaction when computing the fitness function of an individual. However, this approach leads to syntactically-longer individuals, which tends to make fitness computation more computationally expensive. In addition, it may require some modifications to standard genetic operators to cope with relatively complex individuals. Examples of GAs for classification which follow the Pittsburgh approach are GABIL BIB005 , GIL BIB006 , and HDPDCS  . By contrast, in the Michigan approach the individuals are simpler and syntactically shorter. This tends to reduce the time taken to compute the fitness function and to simplify the design of genetic operators. However, this advantage comes with a cost. First of all, since the fitness function evaluates the quality of each rule separately, now it is not easy to compute the quality of the rule set as a whole -i.e. taking rule interactions into account. Another problem is that, since we want to discover a set of rules, rather than a single rule, we cannot allow the GA population to converge to a single individual -which is what usually happens in standard GAs. This introduces the need for some kind of niching method BIB002 , which obviously is not necessary in the case of the Pittsburgh approach. We can avoid the need for niching in the Michigan approach by running the GA several times, each time discovering a different rule. The drawback of this approach is that it tends to be computationally expensive. Examples of GAs for classification which follow the Michigan approach are COGIN BIB007 and REGAL BIB001 . So far we have seen that an individual of a GA can represent a single rule or several rules, but we have not said yet how the rule(s) is(are) encoded in the genome of the individual. We now turn to this issue. To follow our discussion, assume that a rule has the form "IF cond 1 AND ... AND cond n THEN class = c i ", where cond 1 ... cond n are attribute-value conditions (e.g. Sex = "M") and c i is the class predicted by the rule. We divide our discussion into two parts, the representation of the rule antecedent (the "IF" part of the rule) and the representation of the rule consequent (the "THEN" part of the rule). These two issues are discussed in the next two subsections. In these subsections we will assume that the GA follows the Michigan approach, to simplify our discussion. However, most of the ideas in these two subsections can be adapted to the Pittsburgh approach as well.