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]