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$
1
  • 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, 2018 at 21:40

1 Answer 1

Reset to default
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$
10
  • $\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, 2018 at 8:45
  • $\begingroup$ Do you mean when $p$ is very high? $\endgroup$
    – David Masip
    May 17, 2018 at 8:46
  • $\begingroup$ When p is greater than 2 $\endgroup$
    – Qwerto
    May 17, 2018 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, 2018 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, 2018 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.