Automatic Design of Decision-Tree Induction Algorithms (eBook)

Contents 7
Notations 10
1 Introduction 12
1.1 Book Outline 15
References 16
2 Decision-Tree Induction 17
2.1 Origins 17
2.2 Basic Concepts 18
2.3 Top-Down Induction 19
2.3.1 Selecting Splits 21
2.3.2 Stopping Criteria 39
2.3.3 Pruning 40
2.3.4 Missing Values 46
2.4 Other Induction Strategies 47
2.5 Chapter Remarks 50
References 50
3 Evolutionary Algorithms and Hyper-Heuristics 56
3.1 Evolutionary Algorithms 56
3.1.1 Individual Representation and Population Initialization 58
3.1.2 Fitness Function 60
3.1.3 Selection Methods and Genetic Operators 61
3.2 Hyper-Heuristics 63
3.3 Chapter Remarks 65
References 65
4 HEAD-DT: Automatic Design of Decision-Tree Algorithms 68
4.1 Introduction 69
4.2 Individual Representation 70
4.2.1 Split Genes 70
4.2.2 Stopping Criteria Genes 72
4.2.3 Missing Values Genes 72
4.2.4 Pruning Genes 73
4.2.5 Example of Algorithm Evolved by HEAD-DT 75
4.3 Evolution 76
4.4 Fitness Evaluation 78
4.5 Search Space 81
4.6 Related Work 82
4.7 Chapter Remarks 83
References 84
5 HEAD-DT: Experimental Analysis 86
5.1 Evolving Algorithms Tailored to One Specific Data Set 87
5.2 Evolving Algorithms from Multiple Data Sets 92
5.2.1 The Homogeneous Approach 93
5.2.2 The Heterogeneous Approach 108
5.2.3 The Case of Meta-Overfitting 130
5.3 HEAD-DT's Time Complexity 132
5.4 Cost-Effectiveness of Automated Versus Manual Algorithm Design 132
5.5 Examples of Automatically-Designed Algorithms 134
5.6 Is the Genetic Search Worthwhile? 135
5.7 Chapter Remarks 136
References 148
6 HEAD-DT: Fitness Function Analysis 149
6.1 Performance Measures 149
6.1.1 Accuracy 150
6.1.2 F-Measure 150
6.1.3 Area Under the ROC Curve 151
6.1.4 Relative Accuracy Improvement 151
6.1.5 Recall 152
6.2 Aggregation Schemes 152
6.3 Experimental Evaluation 153
6.3.1 Results for the Balanced Meta-Training Set 154
6.3.2 Results for the Imbalanced Meta-Training Set 164
6.3.3 Experiments with the Best-Performing Strategy 172
6.4 Chapter Remarks 177
References 178
7 Conclusions 179
7.1 Limitations 180
7.2 Opportunities for Future Work 181
7.2.1 Extending HEAD-DT's Genome: New Induction Strategies, Oblique Splits, Regression Problems 181
7.2.2 Multi-objective Fitness Function 181
7.2.3 Automatic Selection of the Meta-Training Set 182
7.2.4 Parameter-Free Evolutionary Search 182
7.2.5 Solving the Meta-Overfitting Problem 183
7.2.6 Ensemble of Automatically-Designed Algorithms 183
7.2.7 Grammar-Based Genetic Programming 184
References 184