A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> Sharing is a popular method for introducing divergency in genetic algorithms for multimodal function optimization. In this paper we define three sharing methods and investigate their applicability for concept learning of disjunctive rules from preclassified examples. The sharing methods are incorporated in JGA, a genetic algorithm based concept learning system, where they are compared with two other methods for learning disjunctive rules. <s> BIB001 </s> A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> Describes an extension of a genetic algorithm (GA) based separate-and-conquer propositional rule induction algorithm called SIA (Supervised Inductive Algorithm). While the original algorithm is computationally attractive and is also able to handle both nominal and continuous attributes efficiently, our algorithm further improves it by taking into account recent advances in the rule induction and evolutionary computation communities. The refined system has been compared to other GA-based and non-GA-based rule learning algorithms on a number of benchmark data sets from the UCI (University of California, Irvine) machine learning repository. The results show that the proposed system can achieve higher performance while still producing a smaller number of rules. <s> BIB002 </s> A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> This paper addresses the well-known classification task of data mining, where the objective is to predict the class which an example belongs to. Discovered knowledge is expressed in the form of high-level, easy-to-interpret classification rules. In order to discover classification rules, we propose a hybrid decision tree/genetic algorithm method. The central idea of this hybrid method involves the concept of small disjuncts in data mining, as follows. In essence, a set of classification rules can be regarded as a logical disjunction of rules. so that each rule can be regarded as a disjunct. A small disjunct is a rule covering a small number of examples. Due to their nature, small disjuncts are error prone. However, although each small disjunct covers just a few examples, the set of all small disjuncts can cover a large number of examples, so that it is important to develop new approaches to cope with the problem of small disjuncts. In our hybrid approach, we have developed two genetic algorithms (GA) specifically designed for discovering rules covering examples belonging to small disjuncts, whereas a conventional decision tree algorithm is used to produce rules covering examples belonging to large disjuncts. We present results evaluating the performance of the hybrid method in 22 real-world data sets. <s> BIB003 </s> A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> Classification is one of the fundamental tasks of data mining. Most rule induction and decision tree algorithms perform a local, greedy search to generate classification rules that are often more complex than necessary. Evolutionary algorithms for pattern classification have recently received increased attention because they can perform global searches. In this paper, we propose a new approach for discovering classification rules by using gene expression programming (GEP), a new technique of genetic programming (GP) with linear representation. The antecedent of discovered rules may involve many different combinations of attributes. To guide the search process, we suggest a fitness function considering both the rule consistency gain and completeness. A multiclass classification problem is formulated as multiple two-class problems by using the one-against-all learning method. The covering strategy is applied to learn multiple rules if applicable for each class. Compact rule sets are subsequently evolved using a two-phase pruning method based on the minimum description length (MDL) principle and the integration theory. Our approach is also noise tolerant and able to deal with both numeric and nominal attributes. Experiments with several benchmark data sets have shown up to 20% improvement in validation accuracy, compared with C4.5 algorithms. Furthermore, the proposed GEP approach is more efficient and tends to generate shorter solutions compared with canonical tree-based GP classifiers. <s> BIB004 </s> A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> 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. <s> BIB005 </s> A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> Classical methods for Inductive Concept Learning (ICL) rely mostly on using specific search strategies, such as hill climbing and inverse resolution. These strategies have a great exploitation power, but run the risk of being incapable of escaping from local optima. An alternative approach to ICL is represented by Evolutionary Algorithms (EAs). EAs have a great exploration power, thus they have the capability of escaping from local optima, but their exploitation power is rather poor. These observations suggest that the two approaches are applicable to partly complementary classes of learning problems. More important, they indicate that a system incorporating features from both approaches could benefit from the complementary qualities of the approaches. In this paper we experimentally validate this statement. To this end, we incorporate different search strategies in a framework based on EAs for ICL. Results of experiments show that incorporating standard search strategies helps the EA in achieving better results. <s> BIB006 </s> A Review of Evolutionary Algorithms for Data Mining <s> Searching for a Diverse Set of Rules <s> Data Mining: Practical Machine Learning Tools and Techniques offers a thorough grounding in machine learning concepts as well as practical advice on applying machine learning tools and techniques in real-world data mining situations. This highly anticipated third edition of the most acclaimed work on data mining and machine learning will teach you everything you need to know about preparing inputs, interpreting outputs, evaluating results, and the algorithmic methods at the heart of successful data mining. Thorough updates reflect the technical changes and modernizations that have taken place in the field since the last edition, including new material on Data Transformations, Ensemble Learning, Massive Data Sets, Multi-instance Learning, plus a new version of the popular Weka machine learning software developed by the authors. Witten, Frank, and Hall include both tried-and-true techniques of today as well as methods at the leading edge of contemporary research. *Provides a thorough grounding in machine learning concepts as well as practical advice on applying the tools and techniques to your data mining projects *Offers concrete tips and techniques for performance improvement that work by transforming the input or output in machine learning methods *Includes downloadable Weka software toolkit, a collection of machine learning algorithms for data mining tasks-in an updated, interactive interface. Algorithms in toolkit cover: data pre-processing, classification, regression, clustering, association rules, visualization <s> BIB007
This subsection discusses two mechanisms for discovering a diverse set of rules. It is assumed that each individual represents a single classification rule (Michigan-style approach). Note that the mechanisms for rule diversity discussed below are not normally used in the Pittsburgh approach, where an individual already represents a set of rules whose fitness implicitly depends on how well the rules in the set cooperate with each other. First, one can use a niching method. The basic idea of niching is to avoid that the population converges to a single high peak in the search space and to foster the EA to create stable subpopulations of individuals clustered around each of the high peaks. In general the goal is to obtain a kind of "fitnessproportionate" convergence, where the size of the subpopulation around each peak is proportional to the height of that peak (i.e., to the quality of the corresponding candidate solution). For instance, one of the most popular niching methods is fitness sharing   . In this method, the fitness of an individual is reduced in proportion to the number of similar individuals (neighbors), as measured by a given distance metric. In the context of rule discovery, this means that if there are many individuals in the current population representing the same rule or similar rules, the fitness of those individuals will be considerably reduced, and so they will have a considerably lower probability of being selected to produce new offspring. This effectively penalizes individuals which are in crowded regions of the search space, forcing the EA to discover a diverse set of rules. Note that fitness sharing was designed as a generic niching method. By contrast, there are several niching methods designed specifically for the discovery of classification rules. An example is the "universal suffrage" selection method (Giordana et al. 1994; BIB006 where -using a political metaphor -individuals to be selected for reproduction are "elected" by the training data instances. The basic idea is that each data instance "votes" for a rule that covers it in a probabilistic fitness-based fashion. More precisely, let R be the set of rules (individuals) that cover a given data instance i, i.e., the set of rules whose antecedent is satisfied by data instance i. The better the fitness of a given rule rin the set R, the larger the probability that rule r will receive the vote of data instance i. Note that in general only rules covering the same data instances are competing with each other. Therefore, this selection method implements a form of niching, fostering the evolution of different rules covering different parts of the data space. For more information about niching methods in the context of discovering classification rules the reader is referred to BIB001 BIB005 . Another kind of mechanism that can be used to discover a diverse set of rules consists of using the previously-mentioned "sequential covering" approach -also known as "separate-and-conquer". The basic idea is that the EA discovers one rule at a time, so that in order to discover multiple rules the EA has to be run multiple times. In the first run the EA is initialized with the full training set and an empty set of rules. After each run of the EA, the best rule evolved by the EA is added to the set of discovered rules and the examples correctly covered by that rule are removed from the training set, so that the next run of the EA will consider a smaller training set. The process proceeds until all examples have been covered. Some examples of EAs using the sequential covering approach can be found in BIB002 BIB004 BIB003 . Note that the sequential covering approach is not specific to EAs. It is used by several non-evolutionary rule induction algorithms, and it is also discussed in data mining textbooks such as BIB007 .