K-Nearest Neighbor from scratch - Machine Learning Python

Key Takeaways

what's going on everybody hope you're doing awesome so in this video I want to show you how to code teenage neighbor classifier from scratch in Python and I'll show you multiple ways of doing it first in the inefficient in the most intuitive way and then also in the more vectorized way for that ultra efficient implementation so without further ado let's get right into the code first of all we want to import numpy as NP I'm gonna just declare our class K nearest neighbor then let's just do some skeleton code of how the code is going to look like we're gonna have in it we're gonna sending K oh and I'll assume that you can know how Keener's neighbor works and intuitive way and this is more of the how you would do it then we're gonna have trained self X&Y we're gonna send in our data X and then the target class for each data point predict and then we're just going to send in some X test then we're gonna have compute distance and then lastly we're gonna have a see define predict labels and then we're just gonna have if name main and we're gonna run Keener's neighbor from here all right so the Train part is pretty easy so the training part of Kenya number is just loading the entire data into memory and yeah let's do it in it as well soft our K is K and and let's see here so what we want to do in a prediction we want to call compute distance sending X test so let's do here X test like that then so we compute the distances write the for each example in our test data we want to check what is the distance to every point in the training data but that's what we do with the compute test and then we want to do let's see here we want to do return self-thought predict labels so after computing those distances we want to for each example you want to check well what are the K closest ones and what is the majority class of those K closest ones so let's do the compute distance first let's just do see here yeah so we're gonna do it in the as I said the naive inefficient way first so we're gonna do numb let's see we're gonna do numb test I'm gonna do just to check the shape and then numb train is gonna be self that extreme that shape of zero then let's just define the distances to be MP dot zeroes of shape num test and num train so each row is a test example and then each column is that is the distance to that specific training example so the naive way is just iterating through each test example then each training example and then just doing distances of I to J so the distance between test example I and training example J we're gonna do compute the the Euclidean distance so we're gonna do NP dot square root of n P dot sum of X test I'll see X test right like this and then - self that X train J - all and what i'm doing here is it I'm looking at the ight test example and then all of the features and then the Jade training example and all of the features let's see if we're gonna do this squared right here this and take the sum like this I think that's correct yeah great and then at the end we want to just return the distances analysis we have done to compute distance and now we want to actually when we have the distances we want to find what are the closest ones and so what is the majority class for each what is there the majority closest majority class for the closest K points to each test example and that's our prediction so here we want to do num test let's do distances shape zero right because distances will be the number of training and test examples and then number of training example as the columns so we can do by prediction to be MP dot zeros of num test because we want the prediction for let's see we want the prediction for for each single test example now we're gonna iterate through so we're gonna define range and um test first thing we're gonna do is we're gonna use we're gonna look at the indices so we want to find what are the indices for this the distances which are the smallest distance so we are going to use NPR art sort we're going to ampere arcs of distances of i2 all and this will be the Y indices so essentially let's see maybe I should show you an example of this let's say we have distances and let's say we would have AI don't know 1 5 minus 3 and n minus 10 something like this import numpy SMP and then so the shortest distance here this is just a single test example right and this is the distances to all four training examples if we do MP dot org sort of distances we get back this right here which says that the third index so this one is the one that is closest alright maybe this doesn't make too much sense because the distance can't be negative but well you get the point right we just look which one is the smallest of those and that's the one we get first in our arc sort then what we're gonna do is we're gonna do K closest classes we're gonna check in Y train or those specific Y indices right and then we were gonna do just to self dot cake because we don't want every we don't want the entire training data we just want K points and then we're going to ask type int right so now we get an array here of K point K classes rather that are the closest to that specific test example then we're just going to do by prediction of that test example is we're gonna count and fib in count of K closest classes so what this does is it count how many times each class was in that array so let's do an example again let's do classes are in P dot array until let's say we have the classes one one three four and three again or and then let's say two another three right so we can see here that the majority is three right and then the class one is the the second most frequent if we do n P dot bin count of classes we see here that okay for the zeroth class K it start from zero the zero class has zero in it right and in this array and the first class has two that that is of that class second class is zero and then the third class we have three of the third class right so what we can do is we can take MP dot Arg max of MP dot bin count of classes we'll see that three is the most frequent one that's exactly what we want right that's our prediction for that specific class all right great so now let's just return wipe read and yeah that should be it what we want to do now is we just want to have some example data you can download it from my github if you want to follow exact so we're gonna do X is MP dot load txt and I'll show on the screen how the data looks like example data it's just in another folder we're gonna load that and then the limiter is a comma then Y will be MP dot load txt and then it pretty much the same thing except targets dot txt all right now let's see invalid syntax hmm yeah there should be a Prentiss here then let's do KN is K nearest neighbor let's do our know K equals three and first we're going to train so we're gonna do cane and our train remember this training part is just loading the entire data and then we want to by prediction my prediction is Canon dot predict of X and so you would normally have some training data and some test data and you would send them in sort of separate but we're just gonna do the prediction on the exact same data and then let's also do so let's do print accuracy and then let's do yeah so some of why pred equals y and then divided by y a shape of 0 just to get some sort of accuracy of of our model let's run this and we get some error let's see what it is it should be NP dot-org max as we did and then bin count alright but I actually know that's not correct for this one we should get 93 if I remember correctly all right so I think I found the mistake right here we don't want to take the the sum and then square it we want to square everything and then and then take the song yeah so that should be more like it let's see if this works yeah and then we get 92% and that should be correct for this data all right as I said so this is the intuitive the inefficient you don't want to do this but if you just want to gain an understanding of it this is fine but let's improve on this so let's do this is using two loops and then in the prediction here we're gonna do number of loops and let's say it's two by default and yes we're gonna do if num loops is equal to two then let's do what we what we just did and setup computer since two loops and then let's do if num loops is one then let's do pretty much the same thing but we're gonna change this to one loop right and we haven't implemented this yet but let's start so let's define compute distance one loop and then self and X test all right so we want to use some sort of vectorization to be able to do this and what we can do is we can first define num test similarly as we have done here this and then we can just remove the outer loop so let's do for I in range of num test okay so now what we need to do is we need to compute the distance from a specific test example to all of our training examples at the same time in a single line so the way to do this is we can do distances of I - all right before we did distances from I for specific I J now we do I to all then we're going to do NP dot square root and then we're gonna do NP dots some so pretty much the same right here then we're going to do self dot X train - X test of I - all and we're gonna square this see so we don't make the same mistake so we're gonna do another parenthesis here and then like this okay so what this does it this shape is let's say actually let's see print X shape so X is ninety by two we have nine examples and we have two dimensional data and and this X test I comma all it's just one comma two so when we subtract those we're going to for each training example point we're going to subtract our current test example point right and then since we square so numpy does this broadcasting which it subtracts for each row when the rows don't match and it's going to do it for each row yeah so yeah I think that should be clear and then one thing we need to do also is that we want to sum for axis equals 1 see if that's yeah so X is equals 1 right because we want to subtract for all of the features right using the equivalent distance and then we want to sum all of the the features and then square root of that and we do that for each training example in parallel all right great let's then return distances and now in the predict here let's do Namib equals two and let's run that and we get 93 let's change it number equals one and we don't get the correct thing okay let's see yeah so we want to let's see we want to close this parenthesis right here and then we want to sum using axis one and we want to close that parenthesis and then we want to close the square root parenthesis right here and then that should work yeah so we get the exact same result as using two loops as we did with one and now what we want to do is we want to do the as I said in the beginning the ultra-efficient the fully vectorized version so we're gonna do another function right here I'm going to define compute distance and then vectorized gotta send in the same thing and let's do a pass on this right now and then let's do else if and then let's do else we're gonna do run distances is one loop and we're gonna change this to vectorized okay and let's see here so actually I want to go through how this works before I actually do it so remember that we want to do to compute train - test squared right let's say we do this for a single vector or or just remember if those are two variables we can expand on this square operation so we can do this is train squared minus two train times test and then plus test squared okay this is just using the okay the formula if we expand this and it works the same way with vectors so let's say we actually do to Train equals MP dot random from trend let's do one comma C if we have a single example let's say we have four features and we have test which is also a single one one comma comma 4 and then we have number examples is train that shape of zero and then train ask out comment this one let's just use the one we did here the random ones and we're gonna train using train and we're gonna just send in numpy that zeros of a synonym examples yeah and that's it and then we're gonna predict on on test say like this why it's not defined yeah so this print here I just remove that as well yeah so what we want to do actually let's do just to make a little bit clearer later on let's do test - train and let's just reverse these ones like this and same thing here then like this okay so if we do that let's just do test distance so we just actually just a distance is MP dot square root and then we're gonna do MP dot some of test and an element Y squared right that's this part and we want to sum act is equals one and let's do keep DIMMs equals true just so that numpy doesn't change the dimensions of it when we sum to one we won't get shape like 1 comma 1 comma like this will get shape one by one so that's just what it does and then let's see we want to plus MP dot sum of train so I'm doing this part right now train squared and then keep themes equals true then let's move this a little bit and then act as equals one and then let's do minus two times MP dot some of test an element-wise train so this is just a dot product element-wise and then we sum it so let us compute the distance with the tulip version and call this the correct distance and then let's compute the difference between this correct distance and this distance we just compute it and take the sort of the difference and then sum them and hopefully this should then be a very very small value if if the implementation is correct and then as we can see here there seems to be something wrong so let's find the error yeah so again we get some sort of error here we need to have right here should have it like this and then we should close it yeah so it's just a parenthesis unexpected yeah so we don't have number ups when we do to get distance all right so what we get here is that there's actually no difference which means that this is the same as doing the two loop version all right so it works when we have so I mean this formula right here it works when we have two two vectors but let's say we have I don't know if train was ten examples instead and what we want to do is this part we're gonna change this part to do - - and then NP dot of test and then train transpose and why we do this is because remember we want each example in our train all the features to be multiplied and added with all of the test features right and if we do that for all of the examples then we would have in this case ten I guess one by ten right so if we do test 1 by 4 times 4 by 10 because that's train transpose then in the end we'll get 1 by 10 okay so the shapes add up and it does what we wanted to do it multiplies all the features in the test by all the features in the Train and it does so for all of the examples right let's now check if that works yeah okay so we get an error and first of all let's do access one right here right just to keep it keep it symmetric and then when we do keep them as equals true remember that this part right here will be a ten by one but as we've said this part right here will be a 1 by 10 I'm going to add them so we need to do transpose on this just to to be able to add the dimensions and yeah so we're using broadcasting here again on this one since this will be a one by one it will be added to each all ten of them try to implement this now in the in the general way remove this right here and let's bring this back and let's do this again XY and that predict of X and then wipe red and then remove so we just go back to what we had now we want to implement this computation vectorized right we're going to do SX test squared right so if we actually write that again we do X test minus X train squared X test squared minus 2 times X test times X train plus X train squared so this is the formula we just need to change this up a little bit so that we use the broadcasting from numpy in the correct way as well as yeah having the correct shapes so we're gonna do first MP dot son of X test element-wise and then AK is equals 1 keep Tim's equals true X train squared is gonna be impeded sum of X train squared X is equals 1 keep Tim's equals true and in the last I guess tricky part is the 2x test X train which will be MP dot dot X test self dot X train that transpose and then we just want to return and P dot square root I'm self-taught I guess itself no no self x test squared and then minus two times it's right here and then plus X train squared and that transpose just as we did before then let's see what I actually did in my implementation is I did self dot eps and then I added a small error term right here let's see and all of the square roots I just added self EPS so dot eps and I did that for all of the square root ones I don't think it's actually necessary but yeah just to make it more numerically stable if there would be something very very close to zero for some reason and let's see your ex train yeah we can't use extreme we need to use self that X train and yeah that should be it so that this is a very very compact formula and then yes let's do it now with number loops equals zero and let's see if we get back to it correct result and we do so that's awesome now we did a very general K nearest neighbor classifier and you can sort of choose which one you want to use of course the vectorize is gonna be fastest one loop is pretty fast and then two loops don't use that yeah but that's it thank you so much for watching the video and I hope to see you in the next one [Music]