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.
- 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
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.