## Context and Data

We'll explore KNN regression using the `College` dataset in the `ISLR` package (install it with `install.packages("tidymodels")` in the Console). You can use `?College` in the Console to look at the data codebook.

```{r}
library(ISLR)
library(dplyr)
library(readr)
library(broom)
library(ggplot2)
library(tidymodels) 
tidymodels_prefer() # Resolves conflicts, prefers tidymodel functions


data(College)

# data cleaning
college_clean <- College %>% 
    mutate(school = rownames(College)) %>% # creates variable with school name
    filter(Grad.Rate <= 100) # Remove one school with grad rate of 118%
rownames(college_clean) <- NULL # Remove school names as row names
```


## Exercise 1: Bias-variance tradeoff warmup

a. Think back to the LASSO algorithm which depends upon tuning parameter $\lambda$.
    - For which values of $\lambda$ (small or large) will LASSO be the most biased, and why?
    - For which values of $\lambda$ (small or large) will LASSO be the most variable, and why?

b. The bias-variance tradeoff also comes into play when comparing across algorithms, not just within algorithms. Consider LASSO vs. least squares:
    - Which will tend to be more biased?
    - Which will tend to be more variable?
    - When will LASSO outperform least squares in the bias-variance tradeoff?


## Exercise 2: Impact of distance metric

Consider the 1-nearest neighbor algorithm to predict `Grad.Rate` on the basis of two predictors: `Apps` and `Private`. Let `Yes` for `Private` be represented with the value 1 and `No` with 0.

a. We have a test case whose number of applications is 13,530 and is a private school. Suppose that we have the tiny 2-case training set below. What would the 1-nearest neighbor prediction be using Euclidean distance?

```{r}
college_clean %>%
    filter(school %in% c("Princeton University", "SUNY at Albany")) %>%
    select(Apps, Private, Grad.Rate, school)

sqrt( (13530 - ?)^2 + (1 - ?)^2) # Euclidean distance
sqrt( (13530 - ?)^2 + (1 - ?)^2) # Euclidean distance

```

b. Do you have any concerns about the resulting prediction? Based on this, comment on the impact of the distance metric chosen on KNN performance. How might you change the distance calculation (or correspondingly rescale the data) to generate a more sensible prediction in this situation?


## Exercise 3: Implementing KNN in `tidymodels`

Adapt our general KNN code to "fit" a set of KNN models with the following specifications:

- Use the predictors `Private`, `Top10perc` (% of new students from top 10% of high school class), and `S.F.Ratio` (student/faculty ratio).
- Predict values of `Grad.Rate`
- Use 8-fold CV. (Why 8? Take a look at the sample size.)
- Use mean absolute error (MAE) to select a final model.
- Select the simplest model for which the metric is within one standard error of the best metric.
- Use a sequence of $K$ values from 1 to 100 in increments of 5 (20 values in total).

After adapting the code below (but before inspecting any output), draw a picture of how you expect test MAE to vary with $K$. In terms of the bias-variance tradeoff, why do you expect the plot to look this way?

```{r}
set.seed(2023)
data_cv8 <- vfold_cv(___, v = ___)

# Model Specification
knn_spec <- 
  nearest_neighbor() %>% # new type of model!
  set_args(neighbors = tune()) %>% # tuning parameter is neighbor; tuning spec
  set_engine(engine = 'kknn') %>% # new engine
  set_mode('regression') 

# Recipe with standardization (!)
data_rec <- recipe( ___ ~ ___ , data = ___) %>%
    step_nzv(all_predictors()) %>% # removes variables with the same value
    step_novel(all_nominal_predictors()) %>% # important if you have rare categorical variables 
    step_normalize(all_numeric_predictors()) %>%  # important standardization step for KNN
    step_dummy(all_nominal_predictors())  # creates indicator variables for categorical variables (important for KNN!)

# Workflow (Recipe + Model)
knn_wf <- workflow() %>%
  add_model(knn_spec) %>% 
  add_recipe(data_rec)

# Tune model trying a variety of values for neighbors (using 8-fold CV)
neighbor_grid <- grid_regular(
  neighbors(range = c(______, _____)), #  min and max of values for neighbors
  levels = _______) # number of neighbors values

knn_fit_cv <- tune_grid(knn_wf, # workflow
              resamples = data_cv8, #CV folds
              grid = neighbor_grid, # grid specified above
              metrics = metric_set(rmse, mae))
```

## Exercise 4: Inspecting the results
```{r}
autoplot(knn_fit_cv)

collect_metrics(knn_fit_cv) %>%
  filter(.metric == "mae") %>%
  select(neighbors, .metric, mean)
```

- Use the code above to identify the number of neighbors which led to the lowest MAE.
- Contextually interpret the test MAE.
- Does anything about the results surprise you?



## Exercise 5: Curse of dimensionality

Just as with parametric models, we could keep going and add more and more predictors. However, the KNN algorithm is known to suffer from the "curse of dimensionality". Why? **Hint:** First do a quick Google search of this new idea.



