3.208
Distance Measures

---

Objectives

After completing this lesson, you will be able to:

• state the role and importance of distance measures in machine learning algorithms such as kNN
• calculate Hamming, Euclidean, and Manhattan distance measures
• list additional distance measures
• appreciate the effect that distance measure may have on model performance

---

Distance Measures

Machine learning algorithms often need to measure the distance or similarity between data points for tasks such as clustering, classification, or nearest neighbors. Here are some common distance measures used in machine learning:

Euclidean Distance: Also known as L2 distance. It is calculated as the square root of the sum of the squared differences between two points. It’s the most common use of distance, often used in k-means, k-NN, and other ML algorithms.

Manhattan Distance: Also known as L1 distance. It is calculated as the sum of the absolute differences between two points. It is used when the difference in each dimension matters equally, and is often used in various NLP or computer vision tasks.

Minkowski Distance: This is a generalization of Euclidean and Manhattan distance and adds a parameter, known as the norm order p. When p is 1, it becomes Manhattan distance and when p is 2, it becomes Euclidean distance.

Hamming Distance: Used for categorical variables. It measures the number of positions at which the corresponding symbols are different. It is used in information theory and error detection/correction.

Cosine Distance: Measures the cosine of the angle between two vectors, rather than the magnitude of the difference of the vectors like Euclidean distance. It’s often used in high-dimensional and sparse spaces, such as text documents (TF-IDF vectors) and collaborative filtering recommendation systems.

Mahalanobis Distance: Measures distance relative to the centroid — a base or mean point, taking into account the covariance of the data. This distance measure is scale-invariant and takes into account the correlations of the dataset.

Jaccard Distance: A measure of how dissimilar two sets are. The lower the distance, the more similar the sets are. It’s often used in text mining for comparing documents or other instances that can be represented as sets.

Levenshtein Distance: Also known as Edit Distance, it measures the minimum number of edits (insertions, deletions or substitutions) needed to change one string (or sequence) into another. It is used in spell correction, DNA sequence alignment, etc.

Hellinger Distance or Bhattacharyya Distance: These are used for comparing probability distributions.

Chebyshev Distance: Also known as maximum value distance. It’s defined as the greatest of differences along any coordinate dimension and is used in chessboard distance calculations.

Different distance measures are used for different types of data, so the choice of distance measure can greatly influence the results of your machine learning algorithm. It’s often a good idea to try different distance measures to see which one works best for your specific problem (Alfeilat et al, 2019).

In machine learning, we assume that each feature is a dimension in an N-dimensional space. The features, naturally, must be numeric. Any categorical features require a numeric encoding (see Lesson 3.207 - Encoding Categorical Features).

Euclidean Distance

Euclidean distance is a commonly used distance measure between two points in a Euclidean space (i.e., a space in which the Pythagorean theorem holds). It is calculated using the Pythagorean theorem.

The formula for Euclidean distance between two points in a two-dimensional space is given by:

Definition

In an n-dimensional space, the Euclidean distance is the square root of the sum of the squared differences of each dimension. The formula can be generalized for a multidimensional space to calculate the Euclidean distance between two points p and q in an n-dimensional real space:

\[ D(p,q)=\sqrt{\sum_{i=1}^{n}((p_i-q_i)^2)} \]

In this general form, \(p = (p_1, p_2, ..., p_n)\) and \(q = (q_1, q_2, ..., q_n)\) are two points in n-dimensional space.

Implementation in R

The code below defines a function that calculates the Euclidean distance between two numeric vectors p and q. Note how we are leveraging the power of vector operations in R. The statement (p - q)^2 actually subtracts each element from one vector by the corresponding element of the other and then squares each difference. Finally, the squared differences are added with the function sum.

dist.euclidean <- function (p, q) {
  r <- sqrt(sum((p - q)^2))
  return (r)
}

Let’s try the function by calling it with various vectors. Calculate the result by hand (or using a spreadsheet program) to convince yourself that the function works correctly.

p <- c(-2,3.1,0.2,4.5)
q <- c(-3,4.5,-0.1,6.1)

d <- dist.euclidean(p,q)

print(d)

## [1] 2.368544

Manhattan Distance

Manhattan distance, also known as the L1 norm, taxicab or city block distance, computes the absolute difference between pairs of coordinates. It gets its name from the grid layout of most streets in Manhattan, where you can only move along the grid lines. The image below illustrates this concepts of measuring distance by counting “blocks”:

Definition

In an n-dimensional space, the Manhattan distance is the sum of the absolute differences along each dimension. The formula can be generalized for a multidimensional space to calculate the Euclidean distance between two points p and q in an n-dimensional real space:

\[ D(p,q)=\sum_{i=1}^{n}(|p_i - q_i|) \]

In this general form, \(p = (p_1, p_2, ..., p_n)\) and \(q = (q_1, q_2, ..., q_n)\) are two points in n-dimensional space.

This calculation basically sums up the absolute differences of their coordinates. Note that in high-dimensional spaces, the Euclidean and Manhattan distances can behave quite differently, and the choice between them depends on the specific application and often requires knowledge of the domain and some experimentation.

Implementation in R

The code below defines a function that calculates the Manhattan distance between two numeric vectors p and q. Note how we are leveraging the power of vector operations in R. The statement abs(p - q) actually subtracts each element from one vector by the corresponding element of the other and then applies the function abs to each element of the resulting vector. Finally, the absolute differences are added with the function sum.

dist.manhattan <- function (p, q) {
  r <- sum(abs(p - q))
  return (r)
}

Let’s try the function by calling it with various vectors. Calculate the result by hand (or using a spreadsheet program) to convince yourself that the function works correctly.

p <- c(-2,3.1,0.2,4.5)
q <- c(-3,4.5,-0.1,6.1)

d <- dist.manhattan(p,q)

print(d)

## [1] 4.3

Hamming Distance

Hamming distance is a measure of difference between two strings of equal length. It’s named after Richard Hamming, who introduced it in the field of information theory.

Definition

Hamming distance is simply the count of the positions at which the corresponding symbols (characters, bits, etc.) are different.

For example, consider the binary vectors \(v_1 = <1,0,0,1,1,0,1,1>\) and \(v_2 = <1,1,0,1,1,0,0,1>\). The Hamming distance between these two vectors is 2 because there are two bits that differ:

Hamming distance is used in computer science in various applications such as error detection and error correction. It’s commonly used in genetics to measure the genetic distance between two DNA strings, in information theory for coding theory, and also in some machine learning algorithms, usually for binary data or categorical data encoded using a binary encoding (such as one-hot encoding).

Note that Hamming distance is defined only for strings of equal length. If one needs to compare strings of different lengths, one would need to use a different measure, such as the Levenshtein distance, which can handle strings of different lengths by including insertions and deletions, in addition to substitutions, in its calculation.

Implementation in R

The code below defines a function that calculates the distance between two Boolean vectors p and q. Note how the code leverages the power of vector operations in R. The statement p != q returns a Boolean vector that contains the value of the logical operation != for each corresponding element in two vectors.

dist.hamming <- function(p, q) {
  diffs <- p != q
  
  return (length(which(diffs == T)))
}

Let’s try the function by calling it with various Boolean “strings”.

p <- c(T,T,F,F)
q <- c(T,T,T,F)
w <- c(F,F,T,T)

print(dist.hamming(p,q))

## [1] 1

print(dist.hamming(p,w))

## [1] 4

print(dist.hamming(p,p))

## [1] 0

The dist Function of R

The dist function of the stats package in R can calculate Euclidean, Hamming, and Manhattan distance, as well as Minkowski.

Cosine Distance

Cosine distance, or more often Cosine similarity, is a measure of similarity between two non-zero vectors. Instead of measuring the distance between the two points in Euclidean space like Euclidean distance, it measures the cosine of the angle between the two vectors. The cosine similarity is particularly used when the magnitude of the vectors does not matter.

Definition

The cosine similarity between two vectors A and B is calculated as the dot product of A and B divided by the product of the magnitudes of A and B:

\[ cos(\theta)= \frac{A \cdot B}{\| A\| \times \| B\|} \]

The dot product \(A \cdot B\) is the sum of the product of the corresponding elements of A and B. The magnitude of a vector A, \(\| A\|\), is the square root of the sum of the squares of the elements.

If the vectors are normalized (each vector has a length/magnitude of 1), the cosine similarity simply becomes the dot product of the vectors.

The cosine distance is then defined as 1 minus the cosine similarity and it ranges from 0 (meaning the vectors are identical) to 2 (meaning the vectors are diametrically opposed).

Cosine similarity is especially advantageous in text analysis and other high-dimensional and sparse data. When comparing text documents represented as bag-of-words or TF-IDF vectors, we often don’t care about the length of the documents, just their content. Here, two documents are considered similar if they contain similar words, even if one document is much longer than the other. The cosine similarity handles this situation well, which is why it’s commonly used in Natural Language Processing (NLP) and Information Retrieval.

In summary, cosine similarity/distance is most appropriate when the magnitude of the vectors does not matter, and we’re more interested in the orientation (the direction in which they’re heading) of the vectors.

Tutorial

The chalk-talk by Dr. Schedlbauer will go into more detail on Euclidean, Manhattan, and Hamming Distance measures.

Nota Bene: In the video, the Hamming Distance between the vectors <0,0,1> and <1,0,1> is incorrectly calculated as 2 rather than the correct 1 as the vectors differ in one position, so the sum of the differences is 1.

Conclusion

Distance measures in machine learning help to quantify the similarity or dissimilarity between data points, playing a crucial role in algorithms such as clustering, classification, and nearest neighbors. Common distance measures include Euclidean, Manhattan, Minkowski, Hamming, Cosine, Mahalanobis, Jaccard, Levenshtein, Hellinger, and Chebyshev. The choice of distance measure can significantly influence the outcome of a machine learning model and typically depends on the specific nature and structure of the data.

---

Files & Resources

All Files for Lesson 3.208

---

References

Abu Alfeilat, H. A., Hassanat, A. B., Lasassmeh, O., Tarawneh, A. S., Alhasanat, M. B., Eyal Salman, H. S., & Prasath, V. S. (2019). Effects of distance measure choice on k-nearest neighbor classifier performance: a review. Big data, 7(4), 221-248.

Errata

Let us know.