KDTreeSearcher class

Superclasses: NeighborSearcher

Nearest neighbors search using kd-tree

Description

A KDTreeSearcher object represents kNN (k-nearest neighbor) search using a kd-tree. Search objects store information about the data used, the distance metric and parameters, and the maximal number of data points in each leaf node. You cannot create this object for sparse input data. The search performance for this object, compared with the ExhaustiveSearcher object, tends to be better for smaller dimensions (10 or fewer) and worse for larger dimensions. For more details on search objects, see What Are Search Objects?.

Construction

NS = KDTreeSearcher(X,'Name',Value) constructs a kd-tree based on X and saves the information in a KDTreeSearcher object, where rows of X correspond to observations and columns correspond to variables. You can use this tree to find neighbors in X nearest to the query points.

NS = createns(X,'NSMethod','kdtree','Name',Value) creates a kd-tree based on X using createns and saves the information in a KDTreeSearcher object where rows of X correspond to observations and columns correspond to variables. You can use this tree to find neighbors in X nearest to the query points.

Name-Value Pair Arguments

KDTreeSearcher and createns accept one or more of the following optional name-value pairs as input.

'Distance'

A string specifying the default distance metric used when you call the knnsearch method.

  • 'euclidean' — Euclidean distance (default).

  • 'cityblock' — City block distance.

  • 'chebychev' — Chebychev distance (maximum coordinate difference).

  • 'minkowski' — Minkowski distance.

For more details on these distance metrics, see Distance Metrics.

'P'

A positive scalar indicating the exponent of the Minkowski distance. This parameter is only valid when Distance is 'minkowski'. Default is 2.

'BucketSize'

A positive integer, indicating the maximum number of data points in each leaf node of the kd-tree. Default is 50.

Properties

X

A matrix used to create the object.

Distance

A string specifying a built-in distance metric that you provide when you create the object. This property is the default distance metric used when you call the knnsearch method to find nearest neighbors for future query points.

DistParameter

Specifies the additional parameter for the chosen distance metric. The value is:

  • If 'Distance' is 'minkowski': A positive scalar indicating the exponent of the Minkowski distance.

  • Otherwise: Empty.

Methods

knnsearchFind k-nearest neighbors using KDTreeSearcher object
rangesearchFind all neighbors within specified distance using KDTreeSearcher object

Examples

expand all

Specify the Minkowski Distance for Nearest Neighbor Search

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

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

Grow a 2d-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: [150x2 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 qurey data and Mdl to:

References

[1] Friedman, J. H., Bentely, J., and Finkel, R. A. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software 3, 209.

Was this topic helpful?