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.

  • $\begingroup$ I just implemented something like this, and its performance seems lower than that of a pruned classification tree (based on Kaggle, titanic data). $\endgroup$ – PascalVKooten Oct 4 '13 at 23:53
  • $\begingroup$ 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). $\endgroup$ – PascalVKooten Oct 5 '13 at 0:04

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.

  • $\begingroup$ The first link misses "df" in ".pdf". $\endgroup$ – PascalVKooten Oct 5 '13 at 14:29
  • $\begingroup$ Is there any situation in which it will be one of the best performing algorithms? $\endgroup$ – PascalVKooten Oct 5 '13 at 14:30
  • 1
    $\begingroup$ @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. $\endgroup$ – alto Oct 5 '13 at 14:56

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.