Как найти попарные расстояния между ними

Compute Euclidean Distance and Convert Distance Vector to Matrix

Compute the Euclidean distance between pairs of observations, and convert the distance vector to a matrix using squareform.

Create a matrix with three observations and two variables.

rng('default') % For reproducibility
X = rand(3,2);

Compute the Euclidean distance.

D = 1×3

    0.2954    1.0670    0.9448

The pairwise distances are arranged in the order (2,1), (3,1), (3,2). You can easily locate the distance between observations i and j by using squareform.

Z = 3×3

         0    0.2954    1.0670
    0.2954         0    0.9448
    1.0670    0.9448         0

squareform returns a symmetric matrix where Z(i,j) corresponds to the pairwise distance between observations i and j. For example, you can find the distance between observations 2 and 3.

Pass Z to the squareform function to reproduce the output of the pdist function.

y = 1×3

    0.2954    1.0670    0.9448

The outputs y from squareform and D from pdist are the same.

Compute Minkowski Distance

Create a matrix with three observations and two variables.

rng('default') % For reproducibility
X = rand(3,2);

Compute the Minkowski distance with the default exponent 2.

D1 = pdist(X,'minkowski')

D1 = 1×3

    0.2954    1.0670    0.9448

Compute the Minkowski distance with an exponent of 1, which is equal to the city block distance.

D2 = pdist(X,'minkowski',1)

D2 = 1×3

    0.3721    1.5036    1.3136

D3 = pdist(X,'cityblock')

D3 = 1×3

    0.3721    1.5036    1.3136

Compute Pairwise Distance with Missing Elements Using a Custom Distance Function

Define a custom distance function that ignores coordinates with NaN values, and compute pairwise distance by using the custom distance function.

Create a matrix with three observations and two variables.

rng('default') % For reproducibility
X = rand(3,2);

Assume that the first element of the first observation is missing.

Compute the Euclidean distance.

If observation i or j contains NaN values, the function pdist returns NaN for the pairwise distance between i and j. Therefore, D1(1) and D1(2), the pairwise distances (2,1) and (3,1), are NaN values.

Define a custom distance function naneucdist that ignores coordinates with NaN values and returns the Euclidean distance.

function D2 = naneucdist(XI,XJ)  
%NANEUCDIST Euclidean distance ignoring coordinates with NaNs
n = size(XI,2);
sqdx = (XI-XJ).^2;
nstar = sum(~isnan(sqdx),2); % Number of pairs that do not contain NaNs
nstar(nstar == 0) = NaN; % To return NaN if all pairs include NaNs
D2squared = sum(sqdx,2,'omitnan').*n./nstar; % Correction for missing coordinates
D2 = sqrt(D2squared);

Compute the distance with naneucdist by passing the function handle as an input argument of pdist.

D2 = pdist(X,@naneucdist)

D2 = 1×3

    0.3974    1.1538    0.9448

Accelerate Euclidean Distance Computation Using fasteuclidean Distance

Create a large matrix of points, and then measure the time used by pdist with the default «euclidean" distance metric.

rng default % For reproducibility
N = 10000;
X = randn(N,1000);
D = pdist(X); % Warm up function for more reliable timing information
tic
D = pdist(X);
standard = toc

Next, measure the time used by pdist with the "fasteuclidean" distance metric. Specify a cache size of 10.

D = pdist(X,"fasteuclidean",CacheSize=10); % Warm up function
tic
D2 = pdist(X,"fasteuclidean",CacheSize=10);
accelerated = toc

Evaluate how many times faster the accelerated computation is compared to the standard.

The accelerated version computes about three times faster for this example.

Distance metric parameter values, specified as a positive scalar, numeric vector, or
numeric matrix. This argument is valid only when you specify
Distance as 'seuclidean',
'minkowski', or 'mahalanobis'.

Example:
'minkowski',3

Data Types: single | double

D — Pairwise distances
numeric row vector

Pairwise distances, returned as a numeric row vector of length
m(m–1)/2, corresponding to pairs
of observations, where m is the number of observations in
X.

The distances are arranged in the order (2,1), (3,1), …,
(m,1), (3,2), …, (m,2), …,
(m,m–1), i.e., the lower-left
triangle of the m-by-m distance matrix
in column order. The pairwise distance between observations
i and j is in
D((i-1)*(m-i/2)+j-i) for i≤j.

You can convert D into a symmetric matrix by using
the squareform function.
Z = squareform(D) returns an
m-by-m matrix where
Z(i,j) corresponds to the pairwise distance between
observations i and j.

If observation i or j contains
NaNs, then the corresponding value in
D is NaN for the built-in
distance functions.

D is commonly used as a dissimilarity matrix in
clustering or multidimensional scaling. For details, see Hierarchical Clustering and the function reference pages for
cmdscale, cophenet, linkage, mdscale, and optimalleaforder. These
functions take D as an input argument.

A distance metric is a function that defines a distance between
two observations. pdist supports various distance
metrics: Euclidean distance, standardized Euclidean distance, Mahalanobis distance,
city block distance, Minkowski distance, Chebychev distance, cosine distance,
correlation distance, Hamming distance, Jaccard distance, and Spearman
distance.

Given an m-by-n data matrix
X, which is treated as m
(1-by-n) row vectors
x₁,
x₂, …,
x_m, the various distances between
the vector x_s and
x_t are defined as follows:

The values of the Distance argument that begin
fast (such as 'fasteuclidean' and
'fastseuclidean') calculate Euclidean distances using an
algorithm that uses extra memory to save computational time. This algorithm is named
«Euclidean Distance Matrix Trick» in Albanie [1] and elsewhere.
Internal testing shows that this algorithm saves time when the number of predictors
is at least 10.

To find the matrix D of distances between all the points
x_i and
x_j, where each
x_i has n
variables, the algorithm computes distance using the final line in the following
equations:

The matrix xiTxj in the last line of the equations is called the Gram
matrix. Computing the set of squared distances is faster, but
slightly less numerically stable, when you compute and use the Gram matrix instead
of computing the squared distances by squaring and summing. For a discussion, see
Albanie [1].

To store the Gram matrix, the software uses a cache with the default size of
1e3 megabytes. You can set the cache size using the
cache argument. If the value of cache is
too large or "maximal", pdist might
try to allocate a Gram matrix that exceeds the available memory. In this case,
MATLAB issues an error.

• The distance input argument value (Distance) must
  be a compile-time constant. For example, to use the Minkowski distance,
  include coder.Constant('Minkowski') in the
  -args value of codegen.

• The distance input argument value (Distance)
  cannot be a custom distance function.

• pdist does not support code generation for fast Euclidean
  distance computations, meaning those distance metrics whose names begin with
  fast (for example, 'fasteuclidean').

• The generated code of
  pdist uses parfor (MATLAB Coder) to create loops that run in
  parallel on supported shared-memory multicore platforms in the generated code. If your compiler
  does not support the Open Multiprocessing (OpenMP) application interface or you disable OpenMP
  library, MATLAB
  Coder™ treats the parfor-loops as for-loops. To find supported compilers, see Supported Compilers.
  To disable OpenMP library, set the EnableOpenMP property of the
  configuration object to false. For
  details, see coder.CodeConfig (MATLAB Coder).

• The supported distance input argument values
  (Distance) for optimized CUDA code are
  'euclidean',
  'squaredeuclidean',
  'seuclidean', 'cityblock',
  'minkowski', 'chebychev',
  'cosine', 'correlation',
  'hamming', and
  'jaccard'.

• Distance cannot be a custom distance
  function.

• Distance must be a compile-time constant.

• The distance input argument value (Distance) cannot
  be a custom distance function.