Advertisement
Published in:
2006 | OriginalPaper | Chapter
Finding Optimal Decision Trees
Authors : Petr Máša, Tomáš Kočka
Published in: Intelligent Information Processing and Web Mining
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper presents a new algorithm that finds the generative model of a decision tree from data. We show that for infinite data and finite number of attributes the algorithm always finds the generative model (i.e. the model of the decision tree, from which the data were generated) except measure zero set of distributions. The algorithm returns reasonable results even when the above-mentioned assumptions are not satisfied. The algorithm is polynomial in the number of leaves of the generative model compared to the exponential complexity of the trivial exhaustive search algorithm. Similar result was recently obtained for learning Bayesian networks from data ([1],[2]). Experimental comparison of the new algorithm with the CART standard on both simulated and real data is shown. The new algorithm shows significant improvements over the CART algorithm in both cases. The whole paper is for simplicity restricted to binary variables but can be easily generalized.