# knnsearch

Find *k*-nearest neighbors using input data

## Description

returns `Idx`

= knnsearch(`X`

,`Y`

,`Name,Value`

)`Idx`

with additional options specified using one or more
name-value pair arguments. For example, you can specify the number of nearest
neighbors to search for and the distance metric used in the search.

## Examples

### Find Nearest Neighbors

Find the patients in the `hospital`

data set that most closely resemble the patients in `Y`

, according to age and weight.

Load the `hospital`

data set.

load hospital; X = [hospital.Age hospital.Weight]; Y = [20 162; 30 169; 40 168; 50 170; 60 171]; % New patients

Perform a `knnsearch`

between `X`

and `Y`

to find indices of nearest neighbors.

Idx = knnsearch(X,Y);

Find the patients in `X`

closest in age and weight to those in `Y`

.

X(Idx,:)

`ans = `*5×2*
25 171
25 171
39 164
49 170
50 172

### Find *k*-Nearest Neighbors Using Different Distance Metrics

Find the 10 nearest neighbors in `X`

to each point in `Y`

, first using the Minkowski distance metric and then using the Chebychev distance metric.

Load Fisher's iris data set.

load fisheriris X = meas(:,3:4); % Measurements of original flowers Y = [5 1.45;6 2;2.75 .75]; % New flower data

Perform a `knnsearch`

between `X`

and the query points `Y`

using Minkowski and Chebychev distance metrics.

[mIdx,mD] = knnsearch(X,Y,'K',10,'Distance','minkowski','P',5); [cIdx,cD] = knnsearch(X,Y,'K',10,'Distance','chebychev');

Visualize the results of the two nearest neighbor searches. Plot the training data. Plot the query points with the marker X. Use circles to denote the Minkowski nearest neighbors. Use pentagrams to denote the Chebychev nearest neighbors.

gscatter(X(:,1),X(:,2),species) line(Y(:,1),Y(:,2),'Marker','x','Color','k',... 'Markersize',10,'Linewidth',2,'Linestyle','none') line(X(mIdx,1),X(mIdx,2),'Color',[.5 .5 .5],'Marker','o',... 'Linestyle','none','Markersize',10) line(X(cIdx,1),X(cIdx,2),'Color',[.5 .5 .5],'Marker','p',... 'Linestyle','none','Markersize',10) legend('setosa','versicolor','virginica','query point',... 'minkowski','chebychev','Location','best')

## Input Arguments

`X`

— Input data

numeric matrix

Input data, specified as a numeric matrix. Rows of `X`

correspond to observations, and columns correspond to variables.

**Data Types: **`single`

| `double`

`Y`

— Query points

numeric matrix

Query points, specified as a numeric matrix. Rows of
`Y`

correspond to observations, and columns
correspond to variables. `Y`

must have the same number of
columns as `X`

.

**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: **`knnsearch(X,Y,'K',10,'IncludeTies',true,'Distance','cityblock')`

searches for 10 nearest neighbors, including ties and using the city block
distance.

`IncludeTies`

— Flag to include all nearest neighbors

`false`

(`0`

) (default) | `true`

(`1`

)

Flag to include all nearest neighbors that have the same distance from
query points, specified as the comma-separated pair consisting of
`'IncludeTies'`

and `false`

(`0`

) or `true`

(`1`

).

If `'IncludeTies'`

is `false`

, then
`knnsearch`

chooses the observation with the
smallest index among the observations that have the same distance from a
query point.

If `'IncludeTies'`

is `true`

, then:

`knnsearch`

includes all nearest neighbors whose distances are equal to the*k*th smallest distance in the output arguments. To specify*k*, use the`'K'`

name-value pair argument.`Idx`

and`D`

are*m*-by-`1`

cell arrays such that each cell contains a vector of at least*k*indices and distances, respectively. Each vector in`D`

contains distances arranged in ascending order. Each row in`Idx`

contains the indices of the nearest neighbors corresponding to the distances in`D`

.

**Example: **`'IncludeTies',true`

`NSMethod`

— Nearest neighbor search method

`'kdtree'`

| `'exhaustive'`

Nearest neighbor search method, specified as the comma-separated pair
consisting of `'NSMethod'`

and one of these values.

`'kdtree'`

— Creates and uses a*K*d-tree to find nearest neighbors.`'kdtree'`

is the default value when the number of columns in`X`

is less than or equal to 10,`X`

is not sparse, and the distance metric is`'euclidean'`

,`'cityblock'`

,`'chebychev'`

, or`'minkowski'`

. Otherwise, the default value is`'exhaustive'`

.The value

`'kdtree'`

is valid only when the distance metric is one of the four metrics noted above.`'exhaustive'`

— Uses the exhaustive search algorithm by computing the distance values from all the points in`X`

to each point in`Y`

.

**Example: **`'NSMethod','exhaustive'`

`Distance`

— Distance metric

`'euclidean'`

(default) | `'seuclidean'`

| `'cityblock'`

| `'chebychev'`

| `'minkowski'`

| `'mahalanobis'`

| function handle | ...

Distance metric `knnsearch`

uses, specified as the
comma-separated pair consisting of `'Distance'`

and one
of the values in this table or a function handle.

Value | Description |
---|---|

`'euclidean'` | Euclidean distance. |

`'seuclidean'` | Standardized Euclidean distance. Each coordinate
difference between rows in `X`
and the query matrix `Y` is
scaled by dividing by the corresponding element of
the standard deviation computed from
`X` . To specify another
scaling, use the `'Scale'`
name-value pair argument. |

`'cityblock'` | City block distance. |

`'chebychev'` | Chebychev distance (maximum coordinate difference). |

`'minkowski'` | Minkowski distance. The default exponent is 2. To
specify a different exponent, use the
`'P'` name-value pair
argument. |

`'mahalanobis'` | Mahalanobis distance, computed using a positive
definite covariance matrix. To change the value of
the covariance matrix, use the
`'Cov'` name-value pair
argument. |

`'cosine'` | One minus the cosine of the included angle between observations (treated as vectors). |

`'correlation'` | One minus the sample linear correlation between observations (treated as sequences of values). |

`'spearman'` | One minus the sample Spearman's rank correlation between observations (treated as sequences of values). |

`'hamming'` | Hamming distance, which is the percentage of coordinates that differ. |

`'jaccard'` | One minus the Jaccard coefficient, which is the percentage of nonzero coordinates that differ. |

You can also specify a function handle for a custom
distance metric by using `@`

(for example,
`@distfun`

). A custom distance function must:

Have the form

`function D2 = distfun(ZI,ZJ)`

.Take as arguments:

A 1-by-

*n*vector`ZI`

containing a single row from`X`

or from the query points`Y`

.An

*m*-by-_{2}*n*matrix`ZJ`

containing multiple rows of`X`

or`Y`

.

Return an

*m*-by-1 vector of distances_{2}`D2`

, whose`j`

th element is the distance between the observations`ZI`

and`ZJ(j,:)`

.

For more information, see Distance Metrics.

**Example: **`'Distance','chebychev'`

`P`

— Exponent for Minkowski distance metric

`2`

(default) | positive scalar

Exponent for the Minkowski distance metric, specified as the comma-separated pair consisting of `'P'`

and a positive scalar.

This argument is valid only if `'Distance'`

is `'minkowski'`

.

**Example: **`'P',3`

**Data Types: **`single`

| `double`

`Cov`

— Covariance matrix for Mahalanobis distance metric

`cov(X,'omitrows')`

(default) | positive definite matrix

Covariance matrix for the Mahalanobis distance metric, specified as the comma-separated pair
consisting of `'Cov'`

and a positive definite matrix.

This argument is valid only if `'Distance'`

is `'mahalanobis'`

.

**Example: **`'Cov',eye(4)`

**Data Types: **`single`

| `double`

`Scale`

— Scale parameter value for standardized Euclidean distance metric

`std(X,'omitnan')`

(default) | nonnegative numeric vector

Scale parameter value for the standardized Euclidean distance metric,
specified as the comma-separated pair consisting of
`'Scale'`

and a nonnegative numeric vector.
`'Scale'`

has length equal to the number of columns
in `X`

. When `knnsearch`

computes
the standardized Euclidean distance, each coordinate of
`X`

is scaled by the corresponding element of
`'Scale'`

, as is each query point. This argument is
valid only when `'Distance'`

is
`'seuclidean'`

.

**Example: **```
'Scale',quantile(X,0.75) -
quantile(X,0.25)
```

**Data Types: **`single`

| `double`

`BucketSize`

— Maximum number of data points in leaf node of *K*d-tree

`50`

(default) | positive integer

Maximum number of data points in the leaf node of the
*K*d-tree, specified as the comma-separated pair
consisting of `'BucketSize'`

and a positive integer.
This argument is valid only when `NSMethod`

is
`'kdtree'`

.

**Example: **`'BucketSize',20`

**Data Types: **`single`

| `double`

`SortIndices`

— Flag to sort returned indices according to distance

`true`

(`1`

) (default) | `false`

(`0`

)

Flag to sort returned indices according to distance, specified as the
comma-separated pair consisting of `'SortIndices'`

and
either `true`

(`1`

) or
`false`

(`0`

).

For faster performance, you can set `SortIndices`

to `false`

when the following are true:

`Y`

contains many observations that have many nearest neighbors in`X`

.`NSMethod`

is`'kdtree'`

.`IncludeTies`

is`false`

.

In this case, `knnsearch`

returns the
indices of the nearest neighbors in no particular order. When
`SortIndices`

is `true`

, the
function arranges the nearest-neighbor indices in ascending order by
distance.

`SortIndices`

is `true`

by
default. When `NSMethod`

is
`'exhaustive'`

or `IncludeTies`

is `true`

, the function always sorts the
indices.

**Example: **`'SortIndices',false`

**Data Types: **`logical`

## Output Arguments

`Idx`

— Input data indices of nearest neighbors

numeric matrix | cell array of numeric vectors

Input data indices of the nearest neighbors, returned as a numeric matrix or cell array of numeric vectors.

If you do not specify

`IncludeTies`

(`false`

by default), then`Idx`

is an*m*-by-*k*numeric matrix, where*m*is the number of rows in`Y`

and*k*is the number of searched nearest neighbors.`Idx(j,i)`

indicates that`X(Idx(j,i),:)`

is one of the*k*closest observations in`X`

to the query point`Y(j,:)`

.If you specify

`'IncludeTies',true`

, then`Idx`

is an*m*-by-`1`

cell array such that cell`j`

(`Idx{j}`

) contains a vector of at least*k*indices of the closest observations in`X`

to the query point`Y(j,:)`

.

If `SortIndices`

is `true`

, then
`knnsearch`

arranges the indices in ascending order
by distance.

`D`

— Distances of nearest neighbors

numeric matrix | cell array of numeric vectors

Distances of the nearest neighbors to the query points, returned as a numeric matrix or cell array of numeric vectors.

If you do not specify

`IncludeTies`

(`false`

by default), then`D`

is an*m*-by-*k*numeric matrix, where*m*is the number of rows in`Y`

and*k*is the number of searched nearest neighbors.`D(j,i)`

is the distance between`X(Idx(j,i),:)`

and`Y(j,:)`

with respect to the distance metric.If you specify

`'IncludeTies',true`

, then`D`

is an*m*-by-`1`

cell array such that cell`j`

(`D{j}`

) contains a vector of at least*k*distances of the closest observations in`X`

to the query point`Y(j,:)`

.

If `SortIndices`

is `true`

, then
`knnsearch`

arranges the distances in ascending
order.

## Tips

For a fixed positive integer

*k*,`knnsearch`

finds the*k*points in`X`

that are the nearest to each point in`Y`

. To find all points in`X`

within a fixed distance of each point in`Y`

, use`rangesearch`

.`knnsearch`

does not save a search object. To create a search object, use`createns`

.

## Algorithms

For information on a specific search algorithm, see k-Nearest Neighbor Search and Radius Search.

## Alternative Functionality

If you set the `knnsearch`

function's `'NSMethod'`

name-value pair argument to the appropriate value (`'exhaustive'`

for
an exhaustive search algorithm or `'kdtree'`

for a
*K*d-tree algorithm), then the search results are equivalent to the
results obtained by conducting a distance search using the `knnsearch`

object function. Unlike the `knnsearch`

function, the `knnsearch`

object function requires an
`ExhaustiveSearcher`

or a `KDTreeSearcher`

model object.

## References

[1] Friedman, J. H., J. Bentley, and R. A. Finkel. “An Algorithm for Finding
Best Matches in Logarithmic Expected Time.” *ACM Transactions on
Mathematical Software* 3, no. 3 (1977): 209–226.

## Extended Capabilities

### Tall Arrays

Calculate with arrays that have more rows than fit in memory.

Usage notes and limitations:

If

`X`

is a tall array, then`Y`

cannot be a tall array. Similarly, if`Y`

is a tall array, then`X`

cannot be a tall array.

For more information, see Tall Arrays.

### C/C++ Code Generation

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

Usage notes and limitations:

For code generation, the default value of the

`'NSMethod'`

name-value pair argument is`'exhaustive'`

when the number of columns in`X`

is greater than 7.The value of the

`'Distance'`

name-value pair argument must be a compile-time constant and cannot be a custom distance function.The value of the

`'IncludeTies'`

name-value pair argument must be a compile-time constant.The

`'SortIndices'`

name-value pair argument is not supported. The output arguments are always sorted.Names in name-value pair arguments must be compile-time constants. For example, to allow a user-defined exponent for the Minkowski distance in the generated code, include

`{coder.Constant('Distance'),coder.Constant('Minkowski'),coder.Constant('P'),0}`

in the`-args`

value of`codegen`

(MATLAB Coder).When you specify

`'IncludeTies'`

as`true`

, the sorted order of tied distances in the generated code can be different from the order in MATLAB^{®}due to numerical precision.When

`knnsearch`

uses the*k*d-tree search algorithm, and the code generation build type is a MEX function,`codegen`

(MATLAB Coder) generates a MEX function using Intel^{®}Threading Building Blocks (TBB) for parallel computation. Otherwise,`codegen`

generates code using`parfor`

(MATLAB Coder).MEX function for the

*k*d-tree search algorithm —`codegen`

generates an optimized MEX function using Intel TBB for parallel computation on multicore platforms. You can use the MEX function to accelerate MATLAB algorithms. For details on Intel TBB, see https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/onetbb.html.If you generate the MEX function to test the generated code of the

`parfor`

version, you can disable the usage of Intel TBB. Set the`ExtrinsicCalls`

property of the MEX configuration object to`false`

. For details, see`coder.MexCodeConfig`

(MATLAB Coder).MEX function for the exhaustive search algorithm and standalone C/C++ code for both algorithms — The generated code of

`knnsearch`

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).

Starting in R2020a,

`knnsearch`

returns integer-type (`int32`

) indices, rather than double-precision indices, in generated standalone C/C++ code. Therefore, the function allows for strict single-precision support when you use single-precision inputs. For MEX code generation, the function still returns double-precision indices to match the MATLAB behavior.

For more information on code generation, see Introduction to Code Generation and General Code Generation Workflow.

### GPU Arrays

Accelerate code by running on a graphics processing unit (GPU) using Parallel Computing Toolbox™.

Usage notes and limitations:

The

`'IncludeTies'`

,`'NSMethod'`

, and`'SortIndices'`

name-value pair arguments are not supported.

For more information, see Run MATLAB Functions on a GPU (Parallel Computing Toolbox).

## Version History

**Introduced in R2010a**

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

# Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)