Exact Procedure for KNN classification

Question

I want to know the exact procedure involved in KNN classification. I understand the bigger picture but I miss the details to implement.

I have 3 pieces of data: Train, Validate and Test.

1) Suppose we have training points $x_1, x_2,\dots,x_N$ each in $\Bbb R^D$ where $D$ is number of features and the labels are $y_1,\dots,y_N$ each in $\Bbb R$ where $N$ is number of training points.

What does training involve? Do I need to pick nearest neighbors for each point $j\in\{1,\dots,N\}$ and relabel the points based on majority vote?

2) What does validation involve?

Given a validation point $x\in\Bbb R^D$ with label $y$ what should I do?

3) Is testing same as validation?

Answer 1

1 and 2) Training consists only of saving your training points. If you apply the model to a new data point, you find the neighest neighbours of the new point in the set of training points.

3) The validation step of your procedure is often used for tuning hyperparameters, for example with nearest neighbours this could be the number $n$ of neighbours to consider.

If you want to tune $n$ you can do the following:

1. Save your training points
2. For each $n$ in a reasonable range (e.g. 1-10, depends on dimension of data) classify all your validation points with $n$-Nearest Neighbours. Look at an appropiate measure of the performance of your model (application specific). Pick the $n$ which yields the best results.
3. Save a set consisting of both the training points and the validation points.
4. Use a single $n$-Nearest Neighbours model with the n to predict your test data using the data from step 3. The performance of that model on the test data is your final estimate of the performance of your model.

If you are not tuning parameters you do not need a triple split. Note that considering which type of classifier performs best is also tuning a hyperparameter.

In either case, iterated nested cross validation or bootstrapping gives more accurate estimates compared to this procedure which is rather inefficient.