A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Representing the Rule Consequent (Predicted Class). <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> Representing the Rule Consequent (Predicted Class). <s> 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. <s> BIB002 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Representing the Rule Consequent (Predicted Class). <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> BIB003 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Representing the Rule Consequent (Predicted Class). <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> BIB004 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Representing the Rule Consequent (Predicted Class). <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> BIB005 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Representing the Rule Consequent (Predicted Class). <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
Broadly speaking, there are at least three ways of representing the predicted class (the "THEN" part of the rule) in an evolutionary algorithm. The first possibility is to encode it in the genome of an individual BIB004 , BIB005 -possibly making it subject to evolution. The second possibility is to associate all individuals of the population with the same predicted class, which is never modified during the running of the algorithm. Hence, if we want to discover a set of classification rules predicting k different classes, we would need to run the evolutionary algorithm at least k times, so that in the i-th run, i=1,..,k, the algorithm discovers only rules predicting the i-th class BIB006 , BIB002 . The third possibility is to choose the predicted class most suitable for a rule, in a kind of deterministic way, as soon as the corresponding rule antecedent is formed. The chosen predicted class can be the class that has more representatives in the set of examples satisfying the rule antecedent BIB001 or the class that maximizes the individual's fitness BIB003 . The above first and third possibilities have the advantage of allowing that different individuals of the population represent rules predicting different classes. This avoids the need to perform multiple runs of the evolutionary algorithm to discover rules predicting different classes, which is the case in the above second possibility. Overall, the third possibility seems more sound than the first one.