Decision Tree

This note introduces the Decision Tree algorithm using scikit‑learn, explains the step‑by‑step logic behind how it works, and then demonstrates a from‑scratch implementation to show that the core idea is simple and easy to build.

What is a Decision Tree?

A Decision Tree is a flow‑chart full of yes / no questions.
Starting at the root, each question splits the data into smaller groups until every leaf is pure (all samples inside belong to one class), or a stop condition is met.

The top‑down, greedy procedure we’ll build here uses Gini impurity, which is the splitting rule used by the popular CART algorithm.

CART stands for Classification And Regression Trees. It is the most widely used decision‑tree method, introduced by Breiman et al. in 1984.

In this note, we focus on classification.

This notebook will:

• Use scikit‑learn to demonstrate how Decision Tree works in practice
• Explain the logic behind it in an intuitive way (Gini impurity, Gini gain, recursive splitting)
• Show how to implement the same idea step by step from scratch

Let’s dive into the details to understand how it works and how to implement it ourselves.

Preparation

Implement with Scikit-Learn

Outputs:

We can see that the decision tree is successfully generated using plot_tree():

For later comparison, we also create a text-based representation of the tree using export_text():

Outputs:

Behind the Scenes

1. The Big Picture — Purity vs. Impurity

Imagine a bucket of marbles where each color = a class.

• If the bucket holds only blue marbles, it is perfectly pure — you can always guess “blue” and be right.
• If it holds half blue, half red, it is impure — your guess will be wrong half the time.

A Decision Tree keeps asking yes / no questions that move us into ever‑purer buckets.
To decide which question is best, we need a number that measures “mixiness.”
That number is called an impurity measure.

There are several impurity measures (e.g. entropy / information gain).
Here we use Gini impurity because it’s fast and intuitive.

2. Gini Impurity — One Way to Measure Impurity

Plain language definition:

“Take one marble at random from the bucket and guess its color by picking the most frequent color in that bucket.
The Gini impurity is the probability your guess is wrong.”

• If the bucket is pure (all one color), you’re never wrong → impurity 0.
• If colors are mixed evenly, you’re often wrong → impurity higher.

Formula:
Let $p_k$ be the share of marbles in class $k$ (e.g. 0.5 for 50 %). For $K$ classes:

$$G \;=\; 1 \;-\; \sum_{k=1}^{K} p_k^2$$

• All one color ($p_k=1$ for one class):
  $G = 1 - 1^2 = 0\quad(\text{pure}).$
• Two colors evenly mixed ($p_1 = p_2 = 0.5$):
  $G = 1 - (0.5^2 + 0.5^2) = 0.5.$

3. Gini Gain — Evaluating a Split

When a question splits the parent bucket into left and right:

• $N_P$ = number of samples in parent
• $N_L$, $N_R$ = numbers in left / right children
• $G_P$ = Gini impurity of the parent
• $G_L$, $G_R$ = impurities of left / right

We compute the weighted average impurity after the split:

$$\underbrace{\tfrac{N_L}{N_P}\,G_L}_{\text{left’s impurity × its weight}} \;+\; \underbrace{\tfrac{N_R}{N_P}\,G_R}_{\text{right’s impurity × its weight}}$$

Then the Gini gain measures the drop in impurity:

$$\text{Gain} \;=\; G_P \;-\; \Bigl( \tfrac{N_L}{N_P}\,G_L \;+\; \tfrac{N_R}{N_P}\,G_R \Bigr)$$

• The term in parentheses is the after-split impurity.
• Subtracting it from $G_P$ gives the impurity reduction—i.e. how much clearer (purer) our buckets became thanks to that question.
• We choose the split with the highest gain.

4. Growing the Tree

1. Root bucket = all data.
2. Evaluate every feature + threshold, compute Gini gain, pick the best.
3. Split into left / right buckets.
4. Repeat steps 2–3 recursively on each bucket.
5. Stop when a bucket is pure or when limits (max_depth, min_samples_leaf) are reached.

This greedy, one‑step‑ahead strategy (CART) builds powerful trees quickly.

5. Making Predictions

To classify a new sample:

1. Start at the root.
2. Ask the stored yes / no question.
3. Follow the yes or no branch.
4. Repeat until you reach a leaf; output that leaf’s class label.

Like playing “20 Questions,” each answer narrows possibilities until one remains.

Let's Code It

Okay, so let’s display the generated tree. Since this is a custom decision tree, we’ll also create a simple print function to show the tree structure in a readable way.

Outputs:

It Works!!

The predictions from our scratch Decision Tree (CART w/ Gini) implementation match those from scikit‑learn exactly.

This confirms that our logic — computing Gini impurity, selecting optimal feature splits, recursively building the tree, and predicting by majority vote in the leaves — behaves as expected.

We've successfully built Decision Tree from the ground up!