# Chapter 12 lab: Unsupervised Learning (R version)
# Course: Applied Statistical Learning in R and Python, which follows James, Witten, Hastie and
# Tibshirani (2021), An Introduction to Statistical Learning with Applications in R, 2nd edition,
# Section 12.5, and the Python edition of 2023 (with Taylor).
#
#   [1] the USArrests data;  [2] principal components with prcomp(): loadings, scores, biplot, PVE;
#   [3] matrix completion: the SVD and Algorithm 12.1 written out;  [4] K-means on simulated data;
#   [5] hierarchical clustering: linkages, cutting the tree, scaling, correlation-based distance;
#   [6] the NCI60 data: principal components;  [7] the NCI60 data: clustering the cell lines.
#   [E2]-[E13] the exercises that need a computer.
# The random seeds of [3]-[5] and [7] are those of the R edition, so the printed numbers can be
# compared with it. The Python version is ch12_lab.py; the two agree wherever the computation is
# deterministic (the notes list where and why they differ).
#
# Run: Rscript ch12_lab.R      (prints the results; writes the R plots to ../img/ch12/lab-r-*.pdf)
# The code is my own.

suppressPackageStartupMessages({
  library(ISLR2)    # NCI60 and Boston (USArrests is in base R)
})
.this_dir <- local({
  a <- grep("^--file=", commandArgs(FALSE), value = TRUE)
  if (length(a)) dirname(normalizePath(sub("^--file=", "", a[1]))) else getwd()
})
img_dir <- file.path(.this_dir, "..", "img", "ch12")
dir.create(img_dir, showWarnings = FALSE, recursive = TRUE)
step <- function(k, title) cat(sprintf("\n== [%s] %s\n", k, title))
options(width = 100, digits = 6)

# -- [1] The USArrests data: 50 states, arrests per 100,000 residents and percent urban population
step(1, "The USArrests data")
states <- row.names(USArrests)
head(states, 4)
names(USArrests)
apply(USArrests, 2, mean)
apply(USArrests, 2, var)

# -- [2] Principal components with prcomp(): centre and scale the columns first
step(2, "Principal components")
pr.out <- prcomp(USArrests, scale = TRUE)
names(pr.out)
pr.out$center
pr.out$scale
pr.out$rotation                       # the loading vectors phi_1, ..., phi_4 (columns)
dim(pr.out$x)                         # the score vectors z_1, ..., z_4 (columns)
pr.out$rotation <- -pr.out$rotation   # flip both signs to get the orientation of Figure 12.1
pr.out$x <- -pr.out$x
pdf(file.path(img_dir, "lab-r-biplot.pdf"), width = 6, height = 6)
biplot(pr.out, scale = 0, cex = 0.6)
invisible(dev.off())
pr.out$sdev
pr.var <- pr.out$sdev^2
pve <- pr.var / sum(pr.var)
pve
pdf(file.path(img_dir, "lab-r-pve.pdf"), width = 8, height = 3.8)
par(mfrow = c(1, 2))
plot(pve, xlab = "Principal Component", ylab = "Proportion of Variance Explained",
     ylim = c(0, 1), type = "b")
plot(cumsum(pve), xlab = "Principal Component", ylab = "Cumulative Proportion of Variance Explained",
     ylim = c(0, 1), type = "b")
invisible(dev.off())

# -- [3] Matrix completion: the SVD, then Algorithm 12.1 by hand
step(3, "Matrix completion")
X <- data.matrix(scale(USArrests))
pcob <- prcomp(X)
summary(pcob)
sX <- svd(X)                           # X = U diag(d) V^T
round(sX$v, 3)                         # = the loadings, up to sign
max(abs(abs(sX$u %*% diag(sX$d)) - abs(pcob$x)))   # U d = the scores, up to sign
nomit <- 20
set.seed(15)
ina <- sample(seq(50), nomit)          # 20 states ...
inb <- sample(1:4, nomit, replace = TRUE)          # ... and one variable in each
ina
inb
Xna <- X
index.na <- cbind(ina, inb)
Xna[index.na] <- NA
fit.svd <- function(X, M = 1) {        # the best rank-M approximation of X
  s <- svd(X)
  s$u[, 1:M, drop = FALSE] %*% (s$d[1:M] * t(s$v[, 1:M, drop = FALSE]))
}
Xhat <- Xna                            # step 1: fill in the column means
xbar <- colMeans(Xna, na.rm = TRUE)
Xhat[index.na] <- xbar[inb]
thresh <- 1e-7
rel_err <- 1
iter <- 0
ismiss <- is.na(Xna)
mssold <- mean((scale(Xna, xbar, FALSE)[!ismiss])^2)
mss0 <- mean(Xna[!ismiss]^2)
while (rel_err > thresh) {
  iter <- iter + 1
  Xapp <- fit.svd(Xhat, M = 1)         # step 2(a)
  Xhat[ismiss] <- Xapp[ismiss]         # step 2(b)
  mss <- mean(((Xna - Xapp)[!ismiss])^2)              # step 2(c): (12.14) / |O|
  rel_err <- (mssold - mss) / mss0
  mssold <- mss
  cat("Iter:", iter, "MSS:", format(mss, digits = 6), "Rel. Err:", format(rel_err, digits = 4), "\n")
}
cor(Xapp[ismiss], X[ismiss])

# -- [4] K-means clustering of simulated data with two groups
step(4, "K-means clustering")
set.seed(2)
x <- matrix(rnorm(50 * 2), ncol = 2)
x[1:25, 1] <- x[1:25, 1] + 3
x[1:25, 2] <- x[1:25, 2] - 4
km.out <- kmeans(x, 2, nstart = 20)
km.out$cluster
pdf(file.path(img_dir, "lab-r-kmeans.pdf"), width = 8, height = 4)
par(mfrow = c(1, 2))
plot(x, col = (km.out$cluster + 1), main = "K-Means Clustering Results with K = 2",
     xlab = "", ylab = "", pch = 20, cex = 2)
set.seed(4)
km.out <- kmeans(x, 3, nstart = 20)
plot(x, col = (km.out$cluster + 1), main = "K-Means Clustering Results with K = 3",
     xlab = "", ylab = "", pch = 20, cex = 2)
invisible(dev.off())
km.out$size
km.out$centers
km.out$withinss
km.out$betweenss / km.out$totss
set.seed(4)
km.out <- kmeans(x, 3, nstart = 1)
km.out$tot.withinss
km.out <- kmeans(x, 3, nstart = 20)
km.out$tot.withinss
2 * km.out$tot.withinss                # the objective (12.17) is twice tot.withinss

# -- [5] Hierarchical clustering: three linkages, cutting the tree, scaling, correlation distance
step(5, "Hierarchical clustering")
hc.complete <- hclust(dist(x), method = "complete")
hc.average <- hclust(dist(x), method = "average")
hc.single <- hclust(dist(x), method = "single")
pdf(file.path(img_dir, "lab-r-hclust.pdf"), width = 10, height = 4)
par(mfrow = c(1, 3))
plot(hc.complete, main = "Complete Linkage", xlab = "", sub = "", cex = .7)
plot(hc.average, main = "Average Linkage", xlab = "", sub = "", cex = .7)
plot(hc.single, main = "Single Linkage", xlab = "", sub = "", cex = .7)
invisible(dev.off())
cutree(hc.complete, 2)
cutree(hc.average, 2)
cutree(hc.single, 2)
cutree(hc.single, 4)
round(tail(hc.complete$height, 4), 4)  # the last fusion heights
xsc <- scale(x)
table(cutree(hclust(dist(xsc), method = "complete"), 2), cutree(hc.complete, 2))
x <- matrix(rnorm(30 * 3), ncol = 3)   # 30 observations, 3 features, no true clusters
dd <- as.dist(1 - cor(t(x)))           # correlation between observations, not variables
hc.cor <- hclust(dd, method = "complete")
round(tail(hc.cor$height, 3), 4)

# -- [6] The NCI60 data: principal components of 64 cell lines x 6830 genes
step(6, "NCI60: principal components")
nci.labs <- NCI60$labs
nci.data <- NCI60$data
dim(nci.data)
nci.labs[1:4]
table(nci.labs)
pr.out <- prcomp(nci.data, scale = TRUE)
round(pr.out$x[1:3, 1:3], 4)
Cols <- function(vec) {
  cols <- rainbow(length(unique(vec)))
  cols[as.numeric(as.factor(vec))]
}
pdf(file.path(img_dir, "lab-r-nci-pcs.pdf"), width = 8, height = 4)
par(mfrow = c(1, 2))
plot(pr.out$x[, 1:2], col = Cols(nci.labs), pch = 19, xlab = "Z1", ylab = "Z2")
plot(pr.out$x[, c(1, 3)], col = Cols(nci.labs), pch = 19, xlab = "Z1", ylab = "Z3")
invisible(dev.off())
summary(pr.out)$importance[, 1:6]
pve <- 100 * pr.out$sdev^2 / sum(pr.out$sdev^2)
round(cumsum(pve)[c(5, 7, 10, 20, 63, 64)], 4)

# -- [7] Clustering the NCI60 cell lines
step(7, "NCI60: clustering")
sd.data <- scale(nci.data)
data.dist <- dist(sd.data)
pdf(file.path(img_dir, "lab-r-nci-hclust.pdf"), width = 10, height = 12)
par(mfrow = c(3, 1))
plot(hclust(data.dist), xlab = "", sub = "", ylab = "", labels = nci.labs, main = "Complete Linkage",
     cex = 0.6)
plot(hclust(data.dist, method = "average"), labels = nci.labs, main = "Average Linkage",
     xlab = "", sub = "", ylab = "", cex = 0.6)
plot(hclust(data.dist, method = "single"), labels = nci.labs, main = "Single Linkage",
     xlab = "", sub = "", ylab = "", cex = 0.6)
invisible(dev.off())
hc.out <- hclust(dist(sd.data))
hc.clusters <- cutree(hc.out, 4)
table(hc.clusters, nci.labs)[, c("BREAST", "CNS", "COLON", "LEUKEMIA", "MELANOMA", "NSCLC",
                                 "OVARIAN", "RENAL")]
round(tail(hc.out$height, 4), 2)       # four clusters for any cut between 137.56 and 141.25
pdf(file.path(img_dir, "lab-r-nci-cut.pdf"), width = 10, height = 5)
plot(hc.out, labels = nci.labs, cex = 0.55, xlab = "", sub = "")
abline(h = 139, col = "red")
invisible(dev.off())
hc.out
set.seed(2)
km.out <- kmeans(sd.data, 4, nstart = 20)
km.clusters <- km.out$cluster
table(km.clusters, hc.clusters)
km.out$tot.withinss
hc.pc <- hclust(dist(pr.out$x[, 1:5]))
table(cutree(hc.pc, 4), nci.labs)[, c("BREAST", "CNS", "COLON", "LEUKEMIA", "MELANOMA", "NSCLC",
                                      "OVARIAN", "RENAL")]

# ===================================================================== exercises
# A deterministic stand-in for random numbers, so that R and Python use the same "random" data:
# u = fractional part of |sin(12.9898 i + 78.233 j + 37.719 s)| x 43758.5453.
hash_u <- function(i, j, s = 0) {
  v <- abs(sin(12.9898 * i + 78.233 * j + 37.719 * s)) * 43758.5453
  pmin(pmax(v - floor(v), 1e-12), 1 - 1e-12)
}

# -- [E2] Exercise 2: complete and single linkage from a dissimilarity matrix
step("E2", "Exercise 2")
D2 <- as.dist(matrix(c(0, 0.3, 0.4, 0.7, 0.3, 0, 0.5, 0.8, 0.4, 0.5, 0, 0.45, 0.7, 0.8, 0.45, 0), 4))
hc2c <- hclust(D2, method = "complete")
hc2s <- hclust(D2, method = "single")
hc2c$merge; hc2c$height
hc2s$merge; hc2s$height
cutree(hc2c, 2)
cutree(hc2s, 2)

# -- [E3] Exercise 3: K-means by hand, K = 2, from a fixed starting assignment
step("E3", "Exercise 3")
x3 <- cbind(c(1, 1, 0, 5, 6, 4), c(4, 3, 4, 1, 2, 0))
lab <- c(1, 2, 1, 2, 1, 2)             # observations 1, 3, 5 start in cluster 1
repeat {
  cent <- rbind(colMeans(x3[lab == 1, , drop = FALSE]), colMeans(x3[lab == 2, , drop = FALSE]))
  print(cent)
  d1 <- rowSums(sweep(x3, 2, cent[1, ])^2)
  d2 <- rowSums(sweep(x3, 2, cent[2, ])^2)
  new <- ifelse(d1 <= d2, 1, 2)
  print(new)
  if (all(new == lab)) break
  lab <- new
}

# -- [E7] Exercise 7: correlation-based against squared Euclidean distance
step("E7", "Exercise 7")
xs <- t(scale(t(as.matrix(USArrests))))   # each STATE centred and scaled across its 4 values
d7 <- as.matrix(dist(xs))^2
r7 <- cor(t(xs))
ratio <- d7[upper.tri(d7)] / (1 - r7[upper.tri(r7)])
summary(ratio)                          # constant 2 (p - 1) = 6
xc <- scale(USArrests)                  # columns scaled only: not proportional
dc <- as.matrix(dist(xc))^2
rc <- cor(t(xc))
summary(dc[upper.tri(dc)] / (1 - rc[upper.tri(rc)]))

# -- [E8] Exercise 8: the PVE from sdev and directly from (12.10)
step("E8", "Exercise 8")
pr8 <- prcomp(USArrests, scale = TRUE)
pve.a <- pr8$sdev^2 / sum(pr8$sdev^2)
Xs <- scale(USArrests)
pve.b <- colSums((Xs %*% pr8$rotation)^2) / sum(Xs^2)
rbind(pve.a, pve.b)

# -- [E9] Exercise 9: hierarchical clustering of the states, unscaled and scaled
step("E9", "Exercise 9")
hc9 <- hclust(dist(USArrests), method = "complete")
c9 <- cutree(hc9, 3)
split(state.abb, c9)
hc9s <- hclust(dist(scale(USArrests)), method = "complete")
c9s <- cutree(hc9s, 3)
table(unscaled = c9, scaled = c9s)
round(sapply(split(as.data.frame(USArrests), c9), colMeans), 1)

# -- [E10] Exercise 10: three simulated classes, PCA and K-means
step("E10", "Exercise 10")
I10 <- matrix(rep(1:60, 50), 60)
J10 <- matrix(rep(1:50, each = 60), 60)
x10 <- qnorm(hash_u(I10, J10, 10))      # 60 x 50 "standard normal" values
cls <- rep(1:3, each = 20)
x10[cls == 2, 1:25] <- x10[cls == 2, 1:25] + 1.2    # class 2 shifted up on the first 25 variables
x10[cls == 3, 26:50] <- x10[cls == 3, 26:50] - 1.2  # class 3 shifted down on the last 25
pr10 <- prcomp(x10)
round(summary(pr10)$importance[2, 1:3], 4)
pdf(file.path(img_dir, "lab-r-ex10.pdf"), width = 4.5, height = 4.2)
plot(pr10$x[, 1:2], col = cls + 1, pch = 19, xlab = "Z1", ylab = "Z2")
invisible(dev.off())
set.seed(10)
table(cls, kmeans(x10, 3, nstart = 20)$cluster)
table(cls, kmeans(x10, 2, nstart = 20)$cluster)
table(cls, kmeans(x10, 4, nstart = 20)$cluster)
table(cls, kmeans(pr10$x[, 1:2], 3, nstart = 20)$cluster)
table(cls, kmeans(scale(x10), 3, nstart = 20)$cluster)

# -- [E11] Exercise 11: a matrix completion function, tested on the Boston data
step("E11", "Exercise 11")
mat_complete <- function(Xna, M = 1, thresh = 1e-7, maxit = 500, verbose = FALSE) {
  ismiss <- is.na(Xna)
  xbar <- colMeans(Xna, na.rm = TRUE)
  Xhat <- Xna
  Xhat[ismiss] <- matrix(xbar, nrow(Xna), ncol(Xna), byrow = TRUE)[ismiss]
  mss0 <- mean(Xna[!ismiss]^2)
  mssold <- mean((scale(Xna, xbar, FALSE)[!ismiss])^2)
  rel_err <- 1
  iter <- 0
  while (rel_err > thresh && iter < maxit) {
    iter <- iter + 1
    Xapp <- fit.svd(Xhat, M)
    Xhat[ismiss] <- Xapp[ismiss]
    mss <- mean(((Xna - Xapp)[!ismiss])^2)
    rel_err <- (mssold - mss) / mss0
    mssold <- mss
    if (verbose) cat("Iter:", iter, "MSS:", mss, "Rel. Err:", rel_err, "\n")
  }
  list(Xhat = Xhat, iter = iter, mss = mss)
}
XB <- scale(as.matrix(Boston))
N <- length(XB)
fracs <- seq(0.05, 0.30, by = 0.05)
err <- array(0, c(10, length(fracs), 8))
for (r in 1:10) {
  ord <- order(hash_u(seq_len(N), 0, 100 + r))   # a fixed random order of the entries; nested sets
  for (a in seq_along(fracs)) {
    miss <- ord[seq_len(round(fracs[a] * N))]
    Xna <- XB
    Xna[miss] <- NA
    for (M in 1:8) {
      fit <- mat_complete(Xna, M)
      err[r, a, M] <- mean((fit$Xhat[miss] - XB[miss])^2)
    }
  }
}
E11 <- apply(err, c(2, 3), mean)
dimnames(E11) <- list(paste0(100 * fracs, "%"), paste0("M=", 1:8))
round(E11, 3)

# -- [E12] Exercise 12: Algorithm 12.1 with prcomp() in place of svd()
step("E12", "Exercise 12")
fit.pca <- function(X, M = 1, center = FALSE) {
  p <- prcomp(X, center = center, scale. = FALSE)
  app <- p$x[, 1:M, drop = FALSE] %*% t(p$rotation[, 1:M, drop = FALSE])
  if (center) sweep(app, 2, p$center, "+") else app
}
impute_with <- function(fitfun, Xna, M = 1) {
  ismiss <- is.na(Xna)
  xbar <- colMeans(Xna, na.rm = TRUE)
  Xhat <- Xna
  Xhat[ismiss] <- matrix(xbar, nrow(Xna), ncol(Xna), byrow = TRUE)[ismiss]
  mss0 <- mean(Xna[!ismiss]^2)
  mssold <- mean((scale(Xna, xbar, FALSE)[!ismiss])^2)
  rel_err <- 1
  while (rel_err > 1e-7) {
    Xapp <- fitfun(Xhat, M)
    Xhat[ismiss] <- Xapp[ismiss]
    mss <- mean(((Xna - Xapp)[!ismiss])^2)
    rel_err <- (mssold - mss) / mss0
    mssold <- mss
  }
  Xhat
}
Xna <- X
Xna[index.na] <- NA
c(svd = cor(impute_with(fit.svd, Xna)[ismiss], X[ismiss]),
  prcomp = cor(impute_with(function(X, M) fit.pca(X, M), Xna)[ismiss], X[ismiss]),
  prcomp.centred = cor(impute_with(function(X, M) fit.pca(X, M, TRUE), Xna)[ismiss], X[ismiss]))

# -- [E13] Exercise 13: gene expression of 40 tissue samples (20 healthy, 20 diseased)
step("E13", "Exercise 13")
g13 <- read.csv(file.path(.this_dir, "isl-data", "Ch12Ex13.csv"), header = FALSE)
dim(g13)                               # 1000 genes (rows) x 40 samples (columns)
dcor <- as.dist(1 - cor(g13))          # correlation between samples
grp <- rep(1:2, each = 20)
for (m in c("complete", "average", "single")) {
  cat(m, ":", cutree(hclust(dcor, method = m), 2), "\n")
}
tt <- apply(g13, 1, function(g) t.test(g[1:20], g[21:40])$statistic)
pv <- apply(g13, 1, function(g) t.test(g[1:20], g[21:40])$p.value)
sum(pv < 0.05 / 1000)                  # genes significant after a Bonferroni correction
head(order(-abs(tt)), 10)              # the ten genes with the largest |t|
range(which(pv < 0.05 / 1000))
