# Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from “Nonparametric Methods.” Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004, pp. 174–174: ! [“Nonparametric Methods.” Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004, pp. 174–174.]1

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?

• Can you edit your question to credit the original source where you obtained that screenshot/pseudocode from? (If it's a paper, please also provide title, authors, where published, and a link to a freely available pdf if available.) I don't see anything in there that pseudocode that says you are returning z; why do you think that you are? I suspect there's additional context you haven't provided us. – D.W. Mar 11 at 17:06
• Done @D.W. I am supposed to return Z to use that minimal subset to then use as my training set in KNN. – Jerry M. Mar 11 at 17:14

## 1 Answer

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.

• 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. – Jerry M. Mar 11 at 17:27
• @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. – D.W. Mar 11 at 18:10
• I've edited my answer to elaborate on that point a bit more. – D.W. Mar 11 at 18:15