We replicate one of the examples from The Elements of Statistical Learning (ESL) to illustrate the differences between the two simplest prediction methods for binary outcomes: linear regression and \(k\)-nearest neighbors (\(k\)-NN).

 

Simulation

 

Code

Set the simulation parameters:

p = 2;           ## No. of parameters
sigma = 1;       ## St. Dev for the Normals (common)
mu1 = c(1, 0);   ## Vector of means for the first Normal
mu0 = c(0, 1);   ## Vector of means for the second Normal

Generate \(n\) i.i.d. (independent and identically distributed) samples from each normal to form the training set:

  • rnorm(2*n*p) generates \(2np\) \(N(0,1)\) random variables.
  • matrix(rnorm(2*n*p), 2*n, p)*sigma generates a \(2n\times p\) matrix of two \(N(0, sigma^2)\) each of length \(2n\).
  • Adding matrix(rep(mu1, n), nrow=n,byrow=TRUE) to each column of the previous matrix shifts each of the columns to generate the Normals with means mu1 or mu0.
  • Note that both mu0, mu1 are 2-dimensional.
n = 100;

traindata = matrix(rnorm(2*n*p), 2*n, p)*sigma + 
            rbind(matrix(rep(mu1, n), nrow=n,byrow=TRUE), 
            matrix(rep(mu0, n), nrow=n, byrow=TRUE))

# dim(traindata)

Ytrain = factor(c(rep(1,n), rep(0,n))) # Generates the 0 / 1 labels.

Generate the test set in the same way:

N=10000;  

testdata = matrix(rnorm(2*N*p), 2*N, p)*sigma+ 
           rbind(matrix(rep(mu1, N), nrow=N,byrow=TRUE), 
           matrix(rep(mu0, N), nrow=N, byrow=TRUE))

Ytest = factor(c(rep(1,N), rep(0,N)))

 

Visualization of the Simulated Data

This section also serves as a short review of plotting in R.

We first visualize the training data. In the figure below, Class 1 points are shown in blue and Class 0 points in orange. The two class centers are marked, and a legend is provided.

 

Using the default R functions for plotting
## Create an empty plotting area: The axes are the two vectors of normals generated, 
## each one saved in a column of the `traindata` matrix.
## The following line creates an empty plot, since we used the option type="n"
## We do this so that we can color-code the data.
plot(traindata[,1], traindata[,2], type="n", xlab="", ylab="");

# Add the "Class 1" points - in blue color.
points(traindata[1:n, 1], traindata[1:n,2], pch=16, col="blue");

# Add the "Class 0" points - in orange color
points(traindata[(n+1):(2*n),1], traindata[(n+1):(2*n),2], pch=16, col="orange"); 

# Add the  centers for class 1
points(mu1[1], mu1[2], pch=13, cex=1.5, col="green");    

# Add the  centers for class 0
points(mu0[1], mu0[2], pch=13, cex=1.5, col="red");   

legend("bottomright", pch = c(16,16), col = c("blue", "orange"), 
       legend = c("Class 1", "Class 0"))

 

Using the ggplot2 R library

An equivalent plot can be produced with the ggplot2 package (more information at http://ggplot2.org/):

# install.package("ggplot2")
library("ggplot2")

## The input in a `ggplot` function can only be a data.frame

## In our case the data is a matrix, so we convert them to data.frames here:
mytraindata = data.frame(X1=traindata[,1], X2=traindata[,2], Y=Ytrain)

## The ggplot output is an object which is saved in training.scatter.
## In this object, we can later add --and plot-- additional features.

training.scatter = ggplot(mytraindata, aes(X1, X2)) +  ## creates the empty plot
        geom_point(aes(colour=Y), size=2) + ## adds the points color-coded by the labels in Y
        scale_color_manual(values = c("orange", "blue")) +  ## change the default colors
        ## Use geom_point to add the centers (as before)
        geom_point(data=data.frame(X1=mu1[1], X2=mu1[2]), aes(X1, X2), colour="green", shape=2,size=5) +
        geom_point(data=data.frame(X1=mu0[1], X2=mu0[2]), aes(X1, X2), colour="red", shape=2, size=5) +
        ggtitle("Simulated Training Data")  + ## add a title 
        labs(x = "", y="")  ## remove axes labels
  
plot(training.scatter)

 

\(k\)-Nearest Neighbors

We now apply \(k\)-nearest neighbors. The neighborhood sizes used below follow the values suggested in ESL. We also examine the two extreme cases \(k=1\) and \(k=15\).

library("class") 

neighbor_size = c(151, 101, 69,  45, 31, 21, 11, 7, 5, 3, 1); ## These are different k's to try.
m = length(neighbor_size);  ## needed to run our for-loop below.

train.err.knn = rep(0,m);   ## vector to store training error
test.err.knn = rep(0, m);   ## vector to store testing error

## knn is the R function that runs the kNN method. Output is a factor.

for( j in 1:m){
  Ytrain.pred = knn(traindata, traindata, Ytrain, k=neighbor_size[j])   ## predictions for training data
  train.err.knn[j]= sum(Ytrain != Ytrain.pred)/(2*n)     ## mis-classification training error
  Ytest.pred = knn(traindata, testdata, Ytrain,k=neighbor_size[j])      ## predictions for testing data
  test.err.knn[j] = sum(Ytest != Ytest.pred)/(2*N)       ## mis-classification testing error
}

cbind(train.err.knn, test.err.knn)    ## matrix containing the train and test errors
##       train.err.knn test.err.knn
##  [1,]         0.250      0.24265
##  [2,]         0.225      0.24180
##  [3,]         0.225      0.24485
##  [4,]         0.210      0.24635
##  [5,]         0.195      0.25420
##  [6,]         0.195      0.26125
##  [7,]         0.180      0.26795
##  [8,]         0.210      0.27755
##  [9,]         0.215      0.28080
## [10,]         0.175      0.28960
## [11,]         0.000      0.33505

 

Choosing \(k\) by 5-Fold Cross-Validation

A systematic way to select the neighborhood size \(k\) is 5-fold cross-validation. For each candidate \(k\) we compute the average prediction error across the five folds and choose the value that minimizes this CV error. In the code below the outer loop iterates over the five folds and the inner loop iterates over the candidate values of \(k\). In each iteration four folds are used for training and the remaining fold is used for evaluation.

## In this chunk of code, we use the same vector of k's as above - the neighbor_size vector of size m

## Initialize a vector cv.error to store the CV error for each k.
cv.error = rep(0,m);


id = sample(1:(2*n),(2*n), replace=FALSE);
fold = c(0,  40,  80, 120, 160, 200)

for(i in 1:5)
    for(j in 1:m){
      
      ## ith.fold = rows which are in the i-th fold
      ith.fold = id[(fold[i]+1):fold[i+1]];   
      tmp = knn(traindata[-ith.fold,], traindata[ith.fold,], Ytrain[-ith.fold], k=neighbor_size[j]);
      cv.error[j]=cv.error[j] + sum(tmp != Ytrain[ith.fold])
    }

## Find the optimal k value based 5-fold CV
k.optimal = neighbor_size[order(cv.error)[1]]  

## Error of KNN for the k is chosen by 5-fold CV
Ytrain.pred = knn(traindata, traindata, Ytrain, k=k.optimal)
train.err.knn.CV = sum(Ytrain != Ytrain.pred)/(2*n)
Ytest.pred = knn(traindata, testdata, Ytrain,k=k.optimal)
test.err.knn.CV = sum(Ytest != Ytest.pred)/(2*N)  

&nbsp

Linear Regression (Least Squares)

We fit a linear regression of the numeric response on the two features and convert the continuous fitted values into class predictions by the rule

\[\hat{Y} = \begin{cases} & 1, \text{ if } fitted(Y) > 0.5\\ & 0, \text{ if } fitted(Y) \leq 0.5 \end{cases} \]

 

## Run a regression using the lm function
## Ytrain is a factor, so we need to convert it to a numeric vector to run the lm
RegModel = lm(as.numeric(Ytrain)-1 ~ traindata)

## Compute the \hat{Y} for training 
Ytrain_pred_LS = as.numeric(RegModel$fitted > 0.5)

## Compute the predicted values for testing data and then the \hat{Y}
Ytest_pred_LS = RegModel$coef[1] + RegModel$coef[2] * testdata[,1] + RegModel$coef[3] * testdata[,2]
Ytest_pred_LS = as.numeric(Ytest_pred_LS > 0.5 )


## Cross-tab for training data and training error
table(Ytrain, Ytrain_pred_LS);   
##       Ytrain_pred_LS
## Ytrain  0  1
##      0 76 24
##      1 21 79
train.err.LS = sum(Ytrain !=  Ytrain_pred_LS) / (2*n);  

## Cross-tab for test data and test error
table(Ytest, Ytest_pred_LS);     
##      Ytest_pred_LS
## Ytest    0    1
##     0 7608 2392
##     1 2436 7564
test.err.LS = sum(Ytest !=  Ytest_pred_LS) / (2*N);

&nbsp

Illustration of the Results

We first display the decision boundaries produced by each method.

\(k\)-NN classification for \(k=15\) and \(k=1\)
## Grid Using kNN Classification: We first define the boundaries for the grid

x.min = round(min(mytraindata$X1), digits=1)-0.1
x.max = round(max(mytraindata$X1), digits=1)+0.1
y.min = round(min(mytraindata$X2), digits=1)-0.1
y.max = round(max(mytraindata$X2), digits=1)+0.1
x.range = seq(from=x.min, to=x.max, by=0.1)
y.range = seq(from=y.min, to=y.max, by=0.1)
x.new = expand.grid(x.range, y.range)
names(x.new) = names(mytraindata[,-3])

## Basic scatterplot (same as before): 
##   this is used as a base to add the boundary and shaded areas

grid.plot =  ggplot(mytraindata, aes(X1, X2)) +
            geom_point(aes(colour=Y), size=2) + 
            scale_color_manual(values = c("orange", "blue"))   +
            geom_point(data=data.frame(X1=mu1[1], X2=mu1[2]), aes(X1, X2), colour="red", shape=2,size=5) +
            geom_point(data=data.frame(X1=mu0[1], X2=mu0[2]), aes(X1, X2), colour="green", shape=2, size=5) +
            labs(x = "", y="")


## Plot for k=15

knn.yhat.15 = knn(traindata, x.new, Ytrain,  k=15) 
knn.pred.15 = ifelse(as.numeric(knn.yhat.15)>0.5,"1","0")

knn.plotdata.15 = as.data.frame(cbind(x.new, knn.yhat.15))


knn.plot.15 = grid.plot + 
            theme_bw() + #remove grey background
            geom_point(data=knn.plotdata.15, aes(x=X1, y=X2, colour=knn.yhat.15), size=0.05) +
            geom_contour(data=knn.plotdata.15, aes(x=X1, y=X2, z=as.numeric(knn.yhat.15)), bins=1, color="black")+
            ggtitle("kNN Classification for k=15") 

plot(knn.plot.15)

## Plot for k=1

knn.yhat.1 = knn(traindata, x.new, Ytrain,  k=1) 
knn.pred.1 = ifelse(as.numeric(knn.yhat.1)>0.5, "1", "0")

knn.plotdata.1 = as.data.frame(cbind(x.new, knn.yhat.1))


knn.plot.1 = grid.plot + 
            theme_bw() + 
            geom_point(data=knn.plotdata.1, aes(x=X1, y=X2, colour=knn.yhat.1), size=0.05) +
            geom_contour(data=knn.plotdata.1, aes(x=X1, y=X2, z=as.numeric(knn.yhat.1)), bins=1, color="black")+
            ggtitle("kNN Classification for k=1") 

plot(knn.plot.1)

 

Linear-regression classification

## Grid Using Linear Model Classification

RegModel = lm(as.numeric(Ytrain)-1 ~ traindata)
beta.hat = coef(RegModel)

## We use the same ranges for the grid as before

Reg.yhat = as.matrix(cbind(rep(1, nrow(x.new)), x.new)) %*% beta.hat   ## predicted Y values
Reg.pred = ifelse(Reg.yhat > 0.5, "1", "0")   ## convert numeric Y to factor

Reg.plot.data = cbind(x.new, Reg.pred)

## Basic plot is same as before, so now we add the regression boundary and classiffication results
reg.plot = grid.plot + 
  theme_bw() + 
  geom_abline(slope=-beta.hat[2]/beta.hat[3], intercept=(.5-beta.hat[1])/beta.hat[3],color="black")  +
  geom_point(data = Reg.plot.data, aes(x=X1, y=X2, color=Reg.pred), size=0.05) +
  ggtitle("Regression Classification")

plot(reg.plot)

 

Comparing Training and Test Performance

The figure below shows training error (blue) and test error (magenta) as functions of model complexity.

plot(c(0.5,m), range(test.err.LS, train.err.LS, test.err.knn, train.err.knn),
                  type="n", xlab="Degrees of Freedom", ylab="Error", xaxt="n")

df = round((2*n)/neighbor_size)
axis(1, at=1:m, labels=df)
axis(3, at=1:m, labels=neighbor_size)

points(1:m, test.err.knn, col="magenta", pch=16)
lines(1:m, test.err.knn, col="magenta", lty=1, lwd=2)
points(1:m, train.err.knn, col="blue", pch=16)
lines(1:m, train.err.knn, col="blue", lty=3, lwd=2)

points(3, train.err.LS, pch=2, cex=2, col="blue")
points(3, test.err.LS, pch=2, cex=2, col="magenta")

points((1:m)[neighbor_size == k.optimal], train.err.knn.CV, col="blue", pch=5, cex=2)
points((1:m)[neighbor_size == k.optimal], test.err.knn.CV, col="magenta", pch=5, cex=2)

legend("bottomleft", pch = c(2, 2, 5, 5, 16, 16),  col = c("blue", "magenta"), 
       legend = c("Regression Training Error", "Regression Testing Error", "kNN Optimal k Training Error", "kNN Optimal k Testing Error", "kNN different k Training Error", "kNN different k Testing Error"), cex=0.75)