0
$\begingroup$

I have a question regarding the Condensed Nearest Neighbor algorithm from chapter "Nonparametric Methods" in the book Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004. pp. 174–174.

the Condensed Nearest Neighbor algorithm

Ultimately, I am supposed to return the subset Z to be a local minimal subset to use for training set in KNN. Why am I returning Z, which, if I understand correctly, is the array of all of the misclassified points? Wouldn't I want to return the points that were classified correctly? What benefit does this give me in returning all the points I got wrong?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

Z is not the array of misclassified points. Try working through an example, and be careful and precise when making statements like that; while you can talk about which points are classified by a particular classifier, that will depend on the classifier. So, when there are multiple classifiers floating around (or multiple training sets floating around), you need to specify which classifier you are referring to. I suspect this is what is tripping you up: something that is misclassified with one training set might be correctly classified with another training set.

The key guarantee of this procedure is: if you use Z as your training set for a nearest-neighbor classifier, then this NN classifier will have 100% accuracy. Try working through an example to see why. (It iteratively grows the training set as needed to ensure that every point will be classified correctly by that NN classifier.)

As always, when you are confused, start by working through a small example with a few points (two, three, four), simulating the algorithm by hand, with pencil and paper. That will often be very effective at building intuition -- and in this case it should be sufficient to understand what is going on.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer. I HAVE implemented this (and, correctly, according to my TA), which is why I am posting because I do not understand it. Line 5 of the pseudocode instructs us to test the "classification" to see if we guessed correctly, and if we did not, to add the evaluation point to which we did not guess correctly to Z. I then return Z to use as my training set in another algorithm. $\endgroup$
    – artemis
    Commented Mar 11, 2019 at 17:27
  • $\begingroup$ @JerryM., I didn't mean you should implement it. I meant you should work through an example. I mean you should work through it by hand, simulating the algorithm with pencil and paper and a picture. Also, when you say "classification", it's important to be precise about the classification with respect to which classifier and which training set, as I suspect that is what is tripping you up. Something that is misclassified with one training set might be correctly classified with another training set. $\endgroup$
    – D.W. ♦
    Commented Mar 11, 2019 at 18:10
  • $\begingroup$ I've edited my answer to elaborate on that point a bit more. $\endgroup$
    – D.W. ♦
    Commented Mar 11, 2019 at 18:15
0
$\begingroup$

The idea is to form a subset ($Z$) of the training set such that it classifies the same way as the whole set, using the nearest-neighbor rule.

If a classification error occurs, adding to $Z$ the element that causes the error will obviously fix the error. You continue until there are no more errors.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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