Understanding Decision Trees

It's on a weekend and you are planning on whether you are supposed to go outside and practice for your football match. You go back to your tracker and check how the weather affected your previous practice days. In your tracker there are weather factors like: [Outlook, Humidity, Wind] which affected whether you practiced or not.
The tracker provides the following:

Day	Outlook	Humidity	Wind	Play?
D1	Sunny	High	Weak	No
D2	Sunny	Normal	Weak	Yes
D3	Rain	High	Strong	No
D4	Overcast	High	Weak	Yes

You decide to make decision for tomorrow's pracrice and you come up with:

To determine whether practice should go ahead, the you evaluate environmental factors in a structured hierarchy, starting with the overall Outlook as its primary root split.

1. If the forecast is Overcast, the tree leads directly to a Yes outcome, as historical data (Day D4) shows favorable conditions regardless of other variables.
2. When the forecast indicates Sunny conditions, you branch down to evaluate Humidity: a High humidity level (Day D1) yields a No (canceling practice), whereas Normal humidity (Day D2) results in a Yes.
3. Conversely, when the outlook predicts Rain, the decision hinges entirely on Wind strength.
4. A Strong wind condition (Day D3) poses too much of a disruption, triggering a No decision to call off practice.
5. If the wind is Weak, the path resolves to a Yes, allowing practice to continue safely.

By systematically evaluating conditions through these binary splits, the decision tree provides a clear, reliable rule set for making quick practice decisions based on daily weather inputs.

What is a decision tree?

A decision tree is a supervised machine learning algorithm used for both classification (predicting a category) and regression (predicting a continuous number).
It maps decisions and their potential outcomes in an upside-down, flowchart-like structure that closely mimics human logic.

Anatomy of a decision tree

A decision tree routes a data point from the top down through several key components:
Root Node: The very first node at the top containing the complete dataset. It asks the initial question or evaluates the most important feature.
Internal / Decision Nodes: Sub-nodes that represent subsequent data tests or attributes (e.g., "Is income > $50,000?").
Branches: The paths connecting nodes. They represent the outcomes of a test or choices available (e.g., Yes or No).
Leaf Nodes: The terminal endpoints of the tree. They do not split any further and contain the final prediction or decision.

How a decision tree works

The training and deployment of a decision tree happen in two distinct phases: Phase 1 (Building the Tree) and Phase 2 (Making Predictions).

Phase 1 (Building the Tree)

This phase operates on a recursive binary splitting approach. It works from the top down, splitting data into two branches at a time until the data is organized.

Step 1: Evaluate All Possible Splits

• The algorithm looks at every single feature in your dataset.
• For each feature, it reviews every possible value to split on (e.g., outlook = 'sunny', outlook = 'rainy').

Step 2: Calculate Metric Purity

• For every potential split, it calculates a purity score using Gini Impurity or Entropy.
• It measures which split creates the most "pure" resulting groups (where data points are mostly the same class).

Step 3: Select the Best Split

-The single feature and specific value that maximize Information Gain (or minimize Gini Impurity) are chosen.

• This feature becomes the Root Node (or current decision node), and the dataset splits into two branches.

Step 4: Repeat Recursively

• The algorithm repeats Steps 1–3 for each new branch, treating it as a brand-new mini-dataset.

Step 5: Apply Stopping Criteria

The tree stops growing when it hits a user-defined limit, such as:

• All data points in a node belong to the same class (perfect purity).
• The tree reaches its maximum allowed depth.
• A node contains fewer than the minimum required samples to split.

Phase 2: Making Predictions (Inference)

Once built, the tree is a static set of rules. Predicting the label of a new, unseen data point is incredibly fast and operates like a game of 20 Questions.

                      [ START: Root Node ]
                          Is Outlook?
                         /      |     \
                Overcast/       |Sunny \Rain
                       /        |       \__________
                      v         v                  v
               (Leaf Node)  [ Decision Node ]   (Leaf Node)
                 PLAY: YES     Is Humidity?      PLAY: NO
                             /         \
                        High/           \Normal       
                           /             \
                          v               v
                    (Leaf Node)       (Leaf Node)
                      PLAY: NO         PLAY: YES
                         ▲
                         │
             [ NEW DAY LANDS HERE ]
             Prediction: PLAY = NO

Step 1: Enter at the Root

• The new data point enters the tree at the very top Root Node.

Step 2: Evaluate the Condition

• The model checks the data point's value against the node's rule (e.g., If the node asks Outlook = Sunny? and the data point's outlook is Sunny, the answer is Yes).

Step 3: Follow the Branch

• Based on the answer, the data point travels down the corresponding Yes or No branch to the next node.

Step 4: Repeat Until a Leaf is Reached

• The model evaluates the next internal node's condition and continues routing the data down the branches until it can go no further.

Step 5: Assign the Final Value

Once the data point lands in a terminal Leaf Node, the prediction is made:

• For Classification: It assigns the majority class of the training samples in that leaf.
• For Regression: It assigns the average numerical value of the training samples in that leaf.

Calculate Metric Purity

Entropy

Entropy is a metric that measures the amount of impurity, disorder, or randomness in a dataset.
In information theory, it quantifies how much uncertainty there is in a group of items.

$$H(S) = -\sum_{i=1}^{c} p_{i} \log_{2}(p_{i})$$

Where:
(p_{i}): The proportion (probability) of data points belonging to class (i).
Scale:

• (0.0) (Perfectly Pure): All samples belong to a single class (e.g., a node with only "Yes" entries).There is zero uncertainty.
• (1.0) (Maximum Disorder): The classes are split perfectly down the middle in a two-class system (e.g., 50% "Yes" and 50% "No").

Gini Impurity

Gini Impurity measures the probability that a randomly chosen element from a node would be incorrectly labeled if it were randomly classified according to the distribution of targets in that node.

$$\text{Gini} = 1 - \sum_{i=1}^{c} (p_{i})^{2}$$

Scale:

• (0.0) (Perfectly Pure): Every single element belongs to one class. The chance of misclassification is zero.
• (0.5) (Maximum Disorder): In a two-class system, the data is split 50/50. You have a 50% chance of guessing the wrong label.

Information Gain

Information Gain is the metric used to decide which feature to split on. It measures the reduction in entropy (or disorder) after a dataset is split based on a specific attribute.

$$\text{Information Gain}(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_{v}|}{|S|} H(S_{v})$$

$$H(S) \text{: Baseline entropy of the parent dataset before the split.}$$

$$\sum_{v \in \text{Values}(A)} \frac{|S_{v}|}{|S|} H(S_{v}) \text{: Weighted average entropy of all child nodes created by the split.}$$

Goal: The decision tree algorithm calculates the Information Gain for every available feature and selects the feature that yields the highest value, as it cleans up the data the fastest.

Mathematical operarion in a decision tree

To find the absolute best starting point (the root node) for your dataset, we must calculate the Metric Purity for the entire dataset and evaluate potential splits. We will use Entropy and Information Gain to find the most optimal split.
Here is the step-by-step mathematical calculation:

Keeping in mind

• Total Samples ((S)): 4 days (D1, D2, D3, D4)
• Target Classes ("Play?"): 2 Yes, 2 No

1. Calculate Base Entropy (Total Dataset)

Before making any splits, we calculate the initial disorder ((H)) of the 4 days using the entropy formula:

$$\begin{aligned} H(S) &= -p_{\text{yes}}\log_{2}(p_{\text{yes}}) - p_{\text{no}}\log_{2}(p_{\text{no}}) \ \ \end{aligned}$$

Since 2 out of 4 are "Yes"

$$\begin{aligned} \left(p_{\text{yes}} = \frac{2}{4} = 0.5\right) \end{aligned}$$

and 2 out of 4 are "No"

$$\begin{aligned} \left(p_{\text{no}} = \frac{2}{4} = 0.5\right): \ \end{aligned}$$

$$\begin{aligned} H(S) &= -(0.5 \times \log_{2}(0.5)) - (0.5 \times \log_{2}(0.5)) \ \end{aligned}$$

$$\begin{aligned} H(S) &= -(-0.5) - (-0.5) \ \end{aligned}$$

$$\begin{aligned} H(S) &= 1.0 \end{aligned}$$

The base entropy is (1.0), meaning the dataset is perfectly mixed and completely impure.

2. Evaluate Split on "Outlook"

The feature Outlook splits our 4 days into three distinct branches: Sunny (2 days), Overcast (1 day), and Rain (1 day).

Calculate Entropy for Each Branch:

• Sunny Branch (D1, D2): Contains 1 "No" (D1) and 1 "Yes" (D2).

$$H(\text{Sunny})=-(\frac{1}{2}\log _{2}\frac{1}{2})-(\frac{1}{2}\log _{2}\frac{1}{2})=1.0$$

• Overcast Branch (D4): Contains 1 "Yes". It is perfectly pure.

$$H(\text{Overcast})=-(1\log _{2}1)-(0)=0.0$$

• Rain Branch (D3): Contains 1 "No". It is perfectly pure.

$$H(\text{Rain})=-(0)-(1\log _{2}1)=0.0$$

Calculate Remainder Entropy (Weighted Average):

$$\text{Remainder}(\text{Outlook})=\frac{2}{4}(1.0)+\frac{1}{4}(0.0)+\frac{1}{4}(0.0)=0.5$$

Calculate Information Gain:

$$\begin{aligned} \text{Information Gain} &= \text{Base Entropy} - \text{Remainder} \ \end{aligned}$$

$$\begin{aligned} \text{IG}(\text{Outlook}) &= 1.0 - 0.5 = \mathbf{0.50} \end{aligned}$$

3. 3. Evaluate Split on "Humidity"

The feature Humidity splits our 4 days into two branches: High (3 days) and Normal (1 day).

Calculate Entropy for Each Branch:

• High Branch (D1, D3, D4): Contains 2 "No" (D1, D3) and 1 "Yes" (D4).

$$H(\text{High})=-\left(\frac{1}{3}\log _{2}\frac{1}{3}\right)-\left(\frac{2}{3}\log _{2}\frac{2}{3}\right)\approx 0.918$$

• Normal Branch (D2): Contains 1 "Yes". Perfectly pure.(H(\text{Normal})=0.0)

$$H(\text{Normal})=0.0$$

Calculate Remainder Entropy (Weighted Average):

$$\text{Remainder}(\text{Humidity})=\frac{3}{4}(0.918)+\frac{1}{4}(0.0)\approx 0.689$$

Calculate Information Gain:

$$\text{IG}(\text{Humidity})=1.0-0.689=\mathbf{0.311}$$

4. Evaluate Split on "Wind"

The feature Wind splits our 4 days into two branches: Weak (3 days) and Strong (1 day).

Calculate Entropy for Each Branch:

• Weak Branch (D1, D2, D4): Contains 2 "Yes" (D2, D4) and 1 "No" (D1).

$$H(\text{Weak})=-\left(\frac{2}{3}\log _{2}\frac{2}{3}\right)-\left(\frac{1}{3}\log _{2}\frac{1}{3}\right)\approx 0.918$$

• Strong Branch (D3): Contains 1 "No". Perfectly pure

$$H(\text{Strong})=0.0$$

Calculate Remainder Entropy (Weighted Average):

$$\text{Remainder}(\text{Wind})=\frac{3}{4}(0.918)+\frac{1}{4}(0.0)\approx 0.689$$

Calculate Information Gain:

$$\text{IG}(\text{Wind})=1.0-0.689=\mathbf{0.311}$$

Feature	Base Entropy	Remainder Entropy	Information Gain (Purity Score)
Outlook	1.0	0.500	0.500 (Winner)
Humidity	1.0	0.689	0.311
Wind	1.0	0.689	0.311

Outlook provides the absolute highest Information Gain (0.500). Therefore, the algorithm chooses Outlook as the Root Node for Phase 1 because it cleans up the disorder of the dataset faster than any other feature.