Skip to content
Back to Data ScienceAll lessons

Data Science

Decision Stump (one split via Gini impurity)

With n points there are roughly n candidate thresholds, and scoring each one takes O(n) work to split and measure impurity. That makes O(n^2) time for a single stump. Real implementations sort once and sweep through in O(n log n) instead of rechecking everything from scratch.

The idea, in plain English

A decision stump is the simplest possible decision tree. It is just one yes/no question that splits your data into two groups. Think of it like the single best sorting question you could ask to separate a mixed bag of marbles into two piles that are each as 'pure' (mostly one color) as possible. Gini impurity measures how 'mixed' a pile is. A value of 0 means a pile is perfectly pure (all one label). The value climbs higher the more evenly mixed the pile is. A decision stump tries every possible splitting question and picks whichever one leaves the two resulting piles least mixed, on average.

How it works

  1. 1Sort the data by its numeric feature, and consider a candidate threshold exactly halfway between every pair of neighboring values.
  2. 2For each candidate threshold, split the data into a 'left' group (feature at or below the threshold) and a 'right' group (feature above it).
  3. 3Compute the Gini impurity of each group: 1 minus the sum of the squared proportion of each label present in that group. A group with only one label present has Gini impurity 0.
  4. 4Combine the two groups' impurities into one score, weighted by how many points fall in each group. Keep whichever threshold gives the lowest weighted impurity — that is the stump's one split.

When you'd use it

On its own, a stump is a fast, easy-to-read baseline classifier — one simple rule, like 'studied more than 2.5 hours? predict pass.' Its bigger role is as a building block. Boosting algorithms like AdaBoost combine hundreds of weak stumps, each fixing the last one's mistakes, into one strong classifier.

Common beginner mistakes

  • Do not pick the split that maximizes plain accuracy instead of minimizing impurity. Gini impurity generalizes more smoothly to more than two classes and to deeper trees built the same way.
  • Do not expect one stump to be a full decision tree. It is a single split, a 'weak learner' on its own, not a complete model.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Points (x,label): (1,no) (2,no) (3,yes) (4,no) (5,yes) (6,yes)
Root Gini impurity: 0.50
Best split threshold: x <= 2.50
Weighted Gini after split: 0.25
Left group predicts: no
Right group predicts: yes

Not sure this is the right topic? See the learning paths → or where this leads →