Does kNN algorithm require that the distance follows distance axioms? What happened if I apply a metric which fails:
d(a,c) < d(a,b) + d(b,c)
Same question for KMeans clustering?
Asked
Active
Viewed 60 times
0
-
see my edit, it was a bit late when i answered yesterday, and it didnt cover everything – Kicsi May 18 '14 at 14:53
1 Answers
0
kNN only requires a proximity measure where the smaller value means closer. That is because kNN compares the new observation with the training examples and finds the k closest ones (the first k with the lowest proximity value). For kMeans use search.
EDIT: Even though kNN doesnt need the triangle equation, it runs in O(n*m) time, where n is the size of the training set and m is the size of the evaluated set. Optimizations usually require at least the triangle equation to stand, although some of them have more constraints (eg: k-d trees only work in euclidean space). See this question for more info.
