Most discussions of KNN mention Euclidean,Manhattan and Hamming distances, but they dont mention cosine similarity metric. Is there a reason for this?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ This problem is called "maximum inner product search". There are efficient solutions. $\endgroup$– EmreCommented Jan 9, 2018 at 17:34
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
Short answer: Cosine distance is not the overall best performing distance metric out there
Although similarity measures are often expressed using a distance metric, it is in fact a more flexible measure as it is not required to be symmetric or fulfill the triangle inequality. Nevertheless, it is very common to use a proper distance metric like the Euclidian or Manhattan distance when applying nearest neighbour methods due to their proven performance on real world datasets. They will therefore be often mentioned in discussions of KNN.
You might find this review from 2017 informative, it attempts to answer the question "which distance measures to be used for the KNN classifier among a large number of distance and similarity measures?" They also consider inner-product metrics like the cosine distance.
In short, they conclude that (no surprise) no optimal distance metric can be used for all types of datasets, as the results show that each dataset favors a specific distance metric, and this result complies with the no-free-lunch theorem. It is clear that, among the metrics tested, the cosine distance isn't the overall best performing metric and even performs among the worst (lowest precision) in most noise levels. It does however outperform other tested distances in 3/28 datasets.
So can I use cosine similarity as a distance metric in a KNN algorithm? Yes, and for some datasets, like Iris, it should even yield better performance (p.30) compared as to Euclidian.
-
$\begingroup$ big +1 for posting link to highly relevant paper, thanks! I'm gonna have to compare L2 and cosine for my use case, I'll let you know what I find. $\endgroup$– MerlinCommented Dec 23, 2020 at 4:40
$\begingroup$
$\endgroup$
as Lejafar mentioned cosine violates triangle inequality however maybe this repo will help you
$\begingroup$
$\endgroup$
2
Although cosine similarity is not a proper distance metric as it fails the triangle inequality, it can be useful in KNN.
However, be wary that the cosine similarity is greatest when the angle is the same: cos(0º) = 1, cos(90º) = 0. Therefore, you may want to use sine or choose the neighbours with the greatest cosine similarity as the closest.
-
$\begingroup$ I'm minimizing L2, but I should maximize cosine distance -- dang this is a good callout thank you $\endgroup$– MerlinCommented Dec 23, 2020 at 4:42
-
$\begingroup$ use 1 - cosine similarity. it is the method of choice in many papers on clustering $\endgroup$ Commented Mar 25, 2021 at 4:19
$\begingroup$
$\endgroup$
4
If there does exist a reason it probably has to do with the fact the Cosine distance is not a proper distance metric. Nevertheless, it's still a useful little thing.
-
$\begingroup$ 'Cosine distance is not a proper distance metric' -- Why? $\endgroup$– Dawny33Commented Jan 9, 2018 at 16:35
-
1$\begingroup$ It fails the triange inequality which is a requirement for a proper distance metric. $\endgroup$– TophatCommented Jan 9, 2018 at 16:37
-
$\begingroup$ Interesting. I understand that it fails the triangle inequality. But, that that it is a requirement for a proper distance metric, is a new info to me. Thanks :) $\endgroup$– Dawny33Commented Jan 9, 2018 at 16:41
-
$\begingroup$ View definition of a metric here by en.wikipedia.org/wiki/Metric_(mathematics) $\endgroup$– TophatCommented Jan 9, 2018 at 16:49