Question

Part 1: Implement findknn

Implement the function findknn, which should find the ?k nearest neighbors of a set of vectors within a given training data set. The call of:

 [I,D]=findknn(xTr,xTe,k);

should result in two matrices ?I and ?D, both of dimensions ?×?k×n, where ?n is the number of input vectors in xTe. The matrix ?(?,?)I(i,j) is the index of the ??ℎith nearest neighbor of the vector ???(?,:)xTe(j,:).

So, for example, if we set i=I(1,3), then xTr(i,:) is the first nearest neighbor of vector xTe(3,:). The second matrix ?D returns the corresponding distances. So ?(?,?)D(i,j) is the distance of ???(?,:)xTe(j,:) to its ??ℎith nearest neighbor.

You can use the function l2distance from the previous exercise (which is readily available to you.) You may find np.argsort(D,0) and np.sort(D,0) useful when implementing findknn.

In [3]:

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

    """

->already defined l2distance(x,y) as euclidian distance formula

Answer 1

Working code implemented in Python and appropriate comments provided for better understanding:

Source code for findknn.py:

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
"""

# YOUR CODE HERE
if k > len(xTr):
k = len(xTr)

D=l2distance(xTe, xTr)
(m,n) = D.shape

indices = []
dists = []
for i in range(m):
smallest_indices = np.argsort(D[i])
ind = smallest_indices[:k]
dis = D[i,smallest_indices[:k]]
indices.append(ind)
dists.append(dis)

indices = np.transpose(np.array(indices))
dists = np.transpose(np.array(dists))
return indices, dists

Code Screenshots:

Hope it helps, if you like the answer give it a thumbs up. Thank you.