Alternating Decision Tree - Description of The Algorithm

Description of The Algorithm

The inputs to the alternating decision tree algorithm are:

• A set of inputs where is a vector of attributes and is either -1 or 1. Inputs are also called instances.
• A set of weights corresponding to each instance.

The fundamental element of the ADTree algorithm is the rule. A single rule consists of a precondition, a condition, and two scores. A condition is a predicate of the form "attribute value." A precondition is simply a logical conjunction of conditions. Evaluation of a rule involves a pair of nested if statements:

1 if(precondition) 2 if(condition) 3 return score_one 4 else 5 return score_two 6 end if 7 else 8 return 0 9 end if

Several auxiliary functions are also required by the algorithm:

• returns the sum of the weights of all positively labeled examples that satisfy predicate
• returns the sum of the weights of all negatively labeled examples that satisfy predicate
• returns the sum of the weights of all examples that satisfy predicate

The algorithm is as follows:

1 function ad_tree 2 input Set of training instances 3 4 for all 5 6 a rule with scores and, precondition "true" and condition "true." 7 8 the set of all possible conditions 9 for 10 get values that minimize 11 12 13 14 new rule with precondition, condition, and weights and 15 16 end for 17 return set of

The set grows by two preconditions in each iteration, and it is possible to derive the tree structure of a set of rules by making note of the precondition that is used in each successive rule.