KNearest Neighbors (kNN) is one of the classification algorithms in Machine learing. Since, KNN simply memories or stores the rules in memory, we can also say that it does not follow actual machine learning paradigm.
Before going to implementation, let us build some standard notation so that it is easier to follow the code in the implementation section (next post):
X_training = given training data
Y = labels for your given training data
X_test = new data (For which we need to predict the labels)
The whole algorithm can be divided into three major steps:

Finding most nearest neighbors (similar data instances) from your training data for a given test data (X_test)
Let's say we have total 20 training data, and you find out 4 training instances as nearest neighbors for one of your test data

Once you get the nearest neighbors from your training data, collect all the labels of your selected training data
In our case, we have 4 training instances as nearest neighbors. So, we will collect labels for all these 4 training data.

Finally, predict the label of your test data (X_test) based on majority count.
In our case, suppose 3 out of 4 training instances have the same label. Then, the majority count
will assign the label to new data point
The K
defines the number of neighbors that the algorithm will collect for making the prediction of your new data.
Example¶
Suppose, we have a data set of a students with features : weight and height and labels as "Asian, European, American" as follows:
from IPython.display import HTML, display
import tabulate
table = [["Height(cm)","Weight(kg)","Class"],
[169, 60, 'Asian'],
[171, 59, 'Asian'],
[172, 70, 'European'],
[179, 69, 'European'],
[170, 75, 'Asian'],
[175, 80, 'American'],
[176, 79, 'American'],
[180, 71, 'European'],
[171, 76, 'American'],
]
display(HTML(tabulate.tabulate(table, tablefmt='html')))
Now, suppose new student enters the class with feature
Height : 168
Weight : 65
Which class this new student belongs to?
Now, let us use some distance measure between this new point and all the training data points as follows:
sqrt((169168)^2 + (6065)^2) = 5.09
import math
def distance(p1, p2):
sq_distance = (p1[0]  p2[0])**2 + (p1[1]  p2[1])**2
return math.ceil(sq_distance**(1/2))
table = [["Height(cm)","Weight(kg)","Class", "Distance"],
[169, 60, 'Asian', distance([169, 60], [168, 65])],
[171, 59, 'Asian', distance([171, 59], [168, 65])],
[172, 70, 'European', distance([172, 70], [168, 65])],
[179, 69, 'European', distance([179, 69], [168, 65])],
[170, 75, 'Asian', distance([170, 72], [168, 65])],
[175, 80, 'American', distance([175, 80], [168, 65])],
[176, 79, 'American', distance([176, 79], [168, 65])],
[180, 71, 'European', distance([180, 71], [168, 65])],
[171, 76, 'American', distance([171, 76], [168, 65])],
]
display(HTML(tabulate.tabulate(table, tablefmt='html')))
From the result table, let's select k=3, neighbors having minimal distance(nearest points)
a. 169 60 Asian 6
b. 171 59 Asian 7
c. 172 70 European 7
So all possible labels in our final result is : ['Asian', 'Asian', 'European']
With majority vote, we can classify the new student as 'Asian'