Data Mining and Knowledge Discovery with Evolutionary Algorithms

Front Cover
Springer Science & Business Media, Aug 21, 2002 - Computers - 264 pages
This 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
1222 Developing Multiobjective EAs for Data Mining
260
Index
Copyright

Other editions - View all

Common terms and phrases