Classe « KDTree »

Informations générales

Héritage

builtins.object
    cKDTree
        KDTree

Définition

class KDTree(cKDTree):

help(KDTree)

kd-tree for quick nearest-neighbor lookup.

This class provides an index into a set of k-dimensional points
which can be used to rapidly look up the nearest neighbors of any
point.

Parameters
----------
data : array_like, shape (n,m)
    The n data points of dimension m to be indexed. This array is
    not copied unless this is necessary to produce a contiguous
    array of doubles, and so modifying this data will result in
    bogus results. The data are also copied if the kd-tree is built
    with copy_data=True.
leafsize : positive int, optional
    The number of points at which the algorithm switches over to
    brute-force.  Default: 10.
compact_nodes : bool, optional
    If True, the kd-tree is built to shrink the hyperrectangles to
    the actual data range. This usually gives a more compact tree that
    is robust against degenerated input data and gives faster queries
    at the expense of longer build time. Default: True.
copy_data : bool, optional
    If True the data is always copied to protect the kd-tree against
    data corruption. Default: False.
balanced_tree : bool, optional
    If True, the median is used to split the hyperrectangles instead of
    the midpoint. This usually gives a more compact tree and
    faster queries at the expense of longer build time. Default: True.
boxsize : array_like or scalar, optional
    Apply a m-d toroidal topology to the KDTree.. The topology is generated
    by :math:`x_i + n_i L_i` where :math:`n_i` are integers and :math:`L_i`
    is the boxsize along i-th dimension. The input data shall be wrapped
    into :math:`[0, L_i)`. A ValueError is raised if any of the data is
    outside of this bound.

Notes
-----
The algorithm used is described in Maneewongvatana and Mount 1999.
The general idea is that the kd-tree is a binary tree, each of whose
nodes represents an axis-aligned hyperrectangle. Each node specifies
an axis and splits the set of points based on whether their coordinate
along that axis is greater than or less than a particular value.

During construction, the axis and splitting point are chosen by the
"sliding midpoint" rule, which ensures that the cells do not all
become long and thin.

The tree can be queried for the r closest neighbors of any given point
(optionally returning only those within some maximum distance of the
point). It can also be queried, with a substantial gain in efficiency,
for the r approximate closest neighbors.

For large dimensions (20 is already large) do not expect this to run
significantly faster than brute force. High-dimensional nearest-neighbor
queries are a substantial open problem in computer science.

Attributes
----------
data : ndarray, shape (n,m)
    The n data points of dimension m to be indexed. This array is
    not copied unless this is necessary to produce a contiguous
    array of doubles. The data are also copied if the kd-tree is built
    with ``copy_data=True``.
leafsize : positive int
    The number of points at which the algorithm switches over to
    brute-force.
m : int
    The dimension of a single data-point.
n : int
    The number of data points.
maxes : ndarray, shape (m,)
    The maximum value in each dimension of the n data points.
mins : ndarray, shape (m,)
    The minimum value in each dimension of the n data points.
size : int
    The number of nodes in the tree.

Constructeur(s)

Signature du constructeur	Description
__init__(self, data, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)

Liste des attributs statiques

Attributs statiques hérités de la classe cKDTree

boxsize, data, indices, leafsize, m, maxes, mins, n, size, tree

Liste des propriétés

Nom de la propriété	Description
tree

Liste des opérateurs

Opérateurs hérités de la classe object

__eq__, __ge__, __gt__, __le__, __lt__, __ne__

Liste des méthodes

Toutes les méthodes Méthodes d'instance Méthodes statiques

Signature de la méthode	Description
count_neighbors(self, other, r, p=2.0, weights=None, cumulative=True)	Count how many nearby pairs can be formed. _{[extrait de count_neighbors.__doc__]}
innernode(ckdtreenode)
leafnode(ckdtree_node=None)
node(ckdtree_node=None)
query(self, x, k=1, eps=0, p=2, distance_upper_bound=inf, workers=1)	Query the kd-tree for nearest neighbors. _{[extrait de query.__doc__]}
query_ball_point(self, x, r, p=2.0, eps=0, workers=1, return_sorted=None, return_length=False)	Find all points within distance r of point(s) x. _{[extrait de query_ball_point.__doc__]}
query_ball_tree(self, other, r, p=2.0, eps=0)
query_pairs(self, r, p=2.0, eps=0, output_type='set')	Find all pairs of points in `self` whose distance is at most r. _{[extrait de query_pairs.__doc__]}
sparse_distance_matrix(self, other, max_distance, p=2.0, output_type='dok_matrix')	Compute a sparse distance matrix. _{[extrait de sparse_distance_matrix.__doc__]}