1
$\begingroup$

Why I want to normalize Euclidean distance

Currently, I am designing a ranking system, it weights between Euclidean distance and several other distances.

Euclidean distance behaves unbounded, that is, it outputs any $value > 0$ , while other metrics are within range of $[0, 1]$. Have to come up with a function to squash Euclidean to a value between 0 and 1.

What does my data look like

Euclidean distance is computed by sklearn, specifically, pairwise_distances.

This function takes two inputs: v1 and v2, where $v_1, v_2 \in \mathbb{R}^{1200}$ and $||v_1|| = 1 , ||v_2||=1$ (L2-norm).

My simple method:

Derive the bounds of Eucldiean distance:

$\begin{align*} (v_1 - v_2)^2 &= v_1^T v_1 - 2v_1^T v_2 + v_2^Tv_2\\ &=2-2v_1^T v_2 \\ &=2-2\cos \theta \end{align*}$

thus, the Euclidean is a $value \in [0, 2]$.

to normalize, just simply apply $new_{eucl} = euclidean/2$. Would it be a valid transformation?

Suggestions from other people

As some of people suggest me to try Gaussian, I am not sure what they mean, more precisely I am not sure how to compute variance (data is too big takes over 80G storing space, compute actual variance is too costly). More importantly, I am very confused why need Gaussian here?

Edited

As an extension, suppose the vectors are not normalized to have norm eqauls to 1. What do we do to normalize the Euclidean distance?

$\endgroup$
  • 2
    $\begingroup$ Euclidean distance on L2-normalized vectors is called chord distance. It is a chord in the unit-radius circumference. Its maximum is 2, the diameter. Dividing euclidean distance by a positive constant is valid, it doesn't change its properties. $\endgroup$ – ttnphns Apr 23 '18 at 6:54
  • $\begingroup$ The question is whether you really want Euclidean distance, why not Manhattan? Have a look on Gower similarity (search the site). $\endgroup$ – ttnphns Apr 23 '18 at 6:56
1
$\begingroup$

If you only allow non-negative vectors, the maximum distance is sqrt(2). For example, (1,0) and (0,1). You can only achieve larger values if you use negative values, and 2 is achievable only by v and -v.

You should also consider to use thresholds. The difference between 1.1 and 1.0 probably does not matter.

Then you can simply use min(euclidean, 1.0) to bound it by 1.0.

| cite | improve this answer | |
$\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.