Statistics Glossary → k-Nearest Neighbors (KNN)
k-Nearest Neighbors (KNN)analysis
An assumption-free method that assigns a new observation to the majority class of the k observations whose measurements most resemble it (or predicts its numeric value as the average of these neighbours).
Concept
k-nearest neighbours (KNN) rests on the idea that 'similar observations have similar outcomes'. The model learns no formula or coefficients; it simply stores the training data and, at prediction time, looks at the new observation's nearest neighbours in it. It therefore needs no assumption about the shape of the relationship and can follow complex, irregular boundaries between classes.
For a new observation, its distance to every training observation is computed first; the most common measure is the Euclidean distance: d = √Σ(x_j − y_j)². The k nearest observations are selected; in classification their majority class is the prediction, in regression the average of their values. The class proportions among the neighbours (e.g. 0.8 if 4 of 5 neighbours are A) can be used as class probabilities. A small k gives very local, jumpy predictions; a large k smoother ones that may miss detail; a suitable k is usually chosen by cross-validation.
Because distances are computed directly from the measurements, the scale of the variables is decisive: in unscaled data a variable with large units dominates the distance. Scaling parameters must be computed from the training data only, otherwise information from the test data leaks into the model. As the number of variables grows, all points end up at similar distances from one another and neighbourhoods lose their meaning (the curse of dimensionality); irrelevant variables also lower performance. Performance should be measured on an independent test set or by cross-validation.
When to use it
- In classification or prediction problems with relatively few variables, which are numeric and can be meaningfully scaled, and where the boundary between classes may be irregular.
- With very many variables, or many irrelevant ones, random forest, gradient boosting or a support vector machine usually perform better.
- If functions and coefficients explaining how the groups separate on the measurements are needed, discriminant analysis or logistic regression is preferred.
An everyday example
A bookshop wants to guess which genre (fiction, history, science) a newly registered customer will like most. The customer's age, monthly book purchases and preferred book length are known. KNN finds the 5 existing members most similar to them on these three pieces of information; if 3 of them mostly buy history and 2 fiction, history books are recommended to the new customer. The same method can also estimate how much the new customer will spend by averaging the monthly spending of these 5 similar customers.
Parameters in MerQur
Features (X) and Target class (Y)
Concept: The features are the variables from which similarity (distance) between observations is computed; the target is the outcome to be predicted. Which features are chosen directly determines who counts as whose 'neighbour'.
Everyday example: If the bookshop measures similarity by age, monthly purchases and book length, the neighbours are people with similar reading habits. If an irrelevant piece of information such as shoe size is added, the neighbours start to become random people.
What it does: Selects the features from which the distance is computed and the target to be predicted. Categorical Xs are coded 0/1 and then scaled like numeric ones.
Effect on the result: Determines the distance and the neighbourhoods. Rows with missing values are deleted listwise.
On the validation data: 13 features and 3 classes in Wine, 7 features and 2 classes in Pima, 13 features and a continuous target in Boston.
Task (Classification (categorical Y), Regression (continuous Y))
Concept: If the target is categorical, the neighbours' majority vote is used (classification); if continuous, the average of their values (regression). Performance is measured accordingly by accuracy and kappa, or by RMSE, MAE and R².
Everyday example: 'Which genre will they like?' is classification and is judged by the share of correct guesses. 'How much will they spend a month?' is regression and is judged by how far, on average, the predictions miss the real spending.
What it does: With a categorical target it uses the vote of the neighbours, with a continuous target the neighbour mean.
Effect on the result: Changes the output measures (RMSE, MAE, R2 instead of accuracy and kappa).
On the validation data: Wine and Pima classification, Boston regression: RMSE 4.33993542276 and R2 0.747225110833 (k = 5, z).
k selection (Fixed k, Choose from range by CV), k (number of neighbors), Minimum k, Maximum k
Concept: k is the number of neighbours taking part in the prediction and sets the balance between bias and variance: k = 1 ties each prediction to a single observation and is very sensitive to noise; a large k averages many observations and is stable but can wipe out local differences. When choosing from a range, each k is tried by cross-validation and the best-performing one is taken.
Everyday example: Looking only at the single most similar customer misleads if that person happens to have odd tastes. Looking at 50 customers comes close to recommending the most popular genre to everyone. The bookshop tries k from 1 to 20 and picks the value that hits the mark most often for past customers.
What it does: With fixed selection the number of neighbours is given manually (default 3). With selection from a range, each k in [minimum, maximum] is tried by cross-validation; the highest accuracy (lowest RMSE in regression) is taken, and in a tie the largest k is chosen.
Effect on the result: Determines all predictions and measures. In cross-validation the scale is recomputed from the training part of each fold to prevent leakage.
On the validation data: Wine, k = 1..25, 10 folds: selected k 25, test accuracy 0.9814814815. Pima, k = 1..30, 5 folds: selected k 18. Boston, k = 1..20: selected k 3.
Distance (Euclidean, Manhattan (city block))
Concept: Euclidean distance is the straight-line distance between two points and emphasises large differences by squaring them; Manhattan distance is the sum of the absolute differences and gives less weight to a single large difference in one variable.
Everyday example: Euclidean distance is like distance as the crow flies, Manhattan distance like the route walked block by block through a grid of streets. If one customer differs greatly only in age and is identical otherwise, Euclidean distance counts them as further away than Manhattan distance does.
What it does: Euclidean is the square root of the sum of squares (default); Manhattan is the sum of absolute differences.
Effect on the result: Changes the neighbourhoods and predictions.
On the validation data: Wine, Manhattan + min-max + 1/d, k = 7: accuracy 0.9814814815; Pima, Manhattan + min-max, k = 9: accuracy 0.8; Boston, Manhattan + 1/d, k = 6: RMSE 4.55852723633.
→ Distance measure (Euclidean, Manhattan, Gower, great-circle)
Feature scaling (Min-max [0, 1], z-score, None (original units))
Concept: Scaling brings the variables onto a common scale: min-max squeezes each variable into the range 0 to 1, and the z-score transforms it to mean 0 and standard deviation 1. Without scaling, the variable with the largest numeric range determines the distance on its own.
Everyday example: If age ranges from 18 to 80 while monthly purchases range from 0 to 6 books, the unscaled distance looks almost only at age and ignores reading habits. With z-scores both pieces of information get an equal say.
What it does: Scaling parameters are computed from the training data only (from the training part of each fold in cross-validation). Min-max gives the same neighbours as normalisation to [-1, 1].
Effect on the result: Prevents large-scale features from dominating the distance; changes the neighbourhoods, hence all measures.
On the validation data: Pima, k = 11, unscaled, test proportion 0.25: accuracy 0.766917293233; Wine, min-max, k = 5: 0.962962962963; with z-score at the same k, 0.9444444444.
Weighting (Equal, By distance (1/d))
Concept: With equal weights each neighbour casts one vote; with distance weighting a neighbour's vote is multiplied by the inverse of its distance (1/d), so very close neighbours count for more and ties become rarer.
Everyday example: If 2 of the 5 neighbours, almost twins of the new customer, like science and the 3 a little further away like fiction, fiction wins under equal votes. With distance weighting the two most similar people carry more weight and science may be recommended.
What it does: In equal, each neighbour is one vote; in distance-weighted, neighbours are weighted by 1/distance, and if there are zero-distance neighbours only they are used.
Effect on the result: Gives more weight to near neighbours; dilutes voting ties.
On the validation data: The combinations Manhattan + min-max + 1/d (k = 7) in Wine and Manhattan + 1/d (k = 6) in Boston are run.
Evaluation (Training / test split, k-fold cross-validation)
Concept: Sets which predictions performance is measured from: with a training/test split the model is built on part of the data and assessed on a test set it has never seen; with k-fold cross-validation each observation sits in a validation fold once and all the data take part in the assessment. If k is chosen with the same folds and performance is reported from those folds, the result is somewhat optimistic.
Everyday example: The bookshop can use 210 of its 300 members for the model and keep 90 aside as an exam. Or it can split the 300 members into 10 groups and predict each group in turn by looking at the other 270; with little data, this second route gives a more stable measure of success.
What it does: In the split, the model is built on the training set and performance is measured on the test set (stratified in classification). In CV all data are divided into folds and performance is computed from out-of-fold predictions.
Effect on the result: Determines from which predictions the measures are computed. If k is chosen with the same folds, the CV performance is slightly optimistic (a warning is given).
On the validation data: Wine 10-fold CV, k = 5: accuracy 0.9719101124 (n = 178), kappa 0.9574976122.
Test proportion (default 0.3), CV folds (default 10), Random seed (default 42)
Concept: The test proportion sets how much of the data is held out for testing, and the number of folds how many parts the data are split into in cross-validation. The random seed fixes these splits; re-running the analysis with the same seed puts the same observations in the same sets and reproduces the result exactly.
Everyday example: With a test proportion of 0.3, 90 of the 300 members are set aside for the exam. Which 90 are chosen depends on the seed; if success shifts a little with another seed, that shows how open to chance a single split is.
What it does: Determines the proportion of the test set (default 30 percent), the number of folds (default 10) and the split/CV seed; the same seed gives the same result.
Effect on the result: Determines which observations are held out for testing; the seed affects only the split and folds.
On the validation data: Wine test 54 observations, Pima test 160 observations (proportion 0.3).
Confidence Level (%90, %95, %99, Other (custom))
Concept: The accuracy measured on the test set is also a sample estimate; its confidence interval is computed from the binomial distribution of the number of correct predictions and shows the range in which the true accuracy may lie. The higher the confidence level, the wider the interval.
Everyday example: If the genre was guessed correctly for 81 of the 90 exam customers, accuracy is 90%; but because it rests on only 90 people, the 95% confidence interval runs roughly from 82% to 95%. Asking for 99% confidence widens it further.
What it does: Determines the level of the exact binomial confidence interval for accuracy.
Effect on the result: Changes only the interval.
On the validation data: At 95%, Wine, k = 5, accuracy 0.9444444444: interval 0.8461149662 to 0.9883932256; NIR 0.3888888889.
Save predictions
Concept: Adds each observation's predicted class or value and its class probabilities to the dataset as new columns. A class probability is the (weighted) share of neighbours belonging to that class.
Everyday example: The bookshop adds columns such as 'recommended genre' and 'history probability 0.6, fiction 0.4' next to each member. For members whose top probability is only 0.4, that is whose neighbours are mixed, it can send suggestions from several genres instead of one.
What it does: Adds the predicted value (KNN_PRED) and class probabilities (KNN_P_class) to the dataset as new columns; scores all rows with complete features.
Effect on the result: Does not change the calculation.
Example on real data
Data: UCI Wine, Aeberhard and Forina 1992
Variables: features x1-x13 (13 chemical measurements), target cls (3 cultivars); k = 5, z-score
- Question: How accurately can k-nearest neighbours classify the three wine cultivars (c1, c2, c3) from 13 chemical features? (Wine, n = 178)
- Method: k = 5, Euclidean distance, z-scaling (from the training set), equal vote; 30% stratified test (training 124, test 54, seed 42).
- Result: Test accuracy = 0.944 (95% CI [0.846, 0.988]); no-information rate 0.389, p (accuracy > NIR) < .001.
- Effect size: Cohen's kappa = 0.917, macro F1 = 0.944; agreement far above chance.
- Confusion: Only 3 c2 cases were classified as c3; c2 recall = 0.857, c3 precision = 0.833, c1 perfect.
- Limitation: It rests on a single split; k was not chosen by cross-validation.
- APA: KNN (k = 5), test n = 54: accuracy = .94, 95% CI [.85, .99], κ = .92.
Related concepts
Train-test split (holdout)k-fold cross-validationInverse distance weighting (IDW)z-score (standardization)Distance measure (Euclidean, Manhattan, Gower, great-circle)Prediction error measures (RMSE, MAE, MAPE, MASE)Number of nearest neighbours (k) and the neighbourhood graphKappa statistic (Cohen's κ)
The numbers in the examples are MerQur's output on independent, publicly available validation data; see the MerQur Technical Note for details.