What does condensed nearest neighbour remove from a training set, and what does it risk?

## The problem it solves Exact neighbour search costs `O(n*d)` per query and stores `n*d` values. Trees attack that by skipping candidates. **Prototype selection attacks it from the other end: make `n` smaller.** Condensed nearest neighbour (the CNN rule, Hart 1968) is the classic instance. ## The intuition Under 1-NN, the label a query receives is decided entirely by the decision boundary between classes. A point sitting deep inside a large, pure region of its own class contributes nothing: remove it, and its neighbours of the same class still produce the same label everywhere. A point sitting right against the other class carries the boundary and cannot be removed without moving it. So the useful subset is the boundary points, and everything interior is redundant. ## The algorithm 1. Initialise the subset `S` with a single training point (often the first, or one per class). 2. Sweep the remaining training points. For each point, classify it by 1-NN against `S` only. 3. If the prediction is wrong, move that point into `S`. If it is right, leave it out. 4. Repeat the sweep over the still-excluded points until an entire pass adds nothing. 5. Return `S`, and discard the rest. What `S` gains is the property called **consistency**: run 1-NN with `S` as the stored set over every original training point and you reproduce the original label for all of them. That is a guarantee about the *training* data, not about held-out data — worth stating precisely, because the two get conflated. ## What it buys Because interior mass is exactly what large datasets are made of, the reduction can be dramatic. A million-row training set with well-separated classes can condense to a few thousand boundary prototypes — a three-order-of-magnitude cut in both the per-query scan and the resident memory, with the decision boundary in the interior of the data essentially unchanged. That is the trade that makes it interesting: unlike a faster index, it reduces the *data*, so the savings hit memory and query cost together and hold whatever search implementation you use on top. ## The four things that go wrong **Noise is preserved, not removed.** A mislabelled point is by construction misclassified by its correctly-labelled neighbours, so step 3 always adds it — and once it is in `S`, it also drags in the genuine points around it that it now misclassifies. The rule concentrates exactly the rows you most wanted to lose. The standard fix is to *edit before you condense*: first run an editing pass (the edited nearest-neighbour rule, Wilson 1972) that deletes any training point whose own neighbours disagree with its label, cleaning the boundary, and only then condense the survivors. **It is order-dependent and not minimal.** Sweep the data in a different order and you get a different subset, generally of a different size. CNN finds *a* consistent subset, not the smallest one; finding the minimum is much harder and rarely worth it. **It is built for 1-NN.** The consistency argument is about the single nearest stored point. If you then query with more than one neighbour, the guarantee no longer holds, and the vote is being taken over a set whose local density has been deliberately destroyed. **Density information is gone.** Interior points were removed precisely where a class was dense, so the surviving mixture no longer reflects how much data sat where. Any use of the neighbourhood composition as a confidence or probability estimate becomes unreliable after condensing, even where the hard label is unchanged. ## Using it responsibly Treat condensing as a change to the model and validate it as one. Hold out a genuine test set *before* condensing, condense using training data only, and compare held-out accuracy from the full set against the reduced set — the consistency property says nothing about that number. Record the reduction ratio alongside the accuracy delta, since the entire justification is a cost saving. And keep the original data: the condensed set is a derived artefact you will want to rebuild after an editing pass, after a labelling fix, or when new data shifts the boundary. ## Where it sits There is a family here — editing rules that remove noisy points, condensing rules that remove redundant ones, and hybrids that do both — but the interview-relevant core is the pair of facts: condensing keeps boundary points and discards interior ones, and it keeps mislabelled points for the same reason it keeps boundary ones.