Basics of Minkowski Distance
Tags: machinelearning, datascience, statistics, optimization
Published: 2023-02-08 04:20:40

<figure>
<img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u2oqbdvygayf00yoyjkg.png" alt="Classification problem involving Minkowski distance at p=2 in Iris dataset" style="width:100%">
<figcaption align="center"><p>Classification problem involving Minkowski distance at p=2 in Iris dataset</p></figcaption>
</figure>
<br />


Distance metrics are used by proximity-based models to find certain paths between two points. 

One of the best applications of distance metrics is in the [travelling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) where nearest neighbour, an approximation algorithm, is usually utilized. Aside from combinatorial optimization, distance metrics are also widely used in classification, clustering, and special relativity problems. 

In this article, we will tackle one of the basic distance metrics, named after the German mathematician Hermann Minkowski—the Minkowski distance.

## By definition

Minkowski distance is a distance metric, or a similarity measurement, between two points in a [normed vector space](https://en.wikipedia.org/wiki/Normed_vector_space). It uses a parameter {% katex inline %} p {% endkatex %} which represents the order of the norm.

Let’s say we have {% katex inline %} X_n {% endkatex %} and {% katex inline %} Y_n {% endkatex %} denoted as:

{% katex %} X = (x_1,x_2,...,x_n), {% endkatex %}{% katex %}  Y = (y_1,y_2,...,y_n) {% endkatex %}

The distance of two points can be measured by getting the absolute value of the difference of {% katex inline %} X_i {% endkatex %} and {% katex inline %} Y_i {% endkatex %} ({% katex inline %} |X_i - Y_i| {% endkatex %}). Hence, to get the distances of all {% katex inline %} X,Y {% endkatex %} points ({% katex inline %} D(X,Y) {% endkatex %}), the formula will be in the form of:

{% katex %} D(X,Y) = \displaystyle\sum_{i=1}^n{|x_i - y_i|}^p {% endkatex %}

To satisfy the Minkowski distance, adding {% katex inline %} \frac{1}{p} {% endkatex %} (which, again, represents the order of the norm) completes the equation:

{% katex %} D(X,Y) = \bigg(\displaystyle\sum_{i=1}^n {|x_i - y_i|}^p\bigg)^{\frac{1}{p}} {% endkatex %}

Minkowski distance can also be derived as:
{% katex %} { D(X,Y) = \sqrt[p]{|x_{1}-y_{1}|^p + |x_{2}-y_{2}|^p + ... + |x_{n}-y_{n}|^p} } , {% endkatex %}

{% katex %} D(i,j) = \sqrt[p]{|x_{i1}-x_{j1}|^p + |x_{i2}-x_{j2}|^p + ... + |x_{in}-x_{jn}|^p} {% endkatex %}

## Orders of the norm

<figure>
<img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0us1d5q4gs5y2g65gv1o.png" alt="Unit circles with various values of p" style="width:100%">
<figcaption align="center"><p>Unit circles with various values of p</p></figcaption>
</figure>
<br />

The order of the norm (denoted by the parameter {% katex inline %} p{% endkatex %}) varies the distance norm of the points. 

The case where {% katex inline %} p=1 {% endkatex %} is equivalent to the **Manhattan distance**—named after the rectilinear street layout of Manhattan since it measures the distance between two points in a city if we can only travel along orthogonal city blocks.

Manhattan distance can be calculated using:

{% katex %} { D(X,Y) = \bigg(\displaystyle\sum_{i=1}^n {|x_i - y_i|}\bigg) } , {% endkatex %}

{% katex %} D(i,j) = {|x_{i1}-x_{j1}| + |x_{i2}-x_{j2}| + ... + |x_{in}-x_{jn}|} {% endkatex %}

The case where {% katex inline %} p=2 {% endkatex %} is equivalent to the **Euclidean distance** (or the Pythagorean distance, since it can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem).

Euclidean distance can be calculated using:

{% katex %} { D(X,Y) = \bigg(\displaystyle\sum_{i=1}^n {|x_i - y_i|}^2\bigg)^{\frac{1}{2}} } , {% endkatex %}

{% katex %} D(i,j) = \sqrt{|x_{i1}-x_{j1}|^2 + |x_{i2}-x_{j2}|^2 + ... + |x_{in}-x_{jn}|^2} {% endkatex %}

Therefore, Minkowski distance can also be considered as a generalization of both the Euclidean distance and the Manhattan distance.

The parameter {% katex inline %} p {% endkatex %} can extend to more than the value of {% katex inline %} 2 {% endkatex %} to {% katex inline %} \infty {% endkatex %} that is equal to the [Chebyshev distance](https://en.wikipedia.org/wiki/Chebyshev_distance). Having {% katex inline %} p<1 {% endkatex %} violates the [triangle inequality](https://en.wikipedia.org/wiki/Triangle_inequality)—an advanced topic that is out of the scope of this article.


## Applications of Minkowski distance 

Minkowski distance is widely used in machine learning (classification, clustering, and feature extraction) and special relativity ([Minkowski space](https://en.wikipedia.org/wiki/Minkowski_space)) problems.

One example is in Chess programming. The Minkowski distance at {% katex inline %} p=1 {% endkatex %} can be used in the static evaluation of the late endgame, where for instance races of the two king to certain squares is often an issue—or in so called Mop-up evaluation, which considers the Manhattan-Distance between winning and losing king.<sup>[[1]](https://www.chessprogramming.org/Manhattan-Distance)</sup>

{% katex inline %} p=2 {% endkatex %} has its best usage in calculating the length of a line segment between the two points. It is widely used in geocoding/reverse geocoding applications, such as finding the distance between the geocoded point and the true address location is computed to evaluate the positional accuracy of a geocoding procedure.<sup>[[2]](https://www.sciencedirect.com/science/article/pii/B9780124095489095932)</sup>

<sup>[1]</sup> https://www.chessprogramming.org/Manhattan-Distance
<sup>[2]</sup> https://www.sciencedirect.com/science/article/pii/B9780124095489095932