What is the problem with an asymmetric distance measure in k-NN classifier?

I think it will not cause problem, so long as I compute the distance consistently, say always from test_data to labeled_data.


It has to be symmetric. The reason is because, KNN can be viewed as a non-parametric kernel density estimation problem. In the estimation problem you get a term of the form $K(x-x_{i})$ and $K$ is a Kernel which has to be symmetric (see http://en.wikipedia.org/wiki/Variable_kernel_density_estimation)

Intutively I think this can be explained by noting that two "extremely close" points can get different classifications which is not desirable

| cite | improve this answer | |
  • $\begingroup$ Ok, but what about the other criteria for distance---triangle inequality? It is much more difficult to prove than symmetry especially my distance function is highly nonlinear $\endgroup$ – Sibbs Gambling Mar 22 '15 at 7:55
  • $\begingroup$ It is a distance metric therefore has to satisfy the triangle inequality.. $\endgroup$ – Sid Mar 22 '15 at 8:04

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.