# K-Nearest Neighbours

Classifying or predicting by looking at the k closest training examples — a method with no training phase and all the cost at prediction.

**Rests on:** Two-Class and Multiclass Classifiers

*Machine Learning · Machine Learning Foundations*


## Why learn this

This method helps you make predictions based on similarity to things you already know. You will use it to: (1) label new items by finding the known items most like them, (2) estimate numbers like prices or temperatures by averaging nearby examples, (3) build a working system that stores information but does no upfront calculation, and (4) grasp the central problem of machine learning: making sure a rule works on new cases, not just the ones it has seen. After this, you will study Decision Trees, Logistic Regression, and Naive Bayes — each relies on the same core idea you learn here: how to measure how similar two things are.


## The intuition

Imagine you want to guess whether a new fruit is an apple or an orange. You have a box of known fruits, each with a label. You pick the new fruit, measure its weight and colour, and then look at the three or five known fruits that are most similar. If most of those are apples, you say apple. That is it — no rules about what an apple is, no formula for colour, no training. The method simply stores all the known examples and uses them at the moment of guessing.


## An analogy

Think of moving to a new city and trying to figure out the local food culture. You don't have a manual. Instead, you ask three or five of your closest neighbours — the people who live nearest to you. If most of them eat vegetarian, you conclude the area is vegetarian. You are not inventing a rule; you are trusting proximity. The analogy works because K-Nearest Neighbours is exactly that: the 'neighbours' are the training examples, and 'closeness' is measured by some distance. The choice of k (how many neighbours to ask) is a decision you make, like choosing to ask three people instead of ten. The analogy breaks down when you have millions of neighbours: asking millions of people is slow, and that slowness is the cost of KNN. Also, if the city has no clear majority, asking neighbours is useless — just as KNN fails when classes are heavily overlapping.


## Definition

K-Nearest Neighbours (KNN) is an algorithm that classifies a new point by finding the k closest training examples and taking a majority vote of their labels, or predicts a continuous value by averaging the values of those k neighbours.


## How it connects

You have not yet studied any other machine learning algorithms, so this stands alone as your foundation. It is the first of several algorithms that learn from examples without building an explicit rule. Later, you will compare it with Decision Trees (which build a tree of rules), Logistic Regression (which fits a line), and Naive Bayes (which uses probabilities). KNN is different because it does no learning at all — it just stores the data. This is why it is called a 'lazy' learner, and it is the most direct illustration of the principle that all machine learning is about generalising from examples.


## The mathematics

To understand K-Nearest Neighbours, we need two ideas: how to measure distance between points, and how to make a decision based on those distances.

**Part 1: Measuring Distance**

Imagine you have data points described by several numbers (features). For example, a house might be described by its size in square feet and its age in years. We can treat each house as a point in a space where one axis is size and the other is age.

To find how far apart two houses are, we use Euclidean distance. This is the straight-line distance between them. The formula works like this:

1. Take the first feature (e.g., size). Subtract the size of House A from the size of House B. Let's call this difference `diff1`.
2. Square that difference: `diff1 * diff1`.
3. Take the second feature (e.g., age). Subtract the age of House A from the age of House B. Call this `diff2`.
4. Square that difference: `diff2 * diff2`.
5. Add the squared differences together: `(diff1 * diff1) + (diff2 * diff2)`.
6. Take the square root of that sum. This final number is the Euclidean distance.

If you have more features, such as price and location, you simply repeat steps 1-4 for each feature, add all those squared differences together, and then take the square root of the total sum.

**Part 2: The K-Nearest Neighbours Rule**

Once we can measure distance, the algorithm follows these steps:

1. **Calculate Distances**: For a new point you want to classify (let's call it `x_new`), calculate the Euclidean distance to every single point in your training data.
2. **Sort**: List all the training points from the one closest to `x_new` to the one farthest away.
3. **Select k Neighbours**: Pick the first `k` points from that sorted list. These are the 'k nearest neighbours'. The number `k` is a choice you make before starting (e.g., 3, 5, or 10).
4. **Make a Prediction**:
   - **For Classification** (assigning a category): Look at the labels of those `k` neighbours. Count how many belong to each category. Assign `x_new` to the category that appears most often (the majority vote). If there is a tie, pick one at random.
   - **For Regression** (predicting a number): Take the actual numerical values associated with those `k` neighbours. Add them up and divide by `k`. This average is your prediction for `x_new`.

Why do we use `k`? If `k=1`, the prediction depends entirely on the single closest point, which can be noisy. If `k` is too large, the prediction becomes too smooth and ignores local patterns. A common starting point is an odd number like 3 or 5 to avoid ties in binary classification.


## A worked example

Let's walk through a specific example.

**The Data**
We have three training examples (houses) with two features: Size (in hundreds of sq ft) and Age (in years). Each has a label indicating its style: 'Modern' or 'Classic'.

- House A: Size = 1, Age = 2. Label = 'Modern'
- House B: Size = 2, Age = 4. Label = 'Modern'
- House C: Size = 4, Age = 6. Label = 'Classic'

**The Task**
We have a new house, `x_new`, with Size = 3 and Age = 3. We want to predict its style using K-Nearest Neighbours with k = 2.

**Step 1: Calculate Distance to House A**
- Difference in Size: 3 - 1 = 2
- Difference in Age: 3 - 2 = 1
- Square the differences:
  - Size squared: 2 * 2 = 4
  - Age squared: 1 * 1 = 1
- Sum of squares: 4 + 1 = 5
- Distance (square root of sum): √5 ≈ 2.24

**Step 2: Calculate Distance to House B**
- Difference in Size: 3 - 2 = 1
- Difference in Age: 3 - 4 = -1
- Square the differences:
  - Size squared: 1 * 1 = 1
  - Age squared: (-1) * (-1) = 1
- Sum of squares: 1 + 1 = 2
- Distance (square root of sum): √2 ≈ 1.41

**Step 3: Calculate Distance to House C**
- Difference in Size: 3 - 4 = -1
- Difference in Age: 3 - 6 = -3
- Square the differences:
  - Size squared: (-1) * (-1) = 1
  - Age squared: (-3) * (-3) = 9
- Sum of squares: 1 + 9 = 10
- Distance (square root of sum): √10 ≈ 3.16

**Step 4: Sort the Neighbours**
List the houses from closest distance to farthest:
1. House B (Distance ≈ 1.41)
2. House A (Distance ≈ 2.24)
3. House C (Distance ≈ 3.16)

**Step 5: Select k=2 Neighbours**
We take the top 2 closest houses:
- House B (Label: 'Modern')
- House A (Label: 'Modern')

**Step 6: Majority Vote**
Count the labels among the selected neighbours:
- 'Modern': 2 votes
- 'Classic': 0 votes

The majority is 'Modern'.

**Result**: The new house `x_new` is classified as 'Modern'.


## From scratch, in Python

```python
# We have three training points, each with two features and a label
training = [
    ([1, 2], 'apple'),
    ([2, 4], 'apple'),
    ([4, 6], 'orange')
]

# New point to classify
new_point = [3, 3]

# Number of neighbours to consider
k = 2

# Step 1: compute distances from new_point to each training point
# We use a list to hold (distance, label) tuples
# A tuple is like a list but cannot be changed after creation
# We will build a list of tuples
distances = []

for point, label in training:
    # point is a list like [1,2], label is a string like 'apple'
    # compute sum of squared differences
    sum_sq = 0
    for i in range(len(point)):  # i goes 0, 1, ...
        diff = new_point[i] - point[i]
        sum_sq += diff * diff
    # distance is the square root
    dist = sum_sq ** 0.5
    distances.append((dist, label))

# Step 2: sort the distances from smallest to largest
# sorted() returns a new list sorted by the first element of each tuple
sorted_distances = sorted(distances)

# Step 3: take the k nearest (smallest distances)
nearest = sorted_distances[:k]  # first k elements

# Step 4: count votes
votes = {}
for dist, label in nearest:
    if label not in votes:
        votes[label] = 0
    votes[label] += 1

# Step 5: find the label with the most votes
# We iterate over the dictionary to find the max count
best_label = None
best_count = -1
for label, count in votes.items():
    if count > best_count:
        best_count = count
        best_label = label

print("Predicted label:", best_label)  # prints apple
```


## The same thing, with a framework

```python
Using scikit-learn (the standard Python library for classical machine learning):

from sklearn.neighbors import KNeighborsClassifier
import numpy as np

# Data: same as before, but as a 2D array (list of lists)
X_train = np.array([[1, 2], [2, 4], [4, 6]])
y_train = np.array(['apple', 'apple', 'orange'])

# Create and use the classifier
knn = KNeighborsClassifier(n_neighbors=2)
knn.fit(X_train, y_train)  # KNN doesn't actually learn; it just stores the data
X_new = np.array([[3, 3]])
prediction = knn.predict(X_new)
print(prediction)  # prints ['apple']
```


## What the code does

The plain Python code starts by defining the training data as a list of tuples: each tuple has a list of features and a label. A list is an ordered collection that can be changed; a tuple is like a list but cannot be changed once made. We then define the new point and k. The main loop walks through each training point, computing the difference for each feature, squaring it, and accumulating the sum. We use a for loop with range(len(point)) to go through each index, and we use the fact that new_point[i] and point[i] are both numbers. After the loop, we take the square root using **0.5 (the power of one half). We append a tuple (dist, label) to a list called distances. The sorted() function sorts this list by the first element of each tuple automatically, so the smallest distances come first. We then slice the list with [:k] to take the first k items — this is called a slice, which gives a sublist. To count votes, we use a dictionary: we build it by checking if the label is already a key, and incrementing its count. Finally, we iterate over the dictionary's items() to find the label with the highest count. The framework version uses scikit-learn's KNeighborsClassifier. The fit method does not do any learning — it just stores the training data. The predict method computes distances to all stored points and picks the majority. Underneath, it is doing exactly the same loop we wrote by hand.


## Common misconceptions

**KNN has a training phase** — The algorithm must learn something before it can predict, so there is a training step.

KNN does no learning at all. It just stores the training data. The 'fit' method in scikit-learn does nothing except remember the data. In fact: KNN is a 'lazy' learner: all the work happens at prediction time when it computes distances to every training point.

**k is the number of classes** — k must equal the number of classes you want to predict (e.g., 3 for apple, orange, banana).

k is the number of neighbours you consult, which is independent of the number of classes. You can have 2 classes and use k=5 neighbours. In fact: k is the number of closest training points you consider, not the number of classes. Choose k by testing different values.

**Feature scaling is optional** — The algorithm will figure out which features matter more by itself; scaling is just a nicety.

Distance is computed on the raw feature values. A feature with a large range (like income in rupees, up to lakhs) will dominate a feature with a small range (like age, 0–100). The algorithm has no way to weigh features; it treats all features equally in the distance sum. In fact: Scale every feature to the same range (e.g., 0–1 or standard deviation 1) before using KNN, otherwise the large-scale features decide the neighbours.

**KNN works well for high-dimensional data** — If it works with 2 features, it should work with 200 features; more information is always better.

In high dimensions, distances between points become very similar, so 'nearest' is unstable. The fewer dimensions, the more meaningful the distances. In fact: KNN suffers from the curse of dimensionality; it is best used when you have a few features (or after reducing dimensions).

**The majority vote is always correct if k is large** — Using more neighbours (bigger k) always makes the prediction more reliable.

A very large k includes points that are far away and may belong to a different region; the model becomes too smooth and misses local patterns. What matters is choosing the right k, not the biggest one. In fact: The right k depends on your data. Too small leads to overfitting noise; too large leads to underfitting. Use cross-validation to choose it.


## In short

K-Nearest Neighbours classifies or predicts by looking at the k closest training examples. It has no training phase; all work is at prediction time. The key ideas are: the distance metric is the model, so feature scaling is mandatory; it degrades in high dimensions; and it is a strong baseline that should be tried before complex models. Remember: scale your features, choose k carefully, and understand the curse of dimensionality.


## Where this is used

K-Nearest Neighbours is rarely a headline algorithm in modern deep learning, but it appears in several practical roles.

**In large language models (LLMs):** KNN is used in some retrieval-based language models. For example, in a system that combines a language model with a database of documents, a query is turned into a vector (a list of numbers), and the system uses KNN to find the most similar documents in that vector space. This is called retrieval-augmented generation (RAG). The model doesn't generate from the whole database; it first retrieves the top-k relevant documents using KNN, then feeds those into the language model to generate an answer. The 'nearest neighbours' here are not points with two features but vectors with hundreds of features. The logic is identical: compute distance to every stored document and pick the closest few.

**In small models on devices:** KNN on a phone or a small device often appears in gesture recognition or simple classification tasks where the device needs to run quickly without a large model. A small set of stored templates (e.g., microphone samples for wake words) is used as the training set, and the closest match is returned. This is much faster than running a large neural network on the device.

**In RAG specifically:** The 'embedding' model turns text into vectors. Then KNN finds the closest vectors in a database. This is the core of similarity search. The k in 'top-k retrieval' is exactly the k of KNN. Libraries like FAISS (Facebook AI Similarity Search) are specialised for fast KNN on millions of vectors — they use trees or hashing to approximate the nearest neighbours without checking every one.

**In agentic systems:** Agents that plan and act sometimes use KNN to decide which past action worked in a similar situation. They store experiences as vectors, and when a new situation arises, they find the most similar past situations and choose the action that worked then. This is a simple memory-based approach, used when you want the agent to be transparent and easily debuggable, rather than relying on a black-box neural network.

**In everyday applied machine learning:** This is where KNN shines. For tabular data (like a spreadsheet), KNN is often the first thing you try. For example, predicting house prices based on size, number of bedrooms, and location: you find the k most similar houses that sold recently and average their prices. For churn prediction, you find the k most similar customers and see how many churned. For credit scoring, you find similar past applicants and use their repayment outcomes. In fraud detection, you find similar transactions and flag if most are fraudulent. In crop disease detection, you can classify a leaf image by comparing its feature vector (e.g., colour histogram) to known images. The mechanism is always the same: a distance metric, a k, and a vote or average.

**What a developer writes:** In practice, a developer uses scikit-learn: `from sklearn.neighbors import KNeighborsClassifier`. They fit it on the training data (which just stores it), then call `predict` on new data. But before that, they must do feature scaling — a crucial step. If one feature has a range of 0–1 and another has 0–10,000, the distances are dominated by the large-scale feature. They use `StandardScaler` to make every feature have mean 0 and standard deviation 1. They also choose k by cross-validation: try several values and pick the one that performs best on a held-out set. What breaks when done badly: if you don't scale features, the algorithm effectively ignores the small-scale features. If you choose k too small, the model is sensitive to noise; if too large, it includes points that are far away and misses the local pattern. KNN also degrades in high dimensions: when you have many features, distances become similar for all pairs, so 'nearest' loses meaning. This is called the curse of dimensionality. Developers often address it by reducing dimensions first (e.g., with PCA).


---

Read this on the web: https://basavapurushottam.com/learn-ai/k-nearest-neighbours
