Documentation

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

KDTreeSearcher

Syntax

Mdl = KDTreeSearcher(X)
Mdl = KDTreeSearcher(X,Name,Value)

Description

example

Mdl = KDTreeSearcher(X) grows a default Kd-tree (Mdl) using the n-by-K numeric matrix of training data (X). Mdl is a KDTreeSearcher model object that stores the results of the grown Kd-tree. You can use Mdl to search the training data (X) for the nearest neighbors to the query data.

example

Mdl = KDTreeSearcher(X,Name,Value) grows a Kd-tree (Mdl) with additional options specified by one or more Name,Value pair arguments. For example, you can specify a distance metric or the maximum number of observations in each leaf node (i.e., the bucket size).

Examples

collapse all

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.

Grow a 4-dimensional K d-tree using the entire data set as training data.

Mdl = KDTreeSearcher(X)
Mdl = 

  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'euclidean'
    DistParameter: []
                X: [150×4 double]

Mdl is a KDTreeSearcher model object, and its properties appear in the Command Window. It contains information about the grown 4-dimensional K d-tree, such as the distance metric. You can alter property values using dot notation

To find the nearest neighbors in X to a batch of query data, pass Mdl and the query data to knnsearch or rangesearch.

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

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

Grow a two-dimensional K d-tree using createns and the training data. Specify the Minkowski distance metric.

Mdl = createns(X,'NSMethod','kdtree','Distance','Minkowski')
Mdl = 

  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [150×2 double]

Mdl is a KDTreeSearcher model object. Access properties of Mdl using dot notation. For example, use Mdl.DistParameter to access the Minkowski distance exponent.

Mdl.DistParameter
ans =

     2

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.

Load Fisher's iris data set.

load fisheriris

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

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

Grow a four-dimensional K d-tree using the training data. Specify to use the Minkowski distance for finding nearest neighbors later.

Mdl = createns(X,'NSMethod','kdtree','Distance','minkowski')
Mdl = 

  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'minkowski'
    DistParameter: 2
                X: [145×4 double]

Mdl is a KDTreeSearcher model object. By default, the Minkowski distance exponent is 2.

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

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

    17     4
     6     2
     1    12
    89    66
   124   100

Each row of NN corresponds to a query data observation, and the column order corresponds to the order of the nearest neighbors. For example, using the Minkowski distance, the second nearest neighbor of Q(3,:) is X(12,:).

Input Arguments

collapse all

Training data that grows the Kd-tree, specified as a numeric matrix. X has n rows, each corresponding to an observation (i.e., an instance or example), and K columns, each corresponding to a predictor or feature.

Data Types: single | double

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside single quotes (' '). You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

Example: 'Distance','minkowski','P',3,'BucketSize',10 specifies to use the Minkowski distance when searching for nearest neighbors, to use 3 for the Minkowski distance metric exponent, and to use 10 for the bucket size.

collapse all

Distance metric used to find nearest neighbors of query points, specified as the comma-separated pair consisting of 'Distance' and one of these values.

ValueDescription
'chebychev'Chebychev distance (maximum coordinate difference)
'cityblock'City block distance
'euclidean'Euclidean distance
'minkowski'Minkowski distance

For more details, see Distance Metrics.

The software does not use the distance metric for training the Kd-tree, so you can alter it after training using dot notation.

Example: 'Distance','minkowski'

Data Types: char

Exponent for the Minkowski distance metric, specified as the comma-separated pair consisting of 'P' and a positive scalar. If you specify P and do not specify 'Distance','minkowski', then the software throws an error.

Example: 'P',3

Data Types: double | single

Maximum number of data points in each leaf node of the Kd-tree, specified as the comma-separated pair consisting of 'BucketSize' and a positive integer.

Example: 'BucketSize',10

Data Types: double | single

Output Arguments

collapse all

Grown Kd-tree, returned as a KDTreeSearcher model object. To search the training data for the nearest neighbors of the query data, pass the query data and Mdl to knnsearch or rangesearch.

Introduced in R2010a

Was this topic helpful?