Skip to main content

K-Nearest Neighbors

On this page

• K-nearest neighbors
• Tuning $k$
• The bias-variance trade-off
• KNN for classification
• Example: Artificial data
• Tuning with the caret package
• Distance measures
• Computational issues
• Different KNN functions

← Week 5 overview · Previous: Lasso and Sparsity · Next: The Curse of Dimensionality

K-nearest neighbors

K-nearest neighbors (KNN) is a simple nonparametric method for both regression and classification. In a linear model, we estimate a coefficient vector $\boldsymbol\beta$ and predict at a target $\mathbf x_0$ using $\mathbf x_0^{\mathsf T}\widehat{\boldsymbol\beta}$. KNN instead estimates the function value directly from nearby observations. For regression, it averages their responses.

Suppose we observe $\{(\mathbf x_i,y_i)\}_{i=1}^n$, where $\mathbf x_i$ contains $p$ predictors. The KNN estimate at a target $\mathbf x_0$ is

$$\widehat f(\mathbf x_0)=\frac{1}{k}\sum_{i:\,\mathbf x_i\in N_k(\mathbf x_0)}y_i,$$

where $N_k(\mathbf x_0)$ contains the $k$ closest training observations. We start with ordinary Euclidean distance. Here, $p$ counts the coordinates used to measure distance; we do not add an intercept column.

The following one-predictor example uses $f(x)=2\sin(x)$ with independent normal errors of variance one. With $k=1$, the prediction at each location is the response of its nearest training observation. The object test.x is a grid of evaluation locations; we have not yet generated test outcomes there.

The R and Python simulations use the same model and settings. Their random draws differ because the languages use different random-number generators. Run the code blocks in your chosen language in order.

R

    # generate training data with 2*sin(x) and random Gaussian errors
    set.seed(1)
    x <- runif(15, 0, 2*pi)
    y <- 2*sin(x) + rnorm(length(x))

    # generate testing data points where we evaluate the prediction function
    test.x = seq(0, 1, 0.001)*2*pi

    # "1-nearest neighbor" regression using kknn package
    library(kknn)
    knn.fit = kknn(y ~ ., train = data.frame(x = x, y = y),
                   test = data.frame(x = test.x),
                   k = 1, kernel = "rectangular")
    test.pred = knn.fit$fitted.values

    # plot the data
    par(mar=rep(2,4))
    plot(x, y, xlim = c(0, 2*pi), pch = "o", cex = 2,
         xlab = "", ylab = "", cex.lab = 1.5)
    title(main="1-Nearest Neighbor Regression", cex.main = 1.5)

    # plot the true regression line
    lines(test.x, 2*sin(test.x), col = "deepskyblue", lwd = 3)

    # plot the fitted line
    lines(test.x, test.pred, type = "s", col = "darkorange", lwd = 3)
    legend("topright", c("Fitted line", "True function"),
           col = c("darkorange", "deepskyblue"), lty = 1, cex = 1.5)

Python

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsRegressor

# Generate training data with 2*sin(x) and random Gaussian errors.
np.random.seed(1)
x = np.random.uniform(0, 2 * np.pi, 15)
y = 2 * np.sin(x) + np.random.normal(size=len(x))

# Generate the locations where we evaluate the prediction function.
test_x = np.linspace(0, 2 * np.pi, 1001)
knn_fit = KNeighborsRegressor(n_neighbors=1, weights="uniform")
knn_fit.fit(x.reshape(-1, 1), y)
test_pred = knn_fit.predict(test_x.reshape(-1, 1))

plt.figure(figsize=(9, 6))
plt.scatter(x, y, facecolors="none", edgecolors="black", s=80)
plt.plot(test_x, 2 * np.sin(test_x), color="deepskyblue", linewidth=3,
         label="True function")
plt.step(test_x, test_pred, where="post", color="darkorange", linewidth=3,
         label="Fitted line")
plt.xlim(0, 2 * np.pi)
plt.title("1-Nearest Neighbor Regression")
plt.legend(loc="upper right")
plt.show()

Tuning $k$

The number of neighbors controls how local the average is. Let us generate 200 observations from the same sine model. Even with more data, the 1NN fitted line is very jumpy because each prediction uses just one noisy response.

We now generate independent test outcomes, test.y, at the grid locations. The training data and test outcomes will stay the same as we compare different values of $k$.

R

  # generate more data
  set.seed(1)
  n = 200
  x <- runif(n, 0, 2*pi)
  y <- 2*sin(x) + rnorm(length(x))

  test.y = 2*sin(test.x) + rnorm(length(test.x))

  # 1-nearest neighbor
  knn.fit = kknn(y ~ ., train = data.frame("x" = x, "y" = y),
                 test = data.frame("x" = test.x),
                 k = 1, kernel = "rectangular")
  test.pred = knn.fit$fitted.values

  par(mar=rep(2,4))
  plot(x, y, pch = 19, cex = 1,
       xlim = c(0, 2*pi), ylim = c(-4.25, 4.25))
  title(main="1-Nearest Neighbor Regression", cex.main = 1.5)
  lines(test.x, 2*sin(test.x), col = "deepskyblue", lwd = 3)
  lines(test.x, test.pred, type = "s", col = "darkorange", lwd = 3)
  legend("topright", c("Fitted line", "True function"),
         col = c("darkorange", "deepskyblue"), lty = 1, cex = 1.5)

Python

# Generate more data.
np.random.seed(1)
n = 200
x = np.random.uniform(0, 2 * np.pi, n)
y = 2 * np.sin(x) + np.random.normal(size=len(x))
test_y = 2 * np.sin(test_x) + np.random.normal(size=len(test_x))

knn_fit = KNeighborsRegressor(n_neighbors=1, weights="uniform")
knn_fit.fit(x.reshape(-1, 1), y)
test_pred = knn_fit.predict(test_x.reshape(-1, 1))

plt.figure(figsize=(9, 6))
plt.scatter(x, y, color="black", s=20)
plt.plot(test_x, 2 * np.sin(test_x), color="deepskyblue", linewidth=3,
         label="True function")
plt.step(test_x, test_pred, where="post", color="darkorange", linewidth=3,
         label="Fitted line")
plt.xlim(0, 2 * np.pi)
plt.ylim(-4.25, 4.25)
plt.xlabel("x")
plt.ylabel("y")
plt.title("1-Nearest Neighbor Regression")
plt.legend(loc="upper right")
plt.show()

We can evaluate the observed prediction error on these independent outcomes:

R

  # prediction error
  mean((test.pred - test.y)^2)

[1] 2.097488

Python

np.mean((test_pred - test_y) ** 2)

np.float64(2.1632998751292227)

Next, compare $k=1,5,10,33,66,100$. Each panel uses the same training observations and the same blue true function. The printed errors compare predictions with the same realized test outcomes. They are not expectations over repeated datasets.

R

  par(mfrow=c(2,3))
  par(mar=rep(2,4))

  for (k in c(1, 5, 10, 33, 66, 100))
  {
      knn.fit = kknn(y ~ ., train = data.frame("x" = x, "y" = y),
                     test = data.frame("x" = test.x),
                     k = k, kernel = "rectangular")
      test.pred = knn.fit$fitted.values
      cat(paste("Prediction Error for K =", k, ":", mean((test.pred - test.y)^2)))

      plot(x, y, xlim = c(0, 2*pi), pch = 19, cex = 0.7,
           axes=FALSE, ylim = c(-4.25, 4.25))
      title(main=paste("K =", k))
      lines(test.x, 2*sin(test.x), col = "deepskyblue", lwd = 3)
      lines(test.x, test.pred, type = "s", col = "darkorange", lwd = 3)
      box()
  }

Prediction Error for K = 1 : 2.09748780881932

Prediction Error for K = 5 : 1.39071867992277

Prediction Error for K = 10 : 1.24696415340282

Prediction Error for K = 33 : 1.21589627474692

Prediction Error for K = 66 : 1.37604707375972

Prediction Error for K = 100 : 1.42868908518756

Python

plt.figure(figsize=(12, 6))
for l, k in enumerate([1, 5, 10, 33, 66, 100], start=1):
    knn_fit = KNeighborsRegressor(n_neighbors=k, weights="uniform")
    knn_fit.fit(x.reshape(-1, 1), y)
    test_pred = knn_fit.predict(test_x.reshape(-1, 1))
    print("Prediction Error for K =", k, ":", np.mean((test_pred - test_y) ** 2))

    plt.subplot(2, 3, l)
    plt.scatter(x, y, color="black", s=10)
    plt.plot(test_x, 2 * np.sin(test_x), color="deepskyblue", linewidth=3)
    plt.step(test_x, test_pred, where="post", color="darkorange", linewidth=3)
    plt.xlim(0, 2 * np.pi)
    plt.ylim(-4.25, 4.25)
    plt.xticks([])
    plt.yticks([])
    plt.title(f"K = {k}")

Prediction Error for K = 1 : 2.1632998751292227
Prediction Error for K = 5 : 1.216483355797572
Prediction Error for K = 10 : 1.102826116995153
Prediction Error for K = 33 : 1.0291066603340622
Prediction Error for K = 66 : 1.170161289432704
Prediction Error for K = 100 : 1.3013185135794527

plt.tight_layout()
plt.show()

Larger neighborhoods average more noise, making the fitted function more stable. They also reach farther from the target, which can hide local features of the sine curve. Smaller neighborhoods retain those features but are more sensitive to the noise. This is the bias-variance trade-off. Because we are using these errors to compare choices of $k$, they serve a tuning role here. We will return to cross-validation below.

The bias-variance trade-off

At a fixed target $x_0$, let $Y=f(x_0)+\varepsilon$ be a new response, with mean-zero noise independent of the training data and variance $\sigma^2$. To connect directly to the neighbor average, hold the training covariates fixed and take expectations over the training responses and the new response.

Add and subtract $f(x_0)$ and $E[\widehat f(x_0)]$:

$$\begin{aligned} E\big[(Y-\widehat f(x_0))^2\big] &=E\Big[\big\{ Y-f(x_0)+f(x_0)-E[\widehat f(x_0)]\\ &\hspace{6em}+E[\widehat f(x_0)]-\widehat f(x_0) \big\}^2\Big]\\ &=E\big[(Y-f(x_0))^2\big] +\big(f(x_0)-E[\widehat f(x_0)]\big)^2\\ &\quad+E\Big[\big(E[\widehat f(x_0)]-\widehat f(x_0)\big)^2\Big] +\text{cross terms}\\ &=\underbrace{\sigma^2}_{\text{irreducible error}} +\underbrace{\big(f(x_0)-E[\widehat f(x_0)]\big)^2}_{\text{bias squared}} +\underbrace{\operatorname{Var}(\widehat f(x_0))}_{\text{variance}}. \end{aligned}$$

The cross terms have expectation zero: the new noise is independent of the fitted value and has mean zero, and the centered fitted value also has mean zero.

In the sine example, the irreducible error is one. With fixed training covariates and independent training errors of variance one, the variance of an average of $k$ neighbor responses is $1/k$.

• When $k=1$, that variance is one. With 200 observations and a smooth true function, the nearest point is usually close enough that its mean response is close to $f(x_0)$. The squared bias is then small, so the expected prediction error is close to $1+1=2$. An observed test error need not equal two.
• When $k=n$, every prediction is the overall response average. Its variance is $1/n$, but its bias is the difference between the average of the training-point means and $2\sin(x_0)$. This can be large where the sine curve is far from that overall average.

Typically, increasing $k$ reduces variance while increasing bias from averaging over a wider region. Decreasing $k$ has the opposite effect. The bias need not change monotonically at every target, and one observed error curve need not form a perfect U.

KNN for classification

Classification uses the same neighbor search as regression. The difference is how we combine the neighbors’ responses: we take a majority vote, choosing the most common class label, instead of averaging numerical responses. For 1NN, the prediction is simply the class of the closest observation.

The left panel shows 20 random observations in $[0,1]^2$ with binary labels. The red cross marks the target $(0.7,0.7)$. The right panel shows a Voronoi tessellation: every location in a cell has the same closest training observation and therefore the same 1NN prediction. The circle in the left panel marks a neighborhood around the target for illustration; the rule itself selects the nearest observation.

R

  # knn for classification:
  library(class)
  par(mfrow=c(1,2))
  par(mar=rep(2,4))

  # generate 20 random observations, with random class 1/0
  set.seed(1)
  x <- matrix(runif(40), 20, 2)
  g <- rbinom(20, 1, 0.5)

  # plot the data
  plot(x, col=ifelse(g==1, "darkorange", "deepskyblue"), pch = 19,
       cex = 3, xlim= c(0, 1), ylim = c(0, 1))
  symbols(0.7, 0.7, circles = 0.12, add = TRUE, inches = FALSE)
  points(0.7, 0.7, pch = 4, lwd = 2, col = "red")

  # generate a grid for plot
  xgd1 = xgd2 = seq(0, 1, 0.01)
  gd = expand.grid(xgd1, xgd2)

  # fit a 1-nearest neighbor model and get the fitted class
  knn1 <- knn(x, gd, g, k=1)
  knn1.class <- matrix(knn1, length(xgd1), length(xgd2))

  # Voronoi tessalation plot (1NN)
  library(deldir)
  z <- deldir(x = data.frame(x = x[,1], y = x[,2], z=as.factor(g)),
              rw = c(0, 1, 0, 1))
  w <- tile.list(z)

  plot(w, fillcol=ifelse(g==1, "bisque", "cadetblue1"))
  points(x, col=ifelse(g==1, "darkorange", "deepskyblue"), pch = 19, cex = 3)
  points(0.7, 0.7, pch = 4, lwd = 2, col = "red")

Python

from sklearn.neighbors import KNeighborsClassifier
from scipy.spatial import Voronoi, voronoi_plot_2d
from matplotlib.colors import ListedColormap
from matplotlib.patches import Circle

# Generate 20 random observations, with random class 1/0.
np.random.seed(1)
x = np.random.uniform(size=(20, 2))
g = np.random.binomial(1, 0.5, size=20)

fig, axes = plt.subplots(1, 2, figsize=(12, 6))
axes[0].scatter(x[:, 0], x[:, 1],
                c=np.where(g == 1, "darkorange", "deepskyblue"), s=100)
axes[0].add_patch(Circle((0.7, 0.7), 0.12, fill=False))
axes[0].scatter(0.7, 0.7, marker="x", color="red", s=80)

# Generate a grid and predict the class using one nearest neighbor.
xgd1 = xgd2 = np.linspace(0, 1, 101)
gd1, gd2 = np.meshgrid(xgd1, xgd2)
gd = np.column_stack((gd1.ravel(), gd2.ravel()))
knn1 = KNeighborsClassifier(n_neighbors=1, weights="uniform")
knn1.fit(x, g)
knn1_class = knn1.predict(gd).reshape(gd1.shape)

# Fill the predicted regions and draw the Voronoi cell boundaries.
axes[1].contourf(gd1, gd2, knn1_class, levels=[-0.5, 0.5, 1.5],
                 cmap=ListedColormap(["#98f5ff", "bisque"]))
voronoi_plot_2d(Voronoi(x), ax=axes[1], show_points=False,
                show_vertices=False, line_colors="black", line_width=1)
axes[1].scatter(x[:, 0], x[:, 1],
                c=np.where(g == 1, "darkorange", "deepskyblue"), s=100)
axes[1].scatter(0.7, 0.7, marker="x", color="red", s=80)
for ax in axes:
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_aspect("equal")
plt.tight_layout()
plt.show()

Example: Artificial data

We now use mixture.example from the ElemStatLearn package. Its two classes have overlapping distributions, so a straight boundary may not capture their pattern well.

For Python, the supplied training data and prediction grid are exact exports of the same dataset. Save them in data/knn/ and run the code from the folder containing data/. The grid contains locations for displaying predictions, not additional labeled observations.

R

  library(ElemStatLearn)

  x <- mixture.example$x
  y <- mixture.example$y
  xnew <- mixture.example$xnew

  par(mar=rep(2,4))
  plot(x, col=ifelse(y==1, "darkorange", "deepskyblue"),
       axes = FALSE, pch = 19)
  box()

Python

import pandas as pd

mixture = pd.read_csv("data/knn/mixture-training.csv")
x = mixture[["x1", "x2"]].to_numpy()
y = mixture["y"].to_numpy()
xnew = pd.read_csv("data/knn/mixture-grid.csv").to_numpy()

plt.figure(figsize=(6, 6))
plt.scatter(x[:, 0], x[:, 1],
            c=np.where(y == 1, "darkorange", "deepskyblue"), s=20)
plt.xticks([])
plt.yticks([])
plt.show()

Use $k=15$ to see the nonlinear boundary that KNN produces. The contour separates locations predicted as class zero from those predicted as class one.

R

  # knn classification
  k = 15
  knn.fit <- knn(x, xnew, y, k=k)

  px1 <- mixture.example$px1
  px2 <- mixture.example$px2
  pred <- matrix(knn.fit == "1", length(px1), length(px2))

  contour(px1, px2, pred, levels=0.5, labels="",axes=FALSE)
  box()
  title(paste(k, "-Nearest Neighbor", sep= ""))
  points(x, col=ifelse(y==1, "darkorange", "deepskyblue"), pch = 19)
  mesh <- expand.grid(px1, px2)
  points(mesh, pch=".", cex=1.2, col=ifelse(pred, "darkorange", "deepskyblue"))

Python

k = 15
knn_fit = KNeighborsClassifier(n_neighbors=k, weights="uniform")
knn_fit.fit(x, y)

px1 = np.unique(xnew[:, 0])
px2 = np.unique(xnew[:, 1])
pred = knn_fit.predict(xnew).reshape(len(px2), len(px1))

plt.figure(figsize=(6, 6))
plt.contour(px1, px2, pred, levels=[0.5], colors="black")
plt.scatter(x[:, 0], x[:, 1],
            c=np.where(y == 1, "darkorange", "deepskyblue"), s=20)
plt.scatter(xnew[:, 0], xnew[:, 1], marker=".", s=2,
            c=np.where(pred.ravel() == 1, "darkorange", "deepskyblue"))
plt.xticks([])
plt.yticks([])
plt.title(f"{k}-Nearest Neighbor")
plt.show()

We can summarize the in-sample predictions with a confusion matrix. Rows are predicted classes and columns are observed classes. These observations were also used to fit the rule, so this matrix measures training performance, not test performance.

R

  # the confusion matrix
  knn.fit <- knn(x, x, y, k = 15)
  xtab = table(knn.fit, y)

  library(caret)
  confusionMatrix(xtab)

Confusion Matrix and Statistics

       y
knn.fit  0  1
      0 82 13
      1 18 87
                                          
               Accuracy : 0.845           
                 95% CI : (0.7873, 0.8922)
    No Information Rate : 0.5             
    P-Value [Acc > NIR] : <2e-16          
                                          
                  Kappa : 0.69            
                                          
 Mcnemar's Test P-Value : 0.4725          
                                          
            Sensitivity : 0.8200          
            Specificity : 0.8700          
         Pos Pred Value : 0.8632          
         Neg Pred Value : 0.8286          
             Prevalence : 0.5000          
         Detection Rate : 0.4100          
   Detection Prevalence : 0.4750          
      Balanced Accuracy : 0.8450          
                                          
       'Positive' Class : 0               
                                          

Python

knn_fit = KNeighborsClassifier(n_neighbors=15, weights="uniform")
knn_fit.fit(x, y)
pred = knn_fit.predict(x)
xtab = pd.crosstab(pd.Series(pred, name="Prediction"),
                   pd.Series(y, name="Observed"))
print(xtab)

Observed     0   1
Prediction        
0           82  13
1           18  87

print("Accuracy:", np.mean(pred == y))

Accuracy: 0.845

Tuning with the caret package

As in Week 3, cross-validation lets us choose a tuning parameter using held-out observations within the available training data. In R, caret specifies the resampling rule with trainControl(). The Python counterpart uses StratifiedKFold for the same ten-fold classification procedure.

R

  library(caret)
  control <- trainControl(method = "cv", number = 10)

Python

from sklearn.model_selection import StratifiedKFold, GridSearchCV

control = StratifiedKFold(n_splits=10, shuffle=True, random_state=1)

Other choices include repeated cross-validation (repeatedcv in caret) and leave-one-out cross-validation (LOOCV). See ?trainControl for the R options. Here we keep ten folds and compare every $k$ from 1 through 40. In R, method="knn" selects the model and a factor-valued outcome tells caret to perform classification.

R

  set.seed(1)
  knn.cvfit <- train(y ~ ., method = "knn",
                     data = data.frame("x" = x, "y" = as.factor(y)),
                     tuneGrid = data.frame(k = seq(1, 40, 1)),
                     trControl = control)

  plot(knn.cvfit$results$k, 1-knn.cvfit$results$Accuracy,
       xlab = "K", ylab = "Classification Error", type = "b",
       pch = 19, col = "darkorange")

knn.cvfit$bestTune

  k
6 6

Python

knn_cvfit = GridSearchCV(
    KNeighborsClassifier(weights="uniform"),
    param_grid={"n_neighbors": range(1, 41)},
    scoring="accuracy", cv=control
)
knn_cvfit.fit(x, y)

plt.figure(figsize=(6, 6))
plt.plot(range(1, 41), 1 - knn_cvfit.cv_results_["mean_test_score"],
         "o-", color="darkorange")
plt.xlabel("K")
plt.ylabel("Classification Error")
plt.show()

print("Selected k:", knn_cvfit.best_params_["n_neighbors"])

Selected k: 12

The selected value minimizes the average validation classification error. The curve helps us see the effect of $k$, but it need not be a smooth U. The folds and tie-breaking conventions can differ between packages, so the two languages need not select exactly the same $k$.

Distance measures

Until now, closeness has meant Euclidean distance. Its square is

$$d^2(\mathbf u,\mathbf v)=\lVert\mathbf u-\mathbf v\rVert_2^2 =\sum_{j=1}^p(u_j-v_j)^2.$$

Taking the square root gives Euclidean distance; both versions order the neighbors the same way. The measure depends on units: a variable with a large numerical scale can dominate. A standardized version is

$$d^2(\mathbf u,\mathbf v)=\sum_{j=1}^p\frac{(u_j-v_j)^2}{\sigma_j^2},$$

where $\sigma_j^2$ is the variance of predictor $j$. We can estimate it from the training data. When using cross-validation, estimate these scales within each training fold, just as we did for ridge regression.

The Mahalanobis distance also accounts for correlations:

$$d^2(\mathbf u,\mathbf v) =(\mathbf u-\mathbf v)^{\mathsf T}\boldsymbol\Sigma^{-1}(\mathbf u-\mathbf v),$$

where $\boldsymbol\Sigma$ is the covariance matrix, assumed invertible, and can be estimated using the sample covariance matrix.

In the following example, the population center is $(0,1)$. The red cross at $(1,0.5)$ and orange cross at $(1,1.5)$ have the same Euclidean distance from that center. But the red point is farther from the pattern of the joint distribution. Mahalanobis distance reflects that distinction. The ellipses use the realized sample mean and covariance, so their center need not be exactly $(0,1)$.

R

  x=rnorm(100)
  y=1 + 0.3*x + 0.3*rnorm(100)

  library(car)
  dataEllipse(x, y, levels=c(0.6, 0.9), col = c("black", "deepskyblue"), pch = 19)
  points(1, 0.5, col = "red", pch = 4, cex = 2, lwd = 4)
  points(1, 1.5, col = "darkorange", pch = 4, cex = 3, lwd = 4)

Python

from matplotlib.patches import Ellipse
from scipy.stats import f

x = np.random.normal(size=100)
y = 1 + 0.3 * x + 0.3 * np.random.normal(size=100)

# Sample mean and covariance define the data ellipses.
center = [np.mean(x), np.mean(y)]
values, vectors = np.linalg.eigh(np.cov(x, y))
angle = np.degrees(np.arctan2(vectors[1, 1], vectors[0, 1]))

fig, ax = plt.subplots(figsize=(6, 6))
ax.scatter(x, y, color="black", s=20)
ax.scatter(*center, color="deepskyblue", marker="+", s=80)
for level in [0.6, 0.9]:
    radius = np.sqrt(2 * f.ppf(level, 2, len(x) - 1))
    ax.add_patch(Ellipse(center, width=2 * radius * np.sqrt(values[1]),
                         height=2 * radius * np.sqrt(values[0]), angle=angle,
                         fill=False, edgecolor="deepskyblue", linewidth=2))
ax.scatter(1, 0.5, color="red", marker="x", s=100, linewidths=3)
ax.scatter(1, 1.5, color="darkorange", marker="x", s=150, linewidths=3)
ax.set_xlabel("x")
ax.set_ylabel("y")
plt.show()

For categorical variables, Hamming distance counts the coordinates with different values:

$$d(\mathbf u,\mathbf v)=\sum_{j=1}^p I(u_j\ne v_j).$$

Computational issues

A direct nearest-neighbor search calculates and compares distances to the training observations. This can be expensive when the training sample is large. We also need to retain the training data for future predictions. In a fitted linear model, by comparison, prediction uses the estimated coefficient vector.

More efficient neighbor-search algorithms are available. The R package FNN provides such implementations; we will use it in the companion note.

Different KNN functions

Check whether a function performs regression or classification before using it. In these demonstrations, kknn performs regression with equal neighbor weights because we specified kernel="rectangular". The function class::knn performs classification, and caret::train provides the cross-validation interface. The companion uses FNN::knn.reg for regression. In R, ??knn helps locate the available functions.

Python provides KNeighborsRegressor and KNeighborsClassifier for the two tasks; GridSearchCV chooses $k$ by cross-validation. In both languages, keep track of whether the output is a numerical mean estimate or a class label.

Continue to The Curse of Dimensionality to see what happens when distance involves many predictors.