Introduction

K-Nearest Neighbour (KNN) is a basic classification algorithm of Machine Learning. It comes under supervised learning. It is often used in the solution of classification problems in the industry. It is widely used in pattern recognization, data mining, etc. It stores all the available cases from the training dataset and classifies the new cases based on distance function.
I will explain the KNN algorithm with the help of the "Euclidean Distance" formula.
Euclidean Distance
The Euclidean distance formula is used to measure the distance in the plane. It is a very famous way to get the distance between two points.
Let's say the points (x1, y1) and (x2, y2) are points in 2-dimensional space and distance by using the Pythagorean formula like below.
Then, the Euclidean distance between (x1, y1) and (x2, y2) is,
d = √(x2 - x1)^2 + (y2 - y1) ^2
So, in short form,
Data Classification based on Euclidean Distance Formula
We have two different kinds of data mentioned below,
  • Training Data
    This set of data contains all the information included with classifications like below.
This training data includes classification with given x, y values.
This set of training data doesn't contain a classification type. So, it will be predicted.
Implementation
Import the below libraries.
  1. import csv
  2. import sys
  3. from collections import Counter
  4. from math import sqrt
Import training data set.
  1. x = []
  2. y = []
  3. z = []
  4. with open('training_data.csv','rt') as f:
  5. reader = csv.reader(f)
  6. for row in reader:
  7. x.append(float(row[0]))
  8. y.append(float(row[1]))
  9. z.append(row[2])
  11. coordinates = list(zip(x,y))
  12. input_data = {coordinates[i]:z[i] for i in range(len(coordinates))}
Import test data set.
  1. test_x = []
  2. test_y = []
  3. with open('test_data.csv', 'rt') as f:
  4. reader = csv.reader(f)
  5. for row in reader:
  6. test_x.append(float(row[0]))
  7. test_y.append(float(row[1]))
  9. test_coordinates = list(zip(test_x, test_y))
  10. print (test_coordinates)
Generate the Euclidean distance.
  1. def euclidean_distance(x, y):
  2. if len(x) != len(y):
  3. return "Error: try equal length vectors"
  4. else:
  5. return sqrt(sum([(x[i]-y[i])**2 for i in range(len(y))]))
KNN clissifier.
  1. def knn_classifier(neighbors, input_data):
  2. knn = [input_data[i] for i in neighbors]
  3. knn = Counter(knn)
  4. classifier, _ = knn.most_common(1)[0]
  5. return classifier
Generate Neighbours.
  1. def neighbors(k, trained_points, new_point):
  2. neighbor_distances = {}
  4. for point in trained_points:
  5. if point not in neighbor_distances:
  6. neighbor_distances[point] = euclidean_distance(point, new_point)
  8. least_common = sorted(neighbor_distances.items(), key = lambda x: x[1])
  10. k_nearest_neighbors = list(zip(*least_common[:k]))
  12. return list(k_nearest_neighbors[0])
Print Results.
  1. results = {}
  2. for item in test_coordinates:
  3. results[item] = knn_classifier(neighbors(3,input_data.keys(), item), input_data)
  5. print (results)
Output
Here, x and y data have been classified into different groups. I have attached the zipped Python code. Python 3 or above will be required to execute this code.

Conclusion

K-Nearest Neighbor algorithm is an important algorithm for supervised learning in Machine Learning.