<p>(b) Implement the function <b><code>findknn</code></b>, which should find the $k$ nearest neighbors of a set of vectors within a given training data set. Break ties arbitrarily. The call of <pre> [I,D]=findknn(xTr,xTe,k); </pre> should result in two matrices $I$ and $D$, both of dimensions $k\times m$, where $m$ is the number of input vectors in <code>xTe</code>. The matrix $I(i,j)$ is the index of the $i^{th}$ nearest neighbor of the vector $xTe(j,:)$. So, for example, if we set <code>i=I(1,3)</code>, then <code>xTr(i,:)</code> is the first nearest neighbor of vector <code>xTe(3,:)</code>. The second matrix $D$ returns the corresponding distances. So $D(i,j)$ is the distance of $xTe(j,:)$ to its $i^{th}$ nearest neighbor. </p>
Question
<p>(b) Implement the function <b><code>findknn</code></b>, which should find the nearest neighbors of a set of vectors within a given training data set. Break ties arbitrarily. The call of <pre> [I,D]=findknn(xTr,xTe,k); </pre> should result in two matrices and , both of dimensions , where is the number of input vectors in <code>xTe</code>. The matrix is the index of the nearest neighbor of the vector . So, for example, if we set <code>i=I(1,3)</code>, then <code>xTr(i,:)</code> is the first nearest neighbor of vector <code>xTe(3,:)</code>. The second matrix returns the corresponding distances. So is the distance of to its nearest neighbor. </p>
Solution
To implement the function findknn, we will use the following steps:
-
First, we need to calculate the Euclidean distance between each vector in
xTeand all vectors inxTr. We can use thel2distancefunction for this, which calculates the square root of the sum of the squared differences between two sets of vectors. -
Once we have the distance matrix, we need to sort it in ascending order along each column. This will give us the indices of the nearest neighbors in
xTrfor each vector inxTe. We can use thesortfunction in MATLAB for this, which returns a sorted matrix and an index matrix that can be used to reconstruct the original matrix. -
Finally, we need to return the first
krows of the sorted index matrix and the corresponding distances. These are theknearest neighbors and their distances for each vector in
Similar Questions
#<GRADED> def findknn(xTr,xTe,k): """ function [indices,dists]=findknn(xTr,xTe,k); Finds the k nearest neighbors of xTe in xTr. Input: xTr = nxd input matrix with n row-vectors of dimensionality d xTe = mxd input matrix with m row-vectors of dimensionality d k = number of nearest neighbors to be found Output: indices = kxm matrix, where indices(i,j) is the i^th nearest neighbor of xTe(j,:) dists = Euclidean distances to the respective nearest neighbors """ # Enter your code here n,d = xTr.shape m,d = xTe.shape tempDists = l2distance(xTr,xTe); indices=np.argsort(tempDists,axis=0)[:k]; dists=tempDists[indices,np.arange(tempDists.shape[1])[None, :]]; raise NotImplementedError('Your code goes here!') return indices, dists # until here #</GRADED> using python and without using for loop
Identify the difficulties with the k-nearest neighbor algorithm.(1 Point)Curse of dimensionalityCalculate the distance of the test case from all training casesBoth A and BNone of the above
#<GRADED> def knnclassifier(xTr,yTr,xTe,k): """ function preds=knnclassifier(xTr,yTr,xTe,k); k-nn classifier Input: xTr = nxd input matrix with n row-vectors of dimensionality d xTe = mxd input matrix with m row-vectors of dimensionality d k = number of nearest neighbors to be found Output: preds = 1xd vector of predicted labels, ie preds(i) is the predicted label of xTe(i,:) """ # fix array shapes yTr = yTr.flatten() # Your code goes here raise NotImplementedError('Your code goes here!') return preds #</GRADED> python code with no for loop and return preds
Question 4(True/False) K Nearest Neighbors with large k tend to be the best classifiers.1 pointTrueFalse
Identify the difficulties with the k-nearest neighbor algorithm.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.