Automatic Design of Decision-Tree Induction Algorithms (eBook)

Rodrigo C. Barros, André C.P.L.F de Carvalho, Alex A. Freitas (Autoren)

eBook Download: PDF

2015 | 2015
XII, 176 Seiten
Springer International Publishing (Verlag)
978-3-319-14231-9 (ISBN)

Infos

Presents a detailed study of the major design components that constitute a top-down decision-tree induction algorithm, including aspects such as split criteria, stopping criteria, pruning and the approaches for dealing with missing values. Whereas the strategy still employed nowadays is to use a 'generic' decision-tree induction algorithm regardless of the data, the authors argue on the benefits that a bias-fitting strategy could bring to decision-tree induction, in which the ultimate goal is the automatic generation of a decision-tree induction algorithm tailored to the application domain of interest. For such, they discuss how one can effectively discover the most suitable set of components of decision-tree induction algorithms to deal with a wide variety of applications through the paradigm of evolutionary computation, following the emergence of a novel field called hyper-heuristics.

'Automatic Design of Decision-Tree Induction Algorithms' would be highly useful for machine learning and evolutionary computation students and researchers alike.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 4.2.2015
• Reihe/Serie: SpringerBriefs in Computer Science
• Reihe/Serie: SpringerBriefs in Computer Science
• Zusatzinfo: XII, 176 p. 18 illus.
• Verlagsort: Cham
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik
• Schlagworte: Automatic Design • decision trees • evolutionary computation • hyper-heuristics • machine learning
• ISBN-10: 3-319-14231-3 / 3319142313
• ISBN-13: 978-3-319-14231-9 / 9783319142319