API¶

Distance computation¶

Distance between 2 vectors¶

Warning

doxygenfunction: Unable to resolve multiple matches for function “dist” with arguments (const af::array&, const af::array&, const std::string&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array dist(const af::array &x, const af::array &y, const distance::metric::metric_function &metric)
- af::array dist(const af::array &x, const af::array &y, const std::string &metric)

Warning

doxygenfunction: Unable to resolve multiple matches for function “dist” with arguments (const af::array&, const af::array&, const distance::metric::metric_function&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array dist(const af::array &x, const af::array &y, const distance::metric::metric_function &metric)
- af::array dist(const af::array &x, const af::array &y, const std::string &metric)

Pairwise distances in a matrix¶

Warning

doxygenfunction: Unable to resolve multiple matches for function “pdist” with arguments (const af::array&, const std::string&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array pdist(const af::array &x, const distance::metric::metric_function &metric)
- af::array pdist(const af::array &x, const std::string &metric)

Warning

doxygenfunction: Unable to resolve multiple matches for function “pdist” with arguments (const af::array&, const distance::metric::metric_function&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array pdist(const af::array &x, const distance::metric::metric_function &metric)
- af::array pdist(const af::array &x, const std::string &metric)

af::array distance::squaredform(const af::array &x)¶

Converts a condensed distance vector to a square-form distance matrix.

Return

The square-form matrix \(D\) converted from x, where \(D(i, j) = d(x_i, x_j)\).

Parameters

x: A condensed distance vector as given by distance::pdist

Exceptions

std::invalid_argument: if the length of x is not a binomial coefficient \({n \choose 2}\) for some integer \(n \geq 2\).

Pairwise distances between two matrices¶

Warning

doxygenfunction: Unable to resolve multiple matches for function “cdist” with arguments (const af::array&, const af::array&, const std::string&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array cdist(const af::array &x, const af::array &y, const distance::metric::metric_function &metric)
- af::array cdist(const af::array &x, const af::array &y, const std::string &metric)

Warning

doxygenfunction: Unable to resolve multiple matches for function “cdist” with arguments (const af::array&, const af::array&, const distance::metric::metric_function&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array cdist(const af::array &x, const af::array &y, const distance::metric::metric_function &metric)
- af::array cdist(const af::array &x, const af::array &y, const std::string &metric)

Warning

doxygenfunction: Unable to resolve multiple matches for function “cdist2” with arguments (const af::array&, const af::array&, const std::string&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array cdist2(const af::array &x, const af::array &y, const distance::metric::metric_function &metric)
- af::array cdist2(const af::array &x, const af::array &y, const std::string &metric)

Warning

doxygenfunction: Unable to resolve multiple matches for function “cdist2” with arguments (const af::array&, const af::array&, const distance::metric::metric_function&) in doxygen xml output for project “libdistance” from directory: /home/gitlab-runner/builds/bcUGC6-4/0/abx/libdistance/build/doc/xml/. Potential matches:

- af::array cdist2(const af::array &x, const af::array &y, const distance::metric::metric_function &metric)
- af::array cdist2(const af::array &x, const af::array &y, const std::string &metric)

Dynamic Time Wrapping¶

namespace distance::dtw¶

Functions to compute Dynamic Time Wrapping.

Unnamed Group

void cost(af::array &distance)¶

Computes the DTW cost from a distance matrix.

This function computes the DTW cost in place, directly on the input distance array. This avoids extra memory alllocation.

It computes the whole cost matrix. The final DTW distance is given as the last coefficient:

af::array d = ... // some distance matrix
distance::dtw::cost(d);
float cost = d(af::end, af::end).scalar<float>();

Parameters

distance: The distance matrix (obtained with distance::cdist) on which to compute the DTW costs.

af::array cost(const af::array &distance)¶

Computes the DTW cost from a distance matrix.

This function computes and returns the DTW cost matrix. The final DTW distance is given as the last coefficient:

const af::array d = ... // some distance matrix
af::array cost_matrix = distance::dtw::cost(d);
float cost = cost_matrix(af::end, af::end).scalar<float>();

Return

The whole DTW cost matrix, where the DTW distance is the last coefficient. The returned array has the dimension and type as the input one.

Parameters

distance: The distance matrix (obtained with distance::cdist) on which to compute the DTW costs.

Functions

af::array path(const af::array &cost)¶

Computes the DTW path from a cost matrix.

Return

An array of dimension [2, path_length] of indices of the path in the cost matrix.

Parameters

cost: The DTW cost matrix as obtained by distance::dtw::cost.

Metrics¶

namespace distance::metric¶

Mathematical distance formulas (aka metrics).

A metric function evaluates the distance between two vectors \(x\in\mathbb{R}^n\) and \(y\in\mathbb{R}^n\). Some implemented metrics are defined on a subset of \(\mathbb{R}^n\), please see individual methods for documentation.

The following metrics are implemented:

bray_curtis
canberra
chebyshev
cityblock
correlation
cosine
euclidean
hellinger
jensen_shannon
kullback_leibler
sqeuclidean

Utility functions and types

using metric_function = std::function<af::array(const af::array&, const af::array&)>¶

Signature of a metric function to be used for distance computation.

A metric function takes as input arguments two const references to arrays and returns an array.

distance::metric::metric_function get(const std::string &metric)¶

Returns a metric function from its name.

Return

A metric function

See

distance::metric::metric_function

Parameters

metric: The name of the metric to be returned

Exceptions

std::invalid_argument: If the metric name is unknown.

std::vector<std::string> available_metrics()¶: Returns the names of all the implemented metrics.

Metric functions

af::array bray_curtis(const af::array &x, const af::array &y)¶

Bray-Curtis distance between two vectors.

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

af::array canberra(const af::array &x, const af::array &y)¶

Canberra distance between two vectors.

When \(x_i = y_i = 0\) for a given \(i\), then the fraction \(0/0=0\) is used in the calculation.

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

af::array chebyshev(const af::array &x, const af::array &y)¶

Chebyshev distance between two vectors.

\[ d(x, y) = \textrm{max}_i|x_i - y_i| \]

af::array cityblock(const af::array &x, const af::array &y)¶

Cityblock (Manhattan) distance between two vectors.

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

af::array correlation(const af::array &x, const af::array &y)¶

Correlation distance between two vectors.

\[ d(x, y) = 1 - \frac{(x - \bar{x}) \cdot (y - \bar{y})}{||x - \bar{x}||_2||y - \bar{y}||_2} = 1 - \frac{\sum_{i=1}^n (x_i - \bar{x}) (y_i - \bar{y})} {\sqrt{\sum_{i=1}^n (x_i - \bar{x})^2} \sqrt{\sum_{i=1}^n (y_i - \bar{y})^2}} \]

where \(\bar{x}\) is the mean of the vector \(x\).

af::array cosine(const af::array &x, const af::array &y)¶

Cosine distance between two vector.

\[ d(x, y) = 1 - \frac{x \cdot y}{||x||_2||y||_2} = 1 - \frac{\sum_{i=1}^n x_i y_i}{\sqrt{\sum_{i=1}^n x_i^2} \sqrt{\sum_{i=1}^n y_i^2}} \]

af::array euclidean(const af::array &x, const af::array &y)¶

Euclidean distance between two vectors.

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

af::array hellinger(const af::array &x, const af::array &y)¶

Hellinger distance between two vectors.

This metric assumes probability distributions, i.e. \(0 \leq x_i \leq 1\) and \(0 \leq y_i \leq 1\) for all \( i \). This is not checked by the function and let to the user responsability.

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

See: distance::check to ensure the input vectors are in the metric definition set.

af::array jensen_shannon(const af::array &x, const af::array &y)¶

Jensen-Shannon divergence between two vectors.

This metric is defined only on \( ]0, \infty [ \). This is not checked by the function and let to the user responsability.

\[ d(x, y) = \sqrt{\frac{D(x||m) + D(y||m)}{2}} = \sqrt{\frac{1}{2}\sum_{i=1}^n(r(x_i, m_i) + r(y_i, m_i))} \]

with \(m\) being the mean of \(x\) and \(y\), i.e. \(m_i=\frac{x_i+y_i}{2}\) and

\[\begin{split} r(x, y) = \left\{ \begin{array}{ll} x\log(x/y) & x\gt 0, y\gt 0 \\ 0 & x = 0, y \geq 0 \\ \infty & \mathrm{otherwise} \end{array}\right. \end{split}\]

See: distance::check to ensure the input vectors are in the metric definition set.

af::array kullback_leibler(const af::array &x, const af::array &y)¶

Symmetrized Kullback-Leibler divergence between two vectors.

This metric is defined only on \( ]0, \infty [ \). This is not checked by the function and let to the user responsability.

\[ d(x, y) = \frac{D(x||y) + D(y||x)}{2} = \frac{1}{2}\sum_{i=1}^n (r(x_i, y_i) + r(y_i, x_i)) \]

with

\[\begin{split} r(x, y) = \left\{ \begin{array}{ll} x\log(x/y) & x\gt 0, y\gt 0 \\ 0 & x = 0, y \geq 0 \\ \infty & \mathrm{otherwise} \end{array}\right. \end{split}\]

See: distance::check to ensure the input vectors are in the metric definition set.

af::array sqeuclidean(const af::array &x, const af::array &y)¶

Squared Euclidean distance between two vectors.

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

Utility functions¶

The following functions are used to select the arrayfire backend to use at runtime (CPU, CUDA or OpenCL), and to check input arrays are well formatted before computing their distances.

void distance::setup_backend(const std::string &backend, bool verbose = false)¶

Setups the arrayfire backend to use.

Setups arrayfire to use its CPU, CUDA or OpenCL backend. This function must be called at the very top of the code, before any array has been allocated (see http://arrayfire.org/docs/unifiedbackend.htm).

Parameters

backend: Must be “cpu”, “cuda” or “opencl”.
verbose: If true print the content of af::info() to display information on the backend on stdout.

Exceptions

std::invalid_argument: if the requested backend has not been successfully initialized or is not available.

void distance::check(const af::array &x, const std::string &metric)¶

Ensures the array is valid before computing distance.

This function makes sure the input array is well formated to compute a distance matrix with the specified metric. It should be used before a call to distance::pdist.

The following is checked:

No NaN values
Some metrics (metric::hellinger, metric::jensen_shannon, metric::kullback_leibler) have additional requirements on input.

Parameters

x: The input array to check
metric: The metric on which the distance will be computed on.

Exceptions

std::invalid_argument: If any invalid value is encountered in the input

void distance::check2(const af::array &x, const af::array &y, const std::string &metric)¶

Ensures the two arrays are valid before computing distance.

This function makes sure the input arrays are well formated to compute a distance matrix with the specified metric. It should be used before a call to distance::cdist or ditance::dist.

The following is checked:

No NaN values
Values in x and y have the same type
Arrays x and y have the same features dimension
Some metrics (metric::hellinger, metric::jensen_shannon, metric::kullback_leibler) have additional requirements on input.

Parameters

x: The first input array to check
y: The second input array to check
metric: The metric on which the distance will be computed on.

Exceptions

std::invalid_argument: If any invalid value is encountered in the input