Distance and scale in nearest neighbours
Section of Nearest neighbours, part of Statistical learning
Distance and scale in nearest neighbours
| Type | Section |
| Taught in | Nearest neighbours |
| Part | Statistical learning |
The rule is only as good as its notion of closeness. Any metric that matches the closeness that matters can be used. The usual default is Euclidean distance, the L_2 norm, because it is the ordinary geometric distance once the coordinates are on comparable scales:
\|x-x_i\|_2 =\sqrt{(x-x_i)\cdot(x-x_i)} =\sqrt{(x_1-x_{i1})^2+\cdots+(x_p-x_{ip})^2}.
Euclidean distance depends on scale. Changing metres to centimetres multiplies a coordinate’s squared contribution by 10^4, because each difference is multiplied by 100 and then squared. Subtracting a common mean leaves every distance exactly unchanged, because the mean cancels inside x_j-x_{ij}. Standardisation divides by a training-sample measure of spread and therefore changes the metric. Use the same fitted transformation on new observations. Recomputing it with held-out data changes the procedure being assessed.
Example 1 (Rescaling one coordinate) Take two classes of ten points each, class 1 at (x,x) and class 2 at (x+3.5,x) for x=1,\ldots,10.
Question. What happens to leave-one-out 1-nearest-neighbour accuracy if the first coordinate is multiplied by 10?
Solution. In the original units the two clouds are separated along a diagonal band. Leaving each point out in turn, all 20 are classified correctly, so the leave-one-out accuracy is 1. Multiply the first coordinate by 10. Distances are now dominated by differences in x_1, so a point’s nearest neighbours are points with similar x_1 regardless of class. The leave-one-out accuracy falls to 0.30. Both comparisons can be drawn in the original coordinates. The second classifier multiplies the first coordinate by ten only when it computes distance. Neither choice of units is the correct one by itself. The classifier depends on that choice.
Describing the same observations in different units need not leave the classifier unchanged. Scaling is one way to specify what comparable differences mean. A standard deviation uses second moments and can be unstable for heavy tails. An interquartile range uses a different notion of spread. Neither makes an irrelevant predictor useful. The scientific question still has to determine which differences should count.
A rank distance
Main article: Rank distance
Ranks offer a different trade-off. They preserve order while discarding spacing, so a very large value is simply the largest rank rather than an arbitrarily distant point. A strictly increasing coordinate transformation leaves the ranks unchanged. This is useful when order is meaningful and spacing is unreliable, and it loses information when actual distances matter.
The rank distance of Olshen (1977) and Devroye (1978) does this one coordinate at a time. For each predictor, the training values and the new observation’s value are ranked from 1 to n+1, from smallest to largest. Let r_i^{(j)} be the rank of the jth component of the ith training observation, and let r^{(j)} be the rank of the jth component of the new observation.
Definition 1 (Rank distance) The empirical distance uses the worst coordinate, the L_\infty distance on the ranks:
\rho(x,x_i)=\max_{1\le j\le p}\bigl|r_i^{(j)}-r^{(j)}\bigr|.
Any strictly increasing transformation of a single coordinate, including a change of units, leaves the ranks unchanged, so it leaves \rho unchanged. The distances are integers, so ties are common. They are usually broken by a uniform random ordering among the tied neighbours. The metric has bought invariance by throwing away spacing. If the spacing is real information, for instance if two units of x_1 are known to be equivalent to one unit of x_2, the ranks are the wrong summary. Use the information: replace x_1 by x_1'=x_1/2 so that one unit means the same thing on both axes, and then compute an ordinary distance. Scaling, ranks, and a subject-matter equivalence are three answers to the same difficulty, and they are answers about the metric, not about k.
Used in
See also
Rank distance · -nearest neighbours · Bayes consistency of -nearest neighbours · Ties and the choice of k · Consistency and the factor of two · Laboratory: what a distance metric changes · Cover–Hart bound