What Is k-NN? (k-Nearest Neighbors)
a simple machine learning algorithm that makes predictions by comparing a new data point
Definition
k-Nearest Neighbors (k-NN) is a simple machine learning algorithm that makes predictions by comparing a new data point with the k most similar examples in a labeled dataset. Rather than learning a mathematical model during training, k-NN bases its predictions directly on the examples it has already seen.
The value of k specifies how many nearby examples are considered. For example, if k = 5, the algorithm examines the five closest data points and uses them to predict the class or value of the new example. For classification tasks, it usually chooses the most common class among the neighbors. For regression tasks, it typically predicts the average of their numerical values.
Why It Matters
Although k-NN is one of the oldest machine learning algorithms, it remains an important educational and practical tool. It introduces several fundamental ideas that appear throughout artificial intelligence, including similarity, distance, feature representation, and classification.
Because the algorithm is relatively easy to understand, it is often one of the first machine learning methods taught to students. At the same time, versions of the nearest-neighbor approach continue to appear in modern AI systems, including recommendation engines, image search, anomaly detection, and vector databases used with large language models.
Understanding k-NN provides valuable insight into how AI systems can recognize patterns simply by comparing new information with previously observed examples.
How It Works
The central idea behind k-NN is straightforward: similar things tend to have similar properties.
Imagine moving into a new neighborhood and wanting to estimate the value of your house.
Rather than constructing a complex economic model, you might look at the prices of the five most similar nearby homes—those with comparable size, age, and location—and use them to estimate your own home’s value.
This is essentially how k-NN works.
Instead of learning abstract rules, it asks:
“Which previously seen examples are most similar to this new one?”
The answer determines the prediction.
Measuring Similarity
To compare examples, the algorithm represents each one as a collection of numerical features.
For example, a flower dataset might include:
petal length,
petal width,
sepal length,
and sepal width.
Each flower becomes a point in a multi-dimensional space.
When a new flower is presented, the algorithm measures its distance from every known flower using a mathematical distance metric, such as Euclidean distance.
The nearest examples become the model’s reference points.
Choosing the Value of k
The value of k influences how predictions are made.
A small value, such as k = 1, means the prediction depends on the single closest example.
This makes the algorithm highly sensitive to noise or unusual data points.
A larger value smooths the predictions by considering more neighbors, reducing sensitivity to individual examples.
However, choosing k that is too large may cause the algorithm to ignore meaningful local patterns and produce overly generalized predictions.
Selecting an appropriate value of k is therefore an important part of building a k-NN model.
Classification
One common use of k-NN is classification.
Suppose a model must determine whether a fruit is an apple or an orange.
After identifying the nearest neighbors, the algorithm counts how many belong to each category.
If four of the five nearest examples are apples and one is an orange, the new fruit is classified as an apple.
This process is known as majority voting.
Regression
k-NN can also solve regression problems, where the goal is to predict a numerical value rather than a category.
For example, suppose the nearest five houses sold for:
€295,000
€305,000
€310,000
€315,000
€300,000
The algorithm might predict the new house’s value by averaging these prices.
The same principle of neighboring examples applies, but the output is numerical instead of categorical.
Lazy Learning
Unlike many machine learning algorithms, k-NN performs almost no computation during training.
Instead, it stores the training data and postpones most of the work until a prediction is requested.
For this reason, k-NN is often described as a lazy learning algorithm.
This approach offers some advantages:
training is extremely fast,
adding new examples is straightforward,
and the algorithm is easy to interpret.
However, prediction can become slow when the dataset is very large because every new query may require comparing the new example with many existing ones.
Strengths and Limitations
k-NN has several notable strengths.
It is:
simple to understand,
easy to implement,
effective for many small and medium-sized datasets,
and naturally supports both classification and regression.
However, it also has important limitations.
Performance can decline when:
datasets become very large,
irrelevant features are included,
features have very different numerical scales,
or the data contains many dimensions.
As the number of dimensions increases, measuring meaningful similarity becomes increasingly difficult. This phenomenon is known as the curse of dimensionality.
Common Misconceptions
“k-NN learns complex rules during training.”
It does not.
Unlike neural networks or decision trees, k-NN stores the training data and performs most of its computation only when making predictions.
“The value of k should always be as small as possible.”
Not necessarily.
Very small values of k can make predictions unstable and sensitive to noise, while larger values may produce more reliable results. The optimal value depends on the dataset.
“k-NN only works for classification.”
No.
The algorithm is widely used for both classification and regression, and variations of the nearest-neighbor principle appear in many other machine learning applications.
“The nearest example is always the best predictor.”
Sometimes considering only the single closest example leads to poor results because that example may be unusual or contain errors.
Using multiple neighbors often produces more stable and accurate predictions.
Related Terms
Supervised Learning
k-NN is a supervised learning algorithm because it learns from labeled examples. Understanding supervised learning provides the foundation for understanding how k-NN makes predictions.
Classification
Classification is one of the primary applications of k-NN. Exploring this concept helps explain how the algorithm assigns categories to previously unseen data.
Regression
k-NN can also predict continuous numerical values through regression. Comparing classification and regression illustrates the algorithm’s versatility.
Feature
Features are the measurable properties used to compare data points. The quality and selection of features strongly influence how well k-NN performs.
Distance Metric
A distance metric determines how similarity is measured between examples. Different distance metrics can significantly affect which neighbors are considered closest.
Curse of Dimensionality
As the number of features grows, measuring meaningful similarity becomes increasingly difficult. The curse of dimensionality is one of the main practical limitations of k-NN and many other distance-based algorithms.
Clustering
Clustering groups similar examples without using labeled data. Comparing clustering with k-NN highlights the difference between supervised and unsupervised learning while emphasizing the shared concept of similarity.
Embedding
Modern AI systems often represent text, images, and other data as embeddings—numerical vectors in a high-dimensional space. Many retrieval systems use nearest-neighbor searches on embeddings, making k-NN conceptually relevant to today’s AI applications.
Vector Database
Vector databases are designed to efficiently search large collections of embeddings for the nearest matches. Although much more sophisticated than classical k-NN, they rely on the same fundamental idea of finding similar examples based on distance.