# Does cross-validation apply to K-Nearest Neighbors given no estimated parameters?

Cross validation involves (1) taking your original set X, (2) removing some data (e.g. one observation in LOO) to produce a residual "training" set Z and a "holdout" set W, (3) fitting your model on Z, (4) using the estimated parameters to predict the outcome for W, (5) calculating some predictive performance measure (e.g. correct classification), (6) repeating for different Z and W (e.g. new training/holdout sets), and (7) calculating average predictive performance for your model. Repeating this for multiple modeling decisions, you would then select the model with the best performance.

I am confused about how this works for K-nearest neighbors (KNN). In the KNN context, there are no estimated parameters and only one hyperparameter: $$K$$. Our objective is to select the "best" $$K$$, but there are no learned parameters we can use to produce a prediction for our holdout set: we can't, say, multiply the $$\beta$$ for a feature by the feature value and sum across all such products to obtain a prediction. Furthermore, it is possible to choose a holdout set size with $$j \leq K$$, for which the KNN estimator is undefined.

Is cross-validation then not applicable to KNN? I can see two ways something like cross-validation actually can be used for KNN, but these violate the principle of not validating with your training data (even the concepts are ambiguous):

1. Partition data into smaller data sets, employ KNN on each set, calculate performance measure, then choose model based on the distribution of performance across partitions (e.g. best mean performance). This is not really cross-validation because there are no training/testing/validation sets.

2. Generate bootstrapped data sets, repeat steps in (1).

Note: Posts on this topic (see How does k-fold cross validation fit in the context of training/validation/testing sets? and Cross Validation and Nearest Neighbors) have not specifically asked about what training/holdout sets mean for KNN and instead have received responses discussing how cross-validation works in general without regard for the lack of estimated parameters in KNN.

• Yes it does. Cross validation tests model performance. As you know, it does so by dividing your training set into k folds and then sequentially testing on each fold while using the remaining folds to train the model. Your resulting performance is the average of the fold performance results. Using KNN, you are correct in that you are not calculating a coefficient. However, each set of training folds and corresponding test fold will be different. So if you are doing 5 fold cross validation you are going to have 5 slightly different fold performances. So Cross validation still gives you an idea a – Windstorm1981 Nov 16 '19 at 2:47
• @Windstorm1981 Can you then elaborate here what you are training and testing? What is the parameter you are estimating with the training data? As far as I can tell, this is simply telling us to partition our data into several smaller sets, calculate a performance measure after doing KNN on each, then calculate the averaage across sets. There is no distinction between training and testing sets in this case. – user3614648 Nov 17 '19 at 7:03
• So for each fold in k fold cross validation (not to be confused with k in knn) you are testing on one fold and training the model on the other folds. Whatever parameter value k you choose for the knn model will not change in performing cross validation, but the performance will because you are essentially training and testing on slightly different "sets" of train/test splits. The cross validation procedure uses all that data in different train/test permutations - so you would expect model performance to be better than when tried on a completely unseen validation set. Hope this helps. – Windstorm1981 Nov 18 '19 at 19:22
• You are once again describing cross-validation and NOT how it applies to KNN selection of K, which was my question. My question was asking what it means to "train the data" on one fold and test it on other folds in the case of KNN where you only have a hyperparameter. In other words, are you taking each data point in the current holdout fold then calculating the classification based on distance to the points in the current training (i.e. non-holdout) set, then iterating through points in the holdout data, then across the different folds? What is the actual algorithm for that process? – user3614648 Nov 19 '19 at 19:00
• K in KNN is a hyperparameter. Accordingly, you determine the best K using a grid search. Your question was unclear. – Windstorm1981 Nov 21 '19 at 2:48

Cross validation can be applied as long as the model is predictive (i.e. $$\mathbf x \mapsto y$$), regardless of how that model works internally. This general applicability is one of the strong advantages of cross validation. And it also implies that there is nothing special in the cross validation of a k-nearest neighbour model compared to, say, a logistic regression model.

$$k$$NN produces predictions by looking at the $$k$$ nearest neighbours of a case $$\mathbf x$$ to predict its $$y$$, so that's fine. In particular, the $$k$$NN model basically consists of its training cases - but that's the cross validation procedure doesn't care about at all.

We may describe cross validation as:

loop over splits $$i$$ {

1. split data into $$\mathbf Z_i$$ (train) and $$\mathbf W_i$$ (test)
2. $$model$$ := training_function ($$\mathbf Z_i$$, further parameters)
3. $$predictions_i$$ := prediction_function ($$model$$, $$\mathbf W_i$$)

}

calculate figure of merit from all $$predictions$$ and reference values

training_function and prediction_function are just the same training and prediction functions that are used to produce a production model.

Now, the $$k$$NN training_function would just store the training cases and the chosen $$k$$ in $$model$$, and the $$k$$NN prediction_function would then look up the $$k$$ (number taken from $$model$$) closest training cases (also taken from $$model$$) to the submitted case(s) and calculate the prediction from their $$y$$ values.

So the only thing that is a bit peculiar with $$k$$NN compared to many other models is that the trainings function may not be doing much "proper work" (though that is really true only for the brute force approach, there are ways to put the training data into structures that allow easier prediction and those do "proper work" during training).

• To make sure I understand: you take training cases and chosen K, then take your test set and find the nearest neighbor(s) in the training set for each point in the test set?*In other words, you never allow a point in the test set to have a nearest neighbor that is in the test set? You would then calculate some performance metrix for the entire test set (i.e. share of points correctly classified) for a given K, then repeat the process for another K with the *same training and test data? – user3614648 Nov 17 '19 at 21:18
• Training and Test (or optimization) sets need to be disjoint wrt. cases as you want to get an estimate of your figure of merit for predicting unknown cases. Two independent cases may have equal feature vectors, though and in that case the test case would coincide with a training case. Whether cases in the test set are closeby or not isn't of any concern: they are treated each on its own. – cbeleites unhappy with SX Nov 18 '19 at 10:40
• "repeat process for another K": which K are you talking about: the cross validation fold number or the number of nearest neighbours? (My answer doesn't tackle the question of how to optimize the number of nearest neighbours - you need to understand first how to do cross validation with fixed no of NN) – cbeleites unhappy with SX Nov 18 '19 at 10:41
• going to leave the question unanswered since everyone wanted to explain cross-validation but not cross-validation for selection of the K parameter in KNN. – user3614648 Nov 18 '19 at 18:47
• @user3614648: optimizing the hyperparameter is basically independent of the cross validation procedure as applied to $k$ nearest neighbours. The only link is that you may use the generalization error estimate of the cross validation in pretty much the same way you'd use the generalization error estimated by a single test set. I do think that you still have a very basic misunderstanding about kNN, though: kNN predicts perfectly well for a test set consisting of 1 case, regardless how large k is. The neighbours of the test (to be predicted) case are sought in the training data. – cbeleites unhappy with SX Nov 18 '19 at 19:21

Your confusion might stem from the fact that for KNNs the workload shifts from training to predicting:

Training a KNN model means basically just loading the training data (as long as you do not do anything fancy like creating a hash table for more efficient neigbor lookup later). There is no optimization, no gradient descent, no weight adjustments etc. However, when doing a prediction you need to solve an optimization problem to find the $$K$$ nearest neighbors! So that is where the "magic" is happening.

Using a method like logistic regression has the opposite workload distribution: Training the model means solving an optimization problem to define your weights. However, doing the prediction is pretty simple. Just plug in the numbers and calcuate the result.

Nevertheless both methods have a training and a prediction phase. And accordingly there is conceptually no difference when using cross validation. You can do it to compare KNNs for different levels of $$K$$ just as you would do it for different levels of $$max depth$$ with a decision tree. And you can use cross validation to compare your KNN to that decision tree or the logistic regression model you have trained.

• This provides a seemingly diff explanation of "training" compared to that offered in @cbeiletes's answer. What would be helpful is something explaining each step, e.g.: (1) Split data X into test (W) training set (Z) (2) Generate a vector of values of K. (3) Select a point from Z and obtain KNN classification using ONLY the data from W for a value of K. (4) Iterate through points in Z to find the KNN classification based on the data in W for the same K. (5) Calculate classification error across all points in Z for that value of K. (6) Repeat for different K, select lowest error K. – user3614648 Nov 17 '19 at 21:26
• @user3614648: Sammy's answer says the same I'm saying - just in different words. – cbeleites unhappy with SX Nov 18 '19 at 10:42