# Training set as donor for test set in binary classification problem

I am wondering if there exists such a method in machine learning that:

Given a binary classification problem, for each person in the test set the person that most closely resembles this person in the training set acts as a donor for the value; either 0 or 1.

Could someone show point me in a direction?

Note: For instance, you have the variables age, sex and income. Sex has less spread, so we might standardize this variable to make it comparable with standardized age and income. It might then be calculated which person most closely relates to each test person.

• I just implemented something like this, and its performance seems lower than that of a pruned classification tree (based on Kaggle, titanic data). – PascalVKooten Oct 4 '13 at 23:53
• I improved it by choosing the mean of the 5 "closest", but it is still not near the classification tree. (closest: 0.68 error, best of 5: 0.72 error, 0.77 is classification tree). – PascalVKooten Oct 5 '13 at 0:04

## 1 Answer

What you describe is probably one of the oldest and most well known classifiers, the $k$-nearest neighbors ($k$-nn) classifier with $k=1$.

It has some interesting thoerectical properties. For example, as the number of training points $n \to \infty$ the error rate of the 1-nn classifier is at most twice the Bayes error. See this or this set of lecture notes for more information and results of this type.

In practice $k$-nn can be quite successful provided you have a meaningful distance function for your problem. The biggest drawbacks are the amount of time it takes to classify at test time and being particularly susceptible to the curse of dimensionality. It is worth noting the former of these can be overcome by the use of specialized data structures like M-trees or BK-trees, or approximate nearest neighbor algorithms.

• The first link misses "df" in ".pdf". – PascalVKooten Oct 5 '13 at 14:29
• Is there any situation in which it will be one of the best performing algorithms? – PascalVKooten Oct 5 '13 at 14:30
• @Dualinity sorry about that, link fixed. Questions like "which classifier will perform best for this given finite dataset" are always best answered empirically. However, I would say that if you have a reasonable amount of data which is relatively low dimensional, $k$-nn should at least be consider. – alto Oct 5 '13 at 14:56