2.1 Introduction to NN (L02: Nearest Neighbor Methods)

Key Takeaways

yeah hi everyone and welcome back i hope you had a very nice first week so just to briefly recap what happened so we covered lecture one the introduction to machine learning and in the office ask the most common question was basically about the project the class project i will make a separate announcement about that but uh yeah one thing i can already tell you is that i enabled a function on piazza that you can use to find team members but i will again share that in a separate announcement so today in lecture two we'll mainly talk about the k nearest neighbor algorithm it's a kind of a classic machine learning algorithm but it's still very useful and i would say that is maybe the nicest most gentle introduction to machine learning in in terms of using the first machine learning algorithm and taking a closer look at how machine learning algorithms work so also while it is maybe not the most popular algorithm anymore i would say i would really still recommend it highly to include it in your projects so if you work on a project where you want to classify certain things or even let's say predict continuous outputs i would always start with k nearest neighbors as a performance benchmark so that could be a benchmark in terms of prediction accuracy but also a benchmark in terms of computational efficiency so speaking of which along with introducing how k nearest neighbor works we will also briefly talk a little bit about big o the big o notation which is a very common way of looking at the efficiency of different algorithms it's kind of very computer sciencey but still i think it's useful in this context to talk a little bit about big o notation and analyzing algorithm efficiency that's something i think that is also useful not only for machine learning but yeah like uh programming in general yeah and um at the end of this lecture then uh since i also mentioned computational aspects after introducing the concepts of k n i will also then show you some examples in python how we can use k n and python of course this is just a very brief overview some parts may be confusing but again in the next lecture in lecture three i will talk more about python how to install it and also about uh the main libraries we will be using like numpy and scikit-learn okay so then let's get started so in lecture two we are going to talk about nearest neighbor methods this includes aspects about nearest neighbor methods in general but also more specifically the k nearest neighbor algorithms for example k nearest neighbors for classification or regression to make this lecture a little bit more approachable i structured it into six parts so first we will take a look at some applications of nearest neighbor methods and also just a basic one nearest neighbor method then i will show you the decision boundary of the nearest neighbor method to get a better understanding of how it works after we talked about the nearest neighbor method in general i will introduce the k-nearest neighbor methods for example k-nearest neighbor classifiers and after i mean this is a very simple concept after we went over this we will dive into a more like computer sciencey aspect of this lecture and look at the big o uh runtime complexity of k-nearest neighbor algorithms it's like a computer science topic that deals with analyzing of analyzing how efficient an algorithm is after part 4 i will show you then some ideas and tricks to improve k nearest naval algorithms so this whole part one to five is rather conceptual it kind of kind of introduces the idea behind k nearest neighbors and after we finished these parts in the end i will also show you how you can use k nearest neighbors in python so that is also maybe for some of you the most fun part but of course first concepts and then the application because otherwise um showing you the application first it would be kind of like some magic stuff going on so first let's talk about the concepts and then about the application yeah but in a certain way applications can also be quite motivating for introducing a certain topic so i picked some example applications of k-nearest neighbor methods in practice so here i found a research article entitled automated web usage data mining and recommendation system using the k-nearest neighbor classification method so here the researchers deal with web usage data mining and more specifically this would be a case of a recommender system so kenya's neighbors are still very commonly used for building recommender systems and here what they say is basically they trained the k nearest neighbor classifier to be used online and in real time to identify clients or visitor click stream data matching it to a particular user group and recommend a tailored browsing option that meet the need of the specific user at a particular time so it's um you can think of it as a recommendation system recommend recommending certain i would say i don't know links or websites and so forth based on the past or present browsing behavior yet traditionally k nearest neighbor methods have also been used extensively in the field of biometrics that includes like face recognition or fingerprint analysis and so forth um nowadays it's maybe more common to do biometric research using deep learning but kenya's neighbor algorithms are still very commonly used in established algorithms that are employed in industry so here's a little bit of an older paper demonstrating the use of nearest neighbor classification for image data so here this is just an example of face image data set and here's the mnist data set more specifically this paper was not just about the application of k-nearest neighbors it was about um distance metric learning so learning a distance metric for the k-nearest neighbor method we will talk more about distance metrics also in this lecture only very briefly for instance um the my harlem nova's distance uh was yeah learned here we will also briefly mention uh the mahada nova's distance and how it's related to the euclidean distance measure may be notable is that they achieved a test error rate of one point three percent on mnist hand written digits so it's just uh yeah interesting because we talked about mnist in the past in the last lecture and this is a relatively classic image classification data set where the task was to recognize handwritten digits i think it was like 50 000 training data points in this data set so here is another interesting application of k nearest neighbors so here it's not k nearest neighbor classification but k nearest neighbor regression the title of this paper was remaining useful life estimation of lithium-ion cells based on k-nearest neighbor regression with differential evolution optimization so here they estimated how many life cycles are left in a lithium ion battery using k nearest neighbor regression yeah lastly one of my applications of k nearest neighbors in a recent on research collaboration earlier this year so this paper was entitled machine learning to identify flexibility signatures of class a gpcr inhibition gpcr these are proteins um a special type of membrane protein it's called um well it's a g protein coupled receptor sits in the membrane it's a relatively important receptor throughout the animal kingdom and of course in humans it's one of the most or biggest drug targets in humans it's involved in many many different processes in the body so in any case so here we basically used um k nearest neighbors together with feature selection to pinpoint um certain regions in the protein that are involved in certain activity or in active and inactive states of that protein because they're usually some small ligands small molecules binding to that protein and they can either activate or inhibit the protein receptor so we try to learn what distinguishes basically active and inactive proteins so the inactive and active states and um basically also looking at the flexibility transitions that are triggered by biologically active ligands so here we also used k nearest neighbor classifiers yeah after such a top-down look at the k-nearest neighbor method let us now take a bottom-up approach and talk about the one nearest neighbor method before we dive more into k-nearest neighbors and how it works so the one nearest neighbor method is a very simple method it's a special case of k nearest neighbors so it's um k nearest neighbors with k equals one it's just a special case of k nearest neighbors so how does the k-nearest neighbor method work let's say if we want to use it for making predictions so here i'm showing you a simple data set a toy data set consisting of two features so we have a feature x1 and a feature x2 and the training data set consists of five data points one two three four five so given this data set of these blue dots now assume we have a new data point we have this data point this question mark and we want to predict a target value for this question mark so how do we do that so to make this a little bit more concrete for the target value for now think of it as a classification problem so we have two classes class zero and class one um so i took the five data points here i showed you in the previous slide and just mark them with appropriate class label so the triangles here are class 1 and the squares are class 0. so what would be the class label for the question mark point in the one nearest neighbor method as the name suggests we found we find the most similar data point to our query point here in the training set so for the question mark point this is a new data point this is you can think of it as new data point or new example that we want to classify so what is its label we want to find want to find the label which is either a triangle or the square class class 0 or class 1. and in order to do that we look at the most similar data point in the training set and then look at what the label of this training data set point is so in this case the most similar data point using a euclidean distance measure would be this point here the square so it's the closest point to the question mark so what we would do now is we predict that this question mark belongs to class 0 and that is how the nearest neighbor or the first simple case of a nearest neighbor method works it's k nearest neighbor with k equals 1. so we find the one closest data point so to talk about the nearest neighbor method in a more i would say structured way let's break it down into a training and a prediction step so remember from lecture one we usually have a training and a prediction phase we sometimes also call the prediction phase inference so how um does the training step for k-nearest neighbors or the one nearest neighbor method looks like so the nearest neighbor methods are also called lazy oops lazy or lazy we often say the nearest neighbor classifier is a lazy learner because there's not really a big training step here the training step is simply remembering or memorizing the training data set so if we have a training data set in d here and with the data points um with uh the data points here where x is the feature vector and y is the label or target value so these are the features so it's a feature vector it could be one or more features in the previous slide where we had oops where we had this setup we had two features [Music] and i is the index over the data points in the training set so in this case we have i equals 1 to n we have up to n data points in the training set and the training step is simply remembering these data points there's not really much we have to do here in the training it's just storing storing the data in a sense then in the prediction step there are a few more steps so the prediction phase of the k-nearest neighbor or nearest neighbor methods is a little bit more involved so that's where nearest neighbor does all its work in a sense so again given the training data set of size n the task in prediction is to predict the label of a new data point let's call this new data point xq so we have the features x q you can think of q stands just for query data point it's just a new data point we want to find its label so we want to know what it's um y label is the predicted y label so we use then the nearest neighbor model f to make the prediction on this on these features and the algorithm is as follows so we start by setting it up with the closest point so we want to find the nearest neighbor so in the beginning we don't have a closest point because yeah we we just started it's our initial condition and then we set an additional parameter here a closest distance so that would be the distance to the closest point or the distance corresponding to this closest point here and we set this to infinity here and then for every data point in the training set so we are iterating from of we iterating from one over to n so we have again n data points in the training set what we do is we compute the current distance the current distance means here the distance d some arbitrary distance measure we can choose the distance d between the current training set point so this is a training set point and this one here oh i've written this over here is the query point so we compute the distance between each training data point and the query data point gray data point is uh the one where for which we want to get the class label or target value and given this distance now after we computed this we check it or we compare it to the closest distance so in the first round because we start out with infinity the first point we will encounter will be the closest point but then of course while we iterate we may find another more closer point so if the current distance if we find that the distance of the current point we are currently looking at is smaller than the closest distance we found previously we update this variable closest distance with the current distance and then also we save the closest point so the closest point is the one that corresponds to this closest distance so it's this closest point that we used in this distance computation yeah and then we return the closest point so the prediction so this is uh the algorithm for finding the closest point and the prediction would be returning the class label corresponding to this closest point because um let's say i find that the closest point here is the point 13 in my data set so that would be let's say my my closest point would be 13 where we of course are interested in in the label so what we would do is we would also have to look up the label of the closest point and this is the prediction this is the f closest point the label corresponding to the closest point and we have the label because this data point is of course the data point 13 is in the training set yeah and that is essentially the main idea behind the one nearest neighbor method that's the prediction step so regarding the distance measure in the previous slide i just showed you an arbitrary distance measure that i call the d commonly or most frequently what people use is the euclidean distance so if you have continuous features you don't have any particular preference people usually start out using a euclidean distance measure but there are many many other different choices i will list some of these choices later but yeah one one aspect to mention here is if you use the euclidean measure it's kind of important to make sure that the features are all on a comparable scale that um each feature weighs in equally because if you scale one feature more than the other then this feature will of course um dominate the distance computation so if i have two features like x1 and x2 and let's say i um put a point here in the center and this feature goes from one to ten and this feature goes from one to 100 of course if i have a data point i want to compare it if i compare these two data points to each other so if i make the comparison between these data points then feature x2 will be much more important than feature x1 because you can see the axis here for x2 this axis is much larger the values are much larger so they will dominate in this distance computation so if you want to make a fair comparison then of course uh it's important to have the features on the same scale but um not it's not always also a requirement to have the features on the same scale there may be a reason why you want to weigh a feature more heavily in this case you can also intentionally scale a certain feature but of course we will talk briefly about this later this is a hyper parameter it's like a decision you can make but you don't have to make okay but before i get too distracted by already talking about hyper parameters here let me wrap up this first video and in the next video we will take a closer look at the nearest neighbor decision boundary