Learning Objectives

After completing this exercise, you should be able to:

  1. Explain how a classification tree chooses a split.
  2. Calculate Gini impurity for a candidate split.
  3. Compare several candidate splits using Gini.
  4. Explain the relationship between Gini and variation in the outcome.
  5. Calculate entropy and information gain.
  6. Explain why class imbalance can make accuracy misleading.

1. The Classification Problem

Suppose we want to predict whether a student will Pass or Fail a course.

We have two possible predictors:

  • Study: Did the student study at least 5 hours?
  • Attendance: Was the student’s attendance at least 80%?

Our data are:

students <- data.frame(
  Student = 1:10,
  Study = c("Yes","Yes","Yes","Yes","Yes",
            "Yes","No","No","No","No"),
  Attendance = c("Yes","Yes","Yes","No","Yes",
                 "No","Yes","No","Yes","No"),
  Outcome = c("Pass","Pass","Pass","Pass","Pass",
              "Pass","Pass","Pass","Fail","Fail")
)

students
##    Student Study Attendance Outcome
## 1        1   Yes        Yes    Pass
## 2        2   Yes        Yes    Pass
## 3        3   Yes        Yes    Pass
## 4        4   Yes         No    Pass
## 5        5   Yes        Yes    Pass
## 6        6   Yes         No    Pass
## 7        7    No        Yes    Pass
## 8        8    No         No    Pass
## 9        9    No        Yes    Fail
## 10      10    No         No    Fail

Examine the outcome.

table(students$Outcome)
## 
## Fail Pass 
##    2    8
prop.table(table(students$Outcome))
## 
## Fail Pass 
##  0.2  0.8

There are:

  • 8 Pass
  • 2 Fail

The classes are therefore imbalanced.

A model that simply predicts “Pass” for everyone would achieve 80% accuracy.

But it would fail to identify either student who fails.

A decision tree tries to do something more useful: find a split that separates the classes.

2. What Is a Split?

A decision tree considers different ways of dividing the observations.

For example, we could split the students using:

Study >= 5 hours

or:

Attendance >= 80%

Each candidate split produces groups of students.

The tree needs a way to answer:

Which split produces the cleanest separation of Pass and Fail?

One common measure is Gini impurity.

3. Gini Impurity

Gini measures how mixed the outcomes are.

For outcome classes with proportions \(p_1,p_2,\ldots,p_K\):

\[ Gini=1-\sum_{k=1}^{K}p_k^2 \]

For a two-class problem:

\[ Gini=1-p_{Pass}^2-p_{Fail}^2 \]

Gini is smallest when observations belong to the same class.

For example:

Pass Fail Gini
100% 0% 0.00
90% 10% 0.18
80% 20% 0.32
70% 30% 0.42
50% 50% 0.50

A Gini of 0 represents complete purity.

For a two-class problem, a Gini of 0.50 represents maximum mixing.

4. Gini and Variation

There is a useful way to think about Gini.

Code one outcome as 1 and the other as 0.

For a binary outcome with proportion \(p\) in one class, its variance is:

\[ Variance=p(1-p) \]

For two classes:

\[ Gini=2p(1-p) \]

Therefore:

\[ Gini=2(Variance) \]

For a two-class outcome, Gini is simply a rescaled measure of variation.

This gives us an intuitive interpretation:

A good decision-tree split creates groups with less outcome variation.

5. Score the Entire Split

We do not choose a predictor by looking at only one resulting group.

We score the entire candidate split.

Suppose a split produces \(J\) groups.

Its Gini score is:

\[ Gini_{Split} = \sum_{j=1}^{J} \frac{n_j}{n}Gini_j \]

where:

  • \(n_j\) is the number of observations in group \(j\)
  • \(n\) is the total number of observations
  • \(Gini_j\) is the impurity within group \(j\)

The tree then follows a simple rule:

Choose the candidate split with the lowest Gini score.

6. Candidate Split: Study

First consider:

Study >= 5 hours

table(students$Study, students$Outcome)
##      
##       Fail Pass
##   No     2    2
##   Yes    0    6

The split produces:

Study Pass Fail Total
Yes 6 0 6
No 2 2 4

The first group is completely pure:

\[ Gini_1=0 \]

The second group is evenly divided:

\[ Gini_2=0.50 \]

The score for the entire Study split is therefore:

\[ Gini_{Study} = \frac{6}{10}(0) + \frac{4}{10}(0.50) \]

\[ \boxed{Gini_{Study}=0.200} \]

That single number is the score we need for this candidate split.

7. Candidate Split: Attendance

Now consider:

Attendance >= 80%

table(students$Attendance, students$Outcome)
##      
##       Fail Pass
##   No     1    3
##   Yes    1    5

This produces:

Attendance Pass Fail Total
Yes 5 1 6
No 3 1 4

For the first group:

\[ Gini_1 = 1-\left(\frac{5}{6}\right)^2 -\left(\frac{1}{6}\right)^2 \approx0.278 \]

For the second group:

\[ Gini_2 = 1-\left(\frac{3}{4}\right)^2 -\left(\frac{1}{4}\right)^2 =0.375 \]

Therefore, the score for the entire Attendance split is:

\[ Gini_{Attendance} = \frac{6}{10}(0.278) + \frac{4}{10}(0.375) \]

\[ \boxed{Gini_{Attendance}\approx0.317} \]

8. Select the Split

Now compare the candidate splits.

Candidate Split Gini Score
Study >= 5 hours 0.200
Attendance >= 80% 0.317

The rule is:

\[ \boxed{\text{Choose the split with the lowest Gini}} \]

Therefore, the tree selects:

Study >= 5 hours

The first part of the tree becomes:

                         All Students
                        8 Pass / 2 Fail
                               |
                       Study >= 5 hours?
                         /           \
                       YES            NO
                  6 Pass / 0 Fail  2 Pass / 2 Fail

The tree then repeats the process within any group that needs additional separation.

9. Calculate Split Gini in R

First, create a function to calculate Gini.

gini <- function(y) {
  
  p <- prop.table(table(y))
  
  1 - sum(p^2)
}

Now create a function that scores an entire candidate split.

split_gini <- function(data, predictor, outcome) {
  
  groups <- split(data[[outcome]], data[[predictor]])
  
  n <- nrow(data)
  
  sum(
    sapply(groups, function(group) {
      
      length(group) / n * gini(group)
      
    })
  )
}

Score Study:

split_gini(
  students,
  "Study",
  "Outcome"
)
## [1] 0.2

Score Attendance:

split_gini(
  students,
  "Attendance",
  "Outcome"
)
## [1] 0.3166667

The predictor with the lowest score wins.

10. Compare All Candidate Predictors

Rather than evaluating predictors one at a time, we can score all candidate splits.

predictors <- c("Study", "Attendance")

results <- data.frame(
  Predictor = predictors,
  Gini = sapply(
    predictors,
    function(x)
      split_gini(
        students,
        x,
        "Outcome"
      )
  )
)

results
##             Predictor      Gini
## Study           Study 0.2000000
## Attendance Attendance 0.3166667

Select the best split:

results[
  which.min(results$Gini),
]
##       Predictor Gini
## Study     Study  0.2

The computer is doing exactly what we did manually:

  1. Try a candidate split.
  2. Calculate its Gini score.
  3. Try another split.
  4. Compare the scores.
  5. Choose the lowest.

11. Another Way to Measure Mixing: Entropy

Gini is not the only way to measure how mixed a group is.

Another common measure is entropy:

\[ Entropy = -\sum_{k=1}^{K}p_k\log_2(p_k) \]

Like Gini:

  • Entropy is 0 for a completely pure group.
  • Entropy increases as the classes become more mixed.
  • For two equally represented classes, entropy reaches 1.

For example:

Pass Fail Gini Entropy
100% 0% 0.00 0.00
80% 20% 0.32 0.72
50% 50% 0.50 1.00

The numerical scales differ.

Therefore, do not compare a Gini value directly with an entropy value.

Instead, use either measure to compare candidate splits.

12. Entropy in R

Create an entropy function:

entropy <- function(y) {
  
  p <- prop.table(table(y))
  
  -sum(p * log2(p))
}

Now create a function to score an entire split using entropy.

split_entropy <- function(data, predictor, outcome) {
  
  groups <- split(data[[outcome]], data[[predictor]])
  
  n <- nrow(data)
  
  sum(
    sapply(groups, function(group) {
      
      length(group) / n * entropy(group)
      
    })
  )
}

Compare the two candidate splits:

split_entropy(
  students,
  "Study",
  "Outcome"
)
## [1] 0.4
split_entropy(
  students,
  "Attendance",
  "Outcome"
)
## [1] 0.7145247

Again:

Lower impurity is better.

13. Information Gain

Entropy is also commonly expressed in terms of information gain.

First calculate entropy before making any split:

parent_entropy <- entropy(students$Outcome)

parent_entropy
## [1] 0.7219281

Information gain is:

\[ Information\ Gain = Entropy_{Parent} - Entropy_{Split} \]

Therefore:

study_ig <-
  parent_entropy -
  split_entropy(
    students,
    "Study",
    "Outcome"
  )

attendance_ig <-
  parent_entropy -
  split_entropy(
    students,
    "Attendance",
    "Outcome"
  )

study_ig
## [1] 0.3219281
attendance_ig
## [1] 0.007403392

With entropy, we can therefore use either rule:

Choose the lowest split entropy

or:

Choose the highest information gain

They produce the same choice.

14. Compare Gini and Entropy

Now calculate everything at once.

results <- data.frame(
  Predictor = predictors,
  
  Gini = sapply(
    predictors,
    function(x)
      split_gini(
        students,
        x,
        "Outcome"
      )
  ),
  
  Entropy = sapply(
    predictors,
    function(x)
      split_entropy(
        students,
        x,
        "Outcome"
      )
  )
)

results$Information_Gain <-
  parent_entropy -
  results$Entropy

results
##             Predictor      Gini   Entropy Information_Gain
## Study           Study 0.2000000 0.4000000      0.321928095
## Attendance Attendance 0.3166667 0.7145247      0.007403392

For these data, both methods select Study.

The important idea is not the particular formula.

The important idea is:

A decision tree tries candidate splits and selects the one that best separates the outcome classes.

Gini and entropy provide two different ways of scoring that separation.

15. Why Class Imbalance Matters

Recall that 8 of our 10 students Pass.

If we predict:

“Everyone passes”

our accuracy is:

\[ Accuracy=\frac{8}{10}=80\% \]

But we identify:

\[ 0\% \]

of the students who Fail.

This illustrates why accuracy alone can be misleading when classes are imbalanced.

A decision tree instead looks for predictors that divide the observations into groups with different outcome distributions.

16. Your Turn

Suppose we introduce another possible predictor:

Assignments Completed >= 80%

It produces:

Assignments Pass Fail Total
>= 80% 7 1 8
< 80% 1 1 2

Treat this as a single candidate split.

Calculate:

  1. The Gini score for the Assignments split.
  2. The entropy score for the Assignments split.
  3. The information gain.
  4. Compare Assignments with Study and Attendance.
  5. Which predictor would Gini select?
  6. Which predictor would entropy select?

17. Concept Questions

Answer the following in your own words.

Question 1: What does a low Gini score tell us about a candidate split?

Question 2: Why must we account for the number of observations in each resulting group?

Question 3: Why can 80% accuracy be misleading in our example?

Question 4: What is the difference between Gini and entropy?

Question 5: What is information gain?

Question 6: Suppose one split creates a tiny perfectly pure group but leaves almost everyone else mixed. Why might that split be less useful than one that creates two large, reasonably pure groups?

Key Takeaway

A decision tree repeatedly asks one question:

Which candidate split separates the outcome classes best?

For Gini:

\[ \boxed{\text{Lowest split Gini wins}} \]

For entropy:

\[ \boxed{\text{Lowest split entropy wins}} \]

or equivalently:

\[ \boxed{\text{Highest information gain wins}} \]

Once the best split is selected, the tree repeats the process within the resulting groups.