Hello everyone, welcome to the course of machine learning with Python. In this video, we will learn about a new classifier called k nearest neighbor classifier, it is also known as K in classifier KNN is the short form of K nearest neighbor. So, what is Euclidean distance consider the points in two dimension each point in two dimension can be represented by a vector of dimension two. So, the point u one comma u two can be represented by a vector u and a point P one comma v two can be represented by a vector v okay. So, as you can see these have to tell you and this is written v the Euclidean distance between these two point is d u comma V that is how we denote is equals to square root of u one minus v one whole square plus u two minus v two whole square.

So, it is nothing but the linear distance between this point u and v. Okay. In general, a point in n dimensional space is it presented as u is equals to u one comma u two comma u three up to us transpose So, why transpose because it is a column vector okay. So, it is an n dimensional vector hence the Euclidean distance between two points in n dimensional spaces we present it as it is the square root of one minus v one whole square plus into minus v two whole square up to even minus V and whole square okay. So, in general in vector notation the Euclidean distance is written as square root of u minus v transpose multiplied with u minus v. So, as you can see this scalar no other Distance Matrix So, Manhattan distance for two data points denoted by X and Y both are vectors, the Manhattan distance is defined as it is nothing but the sum of the absolute difference between the coordinates of x and y.

So, it is x one minus y one modulus plus modulus of x two minus y two plus modules of extra minus y three plus two models of x and minus y and so in shorthand sumption notation we can leave Write it like modulus of x i minus y we are summing this up from equals to one to n. Now Minkowski distance for two data points denoted by X and Y the Minkowski distance is defined as So, you can see H is a parameter over here, it is nothing but some of Excel minus y to the power eight items from one to n and the summation and then take into the power one by h note that for each equals to two main cause, the distance is same as the treated distance and for each equals to one it is same as the Manhattan distance Chebyshev distance for two data points in n dimensional space, it is defined as the maximum of the absolute differences of the coordinates.

Now, there are other distance between like molecules which distance but touch at a distance etc, which are used for advanced statistical pattern recognition tasks. So, what is cleaning classifier? The intuition is one is known by the company one keeps So, let's see what does it Me. So, keen algorithm starts with all the training samples and the points and available beforehand that means, we know what are the points in that training data set Okay. Now, when a new test sample and I calculate its distance from all the training points, so, whenever a new sub arise like this, we calculate the distance of this new sample from all the available training samples. Now, choose k nearest neighbor based on the distance calculated.

So, what are the nearest neighbors whose distance are minimum? Okay, so we choose let's say first three or first five or one nearest neighbor, based on the distance calculated usually is a positive odd number and is supplied by the user. Now assign the class level of the test sample based on majority that is for a test sample if most number of neighbors among those k nearest neighbors belong to one particular class C then assign the class level of the test sample as C. So, what we can see from here among these three nearest neighbors of this blue test point, who belongs to class two and one belongs to class one. So, as for majority voting, these test points should belong to class two. So, as you can see this this point now labeled as plus two now, what are the characteristics of K nearest neighbor classifier it does not create model based on the training patterns in advance rather when it when a test instance comes for testing, it runs the algorithm to get the class prediction of the particular testing instance.

Hence, there is no learning in advance hence scan and classified is also known as lazy learner. So, this discuss about the decision boundary created by k nearest neighbor classifier. So, boundary are the points those are equidistant between the points of class one and class two. So, construct the lines between the closest pairs of points individually classes as shown over here draw the perpendicular bisector in bisector at the intersections note that locally the boundary is linear. Hence, the decision boundary is piecewise linear curve for a nearest neighbor classifier for multi class classification also, the same thing is done to find the decision boundary. As you can see over here there are three classes and the decision boundary looks like a piecewise linear curve.

Now on choosing the value of k in K nearest neighbor classifier, increasing the K simplifies the decision boundary because majority voting implies less emphasis on individual points. Let's see, for k equals to one, you can see this is how it looks like the decision boundary. You can see it is very complicated decision boundary for k equals to three however, the decision boundary is complicated but not that like k equals to 140 equals to five we're getting simpler decision boundary. For k equals to seven in simpler decision boundary, so, if we keep on increasing the value of k, we will see simpler and simpler decision boundaries. So however increasing the value of k also increases computational cost. Hence, choosing k is an optimization between how much simplified decision boundary versus how much computational cost we can hear usually k equals 2579 or 11 works fine for most of the practical problems, what are the beats of K nearest neighbor classifier?

K nearest neighbor classifier often works very well for practical problems. It is very easy to implement as there is no complex learning algorithm involved. And it is also robust to noisy data demerits. So, there are so many demerits of K nearest neighbor classifier, choosing the value of k may not be straightforward. Often the same training samples are used for different values of k and we choose the most suitable value of k based on minimum misclassification. errors on disk samples it does not work well for categorical attributes it can encounter problem with sparse training data, that is data points are located far away from each other, it can encounter a problem in very high dimensional spaces.

So, what are the problems in very high dimensional spaces, most points are at the corners, and most points are at the edge of the space. This problem is known as curse of dimensionality and affect many other machine learning algorithms. So, so far, this is our discussion on k nearest neighbor classifier. In the next video, we shall implement the K nearest neighbor classifier in Python from scratch. So, see you in the next lecture. Thank you.