Is creating decision surface necessary in k-NN?

Question

I am new to machine learning and I came across this question.

*1) [True or False]

• k-NN algorithm does more computation on test time rather than train time.

Solution: A

The training phase of the algorithm consists only of storing the feature vectors and class labels of the training samples.

In the testing phase, a test point is classified by assigning the label which are most frequent among the k training samples nearest to that query point – hence higher computation.*

While the solution in itself is simple to understand, I was wondering if creating decision surfaces are important in k-NN. Because once we have decision surfaces, we need not find k-nearest-neighbors, rather we can simply label the data based on the region which it falls into.

Also, in modified versions of k-NN like LSH, the training is not just limited to "storing the feature vectors and class labels of the training samples"

Am I wrong in the above thought process? Isn't the question a bit ambiguous?

Answer 1

During training, the k-NN algorithm simply stores $ m $ training data points with predefined classes. But the testing phase involves computing pairwise distances between each of $ n $ test data points and all training data, thus creating a distance matrix of $ m \times n $ size. Finally, the algorithm assigns each test point to the majority class of its $ k $ nearest neighbors in the training set.

So you're right in the above thought process: for k-NN creating decision surfaces or hyperplanes is unimportant, because it operates on distances from training set to test set. However, there is another classifier named SVM, which aims at finding a hyperplane that separates two classes.