15
$\begingroup$

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$
2
  • 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, 2017 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, 2017 at 13:48

1 Answer 1

25
$\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$
7
  • $\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, 2017 at 13:31
  • $\begingroup$ I updated the answer, hope it helps! $\endgroup$
    – Cherny
    Aug 21, 2017 at 13:55
  • 5
    $\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$ Mar 9, 2018 at 1:50
  • $\begingroup$ That's why I wrote "for normalized vectors" :) $\endgroup$
    – Cherny
    Mar 11, 2018 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, 2019 at 1:20

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