# Decision Trees

Models that recursively split the feature space on single-feature thresholds, producing rules readable end to end.

**Rests on:** Recursive Thinking

**Leads to:** Decision Jungles, Gini and Information Gain, No-Code Model Building, Random Forests, Rule-Based Classifiers

*Machine Learning · Machine Learning Foundations*


## Why learn this

Decision trees let you make predictions by asking a simple series of yes-or-no questions, much like a flowchart you might draw on a whiteboard. This is valuable because the logic behind every prediction is completely transparent: you can trace exactly which features led to a specific outcome. This clarity makes them indispensable when you need to explain your decisions to stakeholders—for example, in credit scoring, medical diagnosis, or fraud detection, where 'why' matters as much as 'what.' They are particularly useful for structured data like spreadsheets, and they serve as the fundamental building block for more advanced ensemble methods that combine many such trees to improve accuracy.


## The intuition

Imagine you have a list of customers, each described by a few numbers: their age, their monthly spending, and whether they have a loyalty card. You want to predict whether they will churn — that is, whether they will stop using your service within the next month. A decision tree asks a series of questions: 'Is their age under 30?' If yes, go down one branch; if no, go down another. Then on each branch, it asks another question: 'Is their monthly spending under ₹2000?' And so on, until it reaches a final node — a terminal box that says 'likely to churn' or 'likely to stay.' The tree is built from historical data: it looks at past customers whose churn is known, and it learns the best questions to ask and the best order to ask them in. The beauty is that the final model is a set of rules you can read and understand: 'If age under 30, and spending under ₹2000, then 80% of such customers churned.' No other model type gives you this clarity.


## An analogy

Think of a doctor diagnosing a patient. The doctor does not consider all possible diseases at once. Instead, she follows a flowchart: 'Is the temperature above 38°C?' If yes, 'Is there a cough?' If yes, 'Is the throat red?' — and so on. Each answer narrows the possibilities until she reaches a diagnosis. A decision tree works exactly the same way. The data is the patient's symptoms (features), the questions are the tests (thresholds on features), and the final diagnosis is the prediction. The doctor's flowchart is learned from years of experience; the decision tree's flowchart is learned from historical data. A caveat: a real doctor can adjust their questions dynamically based on new information, whereas a trained decision tree is fixed once built and cannot adapt to individual nuances outside its original training data.


## Definition

A decision tree is a predictive model that divides data into groups by repeatedly asking single-feature questions, creating a readable map of if-then rules that leads from the initial question to a final prediction.


## How it connects

This concept introduces two foundational ideas: splitting criteria, which are the mathematical methods used to decide which question best separates the data at each step, and model complexity, which refers to how detailed the tree becomes. These concepts help you understand how decision trees relate to ensemble methods like Random Forests, which combine many trees to reduce error, and other classifiers like K-Nearest Neighbors.


## The mathematics

The mathematics behind decision trees is about measuring how "mixed" a group of examples is, and choosing splits that reduce that mix. The branch of mathematics is probability and statistics — specifically, the idea of impurity or disorder. You do not need calculus or algebra; this is purely counting and fractions. The core operation is the impurity calculation. Suppose you have a box of 10 balls, 7 red and 3 blue. The impurity measures how close it is to being all one colour. If all 10 are red, impurity is 0. If 5 red and 5 blue, impurity is maximum. We use a formula called Gini impurity, which is: for each colour, compute (fraction of that colour) squared, sum these squares, then subtract from 1. In words: Gini = 1 - (fraction_red^2 + fraction_blue^2). For 7 red and 3 blue: fraction_red = 0.7, fraction_blue = 0.3. So Gini = 1 - (0.7^2 + 0.3^2) = 1 - (0.49 + 0.09) = 1 - 0.58 = 0.42. For 5 and 5: 1 - (0.25 + 0.25) = 0.5, which is higher. So Gini measures impurity. The decision tree algorithm tries every possible threshold on every feature, and for each threshold, it splits the data into two groups, calculates the weighted average of the impurities of the two groups, and picks the threshold that gives the lowest weighted impurity. This is called the information gain — the reduction in impurity from before the split to after. The tree builds recursively: after splitting, it repeats the process on each subgroup, until the groups are pure enough or some stopping criterion is met.

For a node with K classes, let p_k be the fraction of examples in class k. Then Gini impurity is: Gini = 1 - sum_{k=1}^{K} p_k^2. For a split that divides the data into two groups of sizes N_left and N_right, the weighted impurity is: G = (N_left/N_total) * Gini_left + (N_right/N_total) * Gini_right. The information gain is the difference between the impurity of the parent node and the weighted impurity of the children after the split.


## A worked example

```
We have 6 training examples. Each has one feature: 'spending' (in ₹). The target is 'churn': 1 for churn, 0 for stay. Examples: (100, 0), (200, 0), (300, 1), (400, 1), (500, 1), (600, 1). We want to find the best threshold to split on 'spending' to separate churn=0 from churn=1.

Step 1: Overall impurity: 2 churn=0, 4 churn=1. Fraction 0 = 2/6 = 0.333, fraction 1 = 4/6 = 0.667. Gini = 1 - (0.333^2 + 0.667^2) = 1 - (0.111 + 0.445) = 0.444   # This is the impurity before any split.
Step 2: Try threshold '250' (splits: <=250 vs >250). Left: (100,0) and (200,0) - both class 0, Gini left = 0. Right: (300,1),(400,1),(500,1),(600,1) - all class 1, Gini right = 0. Weighted Gini = (2/6)*0 + (4/6)*0 = 0   # This split perfectly separates the classes.
Step 3: Information gain = 0.444 - 0 = 0.444   # The reduction in impurity is maximum, so threshold 250 is the best split.

Result: The best split is at spending <= 250. The tree is: if spending <= 250, predict churn=0; else churn=1. This perfectly classifies the training data.
```


## From scratch, in Python

```python
def gini(labels):
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    total = len(labels)
    impurity = 1.0
    for count in counts.values():
        fraction = count / total
        impurity -= fraction ** 2
    return impurity

def best_split(feature_values, labels):
    best_gain = -1
    best_threshold = None
    overall_impurity = gini(labels)
    # Sort by feature value to find candidate thresholds
    data = list(zip(feature_values, labels))
    data.sort()
    for i in range(len(data) - 1):
        threshold = (data[i][0] + data[i+1][0]) / 2
        left_labels = [lbl for val, lbl in data if val <= threshold]
        right_labels = [lbl for val, lbl in data if val > threshold]
        weighted = (len(left_labels)/len(data)) * gini(left_labels) + (len(right_labels)/len(data)) * gini(right_labels)
        gain = overall_impurity - weighted
        if gain > best_gain:
            best_gain = gain
            best_threshold = threshold
    return best_threshold, best_gain

# Example data
spending = [100, 200, 300, 400, 500, 600]
churn = [0, 0, 1, 1, 1, 1]
threshold, gain = best_split(spending, churn)
print(f"Best threshold: {threshold}")
print(f"Information gain: {gain}")
```


## The same thing, with a framework

```python
from sklearn.tree import DecisionTreeClassifier
import numpy as np

X = np.array([[100], [200], [300], [400], [500], [600]])
y = np.array([0, 0, 1, 1, 1, 1])
clf = DecisionTreeClassifier(criterion='gini', max_depth=None)
clf.fit(X, y)
print(clf.predict([[150]]))  # Predict for spending=150
print(clf.tree_.feature)  # Which feature used at each split
print(clf.tree_.threshold)  # Threshold values
```


## What the code does

The from-scratch code first defines a function to compute Gini impurity. It uses a dictionary to count how many of each label appear. Then it defines a function to find the best split. It sorts the data by feature value, and for each gap between unique values, it takes the midpoint as a threshold, splits the labels into left and right, computes the weighted impurity, and tracks the best gain. The final example runs this on the small dataset and prints the best threshold. The framework code uses scikit-learn's DecisionTreeClassifier, which does the same thing internally — it computes Gini impurity for every possible threshold and selects the best split. The `criterion='gini'` sets the impurity measure, and `max_depth=None` allows the tree to grow until all leaves are pure. The `predict` method follows the tree's rules to output a class.


## Common misconceptions

**Trees can only split on a single feature at a time** — The tree always asks questions about multiple features together, like 'if age > 30 and income > 50000'.

A decision tree, in its classic form, asks about only one feature at each node: 'is age > 30?' Then later it might ask about income, but never both at once. In fact: Each node examines exactly one feature and a threshold on that feature. Multiple features are considered at different nodes along the path.

**Deeper trees are always better** — A tree that grows until every leaf is pure must be the most accurate model.

Unpruned trees memorize noise in the training data and fail to generalize to new data. This is the overfitting problem. In fact: Trees need depth control (e.g., max_depth) or pruning to prevent overfitting. A slightly impure leaf can generalize better.

**A tree is a box that stores all the data** — The tree remembers every training example and looks them up when predicting.

The tree only stores the thresholds and the leaf outputs, not the original data. In fact: The tree compresses knowledge into a set of split rules and class probabilities at leaves. It does not store data.

**Trees cannot handle numerical features** — A tree can only work with categories like 'red' or 'blue', not with numbers like 250.5.

Trees handle numbers by picking a threshold and splitting into 'less than or equal' vs 'greater than'. In fact: Numerical features are split by a threshold, chosen during training to maximize information gain.


## In short

A decision tree is a set of if-then rules learned from data by repeatedly splitting on the feature and threshold that most reduces impurity. It is interpretable, easy to use, and forms the basis of powerful ensembles. Prevent overfitting with depth limits or pruning, and remember that a single tree is unstable, which is why you'll usually use many trees together.


## Where this is used

Decision trees are used across many AI systems. In everyday applied machine learning, they are the default for tabular data — credit scoring, churn prediction, fraud detection, and medical diagnosis. A developer using scikit-learn writes `DecisionTreeClassifier()` or `RandomForestClassifier()` and fits it on a pandas DataFrame. The tree's rules are often extracted and shown to regulators or customers to explain decisions. In large language models, trees are rarely used directly, but they appear in some efficiency tricks: for example, in neural network architectures, a hard decision tree can replace a soft attention mechanism for routing tokens, but this is research-level. More commonly, trees underpin gradient boosting models like XGBoost and LightGBM, which are often used alongside LLMs in retrieval pipelines to score documents. In small language models running on devices, decision trees are too simple for language, but they are used for on-device intent classification or keyword spotting when the model must be tiny and fast, as part of a hybrid system where a tree decides whether to wake a larger model. In retrieval-augmented generation (RAG), decision trees are used in the retrieval stage: a tree can index embeddings and perform approximate nearest-neighbour search quickly, or a boosted-tree model can rerank retrieved documents before passing them to the LLM. In agentic systems that plan and call tools, decision trees can serve as a simple policy for tool selection: if the user asks for weather, call the weather API; if they ask for email, call the email API. But for complex planning, LLMs are used. Decision trees also appear in time-series forecasting and anomaly detection. The main drawback is that a single tree overfits if unpruned, and it is unstable — a small change in data can cause a very different tree. That is why ensembles like random forests are almost always used in production. When building software, a developer typically uses `scikit-learn` or `XGBoost`; they must set `max_depth`, `min_samples_split`, and pruning to control overfitting, and they must handle categorical features carefully. If done badly — e.g., no depth limit, no cross-validation — the tree will memorize noise and generalize poorly.


---

Read this on the web: https://basavapurushottam.com/learn-ai/decision-trees
