K-Nearest Neighbors
- Introduced by
- Cover, T.M. & Hart, P.E.
- Year
- 1967
- Type
- Instance-based (non-parametric) learning
What does it do?
K-Nearest Neighbors (KNN), formalized by Cover and Hart in 1967, is a non-parametric, instance-based method that classifies or predicts a new observation by looking at the k closest examples in the training data.
For classification it takes a majority vote among those neighbors; for regression it averages their values.
The intuition behind the method
The idea is simple: similar inputs tend to have similar outputs. To label a new point, KNN finds the handful of training examples that sit nearest to it in feature space and lets them decide. There is no equation fitted in advance — the training data itself is the model, and a prediction is made only when a new point arrives.
History
Nearest-neighbor pattern classification was given its formal statistical footing by Thomas Cover and Peter Hart in their 1967 paper in the IEEE Transactions on Information Theory, which analyzed the error rate of the nearest-neighbor rule. KNN became one of the earliest and most enduring instance-based learning methods and remains a standard baseline classifier.
When to use it
Use KNN for classification or prediction on tabular data with continuous, binary, or ordinal features and at least about 30 observations. It assumes no particular distribution, but it does require that features be normalized and that the number of features stay small relative to the sample size (p far less than n is preferred). In small or high-dimensional samples the curse of dimensionality dominates — neighbor distances become uninformative — and a parametric model such as logistic regression or Naive Bayes is the better choice.
Limitations and considerations
- Sensitive to feature scaling; without standardization, large-scale features dominate the distance.
- Degrades quickly in high dimensions (curse of dimensionality), where neighbor distances lose meaning.
- Every prediction requires scanning the whole training set, which is slow at prediction time on large data.
- Needs at least a moderate sample size; in small samples nearest-neighbor distances are not meaningful.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Conceptually simple and easy to explain: no training-time equation, the data is the model.
- Non-parametric — makes no assumption about the underlying distribution.
- Naturally handles multi-class problems and complex, nonlinear decision boundaries.
- Works for both classification and regression with the same basic idea.
Applications
- Classification of tabular data into two or more categories.
- Numeric prediction (regression) by averaging the nearest examples.
- A simple, interpretable baseline before trying more complex models.
- Pattern recognition where similarity to known examples drives the decision.
How it works
How it works
For a new observation, KNN measures how far it is from every training example, typically using Euclidean distance across the features. Because distance is scale-sensitive, features must be standardized first — otherwise a variable measured on a large numeric scale would dominate the calculation and distort which neighbors are considered closest.
Formula
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}The k training points with the smallest distances to the new observation are selected as its neighbors. The value of k controls how local the decision is: a small k follows the data closely but is sensitive to noise, while a larger k smooths the boundary. k should be chosen by cross-validation (for example, the elbow method) rather than guessed.
The neighbors decide the prediction: for classification the new point takes the most common class among its k neighbors (a majority vote), and for regression it takes the average of their values. This makes the method easy to understand, but every prediction requires scanning the training set.
Formula
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}Common pitfalls
- Skipping feature standardization, so one large-scale variable silently controls the distance.
- Picking k by hand instead of selecting it with cross-validation.
- Applying KNN with many features and few observations, where the dimension/sample ratio breaks it.
- Reporting only accuracy instead of precision, recall, F1, and a confusion matrix.
Frequently asked questions
How do I choose the value of k?
k should be selected with cross-validation rather than guessed — for example by trying a range of values and using the elbow method to find where error stops improving. A small k follows the data closely but is noise-sensitive, while a larger k smooths the decision boundary.
Why must I standardize the features?
KNN decides who is 'nearest' using distance, which is scale-sensitive. If one feature is on a much larger numeric scale than the others, it dominates the distance and distorts the neighbor set. Standardizing features (for example with a StandardScaler) is required so each feature contributes fairly.
Why does KNN struggle with many features?
In high-dimensional spaces all points become roughly equidistant — the curse of dimensionality — so 'nearest' neighbors are no longer meaningfully close. KNN performance drops quickly, and a parametric model such as Naive Bayes or logistic regression is usually preferable. Keeping p far smaller than n helps.
Is there a training step?
Not in the usual sense. KNN is instance-based (lazy): it simply stores the training data and does all the work at prediction time, when it computes distances to find the nearest neighbors of a new point.
Related methods
Sources
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Open DOI referenceCopied.