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.