Exact Leave-One-Out Cross-Validation for k-Nearest-Neighbour Regression from a Single Neighbour Search: The (k+1)/k Shortcut, a Check on Three UCI Data Sets, and Where Distance Ties Break It

Leave-one-out cross-validation (LOO) of k-nearest-neighbour regression usually means refitting the model n times. I prove that if each point is its own nearest neighbour and there is no distance tie at the boundary of its k+1 nearest neighbours, the LOO residual equals (k+1)/k times the residual of the in-sample average over the k+1 nearest neighbours including the point itself. One neighbour search therefore gives exact LOO errors for every k. On the UCI combined-cycle power plant (9,527 rows after removing 41 duplicates) and concrete (996 rows after removing 34 duplicates) data sets, the shortcut matches brute-force LOO for 400 sampled rows to within 2e-13. On the airfoil self-noise data, where 14.57% of rows have a tie between their 6th and 7th neighbours, 1.25% of sampled rows differ, by up to 3.11 decibels. The method needs duplicate feature rows removed and a check for ties. LOO and 10-fold cross-validation choose the same k for two data sets (k = 5 and k = 2) and different k for concrete (1 by LOO, 3 by 10-fold), where the LOO curve is not monotone and its minimum is shallow.