2
$\begingroup$

I'm studying the knn classification algorithm. Why can the euclidean distance be considered a nice measure of affinity between examples ?

In one dimension (1 attribute) this seems correct, but if I add dimensions, can the euclidean distance still be considerd a good measure of affinity? Why?

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Your premise is incorrect. Euclidean distance is not the only distance function used for knn or k-means or etc. These models can work with any distance function. $\endgroup$ – Ricardo Cruz May 17 '18 at 21:40
3
$\begingroup$

You can think of examples as vectors in $\mathbb{R}^p$, where $p$ is the number of features. Two examples will be very similar if the distance between them is close to $0$ (in the extreme case, if two examples are equal their euclidean distance is $0$). One way to measure the distance is using euclidean distance, but other distances can be used, as cosine distance or $L^p$ metrics. In fact, if $p$ is very high, then Euclidean distance is not a good measure, as it tends to make the distances too uniform (see this paper).

Edit: When $p$ is very high:

See this magnificient answer to the issues that very high $p$ may have.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Growing the dimensions the distances get bigger. But maybe it's not a problem and maybe the euclidean distance still gives a good measure of affinity. Why not ? $\endgroup$ – Qwerto May 17 '18 at 8:45
  • $\begingroup$ Do you mean when $p$ is very high? $\endgroup$ – David Masip May 17 '18 at 8:46
  • $\begingroup$ When p is greater than 2 $\endgroup$ – Qwerto May 17 '18 at 8:49
  • $\begingroup$ When $p$ is not very big, the euclidean distance works. What's the problem with that? $\endgroup$ – David Masip May 17 '18 at 8:50
  • $\begingroup$ In practice, growing the dimensions and considering euclidean distance, you are giving more "degrees of freedom" to the examples to be considered affine to the query example. Am i correct ? $\endgroup$ – Qwerto May 17 '18 at 8:51

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.