What is a Decision Tree?

Every machine learning course shows you the same picture: a decision tree with clean little boxes and arrows, built as if by magic from a .fit() call. What almost nobody shows you is the arithmetic happening inside that call including the handful of log2 computations that decide, at every fork, which question to ask next.

This article does that arithmetic in the open. By the end, you’ll be able to take a small dataset, a pencil, and a calculator, and build an ID3 decision tree exactly the way the algorithm does,entropy calculation by entropy calculation ,with no library standing between you and the result. We’ll work through a full dataset from root to leaves, hit a genuine tie (and resolve it properly), handle a case the training data never saw, and even extend the method to numeric attributes, which the textbook version of ID3 quietly skips.

If you’ve ever wanted to feel why a decision tree picks the split it picks, rather than trusting that scikit-learn knows best, this is that walkthrough.

The ID3 (Iterative Dichotomiser 3) algorithm is a classification method that builds a decision tree by selecting attributes with the highest Information Gain (IG) at each step.It builds a decision tree greedily from the top down.

Concretely, the loop is:

1. At the current node, measure how “mixed up” the examples are with respect to the target class. This measurement is called entropy.
2. For every attribute not yet used, measure how much asking about it would reduce that mixed-up-ness. This is called Information Gain.
3. Pick the attribute with the highest Information Gain
4. Split the examples into branches, one per value of that attribute, and drop that attribute from consideration further down each branch.
5. Repeat inside each branch, on its own subset of the data, until you hit a stopping condition (covered in Section 12).

Every single decision the algorithm makes traces back to one function: entropy. So before we touch a real dataset, let’s make sure we understand that function.

The Entropy Function.

Here’s the formula, which looks intimidating until you take it apart piece by piece:

Entropy(S) = - Σ  p(i) * log2( p(i) )      for i = 1..k

Let’s unpack every symbol.

What p(i) means. S is a set of examples — rows in a table. p(i) is simply the fraction of those rows that belong to class i. If 9 of 14 rows are "Yes," then p(Yes) = 9/14.

Why we multiply by p(i) and sum. -log2(p(i)) is the surprise of one class. But a set S contains a mix of classes, each with its own surprise value. Entropy is the expected (probability-weighted average) surprise across the whole set.

Put in plain English: entropy is the average number of bits of surprise you’d experience learning the class of a randomly picked example from S.

Entropy is measured in bits. For a binary target (two classes, like Yes/No), it ranges from:0 — pure class to 1 — the two classes are perfectly 50/50. Maximum surprise, exactly like a fair coin flip.

For k classes generally, the ceiling is log2(k).

Entropy Arithmetic on Marbles

Before the real dataset, let’s get the arithmetic mechanical on something trivial. Suppose a bag has 10 marbles: 7 red, 3 blue.

p(red)  = 7/10 = 0.7
p(blue) = 3/10 = 0.3

Most calculators don’t have a log2 button, only ln (natural log) or log10. So use this formula instead:

log2(x) = ln(x) / ln(2) = ln(x) / 0.693147

Applying it:

log2(0.7) = ln(0.7) / ln(2) = -0.35667 / 0.69315 = -0.51457
log2(0.3) = ln(0.3) / ln(2) = -1.20397 / 0.69315 = -1.73697

Now plug into the entropy formula by multiplying each log2(p) by its p, negating, and adding:

Entropy = -(0.7 * -0.51457) - (0.3 * -1.73697)
        =  0.36020         +  0.52109
        =  0.88129 bits

That’s close to the maximum of 1 (which makes sense since 7/3 is a fairly mixed bag, though not as mixed as 5/5 would be).

What Information Gain Is Measuring

Entropy tells you how mixed up a set is. But ID3 needs to decide which attribute to ask about next ,and for that, it needs to know how much asking about a given attribute would clean things up. That’s Information Gain: the drop in entropy you get, on average, from learning the value of an attribute.

To compute it, you first need the weighted (or “remainder”) entropy after a split:

Remainder(S, A) = Σ  ( |S_v| / |S| ) * Entropy(S_v)     for each value v of A

Read this the same way as the entropy sum: it’s an expected value. If attribute A splits S into subsets S_v (one per possible value v), then Remainder(S, A) is the average entropy across those subsets, weighted by how large each subset is relative to the whole (|S_v| / |S|).

Information Gain is then simply:

Gain(S, A) = Entropy(S) - Remainder(S, A)

In words: “How much uncertainty about the class do I remove, on average, by learning the value of A?” ID3’s whole strategy is to greedily pick the attribute that maximizes this number at each node.

Now for a real Dataset Example

I will be using the Lenses dataset from UCI’s ML Repository. You can obtain a view of it below:

Lenses dataset

Step 1 : Root Node Entropy

Over all 24 rows: 15 no contact lenses(N), 5 soft contact lenses(S),4 hard contact lenses(H).

p(N) = 15/24 = 0.625
p(S)  = 5/24 = 0.2083
p(H)= 4/24 =0.1667

log2(15/24) = log10(0.625) / log10(2) = -0.6781
log2(5/24) = log10(0.2083) / log10(2) = -2.2630
log2(4/24) = log10(0.1667) / log10(2) = -2.585
Entropy(S) = - Σ  p(i) * log2( p(i) )      for i = 1..k
           = -[(0.625 * -0.6781) + (0.2083 * -2.2630) + (0.1667 * -2.585)]
           =  1.3261

Given that we have 3 classes,our max node entropy is log2(3) = 1.585 thus we are a LONG way from a pure class(0).

Step Two : Information Gain for every node at the root

A. Gain(S, Age)

Information Gain : Age

Young entropy(4 N,2 S,2 H):

p(N)=0.5
p(S)= p(H) = 0.25
log2(0.5) = -1
log2(0.25) = -2
Entropy(Young) = -[(0.5 * -1) + (0.25 * -2) + (0.25 * -2)]
               = 1.5

Pre-Presbyopic entropy(5 N,2 S,1 H):

p(N) = 0.625
p(S) = 0.25
p(H) = 0.125
log2(0.625) = -0.6781 
log2(0.25) = -2
log2(0.125) = -3
Entropy(Pre-Presbyopic)= -[(0.625 * -0.6781) + (0.25 * -2) + (0.125 * -3)]
                       = 1.2988

Presbyopic entropy(6 N,1 S,1 H):

p(N) = 0.75
p(S) = p(H) = 0.125
log2(0.75) = -0.415 
log2(0.125) = -3
Entropy(Presbyopic) = [(0.75 * -0.415) + [2* (0.125 * -3)]]
                    = 1.0613

Weighted remainder:

Remainder(S,Age) = (8/24)(1.5) + (8/24)(1.2988) + (8/24)(1.1738)
                 = 1.2867

Gain(S, Age) = 1.3261 - 1.2867 = 0.039 bits

The gain from this node is quite low, so we try another attribute.

B. Gain(S,SpectaclePrescription)

Information Gain : SpectaclePrescription

Myope entropy(7 N,2 S,3 H):

p(N) = 0.5833
p(S) = 0.1667
p(H) = 0.25
log2(0.5833) = -0.7776 
log2(0.1667) = -2.585
log2(0.25) = -2
Entropy(Myope)= -[(0.5833 * -0.7776) + (0.1667 * -2.585) + (0.25 * -2)]
              = 1.3844

Hypermetrope entropy(8 N,3 S,1 H):

p(N) = 0.6667
p(S) = 0.25
p(H) = 0.0833
log2(0.6667) = -0.585
log2(0.25) = -2
log2(0.0833) = -3.585
Entropy(Myope)= -[(0.6667 * -0.585) + (0.25 * -2) + (0.0833 * -3.585)]
              = 1.1887

Weighted remainder :

 Remainder = (12/24)(1.38443) + (12/24)(1.18872)
            = 0.5(1.3844 + 1.1887)
            = 0.5(2.5731)
            = 1.2865

  Gain(S, SpectaclePrescription) = 1.32609 - 1.28658 = 0.03951 bits

The gain is still very low but slightly higher than that of the Age attribute. Let us try another attribute.

C. Gain(S,Astigmatic)

Information Gain : Astigmatic

Yes entropy(8 N,0 S,4 H):

p(N) = 0.6667
p(S) = 0 (contributes nothing)
p(H) = 0.3333
log2(0.6667) = -0.585 
log2(0.3333) = -1.585
Entropy(Yes)= -[(0.6667 * -0.585) + (0.3333 * -1.585) + 0]
            = 0.9183

No entropy(7 N,5 S, 0H):

p(N) = 0.5833
p(S) = 0.4167
p(H) = 0
log2(0.5833) = -0.7776
log2(0.4167) = -1.263
Entropy(No)= -[(0.5833 * -0.7776) + (0.4167 * -1.263) + 0]
            = 0.9799

Weighted remainder :

Remainder(S, Astigmatic) = (12/24)(0.9799) + (12/24)(0.9183)
                         = 0.5(0.9799 + 0.9183)
                         = 0.9491

  Gain(S, Astigmatic) = Entropy(S) - Remainder(S, Astigmatic)
                       = 1.3261 - 0.9491
                       = 0.377 bits

This is the strongest gain we have gotten by far. Lets finish off with the TearProductionRate so we can choose what node to split the root at.

Get Carissa Nkya’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

D. Gain(S,TearProductionRate):

Information Gain: TearProductionRate

Reduced entropy(12 N,0 S,0 H) is 0 since this is a pure class.

Normal entropy(3 N,5 S,4 H):

p(N) = 0.25
p(S) = 0.4167
p(H) = 0.3333
log2(0.25) = -2
log2(0.4167) = -1.263
log2(0.3333) = -1.585
Entropy(Normal)= -[(0.25 * -2) + (0.4167 * -1.263) + (0.3333 * -1.585)]
            = 1.5546 

Weighted remainder:

Remainder(S, TearProductionRate) = (12/24)(0) + (12/24)(1.5546)
                                 = 0 + 0.5(1.5546)
                                 = 0.7773

  Gain(S, TearProductionRate) = 1.3261 - 0.7773 = 0.5488 bits

Wow! That is the highest gain so far, and as such we start our split with this attribute.

Our tree now looks like this:

Decision tree at first fork.

And we now put aside the data that we do not need i.e. all data related to the “Reduced” branch. Our dataset becomes:

Forked dataset : TearProductionRate attribute

The root entropy for this branch(3 N,5 S,4 H) is 1.5546(see above).

We need to do the same gain calculations to see how/where to split it further.

A. Gain(Normal,Age):

Information Gain : Age for Nromal branch

Young entropy(0 N,2 S,2 H):

p(N) = 0
p(S) = p(H) = 0.5
log2(0.5) = -1
Entropy(Young)= -[ 0 + (0.5 * -1) + (0.5 * -1)]
            = 1

Pre-Presbyopic entropy(1 N,2 S, 1 H):

p(N) = p(H) = 0.25
p(S) = 0.5
log2(0.25) = -2
log2(0.5) = -1
Entropy(Pre-Presbyopic)= -[(0.25 * -2) + (0.5 * -1) + (0.5 * -1)]
            = 1.5

Presbyopic entropy(2 N,1 S,1 H) is also 1.5 since the information split is the same.

Weighted remainder:

Remainder(Normal, Age) = (4/12)(1) + (4/12)(1.5) + (4/12)(1.5)
                          = (1/3)(1 + 1.5 + 1.5)
                          = (1/3)(4)
                          = 1.3333

  Gain(Normal, Age) = Entropy(Normal) - Remainder(Normal, Age)
                     = 1.5546 - 1.3333
                     = 0.2213 bits

The Information Gain is quite low. We can do better. Let’s try another attribute.

B. Gain(Normal,SpectaclePrescription):

Information Gain : SpectaclePerscription on Normal branch

Note that {1,2,3}/6 and {2,3,1}/6 are the same multiset of probabilities just assigned to different classes, and entropy only depends on the distribution
shape, not which class owns which count.

Thus,Myope entropy and Hypermetrope entropy are the same.

p(N) = 0.3333
p(S) = 0.5
p(H) = 0.1667
log2(0.3333) = -1.585
log2(0.5) = -1
log2(0.1667) = -2.585
Entropy(Myope/Hypermetrope)= -[(0.3333 * -1.585) + (0.5 * -1) + (0.1667 * -2.585)]
            = 1.4592

Weighted remainder:

Remainder(Normal, SpectaclePrescription) = (6/12)(1.45915) + (6/12)(1.45915)
                                         = 1.45915(both branches equal, so the weighted average is just that value)

  Gain(Normal, SpectaclePrescription) = Entropy(Normal) - Remainder(Normal, SpectaclePrescription)
                                        = 1.5546 - 1.4592
                                        = 0.0954 bits

The gain on this attribute is much lower than the Age attribute.Lets try the last one.

C. Gain(Normal,Astigmatic).

Information Gain : Astigmatic on Normal branch

Yes entropy(1 N,5 S,0 H):

p(N) = 0.3333
p(S) = 0
p(H) = 0.667
log2(0.3333) = -1.585
log2(0.6667) = -0.585
Entropy(Yes)= -[(0.3333 * -1.585) + 0 + (0.6667 * -0.585)]
            = 0.9183

No entropy(1 N,5 S,0 H):

p(N) = 0.1667
p(S) = 0.8333
p(H) = 0
log2(0.1667) = -2.585
log2(0.8333) = -0.263
Entropy(No)= -[(0.1667 * -2.585) + (0.8333 * -0.263) + 0]
            = 0.65

Weighted remainder:

Remainder(Normal, Astigmatic) = (6/12)(0.65002) + (6/12)(0.91830)
                              = 0.5(0.65 + 0.9183)
                              = 0.5(1.5683)
                              = 0.7842

  Gain(Normal, Astigmatic) = Entropy(Normal) - Remainder(Normal, Astigmatic)
                             = 1.5546 - 0.7842
                             = 0.7704 bits

This is the highest Information Gain we get,so we can branch off from Astigmatic attribute. The decision tree is now:

Decision Tree: Astigmatic Branch

Branching into the Yes branch first. The dataset becomes:

Dataset on Yes branch

The entropy at this stage is 0.9183(see above).

A. Gain(Astigmatic, Age)

Information Gain : Age on on Asigmatic branch

Here we can see that the entropy for Young is 0 since it is a pure class.

The entropies for both Pre-Presbyopic and Presbyopic classes are 1 since they present a perfect 50/50 split.

Weighted remainder:

Remainder(Age) = (2/6)(0) + (2/6)(1) + (2/6)(1) = 0.6667
Gain(Age) = 0.9183 - 0.6667 = 0.2516

The gain is quite significant but we should explore the other attribute as well.

B. Gain(Astigmatic,SpectaclePrescription)

Information Gain : SpectaclePerscription on Yes branch

Here the entropy for Myope is 0(pure class) and that of Hypermetrope is 0.9183.

Weighted remainder:

 Remainder(SpecPrescription) = (3/6)(0) + (3/6)(0.9183) = 0.4592
  Gain(SpecPrescription) = 0.9183 - 0.4592 = 0.4592

The gain is higher than on Age. We can split again here and we will have Myope as a pure leaf node and Hypermetrope which is mixed can be split according to Age(the last remaining attribute). The decision tree becomes:

Decision tree updated

Finishing off with the Astigmatic = No branch:

The dataset becomes:

A. Gain(Astigmatic,Age)

Information Gain : Age on Astigmatic Branch

Here,the entropies for both Young and Pre-Presbyopic attributes are 0(Pure classes) and that of Presbyopic is 1 since it has a 50/50 information split.

Weighted Remainder:

Remainder(Age) = (2/6)(0) + (2/6)(0) + (2/6)(1) = 0.3333
Gain(Age) = 0.65 - 0.3333 = 0.3167

The gain is quite small. We should explore another attribute.

B. Gain(Astigmatic, SpectaclePrescription).

Information Gain : SpectaclePrescription on Astigmatic branch

Myope entropy(1 N, 2 S,0 H) is 0.9183 and that of Hypermetrope is 0(pure class).

Weighted remainder:

Remainder(SpecPrescription) = (3/6)(0.9183) + (3/6)(0) = 0.4592
Gain(SpecPrescription) = 0.65 - 0.4592 = 0.1909

The gain on this attribute is lower than that on Age thus Age wins (0.31669 > 0.19087).

Young and Pre-Presbyopic are pure leaves (Soft contact lenses ). Presbyopic (rows 18,22: N=1,S=1) are still mixed but since we only have SpectaclePrescription left, we employ it to split further.

The completed decision tree is:

Complete Decision Tree.

And just like that, you’ve implemented one of the most fundamental ML algorithms with nothing but a pen,paper and calculator.