Activity: Making Trees

For this activity, we’ll use data derived from the 1994 U.S. Census (the Adult dataset from the UCI Machine Learning Repository). There are fewer variables than in our proteomics data, and a little variety is nice.

Action: Get set up

On the group workstation at your table or on one of your laptops, have one person open a new R script. Copy and run the following code to load the data.

You don’t need to save your work (unless you want to). The script is just a convenient way to perform calculations during class.

library(tidyverse)

# Data location
url <- "https://archive.ics.uci.edu/ml/machine-learning-databases/adult/adult.data"

# Import the data
census <- read_csv(
  url,
  col_names = c("age",
                "workclass",
                "fnlwgt",
                "education",
                "education_1",
                "marital_status",
                "occupation",
                "relationship",
                "race",
                "sex",
                "capital_gain",
                "capital_loss",
                "hours_per_week",
                "native_country",
                "income"),
  show_col_types = FALSE
) %>%
  mutate(income = factor(income, levels = c("<=50K", ">50K"))) %>%
  select(-fnlwgt, -education_1)

head(census, 4)

Your group’s task is to build a small classification tree that predicts whether someone earns more than $50,000 per year. You’ll use a sample of observations drawn with replacement and just two randomly selected predictors.

The income variable is the response; the other variables are possible predictors. The response has two categories:

• <=50K: $50,000 or less per year (low income for this activity)
• >50K: more than $50,000 per year (high income for this activity)

str(census$income)

Building a tree

Step 1: Resample the data

We’ll first draw a small sample with replacement. This uses the same idea as bootstrap sampling, but we’ll deliberately take only 200 observations to make the activity manageable.

Action: Draw your sample

Copy the code below into your R script and run it once. Keep this sample for the entire activity.

census_boot <- census %>%
  slice_sample(n = 200, replace = TRUE)

Step 2: Select predictors at random

We’ll also limit your tree to two predictors so you can make the splitting decisions by hand.

Action: Select two predictors

Copy and run the code below once, without modification.

# All columns other than the response are possible predictors
possible_predictors <- census %>%
  select(-income) %>%
  names()

# Draw two predictor names at random
predictors <- sample(possible_predictors,
                     size = 2,
                     replace = FALSE)

predictors

# Keep only the response and your two selected predictors
train <- census_boot %>%
  select(income, all_of(predictors))

head(train)

From now on, use train, not the full census data, when deciding where to split. Use only your two assigned predictors.

Step 3a: Find your first split

Choose one of your two predictors and use it to divide the observations into two groups.

For a continuous (numeric) predictor, choose a cutoff. For example, one group could have age >= 35, and the other could have age < 35.

For a categorical predictor, choose which categories go together in one group and put all remaining categories in the other group.

Your goal is to make one group with a higher proportion of high earners and another with a lower proportion of high earners. Ideally, the first group will actually have a majority of high earners, but that might not be possible with your two random predictors.

You do not need to optimize the split mathematically. Use the following code as a guide, make a reasonable choice, and move on.

If your predictor is continuous

Replace age with one of your selected continuous predictors. You can change 35 to experiment with different cutoffs.

# Visualize the relationship between a predictor and income
train %>%
  ggplot(aes(x = age, y = income)) +
  geom_jitter(height = 0.1, width = 0) +
  geom_vline(xintercept = 35)

# Check the income proportions on each side of the proposed cutoff
cutoff <- 35

train %>%
  mutate(side = if_else(age >= cutoff,
                        "At or above cutoff",
                        "Below cutoff")) %>%
  count(side, income) %>%
  group_by(side) %>%
  mutate(prop = n / sum(n)) %>%
  ungroup()

These are within-group proportions: compare the proportion earning >50K on one side of the cutoff with that on the other side. If the larger values are less associated with high income, reverse which side you call the higher-income side.

If your predictor is categorical

Replace workclass with one of your selected categorical predictors. The table shows how often each income category occurs within each predictor category.

category_summary <- train %>%
  count(workclass, income) %>%
  pivot_wider(names_from = income,
              values_from = n,
              values_fill = 0) %>%
  mutate(prop_high = `>50K` / (`<=50K` + `>50K`),
         majority_high = `>50K` > `<=50K`) %>%
  arrange(desc(prop_high))

category_summary

# Identify categories with a majority of high-income observations
highinc_categories <- category_summary %>%
  filter(majority_high) %>%
  pull(workclass)

highinc_categories

The vector highinc_categories contains categories where more than half the sampled observations earn >50K.

What if there aren’t any? If highinc_categories is empty, that’s fine. Instead, choose one or more categories with relatively high proportions of >50K observations. For example, you can choose the category at the top of your table:

# Run this ONLY if highinc_categories was empty,
# or replace it with your own selected categories.
highinc_categories <- category_summary %>%
  slice(1) %>%
  pull(workclass)

Either way, highinc_categories should contain the categories you decide to put on the higher-income side of the first split. The remaining categories go on the lower-income side.

Action: Make your first split

1. Choose whichever of your two predictors seems to distinguish income groups more clearly.
2. If continuous, select a cutoff and decide which side has the higher proportion of high earners. If categorical, select the categories for the higher-income side.
3. Save the cutoff in cutoff or save the selected category names in highinc_categories, as appropriate.
4. Write down your splitting rule and indicate which branch has the higher proportion of high earners.

Step 3b: Split the lower-income side again

Your first split separated observations into a higher-income side and a lower-income side. But it probably didn’t separate high earners from low earners perfectly: some actual high earners are likely in the lower-income side.

Let’s look for a second split within that lower-income side. Importantly, we’re following the first splitting rule, not filtering on the actual income values.

First, make a subset containing only the observations on the lower-income side of your first split. Use one of the following examples, depending on your first predictor.

# CONTINUOUS first split: example assumes age >= cutoff
# was the higher-income side.
# Replace age with your chosen predictor, and reverse the
# inequality if necessary.
low_branch <- train %>%
  filter(age < cutoff)

# CATEGORICAL first split: the selected categories were
# the higher-income side, so keep all OTHER categories.
# Replace workclass with your chosen predictor.
low_branch <- train %>%
  filter(!(workclass %in% highinc_categories))

Notice the ! in the categorical example: it keeps the categories not assigned to the higher-income branch.

# Check the actual income classes in this subset
low_branch %>%
  count(income)

Action: Find your second split

1. Repeat the exploration from Step 3a, but use low_branch instead of train.
2. You may use either of your two assigned predictors, including the predictor you used for the first split.
3. Choose another binary split that you think separates high earners and low earners within this subset. Make sure it actually produces two nonempty groups.
4. Write down the second splitting rule. For each resulting group, determine whether <=50K or >50K is the majority class. The two groups do not have to have different majority classes.

If you use a categorical predictor again, make a new category vector for the second split (for example, highinc_categories_2) rather than overwriting the one used in the first split.

Step 4: Draw your tree

We’ll stop after two splits. Your tree should have one root node, two internal splitting decisions in total (the root decision and one more decision on the lower-income side), and three terminal (leaf) nodes.

A leaf predicts whichever income category is most common among the training observations that reach that leaf. This means the two leaves created by your second split might both predict <=50K—and that’s okay.

Action: Draw your tree on your group’s whiteboard

• At the root, write your first predictor and splitting rule.
• On the higher-income side of that split, draw a terminal leaf.
• On the lower-income side, draw your second splitting rule with its two terminal leaves.
• Label all three leaves with their predicted class (<=50K or >50K), based on the majority class in each leaf.

As a quick check, your diagram should have exactly two splits and three leaves. You can use count(income) on the observations in a leaf to check its majority class.

Classifying an observation

Let’s use your tree to predict the income category of one randomly selected person from the original data. This is practice following the decision rules, not an evaluation of out-of-sample accuracy.

new_person <- census %>%
  slice_sample(n = 1)

# Show only the two predictors your group was allowed to use
new_person %>%
  select(all_of(predictors))

Action: Classify the observation

Follow your first rule, then your second rule if the observation goes down the lower-income branch. Record the income class predicted by the terminal leaf it reaches. Make your prediction before revealing the actual income.

# Check whether your predicted category was correct
new_person %>%
  select(income)

Did your tree predict the correct class? If not, does that necessarily mean your tree was constructed incorrectly?

Algorithmic considerations

You just constructed a simplified classification tree using recursive partitioning: repeatedly dividing observations according to rules involving predictor variables.

Discuss with your group: How did you decide which predictor and split to use? Could you write code to make the same decision automatically? When should an algorithm stop splitting? And if you had more than two splits available, which leaf would you split next?

An automated tree-building algorithm needs at least two things:

1. A criterion for choosing splits. Classification-tree algorithms commonly use a measure of impurity such as Gini impurity or entropy, rather than relying on intuition or simply looking for groups with a high-income majority. A split can improve class separation even when both resulting groups predict the same class.
2. A stopping rule. Continuing to split until the training data are classified as well as possible can produce a tree that overfits. Depending on the predictors, it may not even be possible to classify every training observation correctly.

One final simplification: we drew a small sample with replacement and selected two predictors once for the whole activity. In a random forest, trees are generally built from bootstrap samples, and random subsets of candidate predictors are selected again at each split, not just once at the beginning.

You can read more about how trees are constructed in MDSR, Section 11.1.1.