Distance Metrics

Core requirements #

\(\) Perfect distant metrics must fulfill core requirements:

1. Distance from itself to itself should be 0 $$ d(X, X) = 0 $$
2. Symmetric distances¹ $$ d(X, Y)=d(Y, X) $$
3. Satisfy triangle inequality $$ d(X, Z) \leq d(X, Y)+ d(Y, Z) $$
4. Positive for all other points $$ d(X, Y) > 0 ~~ \forall X, Y ; \text{ where } X \neq Y $$

Satisfiability #

Only some Minkowski distances satisfy these constraints.

Minkowski distance is: $$ d(X, Y) = \left(\sum_{i=1}^{n}{|x-y|^{p}}\right)^{\frac{1}{p}}$$ where \( X = (x_1, x_2, \ldots , x_{n}) \text{ and } Y = (y_1, y_2, \ldots , y_{n}) \in \R\) .²

The only values of \(p\) that satisfies requirements are:

$$p \geq 1 $$

For example,

• \(p = 1\) is Manhattan distance (L1 norm)
• \(p = 2\) is Euclidean distance (L2 norm)

Any \(p < 1\) does not satisfy the triangle inequality (since distances become convex) and therefore isn’t considered a valid distance metric.