Package smile.neighbor
Class KDTree<E>
java.lang.Object
smile.neighbor.KDTree<E>
 Type Parameters:
E
 the type of data objects in the tree.
 All Implemented Interfaces:
Serializable
,KNNSearch<double[],
,E> RNNSearch<double[],
E>
public class KDTree<E>
extends Object
implements KNNSearch<double[],E>, RNNSearch<double[],E>, Serializable
A KDtree (short for kdimensional tree) is a spacepartitioning dataset
structure for organizing points in a kdimensional space. KDtrees are
a useful dataset structure for nearest neighbor searches. The kdtree is a
binary tree in which every node is a kdimensional point. Every nonleaf
node generates a splitting hyperplane that divides the space into two
subspaces. Points left to the hyperplane represent the left subtree of
that node and the points right to the hyperplane by the right subtree.
The hyperplane direction is chosen in the following way: every node split
to subtrees is associated with one of the kdimensions, such that the
hyperplane is perpendicular to that dimension vector. So, for example, if
for a particular split the "x" axis is chosen, all points in the subtree
with a smaller "x" value than the node will appear in the left subtree and
all points with larger "x" value will be in the right subtree.
KDtrees are not suitable for efficiently finding the nearest neighbor
in high dimensional spaces. As a general rule, if the dimensionality is D,
then number of points in the dataset, N, should be N >>
2^{D}.
Otherwise, when kdtrees are used with highdimensional dataset, most of the
points in the tree will be evaluated and the efficiency is no better than
exhaustive search, and approximate nearestneighbor methods should be used
instead.
By default, the query object (reference equality) is excluded from the neighborhood.
 See Also:

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionnearest
(double[] q) Returns the nearest neighbor.static KDTree
<double[]> of
(double[][] data) Return a KDtree of the data.void
Retrieves the neighbors in a fixed radius of query object, i.e.search
(double[] q, int k) Retrieves the k nearest neighbors to the query key.toString()

Constructor Details

KDTree
Constructor. Parameters:
key
 the object keys.data
 the data objects.


Method Details

of
Return a KDtree of the data. Parameters:
data
 the data objects, which are also used as key. Returns:
 KDtree.

toString

nearest
Description copied from interface:KNNSearch
Returns the nearest neighbor. In machine learning, we often build a nearest neighbor search data structure, and then search with object in the same dataset. The object itself is of course the nearest one with distance 0. Since this is generally useless, we check the reference during the search and excludes the query object from the results. 
search
Description copied from interface:KNNSearch
Retrieves the k nearest neighbors to the query key. 
search
Description copied from interface:RNNSearch
Retrieves the neighbors in a fixed radius of query object, i.e.d(q, v) <= radius
.
