1. Home
  2. Blog
  3. Artificial Intelligence

Artificial Intelligence

Decision Tree in Python: Gini, Entropy and Overfitting From Scratch

A decision tree learns a flowchart of yes or no questions that splits data into ever purer groups. We build one from scratch in Python for a loan approval example, calculate Gini impurity and entropy by hand, find the best split, print the learned rules, and measure how growing the tree deeper makes training accuracy climb to 100 percent while test accuracy falls.

9 min read
Decision tree in Python: Gini, entropy and overfitting from scratch

Key takeaways

  • A decision tree repeatedly picks the feature and threshold that best separates the classes, measured by Gini impurity or entropy.
  • On our loan data, both criteria chose the same first question: is the debt ratio at most 0.60?
  • A depth-2 tree reached 96 percent test accuracy; an unlimited tree hit 100 percent on training data but fell to 93 percent on new data.
  • Requiring at least 10 samples per leaf kept the tree to 5 leaves with the same 96 percent test accuracy.

Many decisions are naturally a series of questions: is the income above a threshold, is the debt too high, has the customer paid late before? A decision tree learns those questions automatically from labelled examples. Its predictions can be read as plain rules, it handles mixed features without scaling, and it is the building block of random forests and gradient boosting, some of the strongest models for tabular data.

We wrote a small tree learner from scratch in Python 3.13.6 with NumPy 2.5.5, using a synthetic, seeded loan dataset so we know the true rule. scikit-learn’s DecisionTreeClassifier implements the same CART algorithm with many optimisations; we did not run it here.

What is a decision tree?

A tree starts with all training examples at the root. It asks one yes or no question about one feature, such as “is income at most 45,000?”, and sends each example left or right. Each branch then asks its own question, and so on, until a stopping rule is met. The final nodes, called leaves, predict the majority class of the examples that reached them. Predicting a new case means following the questions from the root to a leaf.

Measuring impurity: Gini and entropy

def gini(y):
    c = Counter(y); n = len(y)
    return 1 - sum((v / n) ** 2 for v in c.values())

def entropy(y):
    c = Counter(y); n = len(y)
    return -sum((v / n) * math.log2(v / n) for v in c.values())

# 5 yes, 5 no:   gini 0.5    entropy 1.0     (maximally mixed)
# 9 yes, 1 no:   gini 0.18   entropy 0.469
# all the same:  gini 0.0    entropy 0.0     (pure)

A good question produces groups that are mostly one class. Gini impurity is the chance of mislabelling a random example if you labelled it randomly according to the group’s class mix. Entropy measures the same mixing in bits of information. Both are 0 for a pure group and highest for an even mix; Gini is slightly faster because it needs no logarithm, which is why CART and scikit-learn use it by default.

Information gain

gain = impurity(parent) - weighted average impurity(children)
     = base - (len(left) * crit(left) + len(right) * crit(right)) / len(y)

The quality of a split is how much it reduces impurity, weighting each child by its size. The tree tries every feature and every possible threshold, and keeps the split with the largest gain. With entropy, this reduction is called information gain, as in the classic ID3 algorithm; with Gini, it is the Gini decrease used by CART.

Our loan dataset

rng = np.random.default_rng(7)
income = rng.uniform(10, 120, 400)      # thousands
debt   = rng.uniform(0, 1, 400)         # debt-to-income ratio
y = ((income > 45) & (debt < 0.6)).astype(int)
flip = rng.uniform(size=400) < 0.05     # 5 percent label noise
y = np.where(flip, 1 - y, y)
# 300 rows for training, 100 for testing

The true rule approves applicants with income above 45 and a debt ratio below 0.6. We flipped about 5 percent of labels at random to imitate real-world inconsistency: human decisions are never perfectly rule-based. That noise is what makes overfitting visible later.

Finding the best split

def best_split(X, y, crit):
    base = crit(y); best = (0, None, None)
    for f in range(X.shape[1]):
        vals = np.unique(X[:, f])
        for t in (vals[:-1] + vals[1:]) / 2:          # midpoints between values
            l = y[X[:, f] <= t]; r = y[X[:, f] > t]
            g = base - (len(l) * crit(l) + len(r) * crit(r)) / len(y)
            if g > best[0]: best = (g, f, t)
    return best

# root split (gini):    debt <= 0.6   gain 0.153
# root split (entropy): debt <= 0.6   gain 0.281

Candidate thresholds are the midpoints between neighbouring values, so every distinct way of dividing the data is tried. Both criteria picked the debt ratio at 0.6 as the first question, exactly the true cut-off. The gain values differ because entropy and Gini use different scales, but the ranking of splits usually agrees. In practice the choice of criterion rarely changes accuracy much.

Growing the tree

def build(X, y, depth, max_depth, crit, min_leaf=1):
    if depth == max_depth or len(set(y)) == 1 or len(y) < 2 * min_leaf:
        return Counter(y).most_common(1)[0][0]           # leaf: majority class
    g, f, t = best_split(X, y, crit)
    if f is None: return Counter(y).most_common(1)[0][0]
    m = X[:, f] <= t
    if m.sum() < min_leaf or (~m).sum() < min_leaf:
        return Counter(y).most_common(1)[0][0]
    return (f, t, build(X[m], y[m], depth + 1, max_depth, crit, min_leaf),
                  build(X[~m], y[~m], depth + 1, max_depth, crit, min_leaf))

The recursion splits, then repeats on each half. It stops when the maximum depth is reached, when a node is already pure, or when a split would create a leaf smaller than min_leaf. This greedy approach picks the best question at each step without looking ahead, which is fast but not guaranteed to find the best possible tree.

Reading the learned rules

if debt <= 0.60:
    if income <= 45.49:
        -> reject
    else:
        -> approve
else:
    if debt <= 0.81:
        -> reject
    else:
        -> reject

The depth-2 tree recovered the real policy almost exactly: low debt and income above about 45 means approve. This is the main attraction of decision trees: a loan officer, auditor or regulator can read the model. Notice the right-hand branch, though. It split on debt at 0.81 and then predicted “reject” on both sides. The split slightly reduced impurity, so the algorithm took it, even though it changes no prediction. Real tree libraries do the same, and pruning removes such useless splits.

Depth and overfitting, measured

Max depth Leaves Train accuracy Test accuracy
1 2 0.750 0.820
2 4 0.943 0.960
3 7 0.947 0.940
5 14 0.963 0.960
8 22 0.983 0.950
Unlimited 29 1.000 0.930

One question was not enough (82 percent on test data). Two questions captured the true rule. After that, deeper trees kept improving on the training data, until the unlimited tree classified every training example perfectly, including the 5 percent of deliberately wrong labels. Those extra leaves memorised noise, and test accuracy dropped to 93 percent. That gap between training and test performance is overfitting, and an unrestricted decision tree will always fit its training data perfectly if no two identical rows disagree.

Controlling tree size

no depth limit, min_samples_leaf=10: leaves 5  train 0.943  test 0.960

Instead of guessing a depth, require every leaf to contain at least 10 training examples. The tree stopped at 5 leaves and matched the best test accuracy, because single noisy points can no longer get a leaf of their own. Other controls are a minimum gain per split and cost-complexity pruning, which grows a full tree and then removes branches that do not pay for themselves. Choose the settings with cross-validation, not by looking at test accuracy repeatedly.

Trees are unstable

full-depth trees trained on 90 percent subsamples disagree on 3.0 percent of test rows

Training an unrestricted tree on a random 90 percent of the same training data changed 3 percent of its test predictions. Because each split depends on the ones above it, a small change near the root can reshape the whole tree. This high variance is exactly what random forests fix: they train many trees on different samples and average their votes.

Diagonal boundaries need many splits

# class is 1 when x1 + x2 > 1 (a diagonal line)
depth 2: leaves 4   test acc 0.870
depth 4: leaves 12  test acc 0.960
depth 8: leaves 16  test acc 0.950

Every split is parallel to an axis: “x1 at most t”. A diagonal boundary must be approximated by a staircase of small steps, which needed 12 leaves to reach 96 percent here. A linear model such as logistic regression would represent that boundary with a single line. Adding a feature like x1 + x2 lets a tree do the same with one split.

Strengths and weaknesses

Strengths Weaknesses
Readable rules, easy to explain Overfits without limits on depth or leaf size
No feature scaling needed Unstable: small data changes alter the tree
Handles non-linear interactions such as income and debt together Axis-aligned splits approximate diagonal boundaries poorly
Fast predictions Greedy: no guarantee of the best tree

Compared with k nearest neighbors, which needs scaled features and stores all training data, a tree is compact and scale-free. Compared with naive Bayes, it captures interactions between features. Unlike k means clustering, it needs labelled examples, because every split is chosen to separate known classes. For regression problems, the same algorithm predicts the average value in each leaf and uses variance reduction instead of Gini, a non-linear alternative to linear regression.

Final thoughts

A decision tree is a learned flowchart: measure impurity with Gini or entropy, choose the split with the largest gain, and repeat. Our from-scratch tree found the true loan rule in two questions, then showed the classic failure mode, memorising noise as it grew deeper. Limit depth or leaf size, validate the settings, and remember that single trees are unstable. When you need more accuracy than one readable tree can give, an ensemble of trees is the natural next step. For text and images, the deep networks behind large language models take over.

Frequently asked questions

How does a decision tree decide where to split?

It tries every feature and threshold and picks the split that reduces impurity the most, measured with Gini impurity or entropy and weighted by the size of each child group.

What is the difference between Gini and entropy?

Both measure how mixed a group is and are zero for a pure group. Gini is slightly faster to compute, entropy is measured in bits. They usually choose the same splits, as they did in our example.

Why does my decision tree overfit?

Without limits, a tree keeps splitting until it fits every training example, including noise. Limit the depth, require a minimum number of samples per leaf, or prune the tree.

Do decision trees need feature scaling?

No. Splits compare one feature with a threshold, so the units and scale of each feature do not matter, unlike distance-based or gradient-based models.

What is information gain?

The reduction in entropy achieved by a split: the parent entropy minus the size-weighted entropy of the child groups. Larger gain means a more useful question.

Keep learning

Work with Stack Quora

Need help with testing, WordPress or SEO?

We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.

Keep reading

More guides on testing, AI & modern development

Enjoyed this article? Pick a topic and jump straight into our newest tutorials.

Artificial Intelligence

Random Forest in Python: Bagging, Feature Sampling and OOB From Scratch

Random forest in Python from scratch: bootstrap sampling, feature sampling, number of trees, out-of-bag evaluation and impurity vs permutation importance.

Read article →
Software Development

MIME Types Explained: Content-Type, nosniff and a Common Types List

MIME types explained and tested in a browser: Content-Type, nosniff, scripts and stylesheets with wrong types, a common MIME types…

Read article →
DevOps

Git Clean Explained: Remove Untracked Files Without Regret

Git clean explained with dry runs: -n, -f, -d, -x, -X, exclusions, paths, nested repositories and interactive mode, plus a…

Read article →
Test Automation

Pytest approx: Comparing Floats With rel, abs and Collections

Pytest approx explained: default tolerances, the near-zero trap, rel and abs, lists and dicts, NaN, NumPy, and how it differs…

Read article →
Software Testing

Accessibility Testing: WCAG Checklist, Automated Tools and Manual Checks

Accessibility testing explained: WCAG basics, an axe-core scan of a broken and a fixed page, what automation missed, contrast checks…

Read article →
Databases & SQL

SQL UNPIVOT: Turn Columns Into Rows, 4 Ways Tested

SQL UNPIVOT explained: turn columns into rows with UNION ALL, CROSS JOIN with CASE, JSON functions or native UNPIVOT, with…

Read article →
Software Development

Intl NumberFormat in JavaScript: Currency, Compact, Percent and Units

Intl.NumberFormat in JavaScript: locales, currency, compact notation, percent, units, rounding, formatToParts, the non-breaking space trap and formatter reuse.

Read article →
Software Development

Python Abstract Class: ABC, abstractmethod and When to Use Them

Python abstract class explained: ABC and abstractmethod, abstract properties, shared logic with super, register, collections.abc and ABC vs Protocol, tested.

Read article →
Software Development

Python Subprocess Explained: run, Capture Output, Timeouts and Safety

Python subprocess explained with tested examples: run, capture_output, check, timeouts, input, environment, shell injection, encoding on Windows and Popen streaming.

Read article →
Databases & SQL

SQL EXPLAIN Plan: How to Read Query Plans and Fix Slow Queries

SQL EXPLAIN plan explained: read scans, index searches, covering indexes and temporary sorts, with before and after timings for five…

Read article →
Artificial Intelligence

Decision Tree in Python: Gini, Entropy and Overfitting From Scratch

Decision tree in Python from scratch: Gini impurity, entropy, information gain, best splits, readable rules, and how depth and leaf…

Read article →
Software Development

URL Query Parameters: Encoding, URLSearchParams and Common Traps

URL query parameters explained: reading and building them with URLSearchParams and urllib, percent encoding, plus signs, repeated keys and nine…

Read article →
DevOps

Git Blame Explained: Find Who Changed a Line, and Why

Git blame explained with a real repository: ignore whitespace, line ranges and functions, ignore-revs files for formatting commits, moved code…

Read article →
Test Automation

Pytest Benchmark: Measure Speed and Catch Performance Regressions

Pytest benchmark tutorial: the benchmark fixture, reading results, parametrized and pedantic benchmarks, saving baselines and failing the build on regressions.

Read article →
Software Testing

Defect Density: Formula, Worked Examples and How to Use It

Defect density explained: the formula, a five-module worked example, per KLOC vs per function point, severity weighting, defect removal efficiency…

Read article →
Databases & SQL

Case Insensitive Search in SQL: LOWER, LIKE, COLLATE and Indexes

Case insensitive search in SQL: LOWER, LIKE, COLLATE NOCASE and expression indexes compared with query plans, plus accented letters and…

Read article →
Databases & SQL

ON DELETE CASCADE in SQL: CASCADE vs SET NULL vs RESTRICT

ON DELETE CASCADE in SQL tested: CASCADE vs SET NULL vs RESTRICT, multi-level cascades, the SQLite foreign key pragma, row…

Read article →
Software Development

JavaScript BigInt Explained: Big Numbers, Division and JSON

JavaScript BigInt explained: the 2^53 limit, creating and converting BigInt, division, mixing types, JSON stringify and parse without losing digits,…

Read article →
Artificial Intelligence

Logistic Regression in Python: Sigmoid, Log Loss and Gradient Descent From Scratch

Logistic regression in Python from scratch: sigmoid, log loss, gradient descent, odds ratios, thresholds, sigmoid overflow and separable data, tested…

Read article →
DevOps

Git Worktree Explained: Work on Two Branches at Once

Git worktree explained: add, list, remove, prune, lock and detached worktrees, a hotfix workflow, and the errors you will hit,…

Read article →
Test Automation

Pytest ini Explained: addopts, markers, testpaths and Precedence

Pytest ini explained: testpaths, addopts, strict markers, xfail_strict, filterwarnings, minversion, config file precedence and command-line overrides, tested.

Read article →
Software Testing

Test Estimation Techniques: WBS, Three Point PERT and Monte Carlo

Test estimation techniques worked through: WBS, three point PERT, total uncertainty, a Monte Carlo check, percentage rules and Wideband Delphi.

Read article →
Databases & SQL

Gaps and Islands in SQL: Find Streaks and Missing Ranges

Gaps and islands in SQL: find login streaks and missing ranges with ROW_NUMBER, DENSE_RANK, LAG and LEAD, plus the duplicate…

Read article →
Databases & SQL

INSERT INTO SELECT in SQL: Copy Rows Between Tables Safely

INSERT INTO SELECT in SQL: copy rows between tables with chosen columns, joins and summaries, avoid duplicates on reruns, upsert,…

Read article →
Artificial Intelligence

Linear Regression in Python: Least Squares From Scratch, With R Squared

Linear regression in Python from scratch: closed form, NumPy least squares and gradient descent, R squared, RMSE, outliers and curved…

Read article →
DevOps

Git Remote Explained: Add, Set-URL, Rename, Remove and Push URLs

Git remote explained: add, set-url, separate push URLs, rename, remove and prune, plus how to avoid leaking tokens in remote…

Read article →
Test Automation

Pytest Mock: mocker.patch, spy, side_effect and autospec Explained

Pytest mock explained: mocker.patch, return_value, side_effect, spy, autospec and PropertyMock, with tested examples for APIs, clocks and retries.

Read article →
Software Testing

System Testing Explained: Types, Process and a Real End-to-End Example

System testing explained: types, entry and exit criteria, the process, and a real end-to-end test suite run against a small…

Read article →
Artificial Intelligence

Naive Bayes Classifier Explained: Build a Spam Filter in Python

Naive Bayes classifier explained by building a spam filter in Python: Bayes rule, the naive assumption, Laplace smoothing, log probabilities…

Read article →
DevOps

Git Branch Explained: Create, Switch, Rename, Delete and Recover

Git branch explained with tested commands: list, create, switch, rename, delete, merged checks, recovering deleted branches, remote tracking and naming.

Read article →
Test Automation

Pytest raises: Testing Exceptions, match and excinfo

Pytest raises explained with tested examples: match regexes, excinfo, custom and chained exceptions, parametrized error cases, pytest.warns and common mistakes.

Read article →
Software Testing

Non Functional Testing: Types, Metrics and a Real Load Test

Non functional testing explained: 10 key types, measurable requirements, latency percentiles and what a small real load test revealed about…

Read article →
Artificial Intelligence

K Means Clustering Explained: How It Works, With Python Code

K means clustering explained: the algorithm, a from-scratch NumPy version, choosing k with the elbow and silhouette methods, k-means++, scaling…

Read article →
DevOps

Git Log Explained: 15 Useful Commands and Pretty Formats

Git log explained with 15 tested commands: oneline, graph, filters by author, date, message and code, file history, stats, pretty…

Read article →
Test Automation

Pytest conftest.py Explained: Shared Fixtures, Hooks and Overrides

Pytest conftest.py explained with a tested suite: shared fixtures, scope and teardown, folder overrides, autouse, custom options, markers and useful…

Read article →
Software Testing

Usability Testing: Methods, Metrics, SUS Score and Checklist

Usability testing explained: methods, planning, writing tasks, running sessions, metrics, SUS scoring, how many users you need and a practical…

Read article →