Machine learning algorithms for inferring decision trees typically choose a single "best" tree to describe the training data. Recent research has shown that classification performance can be significantly improved by voting predictions of multiple, independently produced decision trees. This paper describes an algorithm, OB1, that produces a weighted sum over many possible models. Model weights are determined by the prior probability of the model, as well as the performance of the model during training. We describe an implementation of OB1 that includes all possible decision trees as well as naive Bayesian models within a single option tree. Constructing all possible decision trees is very expensive, growing exponentially in the number of attributes. However it is possible to use the internal structure of the option tree to avoid recomputing values. In addition, the current implementation allows the option tree to be depth bounded. OB1 is compared with a number of other decision tree and instance based learning algorithms using a selection of data sets from the UCI repository and a maximum option tree depth of three attributes. Both information gain and percentage correct are used for the Comparison. For the information gain measure OB1 performs significantly better than the other algorithms. When using percentage correct OB1 is significantly better than all the algorithms except naive Bayes and boosted C5.0 which perform slightly worse than OB1.
展开▼