A Beam Search Based Decision Tree Induction Algorithm

A Beam Search Based Decision Tree Induction Algorithm

Márcio Porto Basgalupp (Federal University of Sao Paulo (UNIFESP), Brazil), Rodrigo Coelho Barros (University of Sao Paulo (ICMC-USP), Brazil), André C. P. L. F. de Carvalho (University of Sao Paulo (ICMC-USP), Brazil) and Alex A. Freitas (University of Kent, UK)
DOI: 10.4018/978-1-4666-1833-6.ch020
OnDemand PDF Download:


Decision tree induction algorithms are highly used in a variety of domains for knowledge discovery and pattern recognition. They have the advantage of producing a comprehensible classification model and satisfactory accuracy levels in several application domains. Most well-known decision tree induction algorithms perform a greedy top-down strategy for node partitioning that may lead to sub-optimal solutions that overfit the training data. Some alternatives for the greedy strategy are the use of ensemble of classifiers or, more recently, the employment of the evolutionary algorithms (EA) paradigm to evolve decision trees by performing a global search in the space of candidate trees. Both strategies have their own disadvantages, like the lack of comprehensible solutions (in the case of ensembles) or the high computation cost of EAs. Hence, the authors of this chapter present a new algorithm that seeks to avoid being trapped in local-optima by doing a beam search during the decision tree growth. In addition, their strategy keeps the comprehensibility of the traditional methods and is much less time-consuming than evolutionary algorithms.
Chapter Preview


Classification aims at building a concise class distribution model taking into account a set of predictive attributes. The outcome of such a model is used for assigning class labels to new examples whose only known information are the values of the predictive attributes (Ye, 2003).

Complete Chapter List

Search this Book: