Â
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).
Â
0 and
1.Â
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\).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.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)))
Â
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.
Â
## 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"))
Â
ggplot2 R libraryAn 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)
Â
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
Â
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)
 
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);
 
We first display the decision boundaries produced by each method.
## 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)
Â
## 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)
Â
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)