Decision Tree Construction

Decision Tree Construction: There are different ways to construct trees from data. We will concentrate on the top-down, greedy search approach:

Basic idea:
1. Choose the best attribute a* to place at the root of the tree.

Saperate training set D into subsets {D1, D2.......... , Dk} where each subsets Di containing examples having the same value for a*

Recoursivly apply the algorithm on each new subset untill examples having the same class or there are few of them.

Illustration:

Attributes:  Size and Humidity

Size has two values: >t1 or <=t1
Humidity has three values: >t2, (>t3 and <=t2), <=t3

Steps:

• Create a root for the tree
• If all examples are of the same class or the number of examples is below a threshold return that class
• If no attributes available return majority class
• Let a* be the best attribute
• For each possible value v of a*

1. Add a branch below a* labeled “a = v”
2. Let Sv be the subsets of example where attribute a*=v
3. Recursively apply the algorithm to Sv