A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Fitness Functions for Rule Discovery <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> Fitness Functions for Rule Discovery <s> 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. <s> BIB002 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Fitness Functions for Rule Discovery <s> Interactive Genetic Algorithms (IGAs) are subjective and interactive methods to evaluate the qualities of offspring generated by genetic operations. We adopt IGA in order to select relevant features in inductive learning problems. The method we propose is used to extract efficient decision knowledge from noisy questionnaire data in marketing data analysis domain. Unlike popular learning-from-example methods, in such tasks, we must interpret the characteristics of the data without clear features of the data nor pre-determined evaluation criteria. The problem is how domain experts get simple, easy-tounderstand, and accurate knowledge from noisy data. The proposed method has been qualitatively and quantitatively validated by a case study on consumer product questionnaire data: the acquired rules are simpler than the results from the direct application of inductive learning; a domain expert admits that they are easy to understand; and they are at the same level on the accuracy compared with the other statistical methods. 1 <s> BIB003 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Fitness Functions for Rule Discovery <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> Fitness Functions for Rule Discovery <s> 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. <s> BIB005 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Fitness Functions for Rule Discovery <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
Recall that, as discussed in section 2.1, ideally the discovered rules should: (a) have a high predictive accuracy; (b) be comprehensible; and (c) be interesting. In this subsection we discuss how these rule quality criteria can be incorporated in a fitness function. To simplify our discussion, throughout this subsection we will again assume that the GA follows the Michigan approach -i.e. an individual represents a single rule. However, the basic ideas discussed below can be easily adapted to GAs following the Pittsburgh approach, where an individual represents a rule set. Let a rule be of the form: IF A THEN C, where A is the antecedent (a conjunction of conditions) and C is the consequent (predicted class), as discussed earlier. A very simple way to measure the predictive accuracy of a rule is to compute the so-called confidence factor (CF) of the rule, defined as: Unfortunately, such a simple predictive accuracy measure favors rules overfitting the data. For instance, if |A| = |A & C| = 1 then the CF of the rule is 100%. However, such a rule is most likely representing an idiosyncrasy of a particular training example, and probably will have a poor predictive accuracy on the test set. A solution for this problem is described next. The predictive performance of a rule can be summarized by a 2 x 2 matrix, sometimes called a confusion matrix, as illustrated in Although this fitness function does a good job in evaluating predictive performance, it has nothing to say about the comprehensibility of the rule. We can extend this fitness function (or any other focusing only on the predictive accuracy of the rule) with a rule comprehensibility measure in several ways. A simple approach is to define a fitness function such as where Simp is a measure of rule simplicity (normalized to take on values in the range 0..1) and w 1 and w 2 are user-defined weights. The Simp measure can be defined in many different ways, depending on the application domain and on the user. In general, its value is inversely proportional to the number of conditions in the rule antecedent -i.e., the shorter the rule, the simpler it is. Several fitness functions that take into account both the predictive accuracy and the comprehensibility of a rule are described in the literature -see e.g. BIB006 , BIB001 ,  , BIB002 . Noda and his colleagues BIB004 have proposed a fitness function which takes into account not only the predictive accuracy but also a measure of the degree of interestingness of a rule. Their GA follows the Michigan approach and was developed for the task of dependence modeling. Their fitness function is essentially a weighted sum of two terms, where one term measures the predictive accuracy of the rule and the other term measures the degree of interestingness (or surprisingness) of the rule. The weights assigned to each term are specified by the user. Another fitness function involving a measure of rule interestingness, more precisely a variation of the well-known J-measure, is discussed in BIB005 . In the above projects the rule interestingness measure is objective. An intriguing research direction would be to design a fitness function based on a subjective rule interestingness measure. In particular, one possibility would be to design a kind of interactive fitness function, where the fitness of an individual depends on the user's evaluation. A similar approach has been reported in an image-enhancement application  , where the user drives GP by deciding which individual should be the winner in tournament selection; and in an attributeselection task BIB003 , where a user drives a GA by interactively and subjectively selecting good prediction rules.