Working of the Decision Tree Method for Classification

What is a Decision Tree?

A decision tree is a flow-chart-like tree structure in which:

• each internal node denotes a test on an attribute,
• each branch represents an outcome of that test,
• each leaf node holds a class label (the prediction),
• the topmost node is the root.

Step-by-Step Construction (Tree Induction)

1. Attribute selection — the best-splitting attribute is chosen at each node using an attribute-selection measure such as Information Gain (used by ID3), Gain Ratio (C4.5), or Gini Index (CART). The attribute that best separates the training tuples (maximally reduces impurity) is selected.
2. Partition/branching — the training set is split according to the distinct values of the chosen attribute.
3. Recursion — the selection-and-split process is repeated on each branch using the remaining attributes.
4. Stopping criteria — a node becomes a leaf when all its tuples belong to the same class, or no attribute remains, or the tuples are too few / other stopping rules apply. The node is labelled with the majority class.
5. Pruning — the fully grown tree is pruned (pre- or post-pruning) to remove branches that overfit the noise, thereby improving generalisation.

To illustrate the attribute-selection idea: given a training set with classes, first compute the entropy of the target attribute $E(S)=-\sum p_i \log_2 p_i$. For each candidate attribute, compute the weighted entropy after splitting by it and take the difference (the information gain); the attribute with the maximum gain becomes the splitting attribute at that node.

Example Dataset

Outlook	Temperature	Play?
Sunny	Hot	No
Overcast	Cool	Yes
Rain	Mild	Yes
Sunny	Mild	Yes

Here the root split is chosen on Outlook (it gives the highest information gain). The resulting tree:

           [Outlook]
         /    |     \
      sunny overcast rain
        |       |      |
      [Temp]   Yes    Yes
      /    \
    Hot     Mild
     |       |
    No      Yes

Classification (Prediction) Phase

A new, unseen tuple is routed from the root down a path whose attribute tests match its values until it reaches a leaf; the class label stored in that leaf is the predicted class.

Advantages

• Easy to understand and interpret; can be directly converted to IF–THEN rules.
• Handles both numeric and categorical attributes.
• Requires little data preparation and no domain knowledge.

Limitations

• Greedy induction — a small change in data can yield a different tree.
• Without pruning it tends to overfit the training data.
• Can be unstable; splitting bias (favours attributes with many values).