SOCR ≫ DSPA ≫ DSPA3 Topics ≫ 

library(ggplot2)
library(dplyr)
library(tidyr)
library(patchwork)
library(plotly)      # interactive figures and ALL 3-D graphics
library(class)       # knn
library(caret)       # confusionMatrix, train, resampling
library(pROC)        # ROC / AUC

How this chapter uses graphics

Every two-dimensional figure is drawn with ggplot2 and rendered statically. Immediately after each one, the equivalent plot_ly() code appears in a chunk marked eval=FALSE, echo=TRUE, printed in these notes, ready to paste into a live session.

Every three-dimensional figure is drawn with plot_ly() and evaluated. That matters unusually much here: a classifier is a posterior probability surface over feature space, and the difference between \(k=1\) and \(k=100\), or between a single tree and a forest, is a difference in the roughness of that surface. A fixed projection hides exactly the property being taught.

0.1 Chapter 5 Live Webapps

The DSPA3 Labs include a number of interactive webapps, which are build as portable, self-contained, and browser accessible applications. These apps demonstrate various concepts discussed in this chapter, including

1 Learning objectives

After completing this chapter you will be able to:

  1. State the Bayes classifier and the Bayes error, and explain why every method in this chapter is an attempt to approximate them.
  2. Compute and interpret the full family of classification metrics — sensitivity, specificity, PPV, NPV, \(F_1\), \(\kappa\), MCC, AUC, Brier score — and choose the right one for a given cost structure.
  3. Compare any reported accuracy against the no-information rate before concluding that a model has learned anything.
  4. Identify the four kinds of data leakage and design a resampling protocol that avoids them.
  5. Derive the Cover–Hart bound \(R_{1\text{NN}}\le 2R_{\text{Bayes}}\) and explain what it says about simple methods.
  6. Analyze the bias–variance tradeoff governing \(k\) in kNN, and state how the optimal \(k\) scales with \(n\) and \(d\).
  7. State the naive Bayes conditional-independence assumption, explain why the classifier works despite its violation, and implement it in log space to avoid underflow.
  8. Derive Laplace smoothing as the posterior mean of a Dirichlet–multinomial model, and tune it by held-out log-loss.
  9. Compare entropy, Gini, and misclassification error as splitting criteria, and explain why the last is used for pruning but not for splitting.
  10. Explain how bagging reduces variance, why decorrelation matters, and what out-of-bag error estimates for free.

Estimated time: 10–13 hours including exercises. Prerequisites: Chapter 2 (contingency tables, class imbalance), Chapter 3 (trees, ensembles, complexity), and Chapter 4, in particular distance concentration (§4.3.1), which is the reason kNN degrades in high dimensions.

2 PART I: THE CLASSIFICATION PROBLEM

3 Supervised and unsupervised learning

Machine learning divides along whether the algorithm is shown the answers.

Supervised learning provides input variables \(X\) and an outcome \(Y\), and seeks a mapping \(\hat f: \mathcal{X}\to\mathcal{Y}\) that generalizes to unseen data. It is “supervised” because training labels correct the learner. When \(Y\) is quantitative the task is regression (Chapter 3); when \(Y\) is categorical it is classification, the subject of this chapter.

Unsupervised learning provides only \(X\) and asks the algorithm to find structure, groupings, associations, low-dimensional coordinates, with no correct answer to compare against. Clustering and association rule mining are the canonical problems (Chapter 8, Chapter 7).

The distinction is about supervision, not about the algorithms themselves. Gaussian mixtures cluster when labels are absent and classify when they are present; the same tree machinery does regression and classification.

A rough map of methods by outcome type. This is a starting point for choosing a method, not a decision rule – always check the data against each method’s assumptions.
Outcome type Supervised methods Unsupervised counterparts
Binary kNN, naive Bayes, logistic regression, LDA/QDA, decision trees, SVM, boosting k-means, Gaussian mixtures, spectral clustering
Multi-class kNN, naive Bayes, multinomial logistic, trees, random forest, neural networks Hierarchical clustering, DBSCAN, HDBSCAN
Ordinal Ordinal logistic, ordinal forests, cumulative-link models Ordinal MDS
Quantitative Linear regression, regression trees, random forest, BART, SVR PCA, factor analysis, autoencoders
None (structure) – Apriori / association rules, t-SNE, UMAP

4 What are we actually trying to compute?

Before any algorithm, there is a target. Without it, “this classifier is 72% accurate” has no reference point.

4.1 The Bayes classifier

Suppose \((X, Y)\) are drawn from a joint distribution with \(Y\in\{1,\dots,K\}\). Under 0–1 loss, every error costs the same, the expected loss of a classifier \(g\) is its misclassification rate

\[R(g)=P\big(g(X)\ne Y\big)=E_X\Big[1-P\big(Y=g(X)\mid X\big)\Big].\]

Minimizing pointwise gives the Bayes classifier

\[\boxed{\;g^{*}(x)=\arg\max_{k\in\{1,\dots,K\}} P(Y=k\mid X=x)\;}\]

and its risk is the Bayes error

\[R^{*}=E_X\Big[1-\max_k P(Y=k\mid X=x)\Big].\]

No classifier can do better than \(R^{*}\). The Bayes error is irreducible: it is the overlap between the classes in the true joint distribution, not a deficiency of any method. If two patients have identical measured features and different outcomes, no algorithm can separate them.

Every method in this chapter is a plug-in rule: estimate \(\hat P(Y=k\mid X=x)\) somehow, then take the argmax. They differ only in how they estimate the posterior.

Method How it estimates \(P(Y=k\mid x)\)
kNN Local vote fraction among the \(k\) nearest training points
Naive Bayes \(\propto \hat P(k)\prod_j \hat P(x_j\mid k)\), assuming conditional independence
LDA / QDA Gaussian class-conditionals with shared / separate covariance
Logistic regression Direct parametric model of the log-odds
Decision tree Class proportions in the leaf containing \(x\)
Random forest Average of many trees’ leaf proportions

4.2 Seeing the Bayes boundary

The Bayes error is normally unknowable, because the joint distribution is unknown. On simulated data we know it exactly, which makes simulation the only setting where “how close to optimal is this classifier?” has an answer.

# Two Gaussian classes with a KNOWN generating process
mu1 <- c(-1, -0.6); mu2 <- c(1.1, 0.7)
S1  <- matrix(c(1.0, 0.35, 0.35, 0.9), 2)
S2  <- matrix(c(1.2, -0.30, -0.30, 0.7), 2)
pi1 <- 0.45

# Posterior P(Y = 2 | x) from the true densities
post2 <- function(x1, x2) {
  z <- cbind(x1, x2)
  d1 <- mvtnorm::dmvnorm(z, mu1, S1)
  d2 <- mvtnorm::dmvnorm(z, mu2, S2)
  (1 - pi1) * d2 / (pi1 * d1 + (1 - pi1) * d2)
}

set.seed(21)
n_sim <- 1200
lab <- rbinom(n_sim, 1, 1 - pi1)                       # 0 -> class 1, 1 -> class 2
Xsim <- rbind(MASS::mvrnorm(sum(lab == 0), mu1, S1),
              MASS::mvrnorm(sum(lab == 1), mu2, S2))
ysim <- factor(c(rep("A", sum(lab == 0)), rep("B", sum(lab == 1))))
sim <- data.frame(x1 = Xsim[, 1], x2 = Xsim[, 2], y = ysim)

# Monte-Carlo estimate of the Bayes error
set.seed(22)
mc <- 2e5
lab_mc <- rbinom(mc, 1, 1 - pi1)
Xmc <- rbind(MASS::mvrnorm(sum(lab_mc == 0), mu1, S1),
             MASS::mvrnorm(sum(lab_mc == 1), mu2, S2))
p_mc <- post2(Xmc[, 1], Xmc[, 2])
bayes_error <- mean(1 - pmax(p_mc, 1 - p_mc))
c(bayes_error = round(bayes_error, 4))
#> bayes_error 
#>      0.1004
g1 <- seq(-4.5, 4.5, length.out = 220)
g2 <- seq(-4, 4, length.out = 220)
grid_df <- expand.grid(x1 = g1, x2 = g2)
grid_df$p <- post2(grid_df$x1, grid_df$x2)

ggplot(grid_df, aes(x1, x2)) +
  geom_raster(aes(fill = p)) +
  geom_contour(aes(z = p), breaks = 0.5, colour = "black", linewidth = 1) +
  geom_point(data = sim, aes(x1, x2, shape = y), size = 1.1, alpha = 0.55,
             colour = "grey15") +
  scale_fill_gradient2(low = "#3B7DD8", mid = "white", high = "#D8433B",
                       midpoint = 0.5, name = "P(Y = B | x)") +
  scale_shape_manual(values = c(A = 1, B = 3), name = "Class") +
  coord_fixed() +
  labs(title = "The Bayes-optimal decision boundary",
       subtitle = sprintf("Black contour is P = 0.5.  Bayes error = %.3f -- no classifier can beat this",
                          bayes_error),
       x = expression(x[1]), y = expression(x[2])) +
  theme_dspa()

Because the posterior is a surface over feature space, it is worth rotating:

Zp <- matrix(grid_df$p, nrow = length(g1))

plot_ly(x = g2, y = g1, z = Zp, type = "surface", colorscale = "RdBu",
        reversescale = TRUE, opacity = 0.92,
        colorbar = list(title = "P(Y=B|x)")) |>
  add_trace(x = sim$x2, y = sim$x1,
            z = post2(sim$x1, sim$x2),
            type = "scatter3d", mode = "markers", name = "Observations",
            marker = list(size = 1.8, opacity = 0.45, color = "black")) |>
  layout(title = "True posterior probability surface",
         scene = list(xaxis = list(title = "x2"), yaxis = list(title = "x1"),
                      zaxis = list(title = "P(Y = B | x)", range = c(0, 1))))