# Metric for nearest neighbor method

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?

• 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.) – Michael M Nov 11 '13 at 18:18
• 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. – Dzung Nguyen Nov 11 '13 at 18:30

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.