DECISION TREE LEARNING

Decision tree learning is a method for approximating discrete-valued target functions, in which the learned function is represented by a decision tree.

 DECISION TREE REPRESENTATION

• Decision trees classify instances by sorting them down the tree from the root to some leaf node, which provides the classification of the instance.
• Each node in the tree specifies a test of some attribute of the instance, and each branch descending from that node corresponds to one of the possible values for this attribute.
• An instance is classified by starting at the root node of the tree, testing the attribute specified by this node, then moving down the tree branch corresponding to the value of the attribute in the given example. This process is then repeated for the subtree rooted at the new node.

 

FIGURE: A decision tree for the concept PlayTennis. An example is classified by sorting it through the tree to the appropriate leaf node, then returning the classification associated with this leaf

• Decision trees represent a disjunction of conjunctions of constraints on the attribute values of instances.
• Each path from the tree root to a leaf corresponds to a conjunction of attribute tests, and the tree itself to a disjunction of these conjunctions

For example, the decision tree shown in above figure corresponds to the expression 

(Outlook = Sunny ∧ Humidity = Normal)

∨       (Outlook = Overcast)

∨       (Outlook = Rain ∧ Wind = Weak)