ExhaustiveSearcher

Create exhaustive nearest neighbor searcher

Description

ExhaustiveSearcher model objects store the training data, distance metric, and parameter values of the distance metric for an exhaustive nearest neighbor search. The exhaustive search algorithm finds the distance from each query observation to all n observations in the training data, which is an n-by-K numeric matrix.

Once you create an ExhaustiveSearcher model object, find neighboring points in the training data to the query data by performing a nearest neighbor search using knnsearch or a radius search using rangesearch. The exhaustive search algorithm is more efficient than the Kd-tree algorithm when K is large (that is, K > 10), and it is more flexible than the Kd-tree algorithm with respect to distance metric choices. The ExhaustiveSearcher model object also supports sparse data.

Creation

Use either the createns function or the ExhaustiveSearcher function (described here) to create an ExhaustiveSearcher object. Both functions use the same syntax except that the createns function has the 'NSMethod' name-value pair argument, which you use to choose the nearest neighbor search method. The createns function also creates a KDTreeSearcher object. Specify 'NSMethod','exhaustive' to create an ExhaustiveSearcher object. The default is 'exhaustive' if K > 10, the training data is sparse, or the distance metric is not the Euclidean, city block, Chebychev, or Minkowski.

Syntax

Mdl = ExhaustiveSearcher(X)

Mdl = ExhaustiveSearcher(X,Name,Value)

Description

Mdl = ExhaustiveSearcher(X) creates an exhaustive nearest neighbor searcher object (Mdl) using the n-by-K numeric matrix of training data (X).

Mdl = ExhaustiveSearcher(X,Name,Value) specifies additional options using one or more name-value pair arguments. You can specify the distance metric and set the distance metric parameter (DistParameter) property. For example, ExhaustiveSearcher(X,'Distance','chebychev') creates an exhaustive nearest neighbor searcher object that uses the Chebychev distance. To specify DistParameter, use the Cov, P, or Scale name-value pair argument.

Input Arguments

X — Training data

numeric matrix

Training data that prepares the exhaustive searcher algorithm, specified as a numeric matrix. X has n rows, each corresponding to an observation (that is, an instance or example), and K columns, each corresponding to a predictor (that is, a feature).

Data Types: single | double

Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is the argument name and Value is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Before R2021a, use commas to separate each name and value, and enclose Name in quotes.

Example: 'Distance','mahalanobis','Cov',eye(3) specifies to use the Mahalanobis distance when searching for nearest neighbors and a 3-by-3 identity matrix for the covariance matrix in the Mahalanobis distance metric.

Properties

X — Training data

numeric matrix

This property is read-only.

Training data that prepares the exhaustive searcher algorithm, specified as a numeric matrix. X has n rows, each corresponding to an observation (that is, an instance or example), and K columns, each corresponding to a predictor (that is, a feature).

The input argument X of createns or ExhaustiveSearcher sets this property.

Data Types: single | double

Distance — Distance metric

character vector | string scalar | custom distance function

Distance metric used when you call knnsearch or rangesearch to find nearest neighbors for future query points, specified as a character vector or string scalar ('chebychev', 'cityblock', 'correlation', 'cosine', 'euclidean', 'fasteuclidean', 'fastseuclidean', 'hamming', 'jaccard', 'minkowski', 'mahalanobis', 'seuclidean', or 'spearman'), or a function handle.

The 'Distance' name-value pair argument of createns or ExhaustiveSearcher sets this property.

The software does not use the distance metric for creating an ExhaustiveSearcher model object, so you can alter it by using dot notation. Algorithms starting with 'fast' do not support sparse data.

DistParameter — Distance metric parameter values

[] | positive scalar

Distance metric parameter values, specified as empty ([]) or a positive scalar.

This table describes the distance parameters of the supported distance metrics.

Distance Metric	Parameter Description
'mahalanobis'	A positive definite matrix representing the covariance matrix used for computing the Mahalanobis distance. By default, the software sets the covariance using cov(Mdl.X,'omitrows'). The 'Cov' name-value pair argument of createns or ExhaustiveSearcher sets this property. You can alter DistParameter by using dot notation, for example, Mdl.DistParameter = CovNew, where CovNew is a K-by-K positive definite numeric matrix.
'minkowski'	A positive scalar indicating the exponent of the Minkowski distance. By default, the exponent is 2. The 'P' name-value pair argument of createns or ExhaustiveSearcher sets this property. You can alter DistParameter by using dot notation, for example, Mdl.DistParameter = PNew, where PNew is a positive scalar.
'seuclidean'	A positive numeric vector indicating the values used by the software to scale the predictors when computing the standardized Euclidean distance. By default, the software: Estimates the standard deviation of each predictor (column) of X using scale = std(Mdl.X,'omitnan') Scales each coordinate difference between the rows in X and the query matrix by dividing by the corresponding element of scale The 'Scale' name-value pair argument of createns or ExhaustiveSearcher sets this property. You can alter DistParameter by using dot notation, for example, Mdl.DistParameter = sNew, where sNew is a K-dimensional positive numeric vector.

If Mdl.Distance is not one of the parameters listed in this table, then Mdl.DistParameter is [], which means that the specified distance metric formula has no parameters.

Data Types: single | double

Object Functions

knnsearch	Find k-nearest neighbors using searcher object
rangesearch	Find all neighbors within specified distance using searcher object

Examples

Train Default Exhaustive Nearest Neighbor Searcher

Load Fisher's iris data set.

load fisheriris
X = meas;
[n,k] = size(X)

n = 150

k = 4

X has 150 observations and 4 predictors.

Prepare an exhaustive nearest neighbor searcher using the entire data set as training data.

Mdl1 = ExhaustiveSearcher(X)

Mdl1 = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [150x4 double]

Mdl1 is an ExhaustiveSearcher model object, and its properties appear in the Command Window. The object contains information about the trained algorithm, such as the distance metric. You can alter property values using dot notation.

Alternatively, you can prepare an exhaustive nearest neighbor searcher by using createns and specifying 'exhaustive' as the search method.

Mdl2 = createns(X,'NSMethod','exhaustive')

Mdl2 = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [150x4 double]

Mdl2 is also an ExhaustiveSearcher model object, and it is equivalent to Mdl1.

To search X for the nearest neighbors to a batch of query data, pass the ExhaustiveSearcher model object and the query data to knnsearch or rangesearch.

Specify the Mahalanobis Distance for Nearest Neighbor Search

Load Fisher's iris data set. Focus on the petal dimensions.

load fisheriris
X = meas(:,[3 4]); % Predictors

Prepare an exhaustive nearest neighbor searcher. Specify the Mahalanobis distance metric.

Mdl = createns(X,'Distance','mahalanobis')

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'mahalanobis'
    DistParameter: [2x2 double]
                X: [150x2 double]

Because the distance metric is Mahalanobis, createns creates an ExhaustiveSearcher model object by default.

Access properties of Mdl by using dot notation. For example, use Mdl.DistParameter to access the Mahalanobis covariance parameter.

Mdl.DistParameter

ans = 2×2

    3.1163    1.2956
    1.2956    0.5810

You can pass query data and Mdl to:

• knnsearch to find indices and distances of nearest neighbors

• rangesearch to find indices of all nearest neighbors within a distance that you specify

Alter Properties of ExhaustiveSearcher Model

Create an ExhaustiveSearcher model object and alter the Distance property by using dot notation.

Load Fisher's iris data set.

load fisheriris
X = meas;

Train a default exhaustive searcher algorithm using the entire data set as training data.

Mdl = ExhaustiveSearcher(X)

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'euclidean'
    DistParameter: []
                X: [150x4 double]

Specify that the neighbor searcher use the Mahalanobis metric to compute the distances between the training and query data.

Mdl.Distance = 'mahalanobis'

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'mahalanobis'
    DistParameter: [4x4 double]
                X: [150x4 double]

You can pass Mdl and the query data to either knnsearch or rangesearch to find the nearest neighbors to the points in the query data based on the Mahalanobis distance.

Search for Nearest Neighbors of Query Data Using Mahalanobis Distance

Create an exhaustive searcher object by using the createns function. Pass the object and query data to the knnsearch function to find k-nearest neighbors.

Load Fisher's iris data set.

load fisheriris

Remove five irises randomly from the predictor data to use as a query set.

rng('default');             % For reproducibility
n = size(meas,1);           % Sample size
qIdx = randsample(n,5);     % Indices of query data
X = meas(~ismember(1:n,qIdx),:);
Y = meas(qIdx,:);

Prepare an exhaustive nearest neighbor searcher using the training data. Specify the Mahalanobis distance for finding nearest neighbors.

Mdl = createns(X,'Distance','mahalanobis')

Mdl = 
  ExhaustiveSearcher with properties:

         Distance: 'mahalanobis'
    DistParameter: [4x4 double]
                X: [145x4 double]

Because the distance metric is Mahalanobis, createns creates an ExhaustiveSearcher model object by default.

The software uses the covariance matrix of the predictors (columns) in the training data for computing the Mahalanobis distance. To display this value, use Mdl.DistParameter.

Mdl.DistParameter

ans = 4×4

    0.6547   -0.0368    1.2320    0.5026
   -0.0368    0.1914   -0.3227   -0.1193
    1.2320   -0.3227    3.0671    1.2842
    0.5026   -0.1193    1.2842    0.5800

Find the indices of the training data (Mdl.X) that are the two nearest neighbors of each point in the query data (Y).

IdxNN = knnsearch(Mdl,Y,'K',2)

IdxNN = 5×2

     5     6
    98    95
   104   128
   135    65
   102   115

Each row of IdxNN corresponds to a query data observation. The column order corresponds to the order of the nearest neighbors with respect to ascending distance. For example, based on the Mahalanobis metric, the second nearest neighbor of Y(3,:) is X(128,:).

Algorithms

Fast Euclidean Distance Algorithm

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. Algorithms starting with 'fast' do not support sparse data.

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:

$$\begin{array}{c}{D}_{i,j}^2=\Vert x_i-x_j{\Vert }^2\\ ={(}^{x_i}(x_i-x_j)\\ =\Vert x_i{\Vert }^2-2x_i^T{x}_j+\Vert x_j{\Vert }^2.\end{array}$$

The matrix $$x_i^T{x}_j$$ 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].

References

[1] Albanie, Samuel. Euclidean Distance Matrix Trick. June, 2019. Available at https://www.robots.ox.ac.uk/%7Ealbanie/notes/Euclidean_distance_trick.pdf.

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

• The knnsearch and rangesearch functions support code generation.

• When you train an ExhaustiveSearcher model object, the value of the 'Distance' name-value pair argument cannot be a custom distance function.

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

For more information, see Introduction to Code Generation and Code Generation for Nearest Neighbor Searcher.

Version History

Introduced in R2010a

R2023a: Fast Euclidean distance using a cache

The 'fasteuclidean' and 'fastseuclidean' distance metrics accelerate the computation of Euclidean distances by using a cache and a different algorithm (see Algorithms). These distance metrics apply only to the knnsearch function.