Use Matlab to implement a kNN classifier Implement a kNN classifier. The format
ID: 3884250 • Letter: U
Question
Use Matlab to implement a kNN classifier
Implement a kNN classifier. The format of the function should be y = kNNClassifier (x, X, t, K)^1. The input pattern to be classified is x, the training data is contained in row vectors in the data matrix X, the target values are in the vector t and the number of nearest neighbours specified by K. You have to implement the following steps: Compute the Euclidean distance from the input pattern to all the patterns in the training data. You can use distance(ii)=norm(x-X (ii,: ),2) where ii is the index into the training data. Obtain ordered indices according to the distance. You can use [dist, NNindex]=sort (distance). Note that NNindex is the ordered indices. Obtain the indices of the K nearest neighbours by NNindex(1: K). Obtain the class labels of the K nearest neighbours with t (NNindex(1: K)). Determine what class is in the majority of the K nearest neighbours and set y to this value. a) Verify that your algorithm works with a single input pattern. You can create training data as in previous exercises, using mu_1 = [1 1] mu_2 = [-1 -1] sigma_1 = [1 0.5 0.5 1] sigma_2 = [1 -0.5 -0.5 1]. b) Create another set of data (using the same parameters) and calculate the test error for K=5. c) See how the test error varies with different values of K. d) Apply your algorithm to the Iris database. State the mis-classficiation rate for different values of K.Explanation / Answer
The basis of the K-Nearest Neighbour (KNN) algorithm is that you have a data matrix that consists of N rows and M columns where N is the number of data points that we have, while M is the dimensionality of each data point. For example, if we placed Cartesian co-ordinates inside a data matrix, this is usually a N x 2 or a N x 3 matrix. With this data matrix, you provide a query point and you search for the closest k points within this data matrix that are the closest to this query point.
We usually use the Euclidean distance between the query and the rest of your points in your data matrix to calculate our distances. However, other distances like the L1 or the City-Block / Manhattan distance are also used. After this operation, you will have N Euclidean or Manhattan distances which symbolize the distances between the query with each corresponding point in the data set. Once you find these, you simply search for the k nearest points to the query by sorting the distances in ascending order and retrieving those k points that have the smallest distance between your data set and the query.
Supposing your data matrix was stored in x, and newpoint is a sample point where it has M columns (i.e. 1 x M), this is the general procedure you would follow in point form:
Find the Euclidean or Manhattan distance between newpoint and every point in x.
Sort these distances in ascending order.
Return the k data points in x that are closest to newpoint.
Let's do each step slowly.
Step #1
One way that someone may do this is perhaps in a for loop like so:
If you wanted to implement the Manhattan distance, this would simply be:
dists would be a N element vector that contains the distances between each data point in x and newpoint. We do an element-by-element subtraction between newpoint and a data point in x, square the differences, then sum them all together. This sum is then square rooted, which completes the Euclidean distance. For the Manhattan distance, you would perform an element by element subtraction, take the absolute values, then sum all of the components together. This is probably the most simplest of the implementations to understand, but it could possibly be the most inefficient... especially for larger sized data sets and larger dimensionality of your data.
Another possible solution would be to replicate newpoint and make this matrix the same size as x, then doing an element-by-element subtraction of this matrix, then summing over all of the columns for each row and doing the square root. Therefore, we can do something like this:
For the Manhattan distance, you would do:
repmat takes a matrix or vector and repeats them a certain amount of times in a given direction. In our case, we want to take our newpoint vector, and stack this N times on top of each other to create a N x M matrix, where each row is M elements long. We subtract these two matrices together, then square each component. Once we do this, we sum over all of the columns for each row and finally take the square root of all result. For the Manhattan distance, we do the subtraction, take the absolute value and then sum.
However, the most efficient way to do this in my opinion would be to use bsxfun. This essentially does the replication that we talked about under the hood with a single function call. Therefore, the code would simply be this:
To me this looks much cleaner and to the point. For the Manhattan distance, you would do:
Step #2
Now that we have our distances, we simply sort them. We can use sort to sort our distances:
d would contain the distances sorted in ascending order, while ind tells you for each value in the unsorted array where it appears in the sorted result. We need to use ind, extract the first k elements of this vector, then use ind to index into our x data matrix to return those points that were the closest to newpoint.
Step #3
The final step is to now return those k data points that are closest to newpoint. We can do this very simply by:
ind_closest should contain the indices in the original data matrix x that are the closest to newpoint. Specifically, ind_closest contains which rows you need to sample from in x to obtain the closest points to newpoint. x_closest will contain those actual data points.
For your copying and pasting pleasure, this is what the code looks like:
Running through your example, let's see our code in action:
By inspecting ind_closest and x_closest, this is what we get:
If you ran knnsearch, you will see that your variable n matches up with ind_closest. However, the variable d returns the distances from newpoint to each point x, not the actual data points themselves. If you want the actual distances, simply do the following after the code I wrote:
Note that the above answer uses only one query point in a batch of N examples. Very frequently KNN is used on multiple examples simultaneously. Supposing that we have Q query points that we want to test in the KNN. This would result in a k x M x Q matrix where for each example or each slice, we return the k closest points with a dimensionality of M. Alternatively, we can return the IDs of the k closest points thus resulting in a Q x k matrix. Let's compute both.
A naive way to do this would be to apply the above code in a loop and loop over every example.
Something like this would work where we allocate a Q x k matrix and apply the bsxfun based approach to set each row of the output matrix to the k closest points in the dataset, where we will use the Fisher Iris dataset just like what we had before. We'll also keep the same dimensionality as we did in the previous example and I'll use four examples, so Q = 4 and M = 2:
Though this is very nice, we can do even better. There is a way to efficiently compute the squared Euclidean distance between two sets of vectors. I'll leave it as an exercise if you want to do this with the Manhattan. Consulting this blog, given that A is a Q1 x M matrix where each row is a point of dimensionality M with Q1 points and B is a Q2 x M matrix where each row is also a point of dimensionality M with Q2 points, we can efficiently compute a distance matrix D(i, j) where the element at row i and column j denotes the distance between row i of A and row j of B using the following matrix formulation:
Therefore, if we let A be a matrix of query points and B be the dataset consisting of your original data, we can determine the k closest points by sorting each row individually and determining the k locations of each row that were the smallest. We can also additionally use this to retrieve the actual points themselves.
Therefore:
We see that we used the logic for computing the distance matrix is the same but some variables have changed to suit the example. We also sort each row independently using the two input version of sort and so ind will contain the IDs per row and d will contain the corresponding distances. We then figure out which indices are the closest to each query point by simply truncating this matrix to k columns. We then use permute and reshape to determine what the associated closest points are. We first use all of the closest indices and create a point matrix that stacks all of the IDs on top of each other so we get a Q * k x M matrix. Using reshape and permute allows us to create our 3D matrix so that it becomes a k x M x Q matrix like we have specified. If you wanted to get the actual distances themselves, we can index into d and grab what we need. To do this, you will need to use sub2ind to obtain the linear indices so we can index into d in one shot. The values of ind_closest already give us which columns we need to access. The rows we need to access are simply 1, k times, 2, k times, etc. up to Q. k is for the number of points we wanted to return:
When we run the above code for the above query points, these are the indices, points and distances we get:
To compare this with knnsearch, you would instead specify a matrix of points for the second parameter where each row is a query point and you will see that the indices and sorted distances match between this implementation and knnsearch
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.