10
$\begingroup$

This question already has an answer here:

I am currently solving a problem where I have to use Cosine distance as the similarity measure for k-means clustering. However, the standard k-means clustering package (from Sklearn package) uses Euclidean distance as standard, and does not allow you to change this.

Therefore it is my understanding that by normalising my original dataset through the code below. I can then run kmeans package (using Euclidean distance); will it be the same as if I had changed the distance metric to Cosine distance?

from sklearn import preprocessing  # to normalise existing X
X_Norm = preprocessing.normalize(X)

km2 = cluster.KMeans(n_clusters=5,init='random').fit(X_Norm)

Please let me know if my mathematical understanding of this is incorrect.

$\endgroup$

marked as duplicate by gung, Nick Cox, mdewey, Michael Chernick, Peter Flom Aug 22 '17 at 12:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ There were many questions like that already asked and answered. Please search K-means euclidean K-means cosine K-means spherical. $\endgroup$ – ttnphns Aug 21 '17 at 13:17
  • $\begingroup$ Sorry I did, but I just wanted to double check that my understanding is correct. As i'm sure you can appreciate, wrapping your head around this can be difficult. However, as it stands now and as per @Cherny great explanation below, by normalizing my data, it in effect the same as if I have used cosine similarity. $\endgroup$ – MSalty Aug 21 '17 at 13:48
17
$\begingroup$

It should be the same, for normalized vectors cosine similarity and euclidean similarity are connected linearly. Here's the explanation:

Cosine distance is actually cosine similarity: $\cos(x,y) = \frac{\sum x_iy_i}{\sqrt{\sum x_i^2 \sum y_i^2 }}$.

Now, let's see what we can do with euclidean distance for normalized vectors $(\sum x_i^2 =\sum y_i^2 =1)$:

$$\begin{align} ||x-y||^2 &=\sum(x_i -y_i)^2 \\ &=\sum (x_i^2 +y_i^2 -2x_iy_i) \\ &= \sum x_i ^2 +\sum y_i^2 -2\sum x_iy_i \\ &= 1+1-2\cos(x,y)\\ &=2(1-\cos(x,y)) \end{align}$$

Note that for normalized vectors $\cos(x,y) = \frac{\sum x_iy_i}{\sqrt{\sum x_i^2 \sum y_i^2 }} =\sum x_iy_i$

So you can see that there is a direct linear connection between these distances for normalized vectors.

$\endgroup$
  • $\begingroup$ That would be great if you could explain it for me, I'm still trying to get my head around this fully. Thank you! $\endgroup$ – MSalty Aug 21 '17 at 13:31
  • $\begingroup$ I updated the answer, hope it helps! $\endgroup$ – Cherny Aug 21 '17 at 13:55
  • 3
    $\begingroup$ I don't see a linear connection. As per your equation: d^2 is linearly related to cos(x, y) and not d. In other words, squared Euclidean distance is linearly related to cosine distance and not just Euclidean distance. Also this holds only and only when vectors are normalized (unit vectors) $\endgroup$ – Trideep Rath Mar 9 '18 at 1:50
  • $\begingroup$ That's why I wrote "for normalized vectors" :) $\endgroup$ – Cherny Mar 11 '18 at 11:40
  • $\begingroup$ Quick question, one major reason opting cosine similarity over euclidean distance will be to avoid ineffectiveness of euclidean distance when handling high dimensionality and sparse dataset. So, shouldn't it be better to use cosine similarity and how will this linear connection play a role? $\endgroup$ – timekeeper Mar 11 at 1:20

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