CoreSource checked

K-Nearest Neighbors

Predicts from the labels or values of the closest training examples.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Machine Learning
Difficulty: Beginner
Family: Instance-Based Learning
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 1
Code example: Not ready
Visualization: Ready
Aliases: KNN

Overview

K-Nearest Neighbors stores examples and answers new queries by finding nearby examples under a distance measure.

Core Concepts

learned parametersdistance lookupclass decision boundaryinstance-based learningmodel fittraining examplesprediction rule

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(d)

Average

O(nd)

Worst

O(nd)

Space

O(n)

When to Use

Use K-Nearest Neighbors when you need to compute distances to stored examples.
Use it when the input assumptions match the method's model.
Use it when you have data that matches the model's assumptions and a measurable target or structure.
Use it when the method's tradeoffs fit the workload.

When Not to Use

Avoid it when there is not enough representative data to train or evaluate the model.
Avoid it when the required output is not predicted label or value.

What It Does

Computes distances to stored examples
Combines the nearest neighbors' labels or values

Use Cases

Simple classification
Recommendation baselines
Local regression

Inputs

Training examples
Query example
Distance metric
K value

Outputs

Predicted label or value

Key Formulas (1)

Euclidean distance

distance(a, b) = √∑((a_i − b_i)²)

distance(a, b) = sqrt(sum((a_i - b_i)^2))

Measures closeness between a query point and stored examples.

Pseudocode

1.Store the training examples
2.Compute distance from the query to each example
3.Select the K closest examples
4.Vote or average their targets
5.Return the combined result

Canonical Example

Input: examples = [[size, price], ...], target = label or value
Output: model predictions for new examples
Explanation: K-Nearest Neighbors: The algorithm learns a pattern from examples and applies it to unseen data.

Implementation Notes

Keep the input contract explicit: Training examples; Query example; Distance metric; K value.
Split data for evaluation and track preprocessing steps so predictions use the same feature format.
Treat examples as educational sketches; production models need validation, monitoring, and domain checks.

Common Pitfalls

KNN is simple but prediction becomes slow without indexing or small data.
Evaluating only on training data and mistaking memorization for useful performance.
Handle empty, invalid, and boundary inputs before trusting predicted label or value.
Data leakage, unscaled features, and validation on training data can make results look better than they are.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show a query point surrounded by its closest examples.

Step 1 of 5: Store the training examples

nearest-neighbors

Notes

K-Nearest Neighbors operates in O(nd) time and O(n) space within the Instance-Based Learning family. Key governing relation: distance(a, b) = sqrt(sum((a_i - b_i)^2)). Often compared with Naive Bayes and DBSCAN.

Sources (1)

What each reference supports for this entry.

The Elements of Statistical Learning

Book

Statistical learning reference for the model family and tradeoffs of K-Nearest Neighbors.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discovery Open map

Alternative toNaive Bayes

Machine Learning · Core

k-nearest neighbors and Naive Bayes are baseline classifiers with very different modeling assumptions.

Compare with this

Relationships

View full relationship page