K-Nearest Neighbors (KNN)
1. Introduction
K-Nearest Neighbors (KNN) is a supervised machine learning algorithm used for classification and regression problems.
KNN makes predictions by looking at the K most similar data points, called neighbors, and using their values to make a prediction.
Simple Definition
K-Nearest Neighbors is a machine learning algorithm that predicts a new data point based on the closest existing data points in the dataset.
KNN is called a lazy learning algorithm because it does not build a traditional model during training. Instead, it stores the training data and performs most of its computation when making predictions.
2. Basic Idea of KNN
The basic idea is:
Similar data points are likely to have similar outcomes.
For example, suppose we want to classify a fruit.
We have:
Apple Orange Apple Orange ?
If the unknown fruit is closest to the apples, KNN may classify it as an Apple.
3. Example
Suppose we want to predict whether a student will pass based on:
- Study Hours
- Attendance
Training data:
| Study Hours | Attendance | Result |
|---|---|---|
| 2 | 60 | Fail |
| 3 | 65 | Fail |
| 4 | 70 | Fail |
| 6 | 85 | Pass |
| 7 | 90 | Pass |
| 8 | 95 | Pass |
For a new student:
Study Hours = 6 Attendance = 80
KNN finds the closest students and uses their results to make the prediction.
4. Meaning of K
The letter K represents the number of nearest neighbors used to make a prediction.
For example:
K = 3
means the algorithm considers the 3 closest data points.
K = 5
means it considers the 5 closest data points.
5. How KNN Works
The general process is:
New Data Point ↓ Calculate Distance ↓ Find Nearest Neighbors ↓ Select K Neighbors ↓ Vote / Average ↓ Make Prediction
6. KNN for Classification
For classification, KNN uses the classes of the nearest neighbors.
Example
Suppose:
K = 5
The five nearest neighbors are:
Pass Pass Fail Pass Fail
Count:
Pass = 3 Fail = 2
Therefore:
Prediction = Pass
The most common class among the neighbors is selected.
This is called majority voting.
7. KNN for Regression
KNN can also be used to predict numerical values.
Instead of voting, it commonly calculates the average of the target values of the nearest neighbors.
Example
Suppose the three nearest houses have prices:
Rs. 30,00,000 Rs. 35,00,000 Rs. 40,00,000
Then:
Prediction = (30,00,000 + 35,00,000 + 40,00,000) / 3 Prediction = Rs. 35,00,000
Therefore, the predicted price is:
Rs. 35,00,000
8. Distance in KNN
KNN needs a way to measure how close two data points are.
The most commonly used distance measure is Euclidean Distance.
9. Euclidean Distance
For two points:
A = (x₁, y₁) B = (x₂, y₂)
The Euclidean distance is:
d = √[(x₂ - x₁)² + (y₂ - y₁)²]
For multiple features:
d = √[Σ(xᵢ - yᵢ)²]
10. Simple Distance Example
Suppose:
A = (2, 3) B = (5, 7)
Then:
d = √[(5 - 2)² + (7 - 3)²] d = √[3² + 4²] d = √[9 + 16] d = √25 d = 5
Therefore:
Distance = 5
11. Other Distance Measures
KNN can use different distance measures depending on the data.
1. Euclidean Distance
Common for numerical data.
d = √Σ(xᵢ - yᵢ)²
2. Manhattan Distance
Measures distance by summing absolute differences.
d = Σ|xᵢ - yᵢ|
3. Minkowski Distance
A generalized distance measure.
d = (Σ|xᵢ - yᵢ|ᵖ)¹/ᵖ
4. Hamming Distance
Often used for categorical or binary representations.
It counts the number of positions where values differ.
12. Feature Scaling
Feature scaling is very important for KNN.
Why?
Because KNN depends on distance.
Suppose we have:
Age = 20 Salary = 500000
Salary has a much larger numerical scale than age.
Without scaling, salary could dominate the distance calculation.
Common scaling methods
- Standardization
- Min-Max Scaling
13. Standardization
Standardization transforms data so that features are typically centered around 0 with a standard deviation of 1.
Formula
z = (x - μ) / σ
Where:
x= original valueμ= meanσ= standard deviation
Python example:
from sklearn.preprocessing import StandardScaler scaler = StandardScaler() X_scaled = scaler.fit_transform(X)
14. Min-Max Scaling
Min-Max Scaling transforms values into a specified range, commonly [0, 1].
Formula
x_scaled = (x - x_min) / (x_max - x_min)
Python:
from sklearn.preprocessing import MinMaxScaler scaler = MinMaxScaler() X_scaled = scaler.fit_transform(X)
15. Choosing the Value of K
Choosing an appropriate value of K is important.
Small K
For example:
K = 1
Advantages:
- Very sensitive to local patterns.
- Can capture detailed boundaries.
Disadvantage:
- Can be sensitive to noise.
- May overfit.
Large K
For example:
K = 50
Advantages:
- More stable.
- Less sensitive to individual noisy observations.
Disadvantage:
- Can oversimplify the data.
- May underfit.
16. Odd Values of K
For binary classification, an odd value of K is sometimes used to reduce the chance of a tie.
For example:
K = 3 K = 5 K = 7
However, the best value should be selected based on validation performance rather than simply choosing an odd number.
17. Choosing K Using Cross-Validation
A common approach is to test several values of K using cross-validation.
Example:
K = 1 K = 3 K = 5 K = 7 K = 9
Evaluate each value and select one based on the validation results.
Python example:
from sklearn.model_selection import cross_val_score from sklearn.neighbors import KNeighborsClassifier for k in [1, 3, 5, 7, 9]: model = KNeighborsClassifier(n_neighbors=k) scores = cross_val_score(model, X, y, cv=5) print(k, scores.mean())
18. KNN Algorithm Steps
The KNN algorithm works as follows:
Step 1: Choose K
Select the number of neighbors.
K = 5
Step 2: Calculate Distance
Calculate the distance between the new data point and training points.
Step 3: Sort Distances
Arrange the data points from nearest to farthest.
Step 4: Select K Neighbors
Choose the closest K observations.
Step 5: Make Prediction
For classification:
Majority Vote
For regression:
Average of Neighbor Values
19. KNN Classification Example
Suppose we have:
| X | Y | Class |
|---|---|---|
| 1 | 1 | A |
| 2 | 2 | A |
| 3 | 3 | B |
| 4 | 4 | B |
| 5 | 5 | B |
New point:
(2.5, 2.5)
Choose:
K = 3
The three closest points might be:
(2,2) → A (3,3) → B (1,1) → A
Votes:
A = 2 B = 1
Therefore:
Prediction = A
20. KNN Regression Example
Suppose K = 3.
The three nearest houses have prices:
20 lakh 25 lakh 30 lakh
Average:
Prediction = (20 + 25 + 30) / 3 = 75 / 3 = 25 lakh
Therefore:
Predicted Price = 25 lakh
21. KNN Using Python
The scikit-learn library provides KNN algorithms.
Installation
pip install scikit-learn
Simple Classification Example
from sklearn.neighbors import KNeighborsClassifier # Training data X = [ [1], [2], [3], [4], [5], [6] ] # 0 = Fail # 1 = Pass y = [0, 0, 0, 1, 1, 1] # Create KNN model model = KNeighborsClassifier(n_neighbors=3) # Train model model.fit(X, y) # Predict prediction = model.predict([[4.5]]) print("Prediction:", prediction[0])
22. KNN with Feature Scaling
A more realistic example:
import pandas as pd from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler from sklearn.neighbors import KNeighborsClassifier from sklearn.metrics import accuracy_score # Load dataset data = pd.read_csv("students.csv") # Features X = data[["StudyHours", "Attendance"]] # Target y = data["Pass"] # Split data X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.2, random_state=42 ) # Scale features scaler = StandardScaler() X_train_scaled = scaler.fit_transform(X_train) X_test_scaled = scaler.transform(X_test) # Create KNN model model = KNeighborsClassifier(n_neighbors=5) # Train model.fit(X_train_scaled, y_train) # Predict y_pred = model.predict(X_test_scaled) # Evaluate accuracy = accuracy_score(y_test, y_pred) print("Accuracy:", accuracy)
23. KNN Regression Using Python
For regression, use KNeighborsRegressor.
from sklearn.neighbors import KNeighborsRegressor # House size X = [ [500], [700], [900], [1100], [1300] ] # House prices y = [ 2000000, 2800000, 3500000, 4300000, 5000000 ] # Create model model = KNeighborsRegressor(n_neighbors=3) # Train model model.fit(X, y) # Predict prediction = model.predict([[1000]]) print("Predicted Price:", prediction[0])
24. KNN Evaluation Metrics
Different metrics can be used depending on the task.
Classification
Common metrics include:
- Accuracy
- Precision
- Recall
- F1-score
- Confusion Matrix
- ROC-AUC
Example:
from sklearn.metrics import accuracy_score accuracy = accuracy_score(y_test, y_pred) print("Accuracy:", accuracy)
Regression
Common metrics include:
- MAE
- MSE
- RMSE
- R²
Example:
from sklearn.metrics import mean_absolute_error mae = mean_absolute_error(y_test, y_pred) print("MAE:", mae)
25. Advantages of KNN
- Simple to understand.
- Easy to implement.
- Can be used for classification.
- Can be used for regression.
- No complex training process is required.
- Can model nonlinear decision boundaries.
- Naturally supports multiple classes.
- Useful for smaller datasets when computation is manageable.
26. Limitations of KNN
- Prediction can be computationally expensive for large datasets.
- Requires appropriate feature scaling for many numerical datasets.
- Sensitive to irrelevant features.
- Sensitive to the choice of
K. - Can be affected by noisy data.
- Performance can degrade in high-dimensional spaces.
- Requires storing the training data.
- Distance calculations can become expensive with many observations.
27. Applications of KNN
Healthcare
- Patient classification
- Disease classification
- Medical pattern recognition
Banking
- Customer classification
- Credit-related classification
- Fraud-related pattern analysis
E-Commerce
- Product recommendation
- Customer similarity
- Customer classification
Education
- Student classification
- Performance prediction
- Learning pattern analysis
Image Recognition
KNN can classify images based on similarities between their feature representations.
Recommendation Systems
KNN can find users or products that are similar to a given user or product.
28. KNN vs Decision Tree
| KNN | Decision Tree |
|---|---|
| Uses nearest data points | Uses decision rules |
| Distance-based | Tree-based |
| Sensitive to feature scaling | Usually does not require feature scaling |
| Lazy learning algorithm | Builds a tree during training |
| Can be computationally expensive during prediction | Prediction is generally fast |
| Can perform classification and regression | Can perform classification and regression |
| Sensitive to choice of K | Sensitive to tree complexity |
29. KNN vs Logistic Regression
| KNN | Logistic Regression |
|---|---|
| Distance-based | Model-based |
| Classification and regression | Mainly classification |
| Non-parametric | Parametric |
| Sensitive to feature scaling | Scaling may be useful |
| Prediction can be slower | Prediction is generally fast |
| Uses nearest neighbors | Uses learned coefficients and logistic function |
30. Important Parameters in KNN
| Parameter | Meaning |
|---|---|
n_neighbors | Number of neighbors (K) |
weights | How neighbors contribute to the prediction |
metric | Distance metric |
p | Power parameter for Minkowski distance |
algorithm | Method used to find nearest neighbors |
Example:
model = KNeighborsClassifier( n_neighbors=5, weights="distance" )
With weights="distance", closer neighbors have more influence than farther neighbors.
31. KNN Workflow
Dataset ↓ Data Cleaning ↓ Feature Selection ↓ Train/Test Split ↓ Feature Scaling ↓ Choose K ↓ Calculate Distances ↓ Find K Neighbors ↓ Make Prediction ↓ Evaluate the Model
32. Real-Life Example
Suppose an online shopping website wants to recommend products.
A customer has purchased:
Laptop Mouse Keyboard
The system searches for other customers with similar purchase patterns.
If similar customers also purchased:
Headphones Laptop Bag USB Hub
the system can recommend those products.
The basic idea is:
Find Similar Customers ↓ Find Their Purchases ↓ Recommend Similar Products
This is an example of using nearest-neighbor concepts for recommendation.
33. Key Points to Remember
- KNN stands for K-Nearest Neighbors.
- It is a supervised machine learning algorithm.
- It can be used for classification and regression.
Krepresents the number of neighbors considered.- KNN uses a distance measure to find similar observations.
- Euclidean distance is commonly used for numerical data.
- Feature scaling is often important.
- Classification commonly uses majority voting.
- Regression commonly uses the average of neighboring target values.
- Small
Kcan make the model sensitive to noise. - Large
Kcan make the model less sensitive to local patterns. - Cross-validation can help select an appropriate value of
K.
Conclusion
K-Nearest Neighbors is a simple and intuitive machine learning algorithm that makes predictions based on the most similar observations in a dataset. It can be used for both classification and regression. Because KNN relies heavily on distance, appropriate feature scaling, feature selection, distance metrics, and selection of K are important for obtaining useful results.