text: import numpy as np
  
  class KNearestNeighbor(object):
    """ a kNN classifier with L2 distance """
  
    def __init__(self):
      pass
  
    def train(self, X, y):
      """
      Train the classifier. For k-nearest neighbors this is just 
      memorizing the training data.
  
      Inputs:
      - X: A numpy array of shape (num_train, D) containing the training data
        consisting of num_train samples each of dimension D.
      - y: A numpy array of shape (N,) containing the training labels, where
           y[i] is the label for X[i].
      """
      self.X_train = X
      self.y_train = y
      
    def predict(self, X, k=1, num_loops=0):
      """
      Predict labels for test data using this classifier.
  
      Inputs:
      - X: A numpy array of shape (num_test, D) containing test data consisting
           of num_test samples each of dimension D.
      - k: The number of nearest neighbors that vote for the predicted labels.
      - num_loops: Determines which implementation to use to compute distances
        between training points and testing points.
  
      Returns:
      - y: A numpy array of shape (num_test,) containing predicted labels for the
        test data, where y[i] is the predicted label for the test point X[i].  
      """
      if num_loops == 0:
        dists = self.compute_distances_no_loops(X)
      elif num_loops == 1:
        dists = self.compute_distances_one_loop(X)
      elif num_loops == 2:
        dists = self.compute_distances_two_loops(X)
      else:
        raise ValueError('Invalid value %d for num_loops' % num_loops)
  
      return self.predict_labels(dists, k=k)
  
    def compute_distances_two_loops(self, X):
      """
      Compute the distance between each test point in X and each training point
      in self.X_train using a nested loop over both the training data and the 
      test data.
  
      Inputs:
      - X: A numpy array of shape (num_test, D) containing test data.
  
      Returns:
      - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
        is the Euclidean distance between the ith test point and the jth training
        point.
      """
      num_test = X.shape[0]
      num_train = self.X_train.shape[0]
      dists = np.zeros((num_test, num_train))
      for i in xrange(num_test):
        for j in xrange(num_train):
          #####################################################################
          # TODO:                                                             #
          # Compute the l2 distance between the ith test point and the jth    #
          # training point, and store the result in dists[i, j]. You should   #
          # not use a loop over dimension.                                    #
          #####################################################################
          dists[i,j] = np.sqrt(np.sum(np.square(X[i,:] - self.X_train[j,:])))
          #####################################################################
          #                       END OF YOUR CODE                            #
          #####################################################################
      return dists
  
    def compute_distances_one_loop(self, X):
      """
      Compute the distance between each test point in X and each training point
      in self.X_train using a single loop over the test data.
  
      Input / Output: Same as compute_distances_two_loops
      """
      num_test = X.shape[0]
      num_train = self.X_train.shape[0]
      dists = np.zeros((num_test, num_train))
      for i in xrange(num_test):
        #######################################################################
        # TODO:                                                               #
        # Compute the l2 distance between the ith test point and all training #
        # points, and store the result in dists[i, :].                        #
        #######################################################################
        dists[i,:] = np.sqrt(np.sum(np.square(X[i,:] - self.X_train), axis=1))
        #######################################################################
        #                         END OF YOUR CODE                            #
        #######################################################################
      return dists
  
    def compute_distances_no_loops(self, X):
      """
      Compute the distance between each test point in X and each training point
      in self.X_train using no explicit loops.
  
      Input / Output: Same as compute_distances_two_loops
      """
      num_test = X.shape[0]
      num_train = self.X_train.shape[0]
      dists = np.zeros((num_test, num_train)) 
      #########################################################################
      # TODO:                                                                 #
      # Compute the l2 distance between all test points and all training      #
      # points without using any explicit loops, and store the result in      #
      # dists.                                                                #
      #                                                                       #
      # You should implement this function using only basic array operations; #
      # in particular you should not use functions from scipy.                #
      #                                                                       #
      # HINT: Try to formulate the l2 distance using matrix multiplication    #
      #       and two broadcast sums.                                         #
      #########################################################################
  #take square from x and x_train
      train_pow=np.square(self.X_train)
      test_sum_dis=np.square(X)
  #sum it up in axis 1
      sumdis_sqx = np.sum(test_sum_dis, axis=1)
      sumdis_sqx_tr = np.sum(train_pow, axis=1)
      s_x_train=self.X_train
      dot_product=np.dot(X, np.transpose(s_x_train))
  
      dists=np.sqrt(sumdis_sqx_tr.reshape(1,-1)-2*dot_product+sumdis_sqx.reshape(-1,1))
      #########################################################################
      #                         END OF YOUR CODE                              #
      #########################################################################
      return dists
  
    def predict_labels(self, dists, k=1):
      """
      Given a matrix of distances between test points and training points,
      predict a label for each test point.
  
      Inputs:
      - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
        gives the distance betwen the ith test point and the jth training point.
  
      Returns:
      - y: A numpy array of shape (num_test,) containing predicted labels for the
        test data, where y[i] is the predicted label for the test point X[i].  
      """
      num_test = dists.shape[0]
      y_pred = np.zeros(num_test)
      for i in xrange(num_test):
        # A list of length k storing the labels of the k nearest neighbors to
        # the ith test point.
        closest_y = []
        #########################################################################
        # TODO:                                                                 #
        # Use the distance matrix to find the k nearest neighbors of the ith    #
        # testing point, and use self.y_train to find the labels of these       #
        # neighbors. Store these labels in closest_y.                           #
        # Hint: Look up the function numpy.argsort.                             #
        #########################################################################
        # sort pred instance according to their distances
        sort_dis = np.argsort(dists[i,:])
        
        knn_sort_dis_in = sort_dis[0:k]
        
        closest_y = self.y_train[knn_sort_dis_in]
        #########################################################################
        # TODO:                                                                 #
        # Now that you have found the labels of the k nearest neighbors, you    #
        # need to find the most common label in the list closest_y of labels.   #
        # Store this label in y_pred[i]. Break ties by choosing the smaller     #
        # label.                                                                #
        #########################################################################
        #counts number of occurrences of each label and find the closest instance to each query instance with argmax
        y_pred[i] = np.argmax(np.bincount(closest_y))
  
        #########################################################################
        #                           END OF YOUR CODE                            # 
        #########################################################################
  
      return y_pred
  
  