Decision Trees Explained: Entropy, Gini, Pruning and Code From Scratch

Imagine a doctor deciding whether a patient needs treatment. Is the fever high? Yes. Is the cough lasting more than a week? No. Each answer narrows the options until a decision pops out. What if a computer could learn that chain of questions by itself, just from data? That is exactly what a decision tree does.

• Questions lead to decisions
• Learned from data

In the last episode we met k nearest neighbors and Naive Bayes, which predict by comparing distances or multiplying probabilities. Trees work differently. They predict by asking simple yes or no questions about one feature at a time. Today we build one by hand, with real numbers, then write the code ourselves.

• Last time: kNN and Naive Bayes
• Today: yes or no questions

Here is our roadmap. First, the geometry: how a tree carves up space. Then entropy, information gain and Gini impurity, computed by hand. We will build a tree on a tiny dataset, extend the idea to regression, study overfitting and pruning, measure feature importance, and finish with code and limitations.

• Geometry, impurity, hand build
• Regression, pruning, code

Picture a scatter plot with two features, say hours studied on the horizontal axis and hours slept on the vertical axis. Blue dots passed the exam, orange dots failed. A tree answers one question: where can I draw a single straight line, parallel to an axis, that separates the colors best?

• Two features, two classes
• Axis-parallel cuts only

Suppose the best vertical line sits at five hours studied. The plane splits into two rectangles. On the right, mostly blue. On the left, a mixture. The tree records this as a root node: is hours studied less than or equal to five? Left branch for yes, right branch for no.

• One question, two regions
• Root node records the cut

Now repeat inside the left rectangle. Find the best horizontal line, perhaps at six hours of sleep. The rectangle divides again, and the tree grows a new level. Each split adds a node, and each final rectangle becomes a leaf that predicts the majority color inside it.

• Repeat inside each region
• Leaves predict the majority

This reveals what a tree really is: a set of axis-aligned boxes, each with its own prediction. To classify a new point, drop it down the tree, answering each question, until it lands in a leaf. Notice that no distances and no scaling are involved, so tree models do not care whether a feature is in meters or millimeters.

• Drop a point down the tree
• No distances, no scaling

The big question is what makes a split good. Intuitively, a good split creates groups that are purer: mostly one class. A group of ten blue dots is perfectly pure. A group with five blue and five orange is maximally confused. We need a number that measures this confusion.

• Good split makes purer groups
• Need a number for confusion

The first measure is entropy, borrowed from information theory, which we met in episode ten. For a group where class k has proportion p sub k, entropy equals minus the sum over classes of p sub k times log base two of p sub k. It measures the average surprise when you draw a random item from the group.

• H = minus sum p log2 p
• Average surprise, in bits

Check the extremes for two classes. A pure group has proportions one and zero. One times log of one is zero, and zero times log of zero is defined as zero, so entropy is zero. A fifty fifty group gives minus point five times minus one, twice, which equals exactly one bit. That is the maximum.

• Pure group: zero bits
• Fifty fifty: one bit

The second measure is Gini impurity. It equals one minus the sum of the squared proportions. The intuition: pick an item at random, then guess its class randomly using the group's proportions. Gini is the probability that you guess wrong. For two classes, it peaks at point five, and is zero for a pure group.

• G = 1 minus sum p squared
• Chance of a wrong random guess

Time for a tiny dataset. Ten customers, and we want to predict whether each buys a product. Six bought, four did not. Two features: is the customer a student, and is their income high or low. Keep these numbers in mind: the whole group has six yes and four no.

• Ten customers, two features
• Six buy, four do not

Parent entropy first. Proportions are point six and point four. Minus point six times log two of point six is about point four four two. Minus point four times log two of point four is about point five two nine. Add them: entropy is roughly point nine seven one bits. Gini is one minus point three six minus point one six, which is point four eight.

• Entropy about 0.971 bits
• Gini equals 0.48

Information gain is the parent entropy minus the weighted average entropy of the children, weighted by how many items each child receives. It answers: how many bits of confusion did this question remove? Gini works the same way, using weighted Gini instead. Let us test splitting on income first.

• Parent minus weighted children
• Bits of confusion removed

Split on income. High income has five customers: four yes, one no. Entropy is point eight times point three two two plus point two times two point three two two, about point seven two two. Low income has five customers: two yes, three no, entropy point nine seven one. Weighted average: about point eight four six. Gain is only point one two five bits.

• Children: 0.722 and 0.971
• Gain is about 0.125 bits

Now split on student. Students number four, and all four buy, so that child is pure with entropy zero. Non-students number six: two yes, four no. Proportions one third and two thirds give entropy about point nine one eight. Weighted: six tenths times point nine one eight is about point five five one. Gain is point four two bits. Much better.

• Student branch is pure
• Gain is about 0.42 bits

Gini agrees. Student yes has Gini zero. Student no has one minus one ninth minus four ninths, which is about point four four four. Weighted: point six times point four four four is point two six seven. The decrease from point four eight is about point two one three. Income gives only point zero eight. Both criteria pick student as the root.

• Gini decrease: 0.213 versus 0.080
• Both choose Student

A common mistake is forgetting to weight the children. If you simply average the two child entropies, a tiny child with one lucky item can look perfect and fool you. Weighting by size ensures that a split is judged by how many data points it actually helps. Another mistake is using log base ten, which rescales every entropy and confuses comparisons with other tools.

• Always weight the children
• Stay consistent with log base

We have the root: student. The student yes branch is pure, all four buy, so it becomes a leaf that predicts yes. The student no branch holds six customers, two yes and four no, still impure. We recurse: treat these six as a brand new dataset and search again for the best question.

• Pure branch becomes a leaf
• Impure branch: ask again

Among the six non-students, only income remains. High income has three: two yes, one no. Low income has three: all no. Entropy of the high group is point nine one eight, the low group is zero. Weighted entropy is point four five nine, so gain is point nine one eight minus point four five nine, which equals point four five nine bits.

• Only income is left
• Gain about 0.459 bits

Low income non-students become a pure leaf: does not buy. High income non-students still hold two yes and one no, but we have used all our features. We stop and predict the majority, yes. The finished tree has three leaves. On our ten customers it gets nine right, ninety percent training accuracy.

• Three leaves, nine of ten right
• Stop when features run out

Read the tree as rules. If student, buys. If not a student and low income, does not buy. If not a student and high income, buys. This readability is the great strength of trees. You can show the model to a manager, a doctor or a regulator, and they can follow every step of the reasoning.

• Every path is an if-then rule
• Interpretable by design

Let us name the algorithm. Recursive partitioning, the heart of methods like CART, goes like this. If the node is pure, or a stopping rule fires, make a leaf. Otherwise, try every feature and every threshold, pick the split with the best impurity decrease, divide the data, and call the same procedure on each child.

• Stop, or find best split
• Recurse on both children

For a numeric feature, which thresholds do we try? Sort the values and consider the midpoint between each pair of neighbors. With ages of twenty, thirty and forty, candidates are twenty five and thirty five. Only boundaries where the label changes can be optimal, which saves time. This is a greedy search: it picks the best split now, never looking ahead.

• Midpoints between sorted values
• Greedy: best split right now

Greedy has a cost. The best first split is not always part of the best overall tree. The classic example is the exclusive or pattern, where neither feature alone reveals anything, yet together they predict perfectly. Finding the truly optimal tree is computationally very hard, so practical algorithms accept the greedy shortcut.

• Best now may not be best overall
• XOR fools single splits

Trees can also predict numbers. The leaf no longer holds a class, but the average target value of its training points. The impurity measure changes too. Instead of entropy, we use variance, the average squared distance from the mean. A good split makes each side's values cluster tightly around its own average.

• Leaf predicts the mean
• Impurity becomes variance

A concrete example. Six houses, sizes fifty, sixty, seventy, one twenty, one thirty, one forty square meters, with prices in thousands: one hundred, one twenty, one ten, three hundred, three twenty, three ten. The mean is two hundred ten. Squared deviations sum to sixty thousand four hundred, so the variance is about ten thousand sixty seven.

• Mean price is 210
• Variance about 10,067

Try splitting at ninety five square meters. The left group has prices one hundred, one twenty, one ten: mean one ten, variance sixty six point seven. The right group has three hundred, three twenty, three ten: mean three ten, variance also sixty six point seven. The weighted variance after the split is just sixty six point seven.

• Left mean 110, right mean 310
• Weighted variance 66.7

Variance reduction is the parent variance minus the weighted child variance: ten thousand sixty seven minus sixty six point seven, about nine thousand nine hundred ninety nine. Nearly all the spread vanished. Notice that a regression tree's prediction is a staircase: flat steps, with jumps at each threshold, rather than a smooth line like linear regression.

• About 10,000 removed
• Predictions form a staircase

This staircase explains a limitation. A tree cannot extrapolate. If the largest training house is one forty square meters, a house of three hundred will still be predicted at three hundred ten, the last step. Linear models continue the trend, trees simply stop. Remember that when forecasting beyond the range of your data.

• Flat beyond the training range
• Linear models keep the trend

What stops the recursion? If we never stop, the tree keeps splitting until every leaf holds a single training point. Training accuracy hits one hundred percent. But the tree has memorized noise, including mislabeled points and coincidences. This is overfitting, which we studied in episode thirteen, and unrestricted trees are masters of it.

• No stopping means one point per leaf
• Perfect training, poor future

Depth is the dial for complexity. A depth one tree, called a stump, underfits. A moderate depth captures real structure. A very deep tree overfits. Plot training and validation accuracy against depth: training keeps rising toward one, while validation rises, peaks, then falls. The peak is where you want to be.

• Training rises with depth
• Validation peaks, then falls

Besides maximum depth, other stopping rules include a minimum number of samples required to split a node, a minimum number of samples in each leaf, and a minimum impurity decrease. Each one prevents the tree from chasing tiny groups. These are hyperparameters, so choose them with a validation set or cross validation, never on the test set.

• Depth, split size, leaf size
• Tune on validation, not test

Pruning takes the opposite approach: grow a large tree, then cut back. Cost complexity pruning scores a tree as its error plus alpha times the number of leaves. Alpha is the price of each extra leaf. A subtree stays only if the error it saves is worth that price. Larger alpha means a smaller tree.

• Error plus alpha times leaves
• Bigger alpha, smaller tree

A worked example. A subtree with three leaves makes two mistakes on one hundred points, an error rate of point zero two. Collapsed into one leaf it makes three mistakes, point zero three. Saving point zero one costs two extra leaves, so the subtree is worth keeping only if alpha is below point zero zero five. Above that, we prune it.

• Saves 0.01 error for 2 leaves
• Threshold alpha equals 0.005

Which features matter most? A standard answer is impurity based importance. For every split, record how much weighted impurity it removed, credit that amount to the feature used, then add up over the tree and normalize to sum to one. In our example, student earned most of the credit at the root.

• Credit each split to its feature
• Sum and normalize to one

Be careful, though. Impurity importance favors features with many distinct values, like an ID number, because they offer many ways to split. It is also computed on training data, so it can credit features for fitting noise. A more trustworthy check is permutation importance: shuffle one feature on held out data and see how much the score drops.

• Biased toward many-valued features
• Permutation importance on held-out data

Now let us implement a small tree. We start with a function that computes Gini for an array of labels: one minus the sum of squared class proportions. Next, a function that tries every feature and every midpoint threshold, computes the weighted Gini of the two sides, and returns the split with the lowest value.

• gini function from proportions
• Loop features and thresholds

Then comes the recursive builder. If the labels are pure, or the depth has reached its limit, or no split improves things, return a leaf holding the majority class. Otherwise split the data into left and right using the best threshold, and build each child with depth plus one. Prediction just walks down comparing feature values.

• Base case returns a leaf
• Children get depth plus one

Run it on our ten customers and the printed tree matches our hand work: student at the root, income below. Now compare with scikit learn. Create a DecisionTreeClassifier with criterion gini and max depth three, fit, and predict. On a held out dataset, our from scratch version and the library agree on almost every prediction, differing only where split ties are broken differently.

• Scratch tree matches by hand
• DecisionTreeClassifier agrees

In scikit learn, the knobs we discussed are all arguments: max depth, min samples leaf, and ccp alpha for cost complexity pruning. You can also call a plotting function to draw the tree, or export its rules as text. Always evaluate with cross validation, and compare against a simple baseline to make sure the tree adds real value.

• max_depth, min_samples_leaf, ccp_alpha
• Cross-validate against a baseline

Now the biggest weakness: instability. Because splits are greedy, a small change in the data can change the root, and then everything below it. Move one customer from yes to no and two features may swap places in the ranking, giving a completely different tree with similar accuracy. Trees have low bias but high variance.

• Tiny data change, new tree
• Low bias, high variance

There are other limits too. Axis-aligned splits approximate a diagonal boundary with a clumsy staircase. Trees cannot extrapolate, and they can be biased toward features with many categories. But the instability points to a beautiful fix. If one tree is unstable, average many different trees and the noise cancels. That is the idea behind ensembles.

• Diagonals need staircases
• Averaging trees tames variance

Let us recap. A tree splits space into boxes using yes or no questions. Entropy and Gini measure impurity, and information gain picks the split. Regression trees use variance reduction. Depth and pruning fight overfitting, importance scores explain the model, and instability is its weakness. Next time: random forests, boosting and SHAP.

• Splits, impurity, pruning, importance
• Next: ensembles and SHAP