58 votes
Accepted

Is cosine similarity identical to l2-normalized euclidean distance?

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} ...
  • 5,832
26 votes

How I can convert distance (Euclidean) to similarity score

If $d(p_1,p_2)$ represents the euclidean distance from point $p_1$ to point $p_2$, $$\frac{1}{1 + d(p_1, p_2)}$$ is commonly used.
  • 7,524
25 votes
Accepted

Cosine Distance as Similarity Measure in KMeans

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) = \...
  • 664
19 votes
Accepted

Why is Kullback-Leilbler divergence a better metric for measuring distance between two probability distributions than squared error?

Overview: KL-Divergence is derived from the Shannon entropy. The Shannon entropy is the amount of information contained in a signal X with distribution $\mathrm{P}(X)$. The cross entropy is the ...
14 votes

How I can convert distance (Euclidean) to similarity score

You could also use: $\frac{1}{e^{dist}}$ where dist is your desired distance function.
11 votes

How I can convert distance (Euclidean) to similarity score

It sounds like you want something akin to cosine similarity, which is itself a similarity score in the unit interval. In fact, a direct relationship between Euclidean distance and cosine similarity ...
  • 81.3k
10 votes

Which distance to use? e.g., manhattan, euclidean, Bray-Curtis, etc

Choosing the right distance is not an elementary task. When we want to make a cluster analysis on a data set, different results could appear using different distances, so it's very important to be ...
10 votes
Accepted

Expected magnitude of a vector from a multivariate normal

The sum of squares of $p$ independent standard normal distributions is a chi-squared distribution with $p$ degrees of freedom. The magnitude is the square root of that random variable. It is sometimes ...
  • 1,002
10 votes

Is one-hot encoding and standardization of data equivalent to Gower's distance?

One hot encoding and then standardization puts much more weight on the categoricial variables. In particular, rare values will get a big distance. Gowers feels a bit more balanced to me. But in the ...
9 votes

How I can convert distance (Euclidean) to similarity score

How about a Gaussian kernel ? $K(x, x') = \exp\left( -\frac{\| x - x' \|^2}{2\sigma^2} \right)$ The distance $\|x - x'\|$ is used in the exponent. The kernel value is in the range $[0, 1]$. There ...
  • 2,043
9 votes

Why does k-means clustering algorithm use only Euclidean distance metric?

I might be a little pedantic here, but K-means is the name given to a particular algorithm that assigns labels to data points such that within cluster variances are minimized, and it is not the name ...
8 votes

Why does k-means clustering algorithm use only Euclidean distance metric?

Since this is apparently now a canonical question, and it hasn't been mentioned here yet: One natural extension of k-means to use distance metrics other than the standard Euclidean distance on $\...
  • 22.6k
8 votes

Definition of normalized Euclidean distance

The normalized squared euclidean distance gives the squared distance between two vectors where there lengths have been scaled to have unit norm. This is helpful when the direction of the vector is ...
  • 3,115
8 votes
Accepted

What is the inverse square of a distance (Euclidean)?

Imagine that we want to classify as red or blue the unknown gray point in the data cloud. Your algorithm is set up to measure ...
7 votes
Accepted

K-means: Why minimizing WCSS is maximizing Distance between clusters?

K-means is all about the analysis-of-variance paradigm. ANOVA - both uni- and multivariate - is based on the fact that the sum of squared deviations about the grand centroid is comprised of such ...
  • 53.3k
7 votes
Accepted

Efficient way to compute distances between centroids from distance matrix

Let the points be indexed $x_1, x_2, \ldots, x_n$, all of them in $\mathbb{R}^d$. Let $\mathcal{I}$ be the indexes for one cluster and $\mathcal{J}$ the indexes for another cluster. The centroids ...
  • 297k
7 votes
Accepted

Variance and asymptotic normality of $\frac{1}{n-1}\sum_{i=1}^{n-1}(x_{i+1}-x_i)^2$, where $X \sim \mathcal{N}(0,1)$

TLDR; $s(z)$ is asymptotically normal, and its variance is $\frac {12} {n-1}$ according to CLT for Markov chains. It can be shown that the distribution is a special case of generalized $\chi^2$ ...
  • 57.1k
6 votes

My neural network can't even learn Euclidean distance

The output seems to strongly suggest that one or more of your neurons goes dead (or perhaps the hyperplane of weights for two of your neurons have merged). You can see that with 3 Relu's, you get 3 ...
  • 13.4k
5 votes

Expected magnitude of a vector from a multivariate normal

The answer by user3697176 gives all the needed information, but nonetheless, here is a slightly different view of the problem. If $X_i \sim N(0,\sigma^2)$, then $Y = \sum_{i=1}^n X_i^2$ has a Gamma ...
5 votes

Is cosine similarity identical to l2-normalized euclidean distance?

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} \...
  • 17.6k
5 votes

Euclidean distance is usually not good for sparse data (and more general case)?

An axiomatic measure of sparsity is the so-called $\ell_0$ count, that counts the (finite) number of non-zero entries in a vector. With this measure, vectors $(1,0,0,0)$ and $(0,21,0,0)$ possess the ...
4 votes

Why does k-means clustering algorithm use only Euclidean distance metric?

I've read many interesting comments here, but let me add that Matlab's "personal" implementation of k-means supports 4 non-Euclidean distances [between data points and cluster centres]. The ...
4 votes

What is the PDF of $[(X-a)^2 + (Y-b)^2]^{1/2}$ where $X$ and $Y$ are two non-standard normal random variables?

Assume that $X$ and $Y$ are independent with known means/variances. Unfortunately, I don't think there's a nice standard form for the distribution of $Z$, but I'd be happy to be shown otherwise. Let $...
  • 22.6k
4 votes

Euclidean distance with sparse and high dimension data

A much better similarity measure for sparse and high dimensional data is that of cosine similarity: $$ s(x, y) = {x^Ty \over ||x|| ||y||}\\ = {\sum_i x_i y_i \over \sqrt{\sum_i x_i^2} \sqrt{\sum_i ...
  • 13.1k
4 votes

Definition of normalized Euclidean distance

The weighted Minkowski distance of order $q$ between two real vectors $u, v \in \mathbb{R}^n$ is given by $$d^{(q)} (u, v) = \left(\sum_{i=1}^n w_i (u_i - v_i)^q \right)^\frac{1}{q}$$ [See equation $...
  • 679
4 votes
Accepted

Need more intuition for the curse of dimensionality

I am used to an essentially same but a bit more illustrative example, in my opinion. Let $x_1,...x_l$ be i.i.d. and uniformly distributed in the unit $n$-ball centered at the origin. Then it can be ...
  • 339
4 votes
Accepted

Constructing N-dimensional vectors out of point distances

You are referring to multidimensional scaling. Specifically metric MDS will do this. You are guaranteed to be able to exactly reproduce the distances in the table if you use $N-1$ dimensions. A ...
4 votes

Is the maximum bound of Euclidean distance between two probability distributions equal to $\sqrt{2}$?

$d_{xy}^2 = \sum{(x-y)^2} = \sum x^2 + \sum y^2 - 2\sum xy$. Given that in probability vectors all values are nonnegative, $d^2$ is max when the last term is zero. Then $d^2 = \sum x^2 + \sum y^2$. ...
  • 53.3k
4 votes

Variance and asymptotic normality of $\frac{1}{n-1}\sum_{i=1}^{n-1}(x_{i+1}-x_i)^2$, where $X \sim \mathcal{N}(0,1)$

Small pedantic note: Below I changed the coefficient into $1/\sqrt{n-1}$ otherwise the limiting distribution will be a degenerate distribution (zero variance). In that case one would also need to ...
4 votes

How to define distance for vector of angles?

You are right that circular data requires special metrics. The distance between 1° and 359° should be small, e.g., not large as $|359-1|$ would suggest. And a circular metric must be "rotation-...
  • 3,296

Only top scored, non community-wiki answers of a minimum length are eligible