sgkit.pairwise_distance

sgkit.pairwise_distance(x, metric='euclidean', split_every=None, device='cpu')

Calculates the pairwise distance between all pairs of row vectors in the given two dimensional array x.

To illustrate the algorithm consider the following (4, 5) two dimensional array:

[e.00, e.01, e.02, e.03, e.04]
[e.10, e.11, e.12, e.13, e.14]
[e.20, e.21, e.22, e.23, e.24]
[e.30, e.31, e.32, e.33, e.34]

The rows of the above matrix are the set of vectors. Now let’s label all the vectors as v0, v1, v2, v3.

The result will be a two dimensional symmetric matrix which will contain the distance between all pairs. Since there are 4 vectors, calculating the distance between each vector and every other vector, will result in 16 distances and the resultant array will be of size (4, 4) as follows:

[v0.v0, v0.v1, v0.v2, v0.v3]
[v1.v0, v1.v1, v1.v2, v1.v3]
[v2.v0, v2.v1, v2.v2, v2.v3]
[v3.v0, v3.v1, v3.v2, v3.v3]

The (i, j) position in the resulting array (matrix) denotes the distance between vi and vj vectors.

Negative, nan and infinite values are considered as missing values. They are ignored for all distance metric calculations.

The distances are computed with matrix multiplications in float64, and returned in the floating point type of x, or in float64 if x has another type. They are computed from sums of squares and products, which are exact for small integers such as allele counts. For other values, a distance much smaller than the values it is computed from, such as between two nearly identical rows, can be inaccurate. Arrays with CuPy chunks are computed on the GPU, where float64 is much slower than float32 on many GPUs.

Parameters:

x ndarray | Array

[array-like, shape: (M, N)] An array like two dimensional matrix. The rows are the vectors used for comparison, i.e. for pairwise distance.

metric Literal['euclidean', 'correlation'] (default: 'euclidean')

The distance metric to use. The distance function can be ‘euclidean’ or ‘correlation’.

split_every int | None (default: None)

Determines the depth of the recursive aggregation in the reduction step over the chunks of the second dimension of x.

Omit to let dask heuristically decide a good default. A default can also be set globally with the split_every key in dask.config.

device Literal['cpu', 'gpu'] (default: 'cpu')

The architecture to run the calculation on, either of “cpu” or “gpu”. With “gpu”, the chunks of x are moved to the GPU with CuPy, and the result is moved back to NumPy, so this requires CuPy.

Return type:

Array

Returns:

[array-like, shape: (M, M)] A two dimensional distance matrix, which will be symmetric. The dimension will be (M, M). The (i, j) position in the resulting array (matrix) denotes the distance between ith and jth row vectors in the input array.

Examples

>>> from sgkit.distance.api import pairwise_distance
>>> import dask.array as da
>>> x = da.array([[6, 4, 1,], [4, 5, 2], [9, 7, 3]]).rechunk(2, 2)
>>> pairwise_distance(x, metric='euclidean').compute()
array([[0.        , 2.44948974, 4.69041576],
       [2.44948974, 0.        , 5.47722558],
       [4.69041576, 5.47722558, 0.        ]])

>>> import numpy as np
>>> x = np.array([[6, 4, 1,], [4, 5, 2], [9, 7, 3]])
>>> pairwise_distance(x, metric='euclidean').compute()
array([[0.        , 2.44948974, 4.69041576],
       [2.44948974, 0.        , 5.47722558],
       [4.69041576, 5.47722558, 0.        ]])

>>> x = np.array([[6, 4, 1,], [4, 5, 2], [9, 7, 3]])
>>> pairwise_distance(x, metric='correlation').compute()
array([[0.        , 0.26295653, 0.00282354],
       [0.26295653, 0.        , 0.21428571],
       [0.00282354, 0.21428571, 0.        ]])