Elements of Data Science
SDS 322E

H. Sherry Zhang
Department of Statistics and Data Sciences
University of Texas at Austin

Get the repository for today:
library(usethis)
create_from_github("SDS322E-26FALL/1102-knn", fork = FALSE)

Learning objectives

  • Understand the idea of K-nearest neighbor (KNN) classification
  • Fit a KNN classifier with tidymodels: nearest_neighbor() and the kknn engine
  • Understand that the number of neighbors \(k\) is a hyperparameter, and why we can’t choose it with the training data
  • Tune \(k\) with cross-validation: vfold_cv(), tune(), grid_regular(), tune_grid(), select_best(), finalize_workflow(), last_fit()

KNN

x -5 -3 -1 0 1 2 3 4 6 8 9 10 12 15
y 1 1 1 1 1 1 0 1 0 1 0 0 0 0

Previously from a logistic regression

for x = 3.5, y = 0.72, predict 1.

Maybe there are other things to make a prediction …

How about we look at the 3 points that are closest to x = 3.5:

x 2 3 4
y 1 0 1

K-nearest neighbor predict based on the “average”/ majority vote: here 1 is the majority, so predict 1.

What would you predict at x = 3 with k = 1?

Applicable both for regression and classification.

Classification with KNN

Goal: predict sex based on bill_len and bill_dep with KNN.

  • previously we used logistic regression, now we will use KNN
penguins_clean <- as_tibble(datasets::penguins) |> na.omit()
head(penguins_clean, 3)
# A tibble: 3 × 8
  species island    bill_len bill_dep flipper_len body_mass sex     year
  <fct>   <fct>        <dbl>    <dbl>       <int>     <int> <fct>  <int>
1 Adelie  Torgersen     39.1     18.7         181      3750 male    2007
2 Adelie  Torgersen     39.5     17.4         186      3800 female  2007
3 Adelie  Torgersen     40.3     18           195      3250 female  2007

The same tidymodels workflow as week 10 b (Oct 28), Practice: Introduction to tidymodels, with two changes:

  • Step 1: the model is nearest_neighbor() with the kknn engine, in "classification" mode
  • Step 2: KNN is based on distances, so the recipe scales the predictors with step_normalize()

A first KNN workflow

Step 1: Specify the model, with \(k = 5\) neighbors:

knn_mod <- nearest_neighbor(mode = "classification", neighbors = 5) |>
  set_engine("kknn")

Step 2: Specify the pre-processing recipe:

knn_rec <- recipe(sex ~ bill_len + bill_dep, data = penguins_clean) |>
  step_normalize(all_predictors())

Step 3: Build a workflow:

knn_wf <- workflow() |> add_recipe(knn_rec) |> add_model(knn_mod)

A first KNN workflow

Step 4: Fit the model:

knn_fit <- knn_wf |> fit(data = penguins_clean)

Step 5: Predict:

knn_pred <- augment(knn_fit, penguins_clean)
knn_pred |> select(sex, .pred_class, .pred_female, .pred_male) |> head(5)
# A tibble: 5 × 4
  sex    .pred_class .pred_female .pred_male
  <fct>  <fct>              <dbl>      <dbl>
1 male   male                0.12       0.88
2 female female              1          0   
3 female female              0.64       0.36
4 female female              0.52       0.48
5 male   male                0.28       0.72

Step 6: Calculate classification metrics:

conf_mat(knn_pred, truth = sex, estimate = .pred_class)
          Truth
Prediction female male
    female    151   13
    male       14  155
accuracy(knn_pred, truth = sex, estimate = .pred_class)
# A tibble: 1 × 3
  .metric  .estimator .estimate
  <chr>    <chr>          <dbl>
1 accuracy binary         0.919

\(k\) is a hyperparameter

We picked \(k = 5\), but nothing in the data told us to. \(k\) is a hyperparameter: a setting we choose before fitting. Each value of \(k\) gives a different model:

  • Small \(k\): the boundary bends around individual penguins, so the model is very flexible
  • Large \(k\): each prediction averages over many penguins, so the boundary is smooth

Which \(k\) is best?

Try \(k = 1, 2, \ldots, 20\), and compute the accuracy on the same data we fit on:

With \(k = 1\), every penguin’s nearest neighbor is itself, so the training accuracy is almost perfect. The training data always rewards the most flexible model: it can’t tell us how well the model predicts new penguins.

Cross-validation

To choose \(k\), we need to score the model on penguins it has not been fit on. First, set aside a test set for the final evaluation. Then split the remaining training set into, say, 10 folds. Each fold takes one turn as the validation set, while the model is fit on the other 9:

Cross-validation

For each \(k\), average the 10 validation accuracies, then pick the \(k\) with the best average:

  • every penguin in the training set is used for validation exactly once, but never by a model fit on it
  • averaging over 10 folds is more stable than relying on one random split
  • the test set is not touched while we choose \(k\), so it stays unseen data for the final evaluation

KNN workflow with tuning and CV

  • Step 0: Training-testing split

  • Step 1: Specify the model, with the number of neighbors left to tune

  • Step 2: Specify the pre-processing recipe

  • Step 3: Build a workflow

  • Step 4: Fit the model

    • 4a: Generate the cross validation folds from the training data
    • 4b: Generate the hyperparameter grid
    • 4c: Fit the model on the cv folds and hp grid
    • 4d: Average the metrics over the folds
    • 4e: Find the best model
    • 4f: Plug in the best \(k\) and refit on the whole training data

  • Step 5/6: Predict and calculate classification metrics on the testing data

KNN workflow with tuning and CV

Step 0: Training-testing split: new

set.seed(123)
penguins_split <- initial_split(penguins_clean, prop = 0.75)
<Training/Testing/Total>
<249/84/333>

249 / 333 = 0.747, 84 / 333 = 0.252

penguins_train <- training(penguins_split)
penguins_test  <- testing(penguins_split)
head(penguins_train, 5)
# A tibble: 5 × 8
  species   island    bill_len bill_dep flipper_len body_mass sex     year
  <fct>     <fct>        <dbl>    <dbl>       <int>     <int> <fct>  <int>
1 Gentoo    Biscoe        59.6     17           230      6050 male    2007
2 Adelie    Torgersen     34.4     18.4         184      3325 female  2007
3 Gentoo    Biscoe        45.2     15.8         215      5300 male    2008
4 Chinstrap Dream         49       19.5         210      3950 male    2008
5 Adelie    Torgersen     41.4     18.5         202      3875 male    2009
dim(penguins_train)
[1] 249   8
dim(penguins_test)
[1] 84  8

KNN workflow with tuning and CV

Step 1/2/3: Specify the model, the pre-processing recipe, and the workflow: can you spot the differences from the previous workflow?

# step 1: specify the model
knn_tune_mod <- nearest_neighbor(mode = "classification", neighbors = tune()) |> set_engine("kknn")

# step 2: specify the pre-processing recipe
knn_rec <- recipe(sex ~ bill_len + bill_dep, data = penguins_train) |> step_normalize(all_predictors())

# step 3: build a workflow
knn_tune_wf <- workflow() |> add_recipe(knn_rec) |> add_model(knn_tune_mod)
  • Step 1: neighbors = tune() is a placeholder: we don’t pick \(k\) now, cross-validation fills it in at step 4
  • Step 2: same recipe, with penguins_train as the template.
  • Step 3: same

KNN workflow with tuning and CV

Step 4a: Create the cross-validation folds from the training data

penguins_folds <- vfold_cv(penguins_train, v = 10)
penguins_folds
#  10-fold cross-validation 
# A tibble: 10 × 2
   splits           id    
   <list>           <chr> 
 1 <split [224/25]> Fold01
 2 <split [224/25]> Fold02
 3 <split [224/25]> Fold03
 4 <split [224/25]> Fold04
 5 <split [224/25]> Fold05
 6 <split [224/25]> Fold06
 7 <split [224/25]> Fold07
 8 <split [224/25]> Fold08
 9 <split [224/25]> Fold09
10 <split [225/24]> Fold10
  • One row per fold. <split [224/25]>: the model is fit on 224 penguins and validated on the other 25
  • Only penguins_train is split: the test set stays aside

KNN workflow with tuning and CV

Step 4b: Set up the hyperparameter grid: the values of \(k\) to try

knn_grid <- grid_regular(neighbors(range = c(1, 20)), levels = 20)
knn_grid
# A tibble: 20 × 1
   neighbors
       <int>
 1         1
 2         2
 3         3
 4         4
 5         5
 6         6
 7         7
 8         8
 9         9
10        10
11        11
12        12
13        13
14        14
15        15
16        16
17        17
18        18
19        19
20        20
  • A tibble with one column per hyperparameter, named after the argument we set to tune(): neighbors
  • range = c(1, 20): the smallest and largest \(k\); levels = 20: how many evenly spaced values, so \(k = 1, 2, \ldots, 20\)
  • With levels = 5, we would get \(k\) = 1, 5, 10, 15, 20

KNN workflow with tuning and CV

Step 4c: Fit the model for every \(k\) on every fold

knn_tune_res <- tune_grid(knn_tune_wf, resamples = penguins_folds, grid = knn_grid)
knn_tune_res
# Tuning results
# 10-fold cross-validation 
# A tibble: 10 × 4
   splits           id     .metrics          .notes          
   <list>           <chr>  <list>            <list>          
 1 <split [224/25]> Fold01 <tibble [60 × 5]> <tibble [0 × 4]>
 2 <split [224/25]> Fold02 <tibble [60 × 5]> <tibble [0 × 4]>
 3 <split [224/25]> Fold03 <tibble [60 × 5]> <tibble [0 × 4]>
 4 <split [224/25]> Fold04 <tibble [60 × 5]> <tibble [0 × 4]>
 5 <split [224/25]> Fold05 <tibble [60 × 5]> <tibble [0 × 4]>
 6 <split [224/25]> Fold06 <tibble [60 × 5]> <tibble [0 × 4]>
 7 <split [224/25]> Fold07 <tibble [60 × 5]> <tibble [0 × 4]>
 8 <split [224/25]> Fold08 <tibble [60 × 5]> <tibble [0 × 4]>
 9 <split [224/25]> Fold09 <tibble [60 × 5]> <tibble [0 × 4]>
10 <split [225/24]> Fold10 <tibble [60 × 5]> <tibble [0 × 4]>
  • How many KNN fits?
  • Each fit: prepare the recipe (step_normalize()) and fit KNN on 224 penguins, then predict the 25 held-out penguins and compute the metrics

KNN workflow with tuning and CV

knn_tune_res |> tidyr::unnest(.metrics)
# A tibble: 600 × 8
   splits           id     neighbors .metric     .estimator .estimate .config   
   <list>           <chr>      <int> <chr>       <chr>          <dbl> <chr>     
 1 <split [224/25]> Fold01         1 accuracy    binary         0.8   pre0_mod0…
 2 <split [224/25]> Fold01         1 roc_auc     binary         0.801 pre0_mod0…
 3 <split [224/25]> Fold01         1 brier_class binary         0.2   pre0_mod0…
 4 <split [224/25]> Fold01         2 accuracy    binary         0.8   pre0_mod0…
 5 <split [224/25]> Fold01         2 roc_auc     binary         0.885 pre0_mod0…
 6 <split [224/25]> Fold01         2 brier_class binary         0.152 pre0_mod0…
 7 <split [224/25]> Fold01         3 accuracy    binary         0.8   pre0_mod0…
 8 <split [224/25]> Fold01         3 roc_auc     binary         0.917 pre0_mod0…
 9 <split [224/25]> Fold01         3 brier_class binary         0.123 pre0_mod0…
10 <split [224/25]> Fold01         4 accuracy    binary         0.88  pre0_mod0…
# ℹ 590 more rows
# ℹ 1 more variable: .notes <list>
  • .metrics: 60 rows for each fold = 20 values of \(k\) \(\times\) 3 default metrics (accuracy, roc_auc, brier_class)

KNN workflow with tuning and CV

Step 4d: Average the metrics over the 10 folds

collect_metrics(knn_tune_res) |> filter(.metric == "accuracy")
# A tibble: 20 × 7
   neighbors .metric  .estimator  mean     n std_err .config         
       <int> <chr>    <chr>      <dbl> <int>   <dbl> <chr>           
 1         1 accuracy binary     0.796    10 0.0200  pre0_mod01_post0
 2         2 accuracy binary     0.796    10 0.0200  pre0_mod02_post0
 3         3 accuracy binary     0.796    10 0.0200  pre0_mod03_post0
 4         4 accuracy binary     0.851    10 0.0135  pre0_mod04_post0
 5         5 accuracy binary     0.859    10 0.0124  pre0_mod05_post0
 6         6 accuracy binary     0.863    10 0.00907 pre0_mod06_post0
 7         7 accuracy binary     0.871    10 0.0133  pre0_mod07_post0
 8         8 accuracy binary     0.863    10 0.0137  pre0_mod08_post0
 9         9 accuracy binary     0.867    10 0.0146  pre0_mod09_post0
10        10 accuracy binary     0.867    10 0.0146  pre0_mod10_post0
11        11 accuracy binary     0.871    10 0.0143  pre0_mod11_post0
12        12 accuracy binary     0.871    10 0.0143  pre0_mod12_post0
13        13 accuracy binary     0.880    10 0.0133  pre0_mod13_post0
14        14 accuracy binary     0.880    10 0.0119  pre0_mod14_post0
15        15 accuracy binary     0.880    10 0.0119  pre0_mod15_post0
16        16 accuracy binary     0.880    10 0.0119  pre0_mod16_post0
17        17 accuracy binary     0.880    10 0.0119  pre0_mod17_post0
18        18 accuracy binary     0.880    10 0.0119  pre0_mod18_post0
19        19 accuracy binary     0.876    10 0.0126  pre0_mod19_post0
20        20 accuracy binary     0.872    10 0.0116  pre0_mod20_post0
  • mean: the average accuracy over the n = 10 folds, for each \(k\); std_err: how much it varies across folds

KNN workflow with tuning and CV

autoplot(knn_tune_res, metric = "accuracy")

KNN workflow with tuning and CV

Step 4e: Find the best \(k\)

show_best(knn_tune_res, metric = "accuracy", n = 5)
# A tibble: 5 × 7
  neighbors .metric  .estimator  mean     n std_err .config         
      <int> <chr>    <chr>      <dbl> <int>   <dbl> <chr>           
1        14 accuracy binary     0.880    10  0.0119 pre0_mod14_post0
2        15 accuracy binary     0.880    10  0.0119 pre0_mod15_post0
3        16 accuracy binary     0.880    10  0.0119 pre0_mod16_post0
4        17 accuracy binary     0.880    10  0.0119 pre0_mod17_post0
5        18 accuracy binary     0.880    10  0.0119 pre0_mod18_post0
best_k <- select_best(knn_tune_res, metric = "accuracy")
best_k
# A tibble: 1 × 2
  neighbors .config         
      <int> <chr>           
1        14 pre0_mod14_post0
  • show_best(): the top \(k\) values, sorted by mean accuracy. Here several \(k\) tie, and select_best() returns the first one
  • select_best(): a one-row tibble with the best \(k\), ready to plug into the workflow in step 5

KNN workflow with tuning and CV

Step 4f: Plug in the best \(k\)

final_wf <- finalize_workflow(knn_tune_wf, best_k)
final_wf
══ Workflow ════════════════════════════════════════════════════════════════════
Preprocessor: Recipe
Model: nearest_neighbor()

── Preprocessor ────────────────────────────────────────────────────────────────
1 Recipe Step

• step_normalize()

── Model ───────────────────────────────────────────────────────────────────────
K-Nearest Neighbor Model Specification (classification)

Main Arguments:
  neighbors = 14

Computational engine: kknn
  • finalize_workflow() replaces the tune() placeholder with the best \(k\)
  • It is now an ordinary workflow, just like the first KNN workflow, so we can fit it

KNN workflow with tuning and CV

Step 4f: Refit on the whole training data

final_fit <- fit(final_wf, data = penguins_train)
  • The 200 fits in step 4c were only used to choose \(k\). Each of them saw 9/10 of the training data
  • The final model is fit once on all 249 training penguins

Step 5/6: Predict and calculate classification metrics on the testing data, once

res_final <- augment(final_fit, penguins_test)
metrics(res_final, truth = sex, estimate = .pred_class)
# A tibble: 2 × 3
  .metric  .estimator .estimate
  <chr>    <chr>          <dbl>
1 accuracy binary         0.798
2 kap      binary         0.593

KNN workflow with tuning and CV

Example: the ROC curve on the testing data

roc_curve(res_final, truth = sex, .pred_male, event_level = "second") |> autoplot()
  • roc_curve() uses the predicted probability (.pred_male), not the predicted class.
  • As in the logistic regression, male is the positive class (1) and female is 0. yardstick treats the first level of sex (female) as the event by default, so we set event_level = "second" to make it male