The alternating decision tree learning algorithm

The application of boosting procedures to decision tree algorithms has been shown to produce very accurate classi ers. These classiers are in the form of a majority vote over anumber of decision trees. Unfortunately, these classi ers are often large, complex and di cult to interpret. This paper describes a new type of classi cation rule, the alternating decision tree, which is a generalization of decision trees, voted decision trees and voted decision stumps. At the same time classi ers of this type are relatively easy to interpret. We present a learning algorithm for alternating decision trees that is based on boosting. Experimental results show it is competitive with boosted decision tree algorithms such as C5.0, and generates rules that are usually smaller in size and thus easier to interpret. In addition these rules yield a natural measure of classi cation con dence which canbe used to improve the accuracy at the cost of abstaining from predicting examples that are hard to classify.