Distance Metrics#

This chapter contains functions for the computation of distance metrics.

Pairwise distances#

A pairwise distance is a measure of similarity between samples. Consider an \(m \times k\) matrix \(X\), and an \(n \times k\) matrix \(Y\). The distance between the row vectors of \(X\) and the row vectors of \(Y\) is represented by a matrix \(D\) of size \(m \times n\). In addition, the distance matrix \(D\) between each row vector of \(X\) can be computed and is of size \(m \times m\). There are different metrics used to compute the distance between two samples. The available metrics are listed below.

Euclidean distance

Each element \(D_{ij}\) of the Euclidean distance matrix \(D\), between two matrices \(X\) and \(Y\), is defined as

\[D_{ij} = \sqrt{(X_i-Y_j)^\mathrm{T}(X_i-Y_j)},\]

where \(X_i\) and \(Y_j\) denote the \(i\)-th and \(j\)-th rows of \(X\) and \(Y\), respectively.

In AOCL-DA, we compute the Euclidean distances using the equivalent formula

\[D_{ij} = \sqrt{X_i^\mathrm{T}X_i + Y_j^\mathrm{T}Y_j - 2X_i^\mathrm{T}Y_j}.\]

The term \(X_i^\mathrm{T}Y_j\) can be computed for all \(i,j\) using highly optimized gemm operations, which yields better performance.

Squared Euclidean distance

Similarly to Euclidean distance above, each element \(D_{ij}\) of the distance matrix \(D\), between two matrices \(X\) and \(Y\), is defined as

\[D_{ij} = (X_i-Y_j)^\mathrm{T}(X_i-Y_j).\]

Examples#

The code below is supplied with your installation (see Python examples).

 1# Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
 2#
 3# Redistribution and use in source and binary forms, with or without modification,
 4# are permitted provided that the following conditions are met:
 5# 1. Redistributions of source code must retain the above copyright notice,
 6#    this list of conditions and the following disclaimer.
 7# 2. Redistributions in binary form must reproduce the above copyright notice,
 8#    this list of conditions and the following disclaimer in the documentation
 9#    and/or other materials provided with the distribution.
10# 3. Neither the name of the copyright holder nor the names of its contributors
11#    may be used to endorse or promote products derived from this software without
12#    specific prior written permission.
13#
14# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17# IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
20# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
23# POSSIBILITY OF SUCH DAMAGE.
24#
25"""
26Metrics example python script
27"""
28
29import sys
30import numpy as np
31from aoclda.metrics import pairwise_distances
32
33
34def metrics_example():
35    """
36    Metrics examples
37    """
38    X = np.array([[2, 3], [3, 5], [5, 8]],
39                 dtype=np.float32,
40                 order='F')
41    print("Sample X:")
42    print(X)
43
44    Y = np.array([[1, 0], [2, 1]],
45                 dtype=np.float32,
46                 order='F')
47
48    print("\nSample Y:")
49    print(Y)
50
51    euclidean_distance_xy = pairwise_distances(X, Y)
52    print(f"\nEuclidean pairwise distances of X and Y:\n {euclidean_distance_xy}")
53
54    euclidean_distance_xx = pairwise_distances(X)
55    print(f"\nEuclidean pairwise distances of rows of X:\n {euclidean_distance_xx}")
56
57    squared_euclidean_distance_xy = pairwise_distances(X, Y, metric='sqeuclidean')
58    print(f"\nSquared euclidean pairwise distances of X and Y:\n {squared_euclidean_distance_xy}")
59
60    squared_euclidean_distance_xx = pairwise_distances(X, metric='sqeuclidean')
61    print(f"\nSquared euclidean pairwise distances of rows of X:\n {squared_euclidean_distance_xx}")
62
63    print("\nMetrics calculations successful")
64    print("---------------------------")
65
66
67if __name__ == "__main__":
68    try:
69        metrics_example()
70    except RuntimeError:
71        sys.exit(1)

The code below can be found in metrics.cpp in the examples folder of your installation.

 1/*
 2 * Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
 3 *
 4 * Redistribution and use in source and binary forms, with or without modification,
 5 * are permitted provided that the following conditions are met:
 6 * 1. Redistributions of source code must retain the above copyright notice,
 7 *    this list of conditions and the following disclaimer.
 8 * 2. Redistributions in binary form must reproduce the above copyright notice,
 9 *    this list of conditions and the following disclaimer in the documentation
10 *    and/or other materials provided with the distribution.
11 * 3. Neither the name of the copyright holder nor the names of its contributors
12 *    may be used to endorse or promote products derived from this software without
13 *    specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
19 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
21 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 *
26 */
27
28#include "aoclda.h"
29#include <cmath>
30#include <iostream>
31
32/* Metrics example
33 *
34 * This example computes the euclidean distance matrix 
35 * between two feature arrays
36 */
37
38int main() {
39    std::cout << "-----------------------------------------------------------------------"
40              << std::endl;
41    std::cout << "Metrics" << std::endl;
42    std::cout << "Euclidean distance matrix for a 3x2 and a 2x2 data matrix" << std::endl
43              << std::endl;
44    std::cout << std::fixed;
45    std::cout.precision(5);
46
47    int exit_code = 0;
48    bool pass = true;
49
50    // Feature data matrices
51    double X[6] = {1.0, 3.0, 5.0, 2.0, 4.0, 6.0};
52    double Y[4] = {7.0, 9.0, 8.0, 10.0};
53
54    da_int m = 3, n = 2, k = 2;
55
56    // Array used to store the distance matrix
57    double D[6];
58
59    // Compute the euclidean distance matrix
60    pass = pass && (da_pairwise_distances_d(m, n, k, X, m, Y, n, D, m, da_euclidean,
61                                            da_allow_infinite) == da_status_success);
62
63    // Check status and print
64    if (pass) {
65        std::cout << "Euclidean distance matrix computed successfully" << std::endl
66                  << std::endl;
67
68        // Print computed matrix
69        std::cout << "Distance matrix D:\n";
70        for (da_int i = 0; i < m; i++) {
71            for (da_int j = 0; j < n; j++)
72                std::cout << "  " << D[i + j * m];
73            std::cout << std::endl;
74        }
75        std::cout << std::endl;
76
77        // Check against expected results
78        double sqrt2 = std::sqrt(2.0);
79        double D_exp[6] = {6 * sqrt2, 4 * sqrt2, 2 * sqrt2,
80                           8 * sqrt2, 6 * sqrt2, 4 * sqrt2};
81
82        double tol = 1.0e-14;
83        double err = 0.0;
84        for (da_int i = 0; i < m * n; i++)
85            err = std::max(err, std::abs(D[i] - D_exp[i]));
86
87        if (err > tol) {
88            std::cout << "Solution is not within expected tolerance. Maximum error is: "
89                      << err << std::endl;
90            exit_code = 1;
91        }
92    } else
93        exit_code = 1;
94
95    std::cout << "-----------------------------------------------------------------------"
96              << std::endl;
97
98    return exit_code;
99}