On Generating and Simplifying Decision Trees Using Tree Automata Models

Abstract

Tree automata are widely used in applications such as XML document manipulation, natural language processing, and formal verification. We propose in this paper to generate decision trees classifiers using tree automata models. Mainly, two objectives are : 1) fitting these methods in a formal frame and, 2) using tree automata in modeling decision trees and classifying heterogeneous information sources. Specifically, the size of a decision tree is reduced by a post-pruning procedure: a given decision tree is converted into a tree automaton and then the latter is simplified by eliminating useless states and non-determinism. We report some empirical experiments on real-world datasets.