Python Machine Learning Tutorial #6 - KNN p.2 - How does K Nearest Neighbors Work?

Key Takeaways

hello and welcome back to another machine learning tutorial so in today's video we're gonna be going through implementing the k-nearest now neighbors algorithm but before we do that I'm gonna talk about exactly how it works like in mathematics and yeah so if you guys are interested in learning about how this works please watch the entire video and then near the end is where I'm gonna implement it because it won't take that long to implement it but if you guys are more interested in the code you can either go look at the text-based version at Tech with Tim net where I'm also gonna have like descriptions of what's going on and all the code that I write or you can just skip forward into the video until when you see that I'm done drawing I don't know how long it's gonna take me to explain because it is a bit more complicated than linear regression but again it's not that crazy difficult okay so let's talk about the K nearest neighbors algorithm and how does this work well as we already know K nearest neighbors is a classification algorithm and the way that it works is given a data point so likes may be something like this it attempts to classify this data point with one of the classes that it knows so in this case our three classes would be well red we have green and we have blue okay now obviously these would most likely represent something but for our cases we're just gonna use colors because it's kind of easy to see and this black is gonna be well our question mark because we don't know what classicism we're trying to predict it so the way that we predict this point essentially is we look for groupings of data points right so you can see and I'm just this is not what the algorithm does this is what we're kind of doing as humans okay we see kind of groups right so we see this group of red we see this group of blue we see this group of green and if I asked you well where does this black point belong most likely you would probably say red or blue right because it's closest to blue or red I would say it's closer to red and that is where you might say that this belongs to you might say belongs to red because well it's closest to that so it would make sense if it's a red color right and that is exactly what our algorithm does now he works a bit more advanced than this but essentially it looks for kind of groupings of data points right and I'll show I'll tell you how it works but and then it will pick the closest point to this black right here and say okay so it is gonna be that class now what does this this K me so I keep saying K nearest neighbors well K is actually known as a hyper parameter and it stands for the amount of neighbors that we are going to look for so I'm just gonna do an example with K equals three okay and go through exactly what happens so given our black data point here alright and you know what actually let's just move it for the first example to be kind of easier to understand okay I'm just gonna move it right here if we have this parameter as K equals three it means we are actually gonna look for three neighbors to this black point so we're gonna find the three closest points out of all of this data to this black point so I would argue that that those points would be probably these three points right like the ones I just put the black dots on okay these three red points now once it finds these three points these points are gonna have a vote and essentially our program is gonna look at what class these points are so you can see like this one's red they're all red and they're gonna vote now since these points are red they're gonna vote for red so we're gonna get a vote of red is three green is zero and blue is zero now because red is the Heintz highest a current occurrence of that vote we are going to classify this point as being red and that is essentially the way that it works if I picked K equals five what we would look for the five closest data points now let's just I know this might not be the closest point but I just wanna do it for example let's say we have that other red point and let's say this blue point is close to this black dog maybe it's moved like over here okay what's gonna happen now is the exact same thing we're gonna look at these five data points that are the closest to this black dot and we're going to say okay we have four red so this is four I should probably have just erased that and so I'm trying to write over it and we have blue which is one okay so red four and blue one and because well red is greater than one and is the highest occurrence we are going to classify this point as red and obviously I think we would all say that is probably an appropriate classification so that is essentially how that works now let's go more into some more detailed math okay so let's say I plot my data point here okay kind of in between two clusters of data so again how does this work right so actually let's talk about why we're gonna pick an even value for K or sorry an odd value for K so let's say k equals five let's let's do this example with K equals five then we'll talk more about the math so I would say the closest data points are probably this one this one this one this one and you know what I want to say it's this one as well okay so we have two blue data points and three green data points now we see that we since we have three green and two blue we're gonna classify this as green but what if I said K equals four and instead of five so cross that out k equals four well now this data point I'm gonna scratch that out just assume that's not there now we have two green points and two blue points so how do we pick which data point that we're going to classify this as well that is it obviously why we need to pick K at to be a odd number so one three five seven nine right so that no matter what we always have a winner and we can decide on a class because right now we don't know which class this is because we'll we had a tie in terms of the voting okay so that's why we pick K to be a odd number all right so now let's go into the math so how does it actually do this what what are the mathematical methods well um you know what let's just actually scrap or I don't know what I just did there what the heck okay can I undo that okay one second how do you make this fullscreen exit out of that there we go okay sorry I don't know what I did there so let's uh scrap all this and let's actually just talk about how we get distance so remember we were saying here like if this is I blocked at a point and we had a maybe a green data point here and we had like another green data point here and another green data point here well we could probably tell this one's the closest but the computer needs to do some math to determine this right and so how does it actually know how which point is closer to which point well it's gonna draw a line from one point to the other point and it's going to find what's known as the magnitude of this line okay um you can just say that's em whatever any value for the magnitude so how can we actually determine the magnitude of this line and then based on that what are we gonna do with that so essentially let's just draw our data point again and let's call this p1 okay and in 2-space it's gonna have coordinates of x1 and y1 now let's draw another point and let's just make it a little orange point here and let's call this data point p2 okay it's gonna have coordinates x-two and y-two so based on these values just say it's a line here how do we find the magnitude of this line well there's a bunch of different ways that we can actually do this but the way that I'm gonna do it is called Euclidean distance now this is I believe the default one that our k-nearest a breeze uses it's probably one of the simplest ones and all the other ones kind of work similarly to this so essentially Euclidean distance is the absolute distance from here to here and how do we get that so we're inside D which stands for distance so you can change this to do K is equal to the square root all right it's a big square root of x2 minus x1 squared plus y2 minus y1 squared and this will apply again to any space coordinates so if I have like an X Y Z coordinate so maybe in three dimensions and we have another coordinate you're gonna do the exact same thing except what you'd add here is you'd add z2 minus z1 squared okay and you just continue the square root like that but we don't need that portion because we're not in three space so essentially what this is gonna do is will give us that absolute position now if we want to prove this on like some standard numbers just to give you an idea if we say like this is zero and this is zero and we say this is zero and this is four well what is the distance here right what's the distance between x1 y1 to x2 y2 well we're just far away on the y axis so it should be four so let's plug this into our formula and see if we get this so we x2 - x1 well that's zero squared okay plus y2 minus y1 what that's 4 so we have 4 squared so we can actually just cross out this 0 and this plus cos well that's nothing so we get the square root of 4 squared which is equal to 4 or you could say it's equal to the root 16 which is equal to 4 right and that gives us the distance for our line so Wow I just did a lot of math on here ok so now that we know that we can find the distance between all these different points here okay I'm just trying to do that to show you where I'm actually writing and based on those distances we can determine where which the closest neighbors are okay so let's do an example in 3-space to wrap it up and then let's implement our algorithm so I always draw my grids kind of weird for three sites okay so this is our three dimensional grid now the reason I'm doing this is because obviously well we have like six attributes or six features that we're going to be using to determine our data points and that means we have to plot them in three dimensions so this is the exact same thing as two dimensions except our data points are just gonna have three coordinates so instead of XY we're gonna have X Y Z right and this is I just want to show you how this works kind of in theory - okay so again we have points let's do one more points here and let's do our data point right maybe here okay now what we have to do is we have to determine like what the XY value of these this is XY value of this and XY value of this and then we have to compare based on how many neighbors we're looking for which point is which now this is where I want to get into that hyper parameter of K so what if I say K equals 9 so right now you would probably say that we want to classify this point as red because it's really close to the red data points but if I put a value of K equals 9 and we start looking for the closest points - Takai well we get these four okay but we also get like one two three four five let's imagine these move over a bit okay so what's happening now well since we picked our K to be way too high what's happening is we're now looking at points way side of the range of our data point right and that means we've found these points over here and we've said that this is going to be blowing into the purple group because well we pick too many values for K so this is just showing you an error that you can run into if you pick too many values okay so I think that is almost about it for what do you call it all this stuff I think the last thing I'm going to talk about is just some limitations to this algorithm and then maybe in the next video we're gonna implement it because it won't take very long and I realize I'm already at 11 minutes but I needed to explain this to you guys ok so some limitations well you may have already noticed that saving this model is not going to do anything for us meaning that's a like it is very computationally heavy so right now I'm only doing I don't know what is 5 10 14 data points and 15 if you include this one okay and every time that I want to classify this point I actually have to find the distance between this point and every other point right I have to I have to figure out what the distance is between every other data point that exists on this grid now this doesn't seem like a lot when you're only doing it 14 times but you can imagine that computation on tens of thousands of data points takes a long time and the reason we have to do that is because we have to know the distance to every data point so we can figure out which ones are the closest to our point right so when we save this model like you can save it if you want to but essentially it has to save every single piece of training data that we've given it every single piece because it has to look at every single data point every time we make a prediction and that means our predictions take a long time and this algorithm is essentially it's useless to train beforehand because it has to constantly keep looking at every data point before it can make a prediction on whatever data point we give it so that means that our time is going up linearly rather than being constant which would be what e-codes constant is an example of like linear regression where it doesn't matter how many times we try to predict using our models since we just created a function we can just use that function right and it takes constant time okay so I think I'm going to wrap the video up here as always if you guys have any questions please feel free to leave one in the comment down below and I'll try to help you out as best as I can and if you guys enjoyed the video please make sure you leave a like I will see you again in another one [Music] you