5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ What happens if two points have exactly the same feature vector? $\endgroup$
    – Sycorax
    Sep 30, 2021 at 16:16
  • $\begingroup$ @Sycorax well in my case (when there is only 1 class), it doesn't matter $\endgroup$
    – Slim Shady
    Sep 30, 2021 at 16:18
  • $\begingroup$ A more typical usage of kNN includes training data with 2 or more classes. The last sentence of your question asks “ What would other situations look like that aren't what I thought of?” $\endgroup$
    – Sycorax
    Sep 30, 2021 at 16:22

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.