# Chapter 8 lab: decision trees, bagging, random forests, boosting and BART (R version).
# Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie and
# Tibshirani (2021), An Introduction to Statistical Learning with Applications in R, 2nd edition,
# Section 8.3, and the Python lab of James et al. (2023), Section 8.3.
#
# The lab works through
#   8.3.1  a classification tree for High = (Sales > 8) on the Carseats data, its test error, and pruning
#          by cross-validation with the misclassification error (tree, cv.tree, prune.misclass);
#   8.3.2  a regression tree for medv on the Boston data, cross-validation and pruning;
#   8.3.3  bagging and random forests on the Boston data (randomForest), with variable importance;
#   8.3.4  boosted regression trees (gbm), relative influence and partial dependence plots;
#   8.3.5  Bayesian additive regression trees (BART::gbart);
# and then the applied exercises 7-12 of Section 8.4. The Python version (ch08_lab.py) does the same;
# it reproduces R's random numbers for set.seed() and sample(), so the training sets, the folds of
# cv.tree() and every tree() result are identical in the two languages. Run from the code/ folder:
#   Rscript ch08_lab.R        (about one minute)
# Figures go to ../img/ch08/lab-r-*.svg and the key numbers to cache/ch08_lab_R.csv.

suppressPackageStartupMessages({
  library(ISLR2)
  library(tree)
  library(randomForest)
  library(gbm)
  library(BART)
  library(glmnet)
  library(class)
})
options(digits = 6, width = 100)

out_dir <- file.path("..", "img", "ch08")
dir.create(out_dir, showWarnings = FALSE, recursive = TRUE)
dir.create("cache", showWarnings = FALSE)
key <- list()                                 # key numbers, written to cache/ch08_lab_R.csv at the end
keep <- function(name, value) key[[name]] <<- unname(value)
open_svg <- function(name, width, height) {
  path <- file.path(out_dir, paste0(name, ".svg"))
  if (requireNamespace("svglite", quietly = TRUE)) svglite::svglite(path, width = width, height = height)
  else grDevices::svg(path, width = width, height = height)
}
quiet <- function(expr) invisible(capture.output(x <- expr)) # BART prints its progress
mse <- function(a, b) mean((a - b)^2)

# ================================================================== 8.3.1 classification trees
Carseats$High <- factor(ifelse(Carseats$Sales <= 8, "No", "Yes"))   # High = Sales above 8 (thousand units)
tree.carseats <- tree(High ~ . - Sales, Carseats)
print(summary(tree.carseats))
s <- summary(tree.carseats)
keep("car_size", s$size); keep("car_dev", s$dev); keep("car_err", s$misclass[1] / 400)

open_svg("lab-r-carseats-tree", 10, 6.5)
plot(tree.carseats)
text(tree.carseats, pretty = 0, cex = 0.55)
invisible(dev.off())
print(tree.carseats)

set.seed(2)
train <- sample(1:nrow(Carseats), 200)
Carseats.test <- Carseats[-train, ]
High.test <- Carseats$High[-train]
tree.carseats <- tree(High ~ . - Sales, Carseats, subset = train)
tree.pred <- predict(tree.carseats, Carseats.test, type = "class")   # ties between classes: at random
print(table(tree.pred, High.test))
keep("car_test_acc", mean(tree.pred == High.test))

set.seed(7)
cv.carseats <- cv.tree(tree.carseats, FUN = prune.misclass)
print(cv.carseats)
keep("car_cv_size", cv.carseats$size); keep("car_cv_dev", cv.carseats$dev); keep("car_cv_k", cv.carseats$k[-1])
open_svg("lab-r-carseats-cv", 8, 3.6)
par(mfrow = c(1, 2))
plot(cv.carseats$size, cv.carseats$dev, type = "b", xlab = "size", ylab = "CV errors")
plot(cv.carseats$k, cv.carseats$dev, type = "b", xlab = "k", ylab = "CV errors")
invisible(dev.off())

prune.carseats <- prune.misclass(tree.carseats, best = 9)
open_svg("lab-r-carseats-pruned", 7, 4.5)
plot(prune.carseats)
text(prune.carseats, pretty = 0, cex = 0.7)
invisible(dev.off())
tree.pred <- predict(prune.carseats, Carseats.test, type = "class")
print(table(tree.pred, High.test))
keep("car_prune9_acc", mean(tree.pred == High.test))
prune.carseats <- prune.misclass(tree.carseats, best = 14)
tree.pred <- predict(prune.carseats, Carseats.test, type = "class")
print(table(tree.pred, High.test))
keep("car_prune14_acc", mean(tree.pred == High.test))

# ================================================================== 8.3.2 regression trees
set.seed(1)
train <- sample(1:nrow(Boston), nrow(Boston) / 2)
tree.boston <- tree(medv ~ ., Boston, subset = train)
print(summary(tree.boston))
open_svg("lab-r-boston-tree", 7, 4.5)
plot(tree.boston)
text(tree.boston, pretty = 0, cex = 0.75)
invisible(dev.off())
print(tree.boston)
keep("bos_size", summary(tree.boston)$size); keep("bos_dev", summary(tree.boston)$dev)

cv.boston <- cv.tree(tree.boston)                    # the folds continue the random stream of set.seed(1)
print(cv.boston)
keep("bos_cv_size", cv.boston$size); keep("bos_cv_dev", cv.boston$dev)
open_svg("lab-r-boston-cv", 4.5, 3.6)
plot(cv.boston$size, cv.boston$dev, type = "b", xlab = "size", ylab = "CV deviance (RSS)")
invisible(dev.off())
prune.boston <- prune.tree(tree.boston, best = 5)
print(prune.boston)

yhat <- predict(tree.boston, newdata = Boston[-train, ])
boston.test <- Boston[-train, "medv"]
cat("regression tree, test MSE:", mse(yhat, boston.test), "\n")
keep("bos_tree_mse", mse(yhat, boston.test))
keep("bos_prune5_mse", mse(predict(prune.boston, newdata = Boston[-train, ]), boston.test))

# ================================================================== 8.3.3 bagging and random forests
set.seed(1)
bag.boston <- randomForest(medv ~ ., data = Boston, subset = train, mtry = 12, importance = TRUE)
print(bag.boston)
yhat.bag <- predict(bag.boston, newdata = Boston[-train, ])
cat("bagging, 500 trees, test MSE:", mse(yhat.bag, boston.test), "\n")
keep("bag_mse", mse(yhat.bag, boston.test)); keep("bag_oob", tail(bag.boston$mse, 1))
bag.boston <- randomForest(medv ~ ., data = Boston, subset = train, mtry = 12, ntree = 25)
yhat.bag <- predict(bag.boston, newdata = Boston[-train, ])
cat("bagging, 25 trees, test MSE:", mse(yhat.bag, boston.test), "\n")
keep("bag25_mse", mse(yhat.bag, boston.test))

set.seed(1)
rf.boston <- randomForest(medv ~ ., data = Boston, subset = train, mtry = 6, importance = TRUE)
yhat.rf <- predict(rf.boston, newdata = Boston[-train, ])
cat("random forest, mtry = 6, test MSE:", mse(yhat.rf, boston.test), "\n")
keep("rf_mse", mse(yhat.rf, boston.test))
print(importance(rf.boston))
keep("rf_incmse", importance(rf.boston)[, 1]); keep("rf_purity", importance(rf.boston)[, 2])
open_svg("lab-r-varimp", 8, 4)
varImpPlot(rf.boston, main = "")
invisible(dev.off())

# ================================================================== 8.3.4 boosting
set.seed(1)
boost.boston <- gbm(medv ~ ., data = Boston[train, ], distribution = "gaussian",
                    n.trees = 5000, interaction.depth = 4)        # shrinkage: gbm's default, 0.1
print(summary(boost.boston, plotit = FALSE))
keep("gbm_relinf_rm", summary(boost.boston, plotit = FALSE)["rm", "rel.inf"])
keep("gbm_relinf_lstat", summary(boost.boston, plotit = FALSE)["lstat", "rel.inf"])
open_svg("lab-r-pdp", 8, 3.6)
par(mfrow = c(1, 2))
print(plot(boost.boston, i = "rm"), split = c(1, 1, 2, 1), more = TRUE)
print(plot(boost.boston, i = "lstat"), split = c(2, 1, 2, 1))
invisible(dev.off())
yhat.boost <- predict(boost.boston, newdata = Boston[-train, ], n.trees = 5000)
cat("boosting, shrinkage 0.1 (the default), test MSE:", mse(yhat.boost, boston.test), "\n")
keep("gbm_mse", mse(yhat.boost, boston.test))
boost.boston <- gbm(medv ~ ., data = Boston[train, ], distribution = "gaussian",
                    n.trees = 5000, interaction.depth = 4, shrinkage = 0.2, verbose = FALSE)
yhat.boost <- predict(boost.boston, newdata = Boston[-train, ], n.trees = 5000)
cat("boosting, shrinkage 0.2, test MSE:", mse(yhat.boost, boston.test), "\n")
keep("gbm02_mse", mse(yhat.boost, boston.test))
set.seed(1)
boost.slow <- gbm(medv ~ ., data = Boston[train, ], distribution = "gaussian",
                  n.trees = 5000, interaction.depth = 4, shrinkage = 0.001)
yhat.boost <- predict(boost.slow, newdata = Boston[-train, ], n.trees = 5000)
cat("boosting, shrinkage 0.001, test MSE:", mse(yhat.boost, boston.test), "\n")
keep("gbm0001_mse", mse(yhat.boost, boston.test))

# ================================================================== 8.3.5 BART
x <- Boston[, 1:12]
y <- Boston[, "medv"]
xtrain <- x[train, ]; ytrain <- y[train]
xtest <- x[-train, ]; ytest <- y[-train]
set.seed(1)
quiet(bartfit <- gbart(xtrain, ytrain, x.test = xtest))
yhat.bart <- bartfit$yhat.test.mean
cat("BART, test MSE:", mse(ytest, yhat.bart), "\n")
keep("bart_mse", mse(ytest, yhat.bart)); keep("bart_sigma", mean(bartfit$sigma[-(1:100)]))
ord <- order(bartfit$varcount.mean, decreasing = TRUE)
print(bartfit$varcount.mean[ord])
keep("bart_varcount", bartfit$varcount.mean)

# ================================================================== applied exercises (Section 8.4)
# Exercise 7: random forests on the Boston data for several mtry, test MSE against the number of trees
p <- 12
ex7 <- sapply(c(12, 6, 3), function(m) {
  set.seed(1)
  randomForest(Boston[train, -13], Boston$medv[train], xtest = Boston[-train, -13],
               ytest = Boston$medv[-train], mtry = m, ntree = 500)$test$mse
})
open_svg("lab-r-ex7", 6, 4)
matplot(1:500, ex7, type = "l", lty = 1, col = c("orange", "blue", "darkgreen"), xlab = "Number of trees",
        ylab = "Test MSE", ylim = c(10, 30))
legend("topright", c("m = p = 12", "m = p/2 = 6", "m = 3"), col = c("orange", "blue", "darkgreen"), lty = 1)
invisible(dev.off())
cat("Exercise 7: test MSE after 500 trees, m = 12, 6, 3:", round(ex7[500, ], 3), "\n")
keep("ex7_500", ex7[500, ])

# Exercise 8: regression trees and ensembles for Sales in Carseats
Carseats$High <- NULL
set.seed(1)
tr8 <- sample(1:nrow(Carseats), nrow(Carseats) / 2)
te8 <- Carseats[-tr8, ]
t8 <- tree(Sales ~ ., Carseats, subset = tr8)
print(summary(t8))
open_svg("lab-r-ex8-tree", 10, 6)
plot(t8); text(t8, pretty = 0, cex = 0.55)
invisible(dev.off())
cat("Exercise 8(b): tree with", summary(t8)$size, "leaves, test MSE", mse(predict(t8, te8), te8$Sales), "\n")
keep("ex8_size", summary(t8)$size); keep("ex8_tree_mse", mse(predict(t8, te8), te8$Sales))
cv8 <- cv.tree(t8)
print(cv8)
best8 <- cv8$size[which.min(cv8$dev)]
p8 <- prune.tree(t8, best = best8)
cat("Exercise 8(c): CV picks", best8, "leaves; pruned test MSE", mse(predict(p8, te8), te8$Sales), "\n")
keep("ex8_cv_dev", cv8$dev); keep("ex8_best", best8); keep("ex8_prune_mse", mse(predict(p8, te8), te8$Sales))
set.seed(1)
bag8 <- randomForest(Sales ~ ., data = Carseats, subset = tr8, mtry = 10, importance = TRUE)
cat("Exercise 8(d): bagging test MSE", mse(predict(bag8, te8), te8$Sales), "\n")
print(round(importance(bag8), 2))
keep("ex8_bag_mse", mse(predict(bag8, te8), te8$Sales))
rf8 <- sapply(1:10, function(m) {
  set.seed(1)
  mse(predict(randomForest(Sales ~ ., data = Carseats, subset = tr8, mtry = m), te8), te8$Sales)
})
cat("Exercise 8(e): random forest test MSE for m = 1..10:", round(rf8, 3), "\n")
keep("ex8_rf_mse", rf8)
set.seed(1)
quiet(bart8 <- gbart(Carseats[tr8, -1], Carseats$Sales[tr8], x.test = Carseats[-tr8, -1]))
cat("Exercise 8(f): BART test MSE", mse(bart8$yhat.test.mean, te8$Sales), "\n")
keep("ex8_bart_mse", mse(bart8$yhat.test.mean, te8$Sales))
lm8 <- lm(Sales ~ ., data = Carseats, subset = tr8)          # for comparison: least squares
cat("Exercise 8: least squares test MSE", mse(predict(lm8, te8), te8$Sales), "\n")
keep("ex8_lm_mse", mse(predict(lm8, te8), te8$Sales))

# Exercise 9: classification trees on the OJ data
set.seed(1)
tr9 <- sample(1:nrow(OJ), 800)
t9 <- tree(Purchase ~ ., OJ, subset = tr9)
print(summary(t9))
print(t9)
open_svg("lab-r-ex9-tree", 7, 4.5)
plot(t9); text(t9, pretty = 0, cex = 0.7)
invisible(dev.off())
pred9 <- predict(t9, OJ[-tr9, ], type = "class")
print(table(pred9, OJ$Purchase[-tr9]))
keep("ex9_size", summary(t9)$size); keep("ex9_train_err", summary(t9)$misclass[1] / 800)
keep("ex9_test_err", mean(pred9 != OJ$Purchase[-tr9]))
cv9 <- cv.tree(t9, FUN = prune.misclass)
print(cv9)
keep("ex9_cv_size", cv9$size); keep("ex9_cv_dev", cv9$dev)
open_svg("lab-r-ex9-cv", 4.5, 3.6)
plot(cv9$size, cv9$dev / 800, type = "b", xlab = "Tree size", ylab = "CV classification error")
invisible(dev.off())
best9 <- cv9$size[which.min(cv9$dev)]
if (best9 == max(cv9$size)) best9 <- 5           # CV keeps the full tree: prune to five leaves instead
p9 <- prune.misclass(t9, best = best9)
pred9p <- predict(p9, OJ[-tr9, ], type = "class")
cat("Exercise 9: pruned to", best9, "leaves; training error", summary(p9)$misclass[1] / 800,
    "test error", mean(pred9p != OJ$Purchase[-tr9]), "\n")
keep("ex9_best", best9); keep("ex9_prune_train_err", summary(p9)$misclass[1] / 800)
keep("ex9_prune_test_err", mean(pred9p != OJ$Purchase[-tr9]))

# Exercise 10: boosting for log(Salary) in the Hitters data, first 200 players for training
H <- na.omit(Hitters)
H$Salary <- log(H$Salary)
Htr <- H[1:200, ]; Hte <- H[-(1:200), ]
lams <- c(0.001, 0.002, 0.005, 0.01, 0.02, 0.05, 0.1, 0.2, 0.3, 0.5, 0.7, 1)
ex10 <- t(sapply(lams, function(l) {
  set.seed(1)
  b <- gbm(Salary ~ ., data = Htr, distribution = "gaussian", n.trees = 1000, shrinkage = l)
  c(train = mse(predict(b, Htr, n.trees = 1000), Htr$Salary), test = mse(predict(b, Hte, n.trees = 1000), Hte$Salary))
}))
print(cbind(lambda = lams, ex10))
keep("ex10_train", ex10[, 1]); keep("ex10_test", ex10[, 2])
open_svg("lab-r-ex10", 8, 3.6)
par(mfrow = c(1, 2))
plot(lams, ex10[, 1], log = "x", type = "b", xlab = "shrinkage", ylab = "training MSE")
plot(lams, ex10[, 2], log = "x", type = "b", xlab = "shrinkage", ylab = "test MSE")
invisible(dev.off())
lm10 <- lm(Salary ~ ., data = Htr)
Xtr10 <- model.matrix(Salary ~ ., Htr)[, -1]; Xte10 <- model.matrix(Salary ~ ., Hte)[, -1]
# ridge regression with lambda chosen by exact leave-one-out (standardised inputs, closed form)
mu <- colMeans(Xtr10); sdv <- apply(Xtr10, 2, sd)
Z <- scale(Xtr10, mu, sdv); Zte <- scale(Xte10, mu, sdv); yc <- Htr$Salary - mean(Htr$Salary)
loo <- sapply(10^seq(-2, 4, length.out = 121), function(l) {
  Hm <- Z %*% solve(crossprod(Z) + l * diag(ncol(Z)), t(Z))
  mean(((yc - Hm %*% yc) / (1 - diag(Hm) - 1 / nrow(Z)))^2)
})
lbest <- 10^seq(-2, 4, length.out = 121)[which.min(loo)]
br <- solve(crossprod(Z) + lbest * diag(ncol(Z)), crossprod(Z, yc))
cat("Exercise 10(e): test MSE: boosting (shrinkage 0.01)", ex10[lams == 0.01, 2], " least squares",
    mse(predict(lm10, Hte), Hte$Salary), " ridge (lambda", signif(lbest, 4), ")",
    mse(mean(Htr$Salary) + Zte %*% br, Hte$Salary), "\n")
keep("ex10_lm_mse", mse(predict(lm10, Hte), Hte$Salary)); keep("ex10_ridge_lambda", lbest)
keep("ex10_ridge_mse", mse(mean(Htr$Salary) + Zte %*% br, Hte$Salary))
set.seed(1)
b10 <- gbm(Salary ~ ., data = Htr, distribution = "gaussian", n.trees = 1000, shrinkage = 0.01)
print(head(summary(b10, plotit = FALSE), 5))
set.seed(1)
bag10 <- randomForest(Salary ~ ., data = Htr, mtry = 19)
cat("Exercise 10(g): bagging test MSE", mse(predict(bag10, Hte), Hte$Salary), "\n")
keep("ex10_bag_mse", mse(predict(bag10, Hte), Hte$Salary))

# Exercise 11: boosting on the Caravan data, first 1000 customers for training
Cv <- Caravan
Cv$Purchase <- as.numeric(Cv$Purchase == "Yes")
Ctr <- Cv[1:1000, ]; Cte <- Cv[-(1:1000), ]
set.seed(1)
b11 <- suppressWarnings(gbm(Purchase ~ ., data = Ctr, distribution = "bernoulli", n.trees = 1000, shrinkage = 0.01))
print(head(summary(b11, plotit = FALSE), 6))
p11 <- predict(b11, Cte, n.trees = 1000, type = "response")
print(table(predicted = p11 > 0.2, purchase = Cte$Purchase))
keep("ex11_boost_prec", sum(p11 > 0.2 & Cte$Purchase == 1) / sum(p11 > 0.2)); keep("ex11_boost_npred", sum(p11 > 0.2))
lg11 <- suppressWarnings(glm(Purchase ~ ., data = Ctr, family = binomial))
q11 <- suppressWarnings(predict(lg11, Cte, type = "response"))
print(table(predicted = q11 > 0.2, purchase = Cte$Purchase))
keep("ex11_logit_prec", sum(q11 > 0.2 & Cte$Purchase == 1) / sum(q11 > 0.2)); keep("ex11_logit_npred", sum(q11 > 0.2))
Xs <- scale(Caravan[, -86])
set.seed(1)
k11 <- knn(Xs[1:1000, ], Xs[-(1:1000), ], Caravan$Purchase[1:1000], k = 5)
print(table(predicted = k11, purchase = Cte$Purchase))
keep("ex11_knn_prec", sum(k11 == "Yes" & Cte$Purchase == 1) / sum(k11 == "Yes"))

# Exercise 12: the Auto data, mpg from the seven other numeric variables
A <- Auto[, 1:8]
set.seed(1)
tr12 <- sample(1:nrow(A), nrow(A) / 2)
lm12 <- lm(mpg ~ ., A, subset = tr12)
set.seed(1); bag12 <- randomForest(mpg ~ ., A, subset = tr12, mtry = 7)
set.seed(1); rf12 <- randomForest(mpg ~ ., A, subset = tr12)
set.seed(1); gb12 <- gbm(mpg ~ ., data = A[tr12, ], distribution = "gaussian", n.trees = 2000,
                         interaction.depth = 2, shrinkage = 0.01)
set.seed(1); quiet(bt12 <- gbart(A[tr12, -1], A$mpg[tr12], x.test = A[-tr12, -1]))
ex12 <- c(lm = mse(predict(lm12, A[-tr12, ]), A$mpg[-tr12]), bagging = mse(predict(bag12, A[-tr12, ]), A$mpg[-tr12]),
          forest = mse(predict(rf12, A[-tr12, ]), A$mpg[-tr12]),
          boosting = mse(predict(gb12, A[-tr12, ], n.trees = 2000), A$mpg[-tr12]),
          BART = mse(bt12$yhat.test.mean, A$mpg[-tr12]))
print(round(ex12, 3))
keep("ex12", ex12)

# ================================================================== key numbers
flat <- unlist(lapply(names(key), function(k) {
  v <- key[[k]]; nm <- if (length(v) > 1) paste0(k, "_", seq_along(v)) else k
  setNames(as.numeric(v), nm)
}))
write.csv(data.frame(name = names(flat), value = sprintf("%.10g", flat)), "cache/ch08_lab_R.csv", row.names = FALSE)
cat("wrote", length(flat), "numbers to cache/ch08_lab_R.csv\n")
