Hello and welcome back to the course on Machine Learning.
In today's tutorial we're going to talk about the k nearest neighbors algorithm.
All right so let's get started.
So let's imagine that we have a scenario
where we have two categories already present in our data set.
So we've identified two categories
and one is category one on the left which is red.
Category two is green on the right.
And for simplicity's sake we're just going to
take into consideration two variables or two columns in our data set.
So all of this grouping is happening based on these two columns x1 and x2.
And now let's say we add a new data point into our dataset.
The question is
should it fall into the red category or should fall into the green category?
How do we decide that?
So how do we classify this new data point to a cluster of files
as a, red data point or a green data point?
And that's where the k nearest neighbors algorithm will come to assist us.
At the end of performing, this algorithm will be able to identify
whether it's a red or green point.
And in this case, the point turned out to be red.
So how does the k nearest neighbor algorithm work?
How did it do it?
Well, we're going to build a step by step rule guide to the kernel.
And after we've built
it we're going to actually perform it manually to see how it works.
And as you'll see it's a very very simple algorithm.
All right.
So the first step is to choose the number k of neighbors
that you're going to have in your algorithm.
So you go to
you have to identify whether k is equal to 1 to 2 three five or some other number.
And one of the most common.
A default values for k is five.
The next you need to take the k nearest neighbors
of the new data point according to their Euclidean distance.
Now here you can.
You don't have to use Euclidean distance.
You can use other distances such as the Manhattan distance
or any other distances that you might be considering,
but in most cases the Euclidean distances are used.
So we're going to stick to those.
So once you've taken the nearest neighbors among these k
neighbors, you need to count the number of data points in each category.
So how many data points fell into one category, into the other category,
and so on.
If you might even have more than two categories in your data set.
So you just need to calculate how many fall into each category.
And then you need to assign the new data
point to the category where you counted the most neighbors.
As simple as that.
That's why it's called K-nearest neighbors.
And then your model is ready.
As you can see, it's
a very simple algorithm and model which is going to do a manual exercise
right now to really solidify this knowledge.
So let's move on to that.
So here we've got the new data
point has been added to our scatterplot as we saw previously.
How do we find the nearest neighbors of this new data point.
Well let's have a look at the Euclidean distance that we're going to use.
So Euclidean distance is a very basic type of distance that we define in geometry.
It's the one we use in geometry.
And basically if you have two points over here p1 and p2,
then the distance between the two points is measured according to this formula.
So x two minus x one.
The difference between the x coordinates and then squared
plus the difference between the y coordinates squared.
And then you take a square root out of all of that.
And that is basically if you look at it this way it's a right angle triangle.
And so you're taking you're taking one cathedral's and you're squaring it.
You're taking the other thing, you're squaring it.
You're taking the you're adding them up.
You're taking the square root.
And that gives you the length of the hypotenuse.
So there we go.
And that's how Euclidean distance work.
Again you could use any type of distance.
But this is the geometrical distance.
And this is the one we're going to stick to.
So basically on a scatterplot a two dimensional scatterplot
we can just draw the lines and see what is closer.
So here's our new data point.
How are we going to identify which are the closest five neighbors.
So basically we just look at them and we see the distances here.
So we can see that's the closest one.
That's probably the second closest one the third closest fourth closest
fifth closest. So let's outline those.
There we go.
So now all we have to do is step three.
Among these kind of k neighbors.
Count the number of data points in each category.
You can see in category one.
In the red one we have three neighbors.
In category two we have two neighbors.
So therefore step four assign the new data point to the category
where you counted the most neighbors.
That means we need to assign it to the red category.
As simple as that. There we go.
Now we have classified this new point and your model is ready.
There we go.
It's a it's a very straightforward algorithm.
One of the simplest you can think about it.
So it's very good to get this section started with a simple example like that.
And also we're going to have a look at some practical exercises
and had learned we'll show you around R and Python.
I look forward to seeing you next time.
And until then enjoy machine learning.