Barros / Freitas Automatic Design of Decision-Tree Induction Algorithms

2015
ISBN: 978-3-319-14231-9
Verlag: Springer Nature Switzerland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 184 Seiten

Reihe: SpringerBriefs in Computer Science

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.

Autoren/Hrsg.

Barros, Rodrigo C.

Freitas, Alex A.

Inhaltsverzeichnis

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