27
$\begingroup$

Identical meaning, that it will produce identical results for a similarity ranking between a vector u and a set of vectors V.

I have a vector space model which has distance measure (euclidean distance, cosine similarity) and normalization technique (none, l1, l2) as parameters. From my understanding, the results from the settings [cosine, none] should be identical or at least really really similar to [euclidean, l2], but they aren't.

There actually is a good chance the system is still buggy -- or do I have something critical wrong about vectors?

edit: I forgot to mention that the vectors are based on word counts from documents in a corpus. Given a query document (which I also transform in a word count vector), I want to find the document from my corpus which is most similar to it.

Just calculating their euclidean distance is a straight forward measure, but in the kind of task I work at, the cosine similarity is often preferred as a similarity indicator, because vectors that only differ in length are still considered equal. The document with the smallest distance/cosine similarity is considered the most similar.

$\endgroup$
  • $\begingroup$ It all depends on what your "vector space model" does with these distances. Could you be more specific about what the model does? $\endgroup$ – whuber Apr 13 '15 at 23:08
  • $\begingroup$ Sorry, sometimes it's hard to get out of my own head. I added a specification. $\endgroup$ – Arne Apr 13 '15 at 23:24
  • $\begingroup$ You still don't describe any model. In fact, the only clue you have left concerning the "kind of task (you) work at" is the nlp tag--but that's so broad it doesn't help much. What I'm hoping you can supply, so that people can understand the question and provide good answers, is sufficient information to be able to figure exactly how you are using your distance measure and how it determines what the "results" might be. $\endgroup$ – whuber Apr 14 '15 at 0:48
  • $\begingroup$ stats.stackexchange.com/a/36158/3277. Any angular aka sscp-type similarity is convertible to its corresponding euclidean distance. $\endgroup$ – ttnphns Sep 30 '16 at 12:18
28
$\begingroup$

For $\ell^2$-normalized vectors $\mathbf{x}, \mathbf{y}$, $$||\mathbf{x}||_2 = ||\mathbf{y}||_2 = 1,$$ we have that the squared Euclidean distance is proportional to the cosine distance, \begin{align} ||\mathbf{x} - \mathbf{y}||_2^2 &= (\mathbf{x} - \mathbf{y})^\top (\mathbf{x} - \mathbf{y}) \\ &= \mathbf{x}^\top \mathbf{x} - 2 \mathbf{x}^\top \mathbf{y} + \mathbf{y}^\top \mathbf{y} \\ &= 2 - 2\mathbf{x}^\top \mathbf{y} \\ &= 2 - 2 \cos\angle(\mathbf{x}, \mathbf{y}) \end{align} That is, even if you normalized your data and your algorithm was invariant to scaling of the distances, you would still expect differences because of the squaring.

$\endgroup$
  • $\begingroup$ Would this have an influence on ranking? Meaning, if I sort a number of vectors 'v_i in V' by their cosine distance to a vector 'u', I get a specific order for them. Would ranking those same vectors with l_2 normalized euclidean distance produce the same order? $\endgroup$ – Arne Apr 14 '15 at 16:18
  • 2
    $\begingroup$ iirc, since squaring is a monotic transformation (for positive numbers), it cannot change the order of a sequence sorted by length. $\endgroup$ – Arne Apr 14 '15 at 16:21
  • 5
    $\begingroup$ You are right, if all you do is rank the vectors by their distance to $\mathbf{u}$, using cosine distance should give the same result as Euclidean distance (for normalized vectors). $\endgroup$ – Lucas Apr 14 '15 at 16:22
  • $\begingroup$ Thank you, do you happen to have a citable source for this connection? $\endgroup$ – Arne Apr 14 '15 at 16:25
  • 1
    $\begingroup$ Well, I guess 'Linear Alebra I' has to suffice then ;) thanks again for the insight! $\endgroup$ – Arne Apr 14 '15 at 16:37
5
$\begingroup$

Standard cosine similarity is defined as follows in a Euclidian space, assuming column vectors $\mathbf{u}$ and $\mathbf{v}$: $$ \cos(\mathbf{u}, \mathbf{v}) = \frac{\langle \mathbf{u}, \mathbf{v} \rangle}{\|\mathbf{u}\| \cdot \|\mathbf{v}\|} = \frac{\mathbf{u}^T\mathbf{v}}{\|\mathbf{u}\| \cdot \|\mathbf{v}\|} \in [-1, 1]. $$ This reduces to the standard inner product if your vectors are normalized to unit norm (in l2). In text mining this kind of normalization is not unheard of, but I wouldn't consider that the standard.

$\endgroup$

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.