Describe a situation where a training point can be removed without affecting the resulting 1-NN classification for any test point in the input space

Question

I have the following question in my textbook:

One of the drawbacks of the nearest-neighbour algorithm is that we must retain all of the training data. Describe a situation where a training point can be removed without affecting the resulting 1-NN classification for any test point in the input space.

One such situation would be if there is only 1 class? Then all of the future test points would be classified as that class.

I can't imagine another situation since from my understanding, for the 1-NN to work, there needs to be at least some datapoints which it would "compare similarity" (measure the distance) with and decide whether it would be some class.

What would other situations look like that aren't what I thought of?

Answer 1

If a training point is "surrounded" by other training points of the same class, removing the central point will not change the 1-NN classification anywhere. Imagine a ring of training points with one point inside the ring, and that all of these points are of the same class. Removing the point inside the ring won't change any classifications, since anything that used that point as its nearest neighbor has a second nearest neighbor of the same class. You could also imagine a large, dense cloud of points all sharing the same class - the many points on the interior of the cloud are redundant, and you don't need them all to define the exact same 1-NN class boundaries.

You can evaluate a data point for removal by identifying the neighborhood in which that point is the nearest neighbor. If every possible point in that neighborhood has a second nearest neighbor of the same class, the point can be removed without affecting 1-NN classification. To put it another way, if a point's "nearest neighborhood" is completely overlapped by "second-nearest neighborhoods" of the same class, removing the point will not affect 1-NN classification.