- author = "Christian Setzkorn",
- title = "On The Use Of Multi-Objective Evolutionary Algorithms For Classification Rule Induction",
- school = "University of Liverpool",
- year = "2005",
- address = "UK",
- month = mar,
- keywords = "genetic algorithms, genetic programming, MOGA, MOGP",
-
URL = "
http://www.zoonosis.ac.uk:8080/download/attachments/17/thesis.pdf",
- size = "259 pages",
- abstract = "The extraction of comprehensible and general classifiers from data in the form of rule systems is an important task within many problem domains. This thesis proposes and evaluates a multi-objective evolutionary algorithm for this task. Multi-objective evolutionary algorithms are a modern heuristic search method, which can generate different trade-off solutions for several objectives in a single run. Hence they can be used to optimise the complexity and the fit of rule systems to the data. Complex rule systems are required to fit the data well. However, overly complex rule systems often generalise badly on new data and are incomprehensible. In addition, they require more storage space and longer execution times. The generation of several trade-off solutions has another advantage. The decision maker is given a choice. If her/his preferences change (e.g. if the classifiers fit to the data becomes more important than its complexity/comprehensibility) the decision maker can choose another solution from the generated set of trade-off solutions. This helps saving computational resources, as the search does not have to be repeated. The proposed multi-objective evolutionary algorithm is evaluated on a large number of benchmark datasets. The results are compared with several existing approaches. It is shown that the proposed multi-objective evolutionary algorithm is competitive with the other approaches on more than fifty percent of these benchmark datasets. This thesis also investigates methods to reduce the execution time and the number of parameters of the proposed multi-objective evolutionary algorithm. The JavaSpaces technology is used to reduce the execution time of the multi-objective evolutionary algorithm. It is shown that this technology can be used to harvest the computational resources of a heterogeneous multi-user computer network in a simple, affordable and reusable manner.",
-
notes = "THESIS 20541.SET http://library.liv.ac.uk Contents
1 Introduction 1
1.1 Motivation 1
1.2 Outline of the Thesis 6
1.3 Contributions 6
1.4 Publications 8
2 Classification using Fuzzy Rule Systems 9
2.1 Introduction 9
2.2 The Problem of Classification 10
2.3 Classification and Comprehensibility 10
2.4 Classification Using Fuzzy Classification Rule Systems 12
2.4.1 Introduction to Classical Rule Systems 12
2.4.2 Advantages of Classical Rule Systems 15
2.4.3 Disadvantages of Classical Rule Systems 15
2.4.4 Classification Using Fuzzy Rule Systems 16
2.5 The Problem of Overfitting 21
2.5.1 An Overview of Methods for the Prevention of Overfitting 25
2.5.1.1 Minimum Description Length Principle 25
2.5.1.2 Resampling Methods 26
2.5.1.3 Ensemble Methods 27
2.5.1.4 Stepwise Methods 28
2.5.1.5 Bayesian Methods 29
2.5.1.6 Early Stopping Rules 30
2.5.1.7 Statistical Learning Theory Approaches 31
2.5.1.8 Regularisation Methods 32
2.6 Determining the Fit of Fuzzy Classification Rule Systems to Data 33
2.6.1 The Area under the Receiver-Operating Curve for Two Class Problems 40
2.6.2 The Area under the Receiver-Operating Curve for Multiple Class Problems 44",
-
notes = "2.7 Summary 45
3 Induction of Fuzzy Classification Rule Systems Using Multi-Objective Evolutionary Algorithms 47
3.1 Introduction 47
3.2 Introduction to Evolutionary Algorithms 48
3.2.1 Representation Scheme 49
3.2.2 Genetic Operator Process 49
3.2.3 Selection Process 50
3.2.4 Diversity Promotion 52
3.2.5 Evolutionary Algorithm Structure 53
3.3 Introduction to Multi-Objective Evolutionary Algorithms 55
3.3.1 Multi-Objective Optimisation and Relevant Concepts 55
3.3.2 An Overview of Existing Multi-Objective Evolutionary Algorithms 60
3.3.2.1 Criterion-Based Selection Approaches 60
3.3.2.2 Aggregation-Based Selection Approaches 61
3.3.2.3 Pareto-Based Selection Approaches 62
3.3.3 Performance Evaluation of MOEAs 64
3.4 Review of Inducers that Use Evolutionary Algorithms for Fuzzy Classification Rule Induction 66
3.4.1 The Main Paradigms 66
3.4.1.1 Michigan Approach 67
3.4.1.2 Pittsburgh Approach 70
3.4.1.3 Iterative Rule Learning Approach 72
3.4.1.4 Cooperative Co-Evolutionary Approaches 73
3.4.2 Existing Single-Objective Evolutionary Algorithms for the Induction of Fuzzy Classification Rules 75
3.4.3 Existing Multi-Objective Evolutionary Algorithms for the Induction of Classification Rules 78
3.5 Discussion and Summary 81",
-
notes = "4 Overview of the Implemented Multi-Objective
Evolutionary Algorithm 85
4.1 Introduction 85
4.2 Representation Scheme 86
4.3 Genetic Operator Process 92
4.3.1 The Application Of Several Genetic Operators 93
4.3.2 Genetic Operators Involving One Individual 94
4.3.2.1 GO11 Operator 94
4.3.2.2 GO12 Operator 95
4.3.2.3 GO13 Operator 95
4.3.2.4 GO14 Operator 95
4.3.2.5 GO15 Operator 95
4.3.2.6 GO16 Operator 96
4.3.2.7 GO17 Operator 96
4.3.2.8 GO18 Operator 96
4.3.2.9 GO19 Operator 98
4.3.2.10 GO110 Operator 98
4.3.2.11 GO111 Operator 99
4.3.2.12 GO112 Operator 99
4.3.2.13 GO113 Operator 99
4.3.2.14 GO114 Operator 99
4.3.2.15 GO115 Operator 100
4.3.2.16 GO116 Operator 101
4.3.2.17 GO117 Operator 101
4.3.2.18 GO118 Operator 101
4.3.3 Genetic Operators Involving Two Individuals 102
4.3.3.1 GO21 Operator 102
4.3.3.2 GO22 Operator 103
4.3.3.3 GO23 Operator 104
4.3.3.4 GO24 Operator 105
4.3.3.5 GO25 Operator 106
4.3.3.6 GO26 Operator 106
4.4 Archive 106
4.5 The Fitness Assignment 109
4.5.1 Possible Objectives 109
4.5.1.1 O1 - Hand et al. AUC 109
4.5.1.2 O2 - Fawcett AUC 109
4.5.1.3 O3 - Accuracy 109
4.5.1.4 O4 - Number Of Rules 110
4.5.1.5 O5 - Number Of Nodes 110
4.5.1.6 O6 - Number Of Different Features 110
4.5.2 Fitness Assignment 111
4.6 Selection Process 112
4.7 The Overall Algorithm 112
4.8 Summary 115
5 JavaSpaces - A Method to Accelerate Multi-Objective Evolutionary Algorithms 117
5.1 Introduction 117
5.2 Parallel Evolutionary Algorithms - Motivation and Brief Review 118
5.2.1 Master-Slave Parallel Evolutionary Algorithms 119
5.2.2 Multiple-Deme Parallel Evolutionary Algorithms 120
5.2.3 Other Parallel Evolutionary Algorithms 121
5.3 Implementation of Parallel Evolutionary Algorithms Using JavaSpaces 121
5.3.1 A Brief Introduction to JavaSpaces 121
5.3.2 The Implemented Parallel Evolutionary Algorithms 122
5.3.2.1 Synchronous Master-Slave Parallel Evolutionary Algorithm 122
5.3.2.2 Asynchronous Master-Slave Parallel Evolutionary Algorithm 125
5.3.2.3 Multiple-Deme Parallel Evolutionary Algorithm 125
5.4 Experiments and Results 127
5.4.1 Preliminary Experiments and Results 127 BibTeX entry too long. Truncated
