Building
k-Nearest Neighbors Algorithm
from Scratch in Python
Without relying on high-level libraries
1 ANSHUMAN JHA
Building K-Nearest Neighbours Algorithm from Scratch in Python
Table of Contents
1. Introduction
2. Fundamental Concepts
3. The Structure of a K-Nearest Neighbours
4. Implementation K-Nearest Neighbours from Scratch in Python
a. Load and Prepare Data
b. Distance Calculation
c. Find Neighbours
d. Make Predictions
i. Classification
ii. Regression
e. Evaluate the Algorithm
f. Diagrams and Visualizations
5. Conclusion
2 ANSHUMAN JHA
Building K-Nearest Neighbours Algorithm from Scratch in Python
1. Introduction to K-Nearest Neighbours Algorithm
k-Nearest Neighbours (k-NN) is a simple, intuitive, and effective algorithm used for both classification and regression
tasks. It is a non-parametric, lazy learning algorithm, which means it makes no assumptions about the underlying data
distribution and performs computations only when it is needed, i.e., during prediction time. In this article, we'll explore
the fundamental concepts and steps involved in building a k-Nearest Neighbours algorithm from scratch in Python,
without relying on high-level libraries.
2. Fundamental Concepts of K-Nearest Neighbours Algorithm
• Distance Metric: k-NN uses a distance metric to measure the similarity between data points. The most
common distance metric is Euclidean distance, but other metrics like Manhattan distance can also be
used.
• Voting Mechanism: For classification tasks, the algorithm assigns the class most frequently represented
among the k nearest Neighbours. For regression tasks, the algorithm calculates the mean or median of
the k nearest Neighbours.
• Choosing k: The choice of k (number of Neighbours) is crucial. A small k can lead to noisy predictions,
while a large k can smooth out predictions too much, potentially missing important patterns.
3 ANSHUMAN JHA
Building K-Nearest Neighbours Algorithm from Scratch in Python
3. The Structure of a K-Nearest Neighbours Algorithm
This Structure includes the steps and sub-steps with appropriate labels and connections. Each step corresponds to a
function or a key part of the process described in the provided implementation.
4 ANSHUMAN JHA
Building K-Nearest Neighbours Algorithm from Scratch in Python
4. Implementation in Python
Let's implement a simple K-Nearest Neighbours Algorithm in Python.
Step 1: Load and Prepare Data
First, we'll import necessary libraries and prepare a simple dataset for demonstration.
import numpy as np
import [Link] as plt
from collections import Counter
# Sample dataset (for simplicity, we use a small dataset)
data = [Link]([
[2, 4, 0],
[4, 2, 0],
[4, 4, 0],
[6, 4, 1],
[6, 6, 1],
[8, 6, 1]
])
# Split into features and labels
X, y = data[:, :-1], data[:, -1]
Step 2: Distance Calculation
We'll implement the Euclidean distance function.
def euclidean_distance(point1, point2):
return [Link]([Link]((point1 - point2) ** 2))
# Test the distance function
point1 = [Link]([2, 4])
point2 = [Link]([4, 2])
print(euclidean_distance(point1, point2)) # Output should be 2.828
Step 3: Find Neighbours
Next, we'll implement a function to find the k nearest Neighbours.
def get_neighbors(X_train, y_train, test_point, k):
distances = []
for i in range(len(X_train)):
dist = euclidean_distance(X_train[i], test_point)
[Link]((X_train[i], y_train[i], dist))
[Link](key=lambda x: x[2])
neighbors = distances[:k]
return neighbors
# Test the neighbors function
test_point = [Link]([5, 5])
neighbors = get_neighbors(X, y, test_point, k=3)
print(neighbors) # Should print 3 nearest neighbors
5 ANSHUMAN JHA
Building K-Nearest Neighbours Algorithm from Scratch in Python
Step 4: Make Predictions
For classification, we'll use a voting mechanism to predict the class. For regression, we'll calculate the mean of
the nearest Neighbours.
Classification
def predict_classification(X_train, y_train, test_point, k):
neighbors = get_neighbors(X_train, y_train, test_point, k)
output_values = [neighbor[1] for neighbor in neighbors]
prediction = Counter(output_values).most_common(1)[0][0]
return prediction
# Test the classification prediction
print(predict_classification(X, y, test_point, k=3)) # Output should be the predicted class
Regression
def predict_regression(X_train, y_train, test_point, k):
neighbors = get_neighbors(X_train, y_train, test_point, k)
output_values = [neighbor[1] for neighbor in neighbors]
prediction = [Link](output_values)
return prediction
# For regression, we would need a dataset with continuous labels
Step 5: Evaluate the Algorithm
We'll create a simple evaluation function to calculate the accuracy for classification tasks.
def accuracy(y_true, y_pred):
correct = [Link](y_true == y_pred)
return correct / len(y_true)
# Prepare test data
X_test = [Link]([
[3, 3],
[7, 5]
])
y_test = [Link]([0, 1])
# Make predictions
predictions = [predict_classification(X, y, test_point, k=3) for test_point in X_test]
# Calculate accuracy
print("Accuracy:", accuracy(y_test, predictions))
6 ANSHUMAN JHA
Building K-Nearest Neighbours Algorithm from Scratch in Python
Step 6: Diagrams and Visualizations
Visualizing the decision boundary of k-NN can help in understanding its behavior. Here's a simple visualization
for our example dataset.
def plot_decision_boundary(X, y, k):
h = 0.1
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = [Link]([Link](x_min, x_max, h),
[Link](y_min, y_max, h))
Z = [Link]([predict_classification(X, y, [Link]([x, y]), k) for x, y in zip([Link](),
[Link]())])
Z = [Link]([Link])
[Link](xx, yy, Z, alpha=0.3)
[Link](X[:, 0], X[:, 1], c=y, edgecolor='k', marker='o')
[Link](f'k-NN Decision Boundary (k={k})')
[Link]('Feature 1')
[Link]('Feature 2')
[Link]()
# Plot decision boundary
plot_decision_boundary(X, y, k=3)
5. Conclusion
We've implemented a k-Nearest Neighbours algorithm from scratch in Python. We covered the fundamental
concepts, including distance calculation, finding Neighbours, making predictions, and evaluating the algorithm.
We also visualized the decision boundary to understand how the algorithm makes predictions. This
implementation serves as a solid foundation for understanding and utilizing k-NN in more complex scenarios.
Constructive comments and feedback are welcomed
7 ANSHUMAN JHA