# ML Wiki

## Euclidean Distance

Euclidean distance is a geometric Distance between two datapoints

• distance between $\mathbf x_1$ and $\mathbf x_2$ is
• length of the line that connects these two points:
• $\| \mathbf x_1 - \mathbf x_2 \| = \sqrt{ (\mathbf x_1 - \mathbf x_2)^T (\mathbf x_1 - \mathbf x_2) } = \sqrt{\sum_i (x_{1i} - x_{2i})^2}$

It's the most common distance metric, also called $L_2$ norm

### Properties

The Euclidean distance is translation invariant

• let $\mathbf a$ be some vector
• then consider the distance in the translated space :
• $\| (\mathbf x_1 - \mathbf a) - (\mathbf x_2 - \mathbf a) \| = \| \mathbf x_1 - \mathbf a - \mathbf x_2 + \mathbf a \| = \| \mathbf x_1 - \mathbf x_2 \|$
• so the distance in the translated space is the same as in the original space

## High Dimensionality

Euclidean distance is not always meaningful for high dimensional data

Consider this example:

$A_1$ $A_2$ $A_3$ $A_4$ $A_5$ $A_6$ $A_7$ $A_8$ $A_9$ $A_{10}$
$\mathbf p_1$ 3 0 0 0 0 0 0 0 0 0
$\mathbf p_2$ 0 0 0 0 0 0 0 0 0 4
$\mathbf p_3$ 3 2 4 0 1 2 3 1 2 0
$\mathbf p_4$ 0 2 4 0 1 2 3 1 2 4

• distance between $\mathbf p_1$ and $\mathbf p_2$ is $\| \mathbf p_1 - \mathbf p_2\| = 5$
• distance between $\mathbf p_3$ and $\mathbf p_4$ is $\| \mathbf p_3 - \mathbf p_4\| = 5$
• so Euclidean distance between these two vectors is the same!
• but suppose these vectors correspond to documents and words (Vector Space Models)
• $\mathbf p_3$ and $\mathbf p_4$ must be more similar to each other than $\mathbf p_1$ and $\mathbf p_2$: $\mathbf p_3$ and $\mathbf p_4$ have 7 words in common whereas $\mathbf p_1$ and $\mathbf p_2$ have none

When the data is sparse it's better to use different measure of distance/similarity

## Sources

• http://en.wikipedia.org/wiki/Euclidean_distance
• Ertöz, Levent, Michael Steinbach, and Vipin Kumar. "Finding clusters of different sizes, shapes, and densities in noisy, high dimensional data." 2003. [1]
• Korenius, Tuomo, Jorma Laurikkala, and Martti Juhola. "On principal component analysis, cosine and Euclidean measures in information retrieval." 2007. [2]