3
$\begingroup$

Is there a requirement that the measure used in Nearest Neighbor methods be a proper metric distance? What will happen if I use an arbitrary function (e.g., one that does not satisfy the triangle inequality)?

How can you convert an arbitrary function to a valid metric distance?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ In principle, you can use any non-negative real-valued function to evaluate distances. Obviously not all of them are useful though (take for instance the constant null function.) $\endgroup$
    – Michael M
    Nov 11 '13 at 18:18
  • $\begingroup$ I though it must satisfy the triangle inequality d(A,B)<d(A,C)+d(C,B). I think some NN algorithms such as KdTree based on that assumption. $\endgroup$
    – Dzung Nguyen
    Nov 11 '13 at 18:30
3
+50
$\begingroup$

Replacing the euclidean distance in kNN with another distance function is equivalent to "kernelizing it." A valid Mercer kernel is any function taking two observations that is continuous, symmetric and has a positive definite covariance matrix $\forall x \in D$. Many interesting properties such as stationarity can be imbued in a kernel that make it an attractive option for things like, time-series and geospatial statistics. There exists kernels for structured input that otherwise could not be represented as fixed length vectors. There exists kernels in the literature that are not valid Mercer kernels and still empirically perform well.

If you would like to know more about kernels, I'd recommend reviewing the literature on Gaussian Processes and SVMs.

Improve this answer
$\endgroup$

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.