## Data Mining and Knowledge Discovery with Evolutionary AlgorithmsThis book addresses the integration of two areas of computer science, namely data mining and evolutionary algorithms. Both these areas have become increas ingly popular in the last few years, and their integration is currently an area of active research. In essence, data mining consists of extracting valid, comprehensible, and in teresting knowledge from data. Data mining is actually an interdisciplinary field, since there are many kinds of methods that can be used to extract knowledge from data. Arguably, data mining mainly uses methods from machine learning (a branch of artificial intelligence) and statistics (including statistical pattern recog nition). Our discussion of data mining and evolutionary algorithms is primarily based on machine learning concepts and principles. In particular, in this book we emphasize the importance of discovering comprehensible, interesting knowledge, which the user can potentially use to make intelligent decisions. In a nutshell, the motivation for applying evolutionary algorithms to data mining is that evolutionary algorithms are robust search methods which perform a global search in the space of candidate solutions (rules or another form of knowl edge representation). In contrast, most rule induction methods perform a local, greedy search in the space of candidate rules. Intuitively, the global search of evolutionary algorithms can discover interesting rules and patterns that would be missed by the greedy search. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 Introduction | 3 |

111 Desirable Properties of Discovered Knowledge | 4 |

12 Knowledge Representation | 5 |

121 Prediction Rules | 6 |

13 An Overview of Data Mining Paradigms | 7 |

131 Rule Induction | 9 |

132 Evolutionary Algorithms | 11 |

2 Data Mining Tasks and Concepts | 15 |

7 Genetic Programming for Rule Discovery | 141 |

72 Booleanizing All Terminals | 142 |

721 Methods for Booleanizing Attributes | 144 |

722 Examples of GP Systems Booleanizing Terminals | 147 |

73 ConstrainedSyntax and StronglyTyped GP | 148 |

74 GrammarBased GP for Rule Discovery | 152 |

75 GP for DecisionTree Building | 155 |

751 Evolving Decision Trees with FirstOrderLogic Conditions | 156 |

211 The Nondeterminism of the Classification Task | 19 |

213 Estimating Accuracy via Training and Testing | 21 |

22 Dependence Modeling | 24 |

221 Dependence Modeling vs AssociationRule Discovery | 25 |

23 The Challenge of Measuring PredictionRule Quality | 26 |

232 Measuring Rule Comprehensibility | 28 |

233 Measuring Rule Interestingness | 29 |

24 Clustering | 33 |

241 Hierarchical Agglomerative Clustering | 35 |

242 The KMeans Algorithm | 36 |

243 The Challenge of Measuring Clustering Quality | 37 |

25 Inductive Bias | 38 |

251 The DomainDependent Effectiveness of a Bias | 39 |

252 The Simplicity Bias of Occams Razor | 40 |

253 The Minimum Description Length MDL Principle | 41 |

References | 42 |

3 Data Mining Paradigms | 47 |

311 DecisionTree Building | 49 |

312 DecisionTree Pruning | 51 |

313 Pros and Cons of DecisionTree Algorithms | 52 |

314 The Inductive Bias of DecisionTree Algorithms | 54 |

315 Linear Oblique Decision Trees | 55 |

32 Rule Induction Algorithms | 56 |

321 The Pitfall of Attribute Interaction for Greedy Algorithms | 57 |

33 InstanceBased Learning Nearest Neighbor Algorithms | 60 |

References | 62 |

4 Data Preparation | 67 |

411 The Motivation for Attribute Selection | 68 |

413 Attribute Selection as a Particular Case of Attribute Weighting | 73 |

421 An Overview of Discretization Methods | 74 |

422 The Pros and Cons of Discretization | 75 |

43 Attribute Construction | 76 |

431 Categorizing Attribute Construction Methods | 77 |

References | 78 |

5 Basic Concepts of Evolutionary Algorithms | 81 |

511 Key Issues in the Design of EAs | 83 |

52 Selection Methods | 85 |

53 Genetic Algorithms GA | 86 |

532 Crossover Operators | 88 |

533 Mutation Operators | 90 |

54 Genetic Programming GP | 91 |

541 Function Set | 92 |

542 Crossover Operators | 94 |

543 Mutation Operators | 97 |

544 The Standard GP Approach for Classification | 101 |

545 Code Bloat | 102 |

55 Niching | 103 |

References | 105 |

6 Genetic Algorithms for Rule Discovery | 109 |

612 Encoding a Rule Antecedent | 112 |

613 Encoding a Rule Consequent | 118 |

621 GeneralizingSpecializing Crossover | 121 |

622 GeneralizingSpecializing Mutation | 124 |

623 Condition RemovalInsertion | 125 |

624 Rule InsertionRemoval | 126 |

63 TaskSpecific Population Initialization and Seeding | 128 |

64 TaskSpecific RuleSelection Methods | 129 |

65 Fitness Evaluation | 131 |

References | 136 |

752 Evolving Linear Decision Trees | 157 |

753 Hybrid GP Cellular Automaton and Simulated Annealing | 159 |

76 On the Quality of Rules Discovered by GP | 160 |

References | 163 |

8 Evolutionary Algorithms for Clustering | 167 |

811 Individual Representation | 168 |

812 Genetic Operators | 169 |

82 CentroidMedoidBased Individual Representation | 171 |

822 MedoidBased Individual Representation | 173 |

83 InstanceBased Individual Representation | 174 |

832 GraphBased Individual Representation | 175 |

84 Fitness Evaluation | 176 |

841 Coping with Degenerate Partitions | 178 |

85 EAs vs Conventional Clustering Techniques | 179 |

9 Evolutionary Algorithms for Data Preparation | 181 |

911 Individual Encoding and Genetic Operators | 182 |

912 Fitness Evaluation | 184 |

913 Attribute Selection via Search for Partially Defined Instances | 189 |

915 Attribute Selection for Clustering | 191 |

916 Discussion | 192 |

92 EAs for Attribute Weighting | 193 |

921 Attribute Weighting | 194 |

922 Towards Constructive Induction | 195 |

93 Combining Attribute Selection and Attribute Weighting | 196 |

94 GP for Attribute Construction | 198 |

941 Constructing Combinations of Boolean Attributes | 199 |

942 Discovering Specialized Functions | 201 |

and Construction with a Hybrid GAGP | 202 |

References | 203 |

10 Evolutionary Algorithms for Discovering Fuzzy Rules | 207 |

1012 Operations on Fuzzy Sets | 209 |

1013 Membership Functions | 211 |

102 Fuzzy Prediction Rules vs Crisp Prediction Rules | 215 |

103 A Simple Taxonomy of EAs for FuzzyRule Discovery | 217 |

1041 Individual Encoding | 218 |

1042 Determining the Degree of Matching Between a Fuzzy Rule Antecedent and a Data Instance | 222 |

1043 Using Fuzzy Rules to Classify a Data Instance | 223 |

1044 Specifying the Shape and the Number of Membership Functions | 224 |

105 Using EAs for Tuning Membership Functions | 226 |

106 Using EAs for Both Generating Fuzzy Rules and Tuning Membership Functions | 227 |

107 Fuzzy Fitness Evaluation | 230 |

11 Scaling up Evolutionary Algorithms for Large Data Sets | 235 |

1112 Adaptive TrainingSubset Selection | 237 |

112 An Overview of Parallel Processing | 239 |

1122 Load Balancing | 241 |

1123 Data Parallelism vs Control Parallelism | 242 |

1124 Speed up and Efficiency Measures | 244 |

113 Parallel EAs for Data Mining | 245 |

1131 Exploiting Control Parallelism | 248 |

1132 Exploiting Data Parallelism | 250 |

1133 Exploiting Hybrid ControlDataParallelism | 252 |

References | 255 |

12 Conclusions and Research Directions | 257 |

1212 On Knowledge Comprehensibility | 258 |

1221 Developing EAs for Data Preparation | 259 |

260 | |

Index | |

### Other editions - View all

Data Mining and Knowledge Discovery with Evolutionary Algorithms Alex A. Freitas Limited preview - 2013 |

Data Mining and Knowledge Discovery with Evolutionary Algorithms Alex A. Freitas No preview available - 2012 |

Data Mining and Knowledge Discovery with Evolutionary Algorithms Alex A. Freitas No preview available - 2014 |

### Common terms and phrases

application approach assigned associated assume attribute selection basic idea bias boolean called candidate chapter classification cluster comprehensible Computation condition Conference considered consists construction contains continuous corresponding covered crossover data instances data mining data set decision tree defined depends discovered discussed domain effectiveness encoding et al evaluation evolutionary algorithms Evolutionary Computation example Figure fitness function Freitas genes genetic Genetic Algorithms Genetic Programming genotype given goal Hence important individual interaction interesting International involving kind measure membership functions methods Michigan Morgan Kaufmann mutation namely node Note operator original parallel partition performance population possible prediction rules predictive accuracy probability problem Proceedings processing processors produced proposed representation represents respectively result rule antecedent rule conditions rule induction rule set satisfy shown simple single solution space specified subsection task tends tion usually weights