Build Your First Machine Learning Algorithm

0:00Hi, Sean here, and welcome to this skill where we're going to start our PCEI journey by taking a look at a simple vanilla Python example that will introduce us to some of the most important AI and machine learning concepts. So, you know, if you've looked at Python examples in the past, you're probably aware of the fact that there are lots and lots and lots of libraries out there for helping you do machine learning and AI. And while those are wonderful tools, once you've actually learned the basics, they're also a great way, as I've heard someone say, I don't remember who it was, to do machine learning and AI in Python without knowing anything about machine learning and AI in Python. And I'm assuming that is not your goal here, is to just get by by running the right lines of code and, you know, copying and pasting the right functions. So what we're going to do here is we're going to take a look at the tremendously popular and also, I would venture to say, quite fun k-nearest neighbor algorithm, right? KNN is typically the abbreviation for that. And how to implement it using just plain old Python. All right. So that brings us to this thing that I have on my screen. And this is two graphs

1:19displaying data from a so-called synthetic data set that I created, right? This is not a real data set gathered from real people. It's just one that I generated using Python. And the idea here is that this data set contains the shirt sizes worn by people with different measurements, right? So we have the person's chest size and waist size, as well as their height and weight. And because there's four features here, we'll talk about that word in a little bit more detail later, because there's four features or dimensions here, we have to display that on two separate graphs in order to see the real picture, okay? So the idea here, and this is something that I'm sure many people out there can sympathize with me on, is that there's not really a hard line between any of these measurements for shirt sizes. And so it can often be very difficult when buying a new shirt to know which size to buy. So what we're going to do here is we're going to use Python and this KNN, right? K nearest neighbor algorithm, to write a program that will allow us to enter our measurements and tell us what the most likely correct shirt size will be for us based on this

2:36data. All right, this sort of use case is very common in machine learning, because basically it involves us making decisions not based on any hard and fast rules, right? Like if there were just hard and fast rules, like if, you know, shirt companies just gave us the exact measurements that they used to draw the line between small and medium and large, well, that would be really easy to write a program for, right? We would just be able to say, you know, if chest size is greater than this number, if waist size is greater than this number, then, you know, assign the following size to that, right? But as it happens, that's not the case. And so that's where machine learning algorithms can really start to come in handy. So anyway, coming back to this data set that we have here, let's just do a quick visual inspection of this to see, you know, what we're looking at, right? So as we can see, the, you know, the dividing lines between these different shirt sizes, given, you know, the different measurements that we have here, are fairly clear. They're not, you know, they're not always foolproof, right? For example, we see that there's this green one here where we might expect to see an orange one. And over here, we see that there's, you know,

3:52green where we might expect red or green where we might expect orange. But for the most part, our data is clustered in a way that's going to make it fairly straightforward for us to use this KNN algorithm to solve it. All right. So here's what we want to do, right? Here's the ultimate goal of what we're going to be doing here. We already know all of these data points and their corresponding sizes, right? And that is in, if you open up the CSV file that I've included with this skill, right? Here it is right here. This just contains, you know, an ID. You can pretty much just ignore that. That's just a unique identifier for each of these measurements.

4:33We have height in centimeters, weight in kilograms, chest in centimeters, and waist in centimeters, as well as the corresponding size for each of the data points or rows in this file. Okay? So the key point here is that we already know what shirt sizes these people with these measurements wear. But what we want to be able to do is create a Python program that based on this data will be able to predict where a new data point would fall, right? So if we have a new person whose measurements fall around here on these two dimensions and around here on these two dimensions, right? Which shirt size would they be most likely to need? Well, the first and most important thing to understand when getting started with machine learning with problems like this is that there's generally not a single so-called best approach for any one problem, right? There might be certain approaches that are better than others. And certainly there are approaches that just don't make sense for certain situations. But even a problem that's as straightforward as this one has a variety of different approaches, right? A variety of different algorithms or strategies that we could use to try and answer questions like this one, right? Like which is

5:52what shirt size would be best for this person here based on these measurements? So going back to the KNN or K nearest neighbor algorithm, I'm just going to say KNN from now on because I'm tired of having to edit out myself saying K nearest neighbor and, you know, butchering it, right? All right. But KNN, the way that this works or the solution to this problem that KNN proposes is to take this unknown data point and find which data points are closest to it.

6:27And then simply take the average of what those data points are, right? So let's just take a simple look at what this would look like if we wanted to make the decision for this one based on what the three closest points are. So let's say that these three are the closest points, orange, green, and green. And I'm just going to do this in two dimensions here because it's kind of hard to tell what's closest to what in four dimensions. But let's just imagine that these are the three closest points, green, green, and orange. Well, in this case, we would say that this should be green or large because there are more large data points that are closer to this one than medium. OK, so this is a very simple heuristic, a very simple algorithm for using data to make decisions. And the nice part about this is that it's also fairly straightforward to implement in Python, which is what we're going to do, as I said, in the rest of this skill.

7:24So anyway, with that in mind, in the next video, we're going to start implementing this algorithm so that we can use K nearest neighbor in order to assign shirt sizes to unknown data points.

0:00All right. Well, now that we've discussed the problem at hand and we know the algorithm that we're going to be using in order to help solve it, let's get started by implementing this algorithm. And once again, we're just going to be using plain old vanilla Python in order to do this because, you know, it'll really help us to focus in on some concepts and terminology, and also just use our problem solving skills to implement a basic machine learning algorithm. So here's what we're going to do. We're going to start off by creating a new file. And again, I'm just doing this in a simple directory. So you're just going to want to have Python installed if you're going to want to follow along. So I'm going to create a new file and we'll call this something like knnbasics.py. And the first thing that we're going to need to do here, and for now I'm just going to close these two images. The first thing we're going to do here is we're going to need to load this CSV file into our file, right? There's not really a whole lot we can do with our data until we have it in our program where we can manipulate it and, you know, work with it in different ways. So here's what this is going to look like. We're going to say import CSV, and this is a built-in module in Python, so this is still technically vanilla Python, right? We're going to say with open, and then we're going to open our file here,

1:16which is called shirt-sizes.csv, right? And you can download this from above in this skill if you want to follow along. All right, and then we're going to say as file, and all we really need to do to load this in is read in each thing as a line and then convert it to a list, right? It's going to be as simple as that. So here's what this is going to look like. We're going to say reader equals csv.reader file, and then we're just going to say rows equals list reader, okay? So that's all we need to do there, and now we should be able to print out our rows to the console by saying print rows, and if we run our program here, which we can do by saying, let's just wait for that there. There we go. We can do that by saying python3 knnbasics.py, your exact command for running Python may vary, but I'm going to be using Python 3 here for this course, and sure enough, we see that this has successfully loaded all of that data into our Python program. Now, notice that the first line here contains all of the column headers, and so there's probably a better way that we can do this by using csv.dictionary reader instead of csv.reader. So let's try that,

2:35and that should improve things a little bit for us. It's always a good idea to, you know, actually take a look at the data that you've loaded before you start working with it, which is, you know, hopefully what that little demo showed you, and sure enough, we see that this has id, height centimeters, weight kilograms, chest centimeters, and waist centimeters, as well as the size all in their own dictionaries, right? So each one of these dictionaries represents a separate data point that, you know, forms part of our data set. So it's at this point that I'd like to just pause for a moment and talk about a little bit of terminology that is going to be very relevant to us going forward. The first thing is you've probably already heard me say half a dozen times the word data set, right? Now, this one's pretty self-explanatory. It basically just refers to a large collection of data, right? So in our case, this is the shirt size data that we've been working with that we're planning on using for a specific purpose, okay? Now, inside that data set, we have a number of what are known as data points, all right? And a data point just refers to an individual collection of, you know, values in all of the columns that this data set contains,

3:53right? So if our data set were, I don't know, geographical data, and we had the latitude, the longitude, and the elevation of different points on Earth, then a single data point would consist of a latitude value, a longitude value, and an elevation value, right? So that would be one data point, okay? All right, so that's data sets and data points. And this brings us to two other words that you've already heard me use, at least I think so. And those are labels and features, right? So features in a data set basically just refer to the columns, right? Or the individual types of data that each data point can have. So in our case here, with this one that I just drew out, latitude, longitude, and elevation would each be features of the data set. And in our shirt size, right? Let's just open that back up here. We'll open up shirtsize.csv. The features in this data set are the person's height, weight, chest size, and waist size. Now, what about this size thing, right? Is this a feature? Well, this is actually what's referred to in many cases as a

5:10label because this is the thing that we're trying to predict using our machine learning algorithm, right? So in our case, we're trying to use these features, right? The height, weight, chest size, and waist size to predict what the shirt size should be for a given person. So that's the difference in machine learning between labels and features. The features are typically the things that we're going to use, that we're going to feed into the algorithm. And the labels are typically the things that we're going to be predicting with the algorithm, all right? That's just kind of a rough definition there, but that's the one we're going to use for now. So anyway, just to kind of draw that back on here, let me just hide all these things and bring my drawing back. Each data point has features, all right? Let's just write that here. And labels or, you know, a label could be one or multiple labels depending on how many pieces of information are contained in there. And in case you need a little way to help remember this, features are sort of like the clues, whereas labels are like the answers in whatever problem it is we're trying to solve,

6:26right? And, you know, these terms will become a little bit more useful as we go along, but I just wanted to get those out of the way right now, just while we're in the process of loading our data. All right. So at this point, we have our data set successfully loaded into our Python program. And so here's the next thing that we're going to do. We're going to create a function that will tell us the distance between any two points in multiple dimensions, right? And specifically with the four features that our data set here has. So, you know, this is going to be used in our KNN algorithm because when we have many points like this, right, when we have points here, and then we have a new point that we want to know the label for, we're going to need to figure out which of these points are closest to this point by basically just calculating the distance between this point and all of the other points in our data set. Now, this might sound computationally expensive, and it certainly can be for larger data sets, but we'll take a look at that in a little bit more detail, what some things that can be done to improve this are. But, you know, anyway, we're going to create a function that will just tell us for any two points, right, for example, this point and this point, how far away they are. All right. Now, the good news here

7:47is that there's a very commonly known equation for doing this, and this is called the Pythagorean theorem. I'm not going to try spelling that out because frankly, I'm not quite sure that I could do it right now, but the good news is that while the Pythagorean theorem is typically taught in two dimensions, right, a squared plus b squared equals c squared, it actually works for higher dimensions as well. So if we want to find the closest points in four dimensions, which our data set does have four dimensions, then we can generalize it to a squared plus b squared plus c squared plus d squared equals e squared, right? It works in higher dimensions as well. So here's what this is going to look like. We're going to create a function in Python called get distance, and this is going to take two points, right? We're going to call those point one and point two, and it's going to return the distance between them by basically just using the Pythagorean theorem. So here's what that's going to look like. First of all, we're going to need to access the values on each of these points. So let's just open up the output from our previous, uh, you know, from the previous time we ran the program. So we're going to want to get the height in centimeters. In fact, what I'm going to do is I'm just going to copy and paste these things here so that I won't have to type all of them out. All right, we'll copy those like so, and then I'm going

9:04to just paste that right here, and we're just going to use the, uh, keys there. All right, so we'll say, uh, height centimeter, weight kilograms, chest centimeter, and waist centimeters, and those are going to be the four dimensions that we're going to access on each point. So here's what this is going to look like is we're going to say dimensions. In fact, we'll call this something like dimension keys equals, and we're just going to put all of those in a list because that'll make it a little bit easier here. So let's just add commas to those and square brackets, and now we're just going to say four key in dimension keys. All we're doing here is we're just saying, okay, we have two points here, right, point one and point two. All right, um, how far are they in the x direction, and how far apart are they in the y direction, and we're just generalizing this to more than two dimensions. Okay, so anyway, here's what that's going to look like. We're going to say something like total equals, and then we're just going to say zero, and now we're going to say total plus equals, and then we're going to say p1, and then we'll get the key like so minus p2

10:21key, and we're going to square that, and you can square things in Python just by putting parentheses around these, and then using the double asterisk operator and saying two, right, so that's going to give us the square of the distance between these two points in that single dimension, and now we just need to return the square root of that total, right, that's how you solve the equation a squared plus b squared equals c squared is you can just say that c is equal to the square root of a squared plus b squared. All right, if this is giving you nightmares by the way that I'm writing algebraic equations out here, then please feel free to ignore them. I'm just using that to give a little bit more explanation behind what I'm doing here.

11:09All you really need to know though is that this function is going to do basically what it says in the name, right, it's just going to give us the distance between any two points in our data set as well as other points that we might want to label, all right, so this is going to be very important for implementing this algorithm, and so the last thing here we just we're going to say return math dot square root, and we're going to return the square root of the total, and so here let's just say import math up at the top, and that should be all we need to do. All right, so let's just test this out. In order to make sure that this is working, we're just going to get the distance between the first two points in our data set, and so here's what that'll look like. We're going to say print, and then we'll say get distance, and then we're going to use rows index zero and rows index one as our data points. Now let's just take a look at what those values are to get some idea of what those should be. So this is the first row here, and this is the second row here. All right, so as we can see they're fairly close to each other, and you can do the calculation by hand if you really want to know, but let's just run our application here, or run our script rather, by saying python3 knnbasics.py, and uh-oh, this is why we run our script to make sure that,

12:29you know, to make sure that it's working so far, because it's way easier to fix when it's nice and small like this than when you've tried to implement the entire algorithm and left a few things like this out. So you may have noticed previously, and here let's just go back to where we were before, let's just print out our rows again. You may or may not have noticed that the measurements here, even though we know that they're supposed to be numbers, Python has actually interpreted these as strings, right? So chest centimeter here is 100.8 as a string, which is a very different thing in Python from 100.8 as a number, and this is a very important thing to pay attention to when doing machine learning in Python, is you need to make sure you're getting the right data types. All right, so here's what we're going to do. We're going to do our first example of data cleaning, right? Data cleaning is where you take data that's not quite in the format that you need, or that has some other sorts of problems, and there's lots of problems that data can have, as you'll see later on in the course, and we're going to convert it into data that fits our purposes here for our program. So here's what this is going to look like. We're going to say, well, first of all, we'll create one called rows here, and we'll rename this one to rows raw,

13:47right? Basically meaning that that's the raw data, which is not quite in the format that we need it in, and then we're going to say rows empty list, and we'll say for raw row in rows raw, we're going to say that we want to append a new dictionary to rows, so we'll say rows.append, and here's what this is going to look like. We're just going to take height centimeters, and we're going to set that to, we'll parse this as a float here. We'll say float raw row, and then we'll say height centimeters there, and then we're just going to do that same thing with the other columns, right? So we're going to copy that, and I'll just paste that underneath like so, and we'll just change this one to weight in kilograms. In fact, I'll just copy this and paste it, all right? There we go. That'll help us avoid typos, and then we're going to do chest centimeters. We're going to replace that here like so, and then we'll do waist centimeters and replace this one here, all right? Now, there probably is a slightly more concise way that we could have done this here, but well, we'll just leave it the way it is. So anyway, oh, here, let's change that to row.append. I don't know why I wrote appends, and now let's print out our rows, and they should now be numbers, so let's just try that again, and sure enough, we see that these are

15:06now numbers, which means that we should be able to go back to testing our get distance function, so let's uncomment that here. We're going to run our code, and sure enough, that gives us the distance between those two points. Now again, I'll leave it up to you to figure out whether that is the right answer or not, but if you want to take my word for it, that is the right answer. So anyway, what we've done here is we've implemented a very important function that will tell us the distance between any two points, and so the next thing we're going to do is we're going to see how we can use this function to actually put the KNN algorithm together and make a decision for a new point.

0:00All right. Well, at this point, we have this get distance function, which will tell us how far apart any two points are in our data set. And we also are loading in all of our data and converting it to the right type so that these end up being numbers instead of strings as they were before. So really, all that's left for us to do here is write some logic that will use this get distance function to find the closest points for some unknown point that we want to add a label to.

0:32All right. So here's what this is going to look like. The first thing we're going to need to do in order to get the closest points is we're going to need to basically just create a function called get closest points. OK, so we'll say get closest points. And what this one's going to do is this is going to take an unlabeled point. All right. Let me just spell that like that. There we go. And it's going to take all of the points that we want to basically measure this unlabeled point against. Right. So we'll say something like labeled points for that argument. And the last thing that we're going to do is we're going to add one more parameter that will be the K. And in case you were wondering what the K nearest neighbors are, what the K was, that is in K nearest neighbors, K is basically any integer number that refers to how many of the nearest neighbors we're going to find that, you know, we'll get the labels from. Right. So K could be three. K could be five. Right. Typically, it's an odd number or even a prime number. Anything that, you know, we can use to avoid a tie. OK, so anyway, we're just going to you know, we'll probably use three just for our demo, but it's nice to design this function from the outset

1:50to allow us to pass in different values there. So here's what this is going to look like. We're going to loop through our labeled points and calculate the distance between each one of those and our new unlabeled point. So here's what this is going to look like. We're going to say for point in labeled points. All right. We're going to say in here what we're going to do is we're going to say distances and create a list there. What we're going to do is we're going to say distance equals get distance. All right. And then we're going to pass the point in as well as the or sorry here, we're going to pass the unlabeled point in first rather. And then we're going to pass in the new point, which is the, you know, labeled point that we're currently looking at. Awesome. So now that we have the distance, here's what we're going to do. We're going to append this onto the distances list by saying distances dot append. And then instead of just storing the number, we're also going to need to know what label is associated with each distance.

2:56We'll use that in order to, you know, return the appropriate label here in just a minute. And so we're going to say distances dot append, and we're actually going to add a dictionary onto this that will have the distance. All right. As one of the entries. So distance, distance, and then the label for that distance is going to be the label from the point here. And we can get that by saying point. And then we're going to get the size entry from that. All right. So that's what's going to happen there. So let's just test this out right now.

3:30We're going to say here, we'll just say print distances after we're done with that. And what we hope is that we'll have a list of dictionaries, each containing a distance value and the associated label for that value, because what we'll do after that is we'll actually sort this and get the closest points. So here's what that'll look like. Let's just run this, but instead of calling print get distance, we're just going to call, get closest points. And what we're going to do is we're going to create a new unlabeled point. Well, actually, um, one thing that's nice to do to test this algorithm out is because we already know what the label is for the first one here. We're just going to use the first point as our quote unquote unlabeled point. And then we'll use the rest of them in order to calculate what the label for this should be. Now, it's not always going to return the, the label that we know should be on this, just because this point might be in a weird position, right? It might be in the middle of a bunch of other points that have a different label, but nevertheless, it just makes it easy so that we don't have to come up with our own numbers here for each of these, uh, you know, for each of these features. So here's what this is going to look like. We're going to say, get closest points. We're going to say, um, here, up here, we have

4:49rows is what we want. So we're going to say rows index zero for the unlabeled point. And then for the labeled points, we're going to say rows index, and then we'll use a slice to get the rest of them. And then we'll say maybe three. It doesn't really matter what we pass in there at this point. Um, just matters that we pass in something. So let's give this a try. We're going to run our, uh, code and oops. Uh, the reason we're getting this is because we actually inadvertently removed the size, uh, from our rows. So we're just going to say size here. All right. And that's just going to be, um, raw row size, right? So we don't need to convert that to a number. In fact, we don't want to convert that to a number because it's not a number, right? It's just a size label.

5:33So let's try this again. And sure enough, what we'll see is that we end up with a list of distances and labels associated with those distances. So let's finish this thing up here. What we're going to do is we're going to sort them and we can do that by saying sorted. And then we're going to pass in the distances that we have, but, um, we're going to want to sort those in ascending order by their distance key, right? We're going to want to sort them in ascending order by, oops, let's just scroll up here by this thing here so that we get the smallest distances first, and we can take a slice. So here's what we're going to need to do for that. We're going to need to say, um, key equals, and then we're going to need to use a Lambda expression here so that we can say D and then we'll say D, uh, and that'll be distance. Okay. So that's just going to cause it to sort by the distance. That's all that is awesome. So now that we have that, we're just going to say, um, uh, sorted distances. There we go. Equals. And then that's going to be sorted distances, key blah, blah, blah, a little bit repetitive there, but you know, it just prevents us from having to type this out again if we need it. And, uh, anyway, now that we've done that,

6:49we're going to return what the, uh, K closest points are. And here's what that's going to look like. We're going to say sorted distances, and we're just going to say, oops, here, we'll say return sort of distances. And then we're going to say, uh, slice, and we're going to get zero through K like that. All right. So that should give us the closest points. So we're going to print those out and see what those look like. And here, just to make it a little bit easier, we'll start by getting the 10 closest points, just so that we can see what they look like.

7:21So let's run this again. And sure enough, what we see is that we start off with the closest distances, right? So four points, something, four points, something, four points, something. And then we go up to some of the further distances, like six points, something, seven points, something, and so on. All right. And so the last thing that we're going to need to do here is use these closest distances to sort of like vote on what the label for this point should be. So here's what that's going to look like. We're actually just going to use the Python collections module. So we're going to say from collections, there we go. Uh, we're going to import counter. And now if we scroll down here, what we're going to do is we're going to say, um, here, we'll just say, uh, first of all, we're going to get the closest points. So we'll say closest equals. And then what we're going to do is we're going to get the, uh, labels here. So we'll say closest labels. All right. And then we're just going to use a list comprehension here.

8:26We're just going to say C and we'll get the label, uh, entry from that for C in closest. And that should give us the, uh, labels. So now in order to basically take a vote on those, we can just use that counter thing. Um, right. This thing up here in order to get the most common element from that list. So here's what that's going to look like. We're going to say counter, and then we're going to paste those labels in there. Right. And then we're going to say dot most common, and we're going to get the first most common one there. And then we just have to say zero, zero at the end there. If you don't know how counter works, right. Or counter most common, don't worry too much about it. Just know that this will get us the most common one.

9:08This is just the most sort of Pythonic clean way of doing it. All right. So let's get the closest label here. Okay. And what that's going to look like, well, let's just print it out. So we'll say closest label like so. All right. If we run this, what we'll see is that the closest label is in fact extra large. Okay. And as we remember from the data set itself, that was the correct label for this one. That's not always going to work out that way, but it does seem to have worked out that way in this case. All right. So now all we have left to do is rewrite this into sort of like a, an all encompassing function that we can use to label pretty much any, uh, new person, right. Or suggest a shirt size for any new person based on their measurements. So here's what this is going to look like. We're just going to say, um, define, and we'll say something like, uh, label shirt size, or you know what? We'll say something like predict shirt size. We'll be a little bit better there.

10:08And then what we're going to do is we're going to take the new measurements here. All right. So what that's going to look like is we'll say, uh, measurements. All right. And now we're going to basically just put all of this inside that function. All right. And then let's just go through and clean this up a little bit. So we already have get distance inside here. We could make those, you know, we might want to move those outside of this function here. In fact, here, let's do that just to make it a little bit cleaner here. So we'll move, uh, get distance and get closest points outside of there. All right. And those are pretty self-contained functions. So those shouldn't be, uh, there shouldn't be any problems there. And now that we've done that, what we're going to do is we're going to just say that we want to return the closest label.

10:58And there we go. We'll also change this to some other value besides 10. Maybe we'll do like the seven nearest neighbors there. And well, what we're going to do is we're going to say, predict shirt size. All right. And we are going to actually define a new set of measurements here. Let's just look through our shirt sizes here and just pick something that's kind of close to one of these. So, um, maybe we'll do for the, Oh, here, first of all, let me just copy these here. And then we'll put those into here and we'll use those as the keys like, so that'll just make it a little bit easier there. Cause we won't have to type each of them out. All right. And now that we have those, here's what this is going to look like. We're going to say that the height in centimeters, let's just, um, pick something kind of roughly in this range here. So we'll say, uh, here we'll pick something between two of the mediums so that we know that it should probably be medium. So we'll do like 177 for height in centimeters, 177.0 for weight in kilograms. Here's what this is going to look like. We're going to go and take a look between some of the mediums here again. So we'll pick maybe a 79 for the weight. All right. And then for chest centimeters, we're going to use another value from that or sort of like an in-between value here.

12:16So we're going to pick, uh, let's see here. We'll do 98 perhaps. So we'll say 98.0 and I'm just doing 0.0 for the sake of simplicity here. And then for waist centimeters, what we're going to do is we're going to say, uh, let's just go back here and take a look at some of those. Uh, we'll do maybe a 90. Okay. For that. So we'll say 90.0. And now that we've done that, let's see what this one predicts. All right. And here we need to actually print that out. All right. And if we run this now, what we're going to see is, Oh, it looks like it gave us XL. Oh. And the reason for that is that we forgot to actually pass in these new measurements here instead of just picking the first one there. So here's what this is going to look like. We're going to swap this out. So instead of rows zero, we're going to say measurements. All right. And then what we're going to do is we're going to swap that out with just plain old rows and that should be all we need to do there. So let's try running this again. And sure enough, that now gives us medium, which is our expected value. So anyway, that is the basics of implementing a K nearest neighbor algorithm.

13:23So in the next video, I'm going to give you a challenge that will basically require you to take this a little bit further and play around with some of the different pieces and the available alternatives to them.

0:00All right, well, now that we've finished our simple implementation of the k-nearest-neighbors algorithm, it's time for you to do a challenge. And in this challenge, you're gonna be creating an alternative distance function for calculating the distance between two points. Now, Sean, what on earth do you mean alternative distance function? Well, the distance function that we just used in this example is what's often referred to as the Euclidean distance, right? This is the, you know, Pythagorean theorem at work, basically, where if you have a point here and a point here, the actual distance between them, the diagonal distance, if you wanna call it that, is the square root of the sum of the squares of both those sides.

0:47And that might sound confusing, but it's just the good old A squared plus B squared equals C squared thing at work, right? Which, as we've learned in this skill, applies to higher dimensions as well. However, this way of calculating distances does have some important issues, and we'll talk about those in a little bit more detail later in the course, but one of those issues is that because it involves squares, the Euclidean distance, right, spelled like this after this guy named Euclid, but the Euclidean distance overemphasizes occasional large variations, right?

1:24So because we're doing like A squared and B squared, if, oops, I wrote B as the exponent there, B squared is what I meant to say there, because we're doing A squared and B squared, when we have the occasional value that's like, you know, way out of range, right, or way out of the normal range, and A or B happens to be very large, then squaring that gives an unusual amount of weight to that particular dimension, and that's often not what we want.

1:54Now, if this is not making sense to you, don't worry too much about the exact details. Just know that there are certain situations where the Euclidean distance is not desirable, and so in place of this, there are other distance functions, and the one that you're gonna be working with in this challenge is known as the Manhattan distance. All right, now this is, I think, a somewhat humorously named distance, because as we just saw, the Euclidean distance is basically the shortest distance, the length of the shortest line between two points in space, but the Manhattan distance is literally just A plus B, right, now why is this?

2:37Well, think about Manhattan. If you've ever been to Manhattan, you know that the entire place is laid out like a grid, right? So if you're trying to get from one place to another in Manhattan, you have to travel along the roads, which go like this, right? They're like a grid, and so the shortest distance between two points in Manhattan is not as the crow flies, right, unless you have a helicopter, and you know, some people do, but for most of us, the shortest distance between two points in Manhattan is going along the streets, right, or the sidewalks or whatever, and so that's where this Manhattan distance idea comes from.

3:16Now this distance, it might seem kind of arbitrary to just do A plus B instead of the square root of A squared plus B squared, but this actually has some very nice properties in certain situations. I'm not gonna go into much detail on that right now, but anyway, this is your challenge is you're going to implement a Manhattan distance function and use that to replace our regular Euclidean distance function in the algorithm that we just implemented here. So that's your challenge, and this should take you maybe about five to 10 minutes to complete.

3:51So once you've given it a try, you can feel free to move on to the next video where I'll walk you through the challenge. Oh, and one last thing that is probably relevant here is that just like how the Euclidean distance generalizes to multiple dimensions, right, so you can do A squared plus B squared, but you can also do A squared plus B squared plus C squared plus D squared plus as many dimensions as you want, long as you take the square root of those, of course, you can do the same thing with the Manhattan distance, right? So just like how the Manhattan distance between two points is just A plus B, well, in two dimensions, that is, the distance between two points in three dimensions is A plus B plus C, with C being the distance between them in the third dimension, and if you're in four dimensions, that would be the distance between them in the fourth dimension.

4:35So anyway, best of luck on your challenge, and I'll see you in the next video.

0:00All right, well, hopefully you gave this challenge a try, so let's take a look at the solution. So all you really had to do for this challenge was define a new function called get Manhattan distance. Probably the hardest part of this challenge was spelling Manhattan. So we're gonna say get Manhattan distance, and from point one to point two, the Manhattan distance was just the sum of the distances between each point. So, you know, another hard aspect of this too is that sometimes this could turn out to be negative.

0:33So you did actually have to add an absolute value into here. If you didn't get that, don't worry too much about it. I didn't mention that in the challenge video. So anyway, just make sure to fix that going forward because we are gonna be reusing this code in the following skills to learn more about machine learning. But here's what we're gonna do. We're just going to reuse a lot of this code from the get distance function, which we'll also rename in Euclid's honor to get Euclidean distance. And now for get Manhattan distance, we're gonna say total equals zero, and then we're gonna say total plus equals, and we're literally just gonna get the difference there between those two, and then we're just gonna get the absolute value by saying abs and wrapping that there.

1:19And then we don't need to take the square root either, right, it's just the total of all of those. So that should be all we really need to do there. Let's just swap out the get distance function down here with the get Manhattan distance function. And oops, sorry, that should be inside get closest points. So we're gonna swap this one out. There isn't even a get distance function anymore. So we're gonna replace that with get Manhattan distance, and that should be all we really need to do there. So let's just save this and try running it again.

1:52And what we should see is that we'll still get similar results. Typically the Manhattan distance and the Euclidean distance don't give significantly different results for fairly normal situations, like the one that we saw here, where there's not really any outliers. The place where you start to see, or the situations rather, where you start to see some major differences is if we had someone like way down here who wore extra large clothing, right, that might skew things a little bit, right? Or if we had someone like way over here, or someone way over here, if we had some unexpectedly large distances, that's when the Manhattan distance would tend to give more accurate answers than the Euclidean distance.

2:35It's not always better, but it is better in certain cases like that.