Metrics

library(rnndescent)

A lot of distance functions are implemented in rnndescent, which you can specify in every function which needs them with the metric parameter. Technically not all of these are metrics, but let’s just let that slide. Typical are "euclidean" or "cosine" the latter being more common for document-based data. For binary data, "hamming" or "jaccard" might be a good place to start.

The metrics here are a subset of those offered by the PyNNDescent Python package which in turn reproduces those in the scipy.spatial.distance module of SciPy. Many of the binary distances seem to have definitions shared with (Choi et al. 2010) so you may want to look in that reference for an exact definition.

  • "braycurtis": Bray-Curtis.
  • "canberra": Canberra.
  • "chebyshev": Chebyshev, also known as the L-infinity norm (\(L_\infty\)).
  • "correlation": 1 minus the Pearson correlation. The distance between two all-zero vectors is 0 for dense and sparse input. This is a package convention: Pearson correlation is undefined for zero-variance vectors.
  • "cosine": 1 minus the cosine similarity.
  • "dice": the Dice coefficient, also known as the Sørensen–Dice coefficient. Intended for binary data.
  • "euclidean": the Euclidean distance, also known as the L2 norm.
  • "hamming": the Hamming distance. Intended for binary data.
  • "haversine": the Haversine (great-circle) distance for 2D latitude and longitude coordinates in radians. This is for compatibility with the PyNNDescent implementation, but be aware that functions like distHaversine in the geosphere package expect latitude and longitude in degrees. An error will be raised if values that appear to be supplied in degrees are encountered.
  • "hellinger": the Hellinger distance. This is intended to be used with a probability distribution, so ensure that each row of your input data contains non-negative values which sum to 1.
  • "jaccard": the Jaccard index, also known as the Tanimoto coefficient. Intended for binary data.
  • "jensenshannon": the Jensen-Shannon divergence. Like "hellinger", this is intended to be used with a probability distribution.
  • "kulsinski": the Kulsinski dissimilarity as defined in the Python package scipy.spatial.distance.kulsinski (this function is deprecated in scipy). Intended for binary data.
  • "sqeuclidean" (squared Euclidean)
  • "manhattan": the Manhattan distance, also known as the L1 norm or Taxicab distance.
  • "rogerstanimoto": the Rogers-Tanimoto coefficient.
  • "russellrao": the Russell-Rao coefficient.
  • "sokalmichener". Intended for binary data.
  • "sokalsneath": the Sokal-Sneath coefficient. Intended for binary data.
  • "spearmanr": 1 minus the Spearman rank correlation
  • "symmetrickl" symmetrized version of the Kullback-Leibler divergence. The symmetrization is calculated as \(D_{KL}(P||Q) + D_{KL}(Q||P)\).
  • "trueangular": the angle between vectors divided by \(\pi\), from 0 for the same direction to 1 for opposite directions. By package convention, the distance is 0 between two zero vectors and 1/2 when exactly one vector is zero.
  • "tsss" the Triangle Area Similarity-Sector Area Similarity or TS-SS metric as described in (Heidarian and Dinneen 2016). Compared to results in PyNNDescent (as of version 0.5.11), distances are smaller by a factor of 2 in this package. This does not affect the returned nearest neighbors, only the distances. Multiply them by 2 if you need to get closer to the PyNNDescent results.
  • "yule" the Yule dissimilarity. Intended for binary data.

For non-sparse data, the following variants are available with preprocessing: this trades memory for a potential speed up during the distance calculation. Some minor numerical differences should be expected compared to the non-preprocessed versions:

  • "cosine-preprocess": cosine with preprocessing.
  • "correlation-preprocess": correlation with preprocessing.

Numerical precision

Numeric coordinates are converted to single precision (float) in the native code, which also stores distances in single precision. The returned dist matrices use R’s double precision, but that does not recover information lost during conversion or calculation. Brute force compares every pair of points; “exact” describes the search, not double-precision numerical accuracy.

For example, these two values differ by 1 in R, but become the same number in single precision:

query <- matrix(1e8)
reference <- matrix(1e8 + 1)
c(
  R = abs(reference - query),
  rnndescent = brute_force_knn_query(query, reference, k = 1)$dist
)
#>          R rnndescent 
#>          1          0

For Euclidean data with a large common offset, subtracting that offset from both query and reference in R can help retain small differences. A common translation preserves Euclidean distances but generally changes cosine and probability distances, so the choice of preprocessing depends on the metric.

Very large finite inputs can also overflow intermediate calculations and leave missing neighbors (idx = 0, dist = NA), including with brute force. This remains an unresolved numerical limitation.

Specialized Binary Metrics

Logical feature matrices must contain only TRUE and FALSE. Missing logical values (NA) raise an error when the features are used, with both ordinary and specialized binary metrics. If treating missing values as FALSE is appropriate for your data, replace them explicitly before calling, for example with x[is.na(x)] <- FALSE.

Some metrics are intended for use with binary data. This means that:

  • Your numeric data should consist of only two distinct values, typically 0 and 1. You will get unpredictable results otherwise.
  • If you provide the data as a logical matrix, a much faster implementation is used.

The metrics you can use with binary data are:

  • "dice"
  • "hamming"
  • "jaccard"
  • "kulsinski"
  • "matching"
  • "rogerstanimoto"
  • "russellrao"
  • "sokalmichener"
  • "sokalsneath"
  • "yule"

Here’s an example of using binary data stored as 0s and 1s with the "hamming" metric:

set.seed(42)
binary_data <- matrix(sample(c(0, 1), 100, replace = TRUE), ncol = 10)
head(binary_data)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#> [1,]    0    0    0    1    0    1    0    1    1     0
#> [2,]    0    1    0    1    0    0    1    0    0     1
#> [3,]    0    0    0    1    1    1    1    1    1     0
#> [4,]    0    1    0    1    1    1    1    1    0     1
#> [5,]    1    0    0    0    1    1    1    1    0     1
#> [6,]    1    0    1    1    1    1    1    1    1     1
nn <- brute_force_knn(binary_data, k = 4, metric = "hamming")

Now let’s convert it to a logical matrix:

logical_data <- binary_data == 1
head(logical_data)
#>       [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]  [,9] [,10]
#> [1,] FALSE FALSE FALSE  TRUE FALSE  TRUE FALSE  TRUE  TRUE FALSE
#> [2,] FALSE  TRUE FALSE  TRUE FALSE FALSE  TRUE FALSE FALSE  TRUE
#> [3,] FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE
#> [4,] FALSE  TRUE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE
#> [5,]  TRUE FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE FALSE  TRUE
#> [6,]  TRUE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
logical_nn <- brute_force_knn(logical_data, k = 4, metric = "hamming")

The results will be the same:

all.equal(nn, logical_nn)
#> [1] TRUE

but on a real-world dataset, the logical version will be much faster.

References

Choi, Seung-Seok, Sung-Hyuk Cha, Charles C Tappert, et al. 2010. “A Survey of Binary Similarity and Distance Measures.” Journal of Systemics, Cybernetics and Informatics 8 (1): 43–48.
Heidarian, Arash, and Michael J. Dinneen. 2016. “A Hybrid Geometric Approach for Measuring Similarity Level Among Documents and Document Clustering.” 2016 IEEE Second International Conference on Big Data Computing Service and Applications (BigDataService), 142–51. https://doi.org/10.1109/BigDataService.2016.14.