do in python. def kNN_quick (k, X_train, Y_train,x_test) return y_pred. Problem 2: Fast k-NN in 1D. In

do in python.

def kNN_quick (k, X_train, Y_train,x_test)

return y_pred.

Transcribed Image Text:

Problem 2: Fast k-NN in 1D. In Problem 1, even if we use quickselect, we need to do a whole pass over the training dataset for each test point. This means that it requires 0 (n) cost per prediction where n is the number of training points and it is not realistic in practice where we wish to run kNN in millions of test points. One way to go about this is preprocessing the training data. Suppose input data is 1-dimensional floating numbers i.e. X_train is a list of numpy floats. If you sort X_train, you can run k-NN in logarithmic time via bisection search. Your task is to implement k-NN classification on a test dataset X_test by first sorting X_train, y_train and then running k-NN over X_test to output list of predictions Y_pred. Unlike Problem 1 where x_test is a single input, X_test might contain millions of inputs and your output Y_pred should be a list with same size. Romark: You nood to implement overything yourself howoror you can uso codos from oorlier HWe Problem 2: Fast k-NN in 1D. In Problem 1, even if we use quickselect, we need to do a whole pass over the training dataset for each test point. This means that it requires 0 (n) cost per prediction where n is the number of training points and it is not realistic in practice where we wish to run kNN in millions of test points. One way to go about this is preprocessing the training data. Suppose input data is 1-dimensional floating numbers i.e. X_train is a list of numpy floats. If you sort X_train, you can run k-NN in logarithmic time via bisection search. Your task is to implement k-NN classification on a test dataset X_test by first sorting X_train, y_train and then running k-NN over X_test to output list of predictions Y_pred. Unlike Problem 1 where x_test is a single input, X_test might contain millions of inputs and your output Y_pred should be a list with same size. Romark: You nood to implement overything yourself howoror you can uso codos from oorlier HWe