Algorithms

Jan 15th, 2020

Distance Measures

Distance Measures

Manhattan Distance

Manhattan distance calculates the distance between two real-valued vectors.

\[D_{Manhattan}(x,y) = \sum_{i=1}^{n} |x_i - y_i|\]

Euclidean Distance

Euclidean distance calculates the distance between two real-valued vectors.

\[D_{Euclidean}(x,y) = \sqrt{\sum_{i=1}^{n} |x_i - y_i|^2}\]

Minkowski Distance

Minkowski distance calculates the distance between two real-valued vectors.

It is a generalization of the Euclidean and Manhattan distance measures and adds a parameter, called the “order” or “p“, that allows different distance measures to be calculated.

  • \(p\) is an integer
  • \(x=(x_1,x_2,...,x_n) ]\in \mathbb{R}^n\) is a real-valued vector
  • \(y=(y_1,y_2,...,y_n) ]\in \mathbb{R}^n\) is a real-valued vector
\[D_{Minkowski}(x,y) = \Big( \sum_{i=1}^{n} | x_i - y_i | ^p \Big) ^{1/p}\]
  • \(p=1 \Rightarrow\) Manhattan distance
  • \(p=2 \Rightarrow\) Euclidean distance
  • \(p=\infty \Rightarrow\) Chebyshev distance