What is the Alternating Decision Tree Learning Algorithm?

The alternating decision tree learning algorithm is an advanced decision tree learning algorithm that uses boosting to gain precision. This type of decision tree is normally used in binary classification problems.

Boosting

Boosting is a meta-algorithm that uses many weak classifiers in together to create one strong classifier. For alternating decision trees, boosting adds three nodes to the tree for each iteration. Then, the algorithm determines a place for the splitter node by analyzing all prediction nodes created by boosting.

The Tree

In essence, the alternating decision tree is an and/or graph that is transversed in order to arrive at predictions. To gain prediction values, the algorithm takes the overall sum of all prediction nodes crossed in the transversal. In other words, the alternating decision tree can make use of all the weak hypotheses in boosting to arrive at a single, easily-understood representation.

Advantages

Alternating decision trees have advantages over both normal decision trees and over normal boosting. Alternating decision trees surpass decision trees in that they have increased performance for predictions due to boosting. Moreover, alternating decision trees can be merged together, something that cannot be done with normal boosting methods.

References

• "Data Mining with Decision Trees : Theory and Applications"; Lior Rokach, Oded Maimon; 2008
• "Nonlinear Estimation and Classification"; The Boosting Approach to Machine Learning An Overview; Robert Schapire; December; 2001
• "Proceedings of the 16th International Conference on Machine Learning"; The Alternating Decision Tree Algorithm; Yoav Freund and Llew Mason; 1999

Resources

• Alternating Decision Tree at WorldLingo