K-Nearest Neighbors
K-Nearest Neighbors (KNN) is an algorithm used for both classification and regression tasks. Unlike many algorithms, it does not build a complex internal model but relies directly on the distance between data points to make predictions.
KNN in Simple Words
KNN answers a simple question: “Which known examples are closest to this new example?”It then uses those nearby examples to make a prediction.
New Example
A new data point arrives
Measure Distance
Compare it with known points
Choose K Neighbours
Keep the closest K examples
Predict
Vote or take an average
A Tiny Student Example
Suppose we use only study hours to keep the first example easy. Past students are:
| Study Hours | Result |
|---|---|
| 1 | Fail |
| 2 | Fail |
| 4 | Pass |
| 5 | Pass |
New student: 3.6 study hours, K = 3
- The three closest study-hour values are 4, 5, and 2.
- Their results are Pass, Pass, Fail.
- Pass gets 2 votes and Fail gets 1 vote.
Prediction: Pass
Real KNN problems can use many features. We start with one feature only so the idea is easy to see.
What is K-Nearest Neighbors?
KNN is a supervised machine learning algorithm that predicts the output of a new, unseen data point by looking at the closest (nearest) data points in the training dataset.
Algorithm Characteristics
KNN is commonly described using a few useful ideas:
- Lazy / Instance-Based Learning: KNN does not fit a compact equation or tree of decision rules. It keeps the training examples and performs most of its work when a new point must be predicted.
- Local Prediction: The prediction depends mainly on training examples located near the new point, rather than on one global formula.
- Distance-Based Algorithm: A distance metric is used to define what “near” means mathematically.
Real-Life Intuition (Local Similarity)
The core intuition of K-Nearest Neighbors is simple: "Nearby examples may have similar outputs." This is useful only when the chosen features and distance metric make “nearby” meaningful.
Analogy: The New Student. Suppose a new student joins a school. To predict the student's interests, observers evaluate: Who are the student's closest friends? If most nearby students (friends) play sports, it is highly likely the new student will too. KNN uses this exact principle.
K = 1
Overfitting risk
Only 1 neighbour. Extremely sensitive to noise and outliers. Decision boundary is jagged.
K = 5
Middle-sized example
Five neighbours vote. This can be less sensitive than K=1, but whether K=5 is good must be checked on validation data.
K = 15
Underfitting risk
A larger neighbourhood can smooth local patterns. If K becomes too large for the dataset, underfitting can occur.
These K values are illustrations, not universal rules.
Meaning of "K" and "Nearest Neighbors"
The "K" represents the predefined number of nearest neighbors considered during prediction.
Example: K = 3 implies "consider the 3 closest neighbors""Nearest Neighbors" refers to the actual data points from the training set that have the shortest mathematical distance to the new test point.
Interactive KNN Decision Visualizer
Click anywhere on the grid to place the test point (⭐). Adjust K to see how neighborhood voting dynamically assigns the predicted class.
Nearest 3 Neighbors Ranked by Distance
| Rank | Point | True Class | Distance (d) |
|---|---|---|---|
| #1 | P5 | Class A | 16.6 |
| #2 | P11 | Class B | 18.7 |
| #3 | P7 | Class B | 19.8 |
KNN Classification vs Regression
KNN is unique because it handles both classification (predicting categories) and regression (predicting continuous numbers) using the same underlying distance concept.
1. Classification (Categories)
Used when the output belongs to distinct classes (e.g., Spam / Not Spam).
Prediction Rule: Majority Voting
If K = 5, and the nearest neighbors are: Red, Red, Blue, Red, Blue.
2. Regression (Numerical)
Used when predicting continuous numerical targets (e.g., House Prices).
Prediction Rule: Average Value
If K = 5, and nearest neighbor house values are: 100k, 120k, 110k, 130k, 140k.
Step 1: 100 + 120 + 110 + 130 + 140 = 600
Step 2: 600 ÷ 5 = 120
Prediction = 120k
Complete KNN Workflow
KNN is called a lazy learner because it does not learn a compact predictive equation during fitting. Its fit() step stores the training examples and may prepare a neighbour-search structure; most of the prediction work happens when a query point arrives.
Prediction Workflow
- Fit / Store Training Examples: The estimator keeps the labelled examples and may build a search structure.
- Receive New Data: A new, unseen data point is presented.
- Find Nearby Points: The estimator uses the chosen distance metric and neighbour-search method to locate close training examples.
- Select the K Nearest: Keep the nearest
Ktraining examples. - Generate Prediction: Use a class vote (classification) or a local average/interpolation (regression).
Distance Metrics in KNN (The Math)
Distance measurement is central to KNN because it determines which training examples count as neighbours. Below are two common distance calculations. Scikit-learn also supports the broader Minkowski family and other metrics.
1. Euclidean DistanceCommon
Measures straight-line distance between two points. In two dimensions, it is the familiar Pythagorean-distance calculation; the same idea extends to more features.
Formula
d = √( ∑(x_i - y_i)² )Worked Example [Points: A(2,3) & B(6,7)]
d = √( (6 - 2)² + (7 - 3)² )
d = √( (4)² + (4)² )
d = √( 16 + 16 ) = √32
d ≈ 5.66
2. Manhattan Distance (City Block)
Measures movement along strictly horizontal and vertical grid lines. Think of it as how a taxicab moves through city blocks, unable to cut diagonally through buildings.
Formula
d = ∑ | x_i - y_i |Worked Example [Points: A(2,3) & B(6,7)]
d = |6 - 2| + |7 - 3|
d = |4| + |4|
d = 8
Why Feature Scaling Matters in KNN
Distance compares numeric differences. If one feature is measured in much larger numbers, it can dominate the distance even when it is not more important.
| Feature | Student A | Student B | Raw difference |
|---|---|---|---|
| Age | 20 | 25 | 5 |
| Salary | ₹30,000 | ₹50,000 | 20,000 |
What would happen with raw Euclidean distance?
The salary difference is numerically much larger than the age difference, so salary would dominate the calculation. Scaling puts features onto more comparable numerical scales when their units differ greatly.
Scaling is especially important for distance-based methods such as KNN. Fit the scaler on training data only, then transform validation/test data with the same scaler.
Uniform Vote vs Distance-Weighted Vote
Uniform weights
Every selected neighbour gets the same vote.
weights='uniform'Distance weights
Closer neighbours receive more influence than farther neighbours.
weights='distance'Choosing a Useful Value of K
The value of K controls how local or smooth the prediction is. There is no universally best K: choose it using validation or cross-validation for the dataset and metric you care about.
- Small K (for example K = 1): Can be very sensitive to individual noisy points and often has higher variance.
- Large K: Uses a broader neighbourhood and produces smoother predictions. If K is too large relative to the dataset, useful local patterns can be lost and underfitting can occur.
Methods for Selecting K
A rough heuristic can suggest values to try, but validation or cross-validation is the more dependable way to choose K. A validation-error plot can then make the comparison easy to see.
1. The Square Root Heuristic
The square-root heuristic (K ≈ √N) is a rough rule of thumb sometimes used to generate a starting value to try. It is not an optimization rule and should not replace validation.
Step-by-Step:
- Count the total number of samples (rows) in your training dataset (
N). - Calculate the square root of
N. - For binary classification with uniform voting, you may also try nearby odd values to reduce the chance of an equal vote.
Practical Example:
Training set rows (N) = 1,000
√1,000 ≈ 31.62
Round to nearest whole number ≈ 32
Nearby candidates might include 31, 32 and 33.
These are candidates to validate — not guaranteed optimal values.
2. K-Fold Cross Validation
Cross-validation is a practical way to compare candidate K values without using the final test set for model selection. The training data is repeatedly divided into training and validation folds, and each K is evaluated across those folds.
Step-by-Step:
- Define a range of odd K values to test (e.g., K = 1, 3, 5, 7, 9, 11).
- For each K value, fit KNN on the training folds.
- Evaluate it on the corresponding validation fold.
- Average the validation scores across folds and select a K using the metric that matters for your task.
Practical Example (Testing Range 1-9):
Iteration 1: K=1 -> Accuracy: 82%
Iteration 2: K=3 -> Accuracy: 87%
Iteration 3: K=5 -> Validation Accuracy: 91% (best in this toy example)
Iteration 4: K=7 -> Accuracy: 89%
Iteration 5: K=9 -> Accuracy: 86%
Conclusion: In this toy comparison, K=5 would be the candidate to carry forward and then evaluate once on untouched test data.
3. Validation Error Curve (Visual Aid)
A simple visual aid is to plot validation error for the K values you tested. Prefer the value that performs well on validation data while avoiding an unnecessarily sensitive or overly smooth model.
Step-by-Step:
- Compute validation error (for example,
1 - accuracy) for a range of K values. - Plot K on the X-axis and validation error on the Y-axis.
- Compare the curve and select a K supported by validation performance.
In this illustration, validation error is lowest at K=5. That makes K=5 the strongest candidate among the values shown, but a different dataset can prefer a different K.
Implementation in Python
Here is a small Scikit-Learn pipeline. The important detail is the order: split first, then fit the scaler using training data only, and finally transform the test data with that same scaler.
Interactive: Train & Evaluate KNN in Python
Adjust K and the weighting function below, then click 'Run Code' to execute the scikit-learn model in real-time.
Number of nearest neighbors taking part in the majority vote.
Uniform gives every neighbor 1 vote; distance weighs closer neighbors higher.
| 1 | import pandas as pd |
| 2 | from sklearn.model_selection import train_test_split |
| 3 | from sklearn.neighbors import KNeighborsClassifier |
| 4 | from sklearn.preprocessing import StandardScaler |
| 5 | from sklearn.metrics import accuracy_score |
| 6 | |
| 7 | # 1. Dataset |
| 8 | data = { |
| 9 | 'Age': [22, 25, 47, 52, 46, 56, 31, 45, 33, 40], |
| 10 | 'Salary': [20000, 25000, 50000, 60000, 52000, 65000, 30000, 48000, 35000, 42000], |
| 11 | 'Buy': [0, 0, 1, 1, 1, 1, 0, 1, 0, 1] |
| 12 | } |
| 13 | df = pd.DataFrame(data) |
| 14 | X = df[['Age', 'Salary']] |
| 15 | y = df['Buy'] |
| 16 | |
| 17 | # 2. Split before scaling |
| 18 | X_train, X_test, y_train, y_test = train_test_split( |
| 19 | X, y, test_size=0.2, random_state=42, stratify=y |
| 20 | ) |
| 21 | |
| 22 | # 3. Fit scaler on training set only |
| 23 | scaler = StandardScaler() |
| 24 | X_train_scaled = scaler.fit_transform(X_train) |
| 25 | X_test_scaled = scaler.transform(X_test) |
| 26 | |
| 27 | # 4. KNN Model |
| 28 | n_neighbors = 3 |
| 29 | weights = 'uniform' |
| 30 | model = KNeighborsClassifier(n_neighbors=3 |
| 31 | model.fit(X_train_scaled, y_train) |
| 32 | |
| 33 | # 5. Predict and evaluate |
| 34 | predictions = model.predict(X_test_scaled) |
| 35 | acc = accuracy_score(y_test, predictions) |
| 36 | |
| 37 | print(f"Nearest Neighbors K = {n_neighbors}") |
| 38 | print(f"Weighting Scheme: {weights}") |
| 39 | print(f"Test Set Predictions: {predictions.tolist()}") |
| 40 | print(f"Test Set Ground Truth: {y_test.values.tolist()}") |
| 41 | print(f"Accuracy: {acc:.2f}") |
Advantages vs Disadvantages
Advantages
- Simple: Easy to logically understand and implement.
- Little Model Fitting: There is no large parametric training loop; fitting mainly stores examples and may prepare a search structure.
- Local, Non-linear Behaviour: KNN can represent flexible local decision boundaries when the distance measure is meaningful.
- Versatile: Supports both classification and regression.
Disadvantages
- Prediction Cost: Neighbour searches can become expensive as the number of stored examples grows.
- Curse of Dimensionality: Distance can become less informative in high-dimensional spaces, which can reduce KNN effectiveness.
- Sensitive to Feature Scale: Features measured on very different numerical scales can distort distance unless handled appropriately.
- Storage: KNN retains the training examples, so memory/storage requirements grow with the dataset.
Common KNN Questions
Does KNN always need feature scaling?
Scaling is usually very important when numeric features use very different units because KNN relies directly on distance. If features are already meaningfully comparable, the exact preprocessing choice can differ.
Is K=5 always a good choice?
No. K=5 is a common teaching example, not a rule. Compare several K values using validation or cross-validation.
Why can KNN struggle with many features?
In high-dimensional spaces, points can all start to look far apart in similar ways. This is part of the curse of dimensionality, and it can make neighbourhoods less informative.
Continue learning
Review Feature Scaling, compare KNN with other methods in Classification Algorithms Overview, and use Cross-Validation to choose K more reliably.
Final Summary
K-Nearest Neighbors is an intuitive machine learning algorithm based on proximity. Rather than fitting a compact predictive equation during training, it retains the training examples and uses nearby records to guide predictions.
KNN can work well when meaningful nearby examples exist, but prediction cost, feature scaling, the choice of K, the distance metric, and high dimensionality all matter. Its simplicity also makes it a useful baseline for suitable small-to-medium problems.
Most Important Insight to Remember:
"KNN predicts locally: define a meaningful distance, find nearby labelled examples, and let those neighbours guide the prediction."