scipy.spatial.

KDTree

класс scipy.spatial.KDTree(данные, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)

kd-дерево для быстрого поиска ближайшего соседа.

Этот класс предоставляет индекс для набора k-мерных точек, который можно использовать для быстрого поиска ближайших соседей любой точки.

Параметры:

данныеarray_like, shape (n,m)

n точек данных размерности m для индексации. Этот массив не копируется, если это не необходимо для создания непрерывного массива double, поэтому изменение этих данных приведёт к некорректным результатам. Данные также копируются, если kd-дерево построено с copy_data=True.

leafsizeположительное целое, опционально

Количество точек, при котором алгоритм переключается на полный перебор. По умолчанию: 10.

compact_nodesbool, необязательно

Если True, kd-дерево строится с уменьшением гиперпрямоугольников до фактического диапазона данных. Обычно это дает более компактное дерево, устойчивое к вырожденным входным данным и обеспечивающее более быстрые запросы за счет большего времени построения. По умолчанию: True.

copy_databool, необязательно

Если True, данные всегда копируются для защиты kd-дерева от повреждения данных. По умолчанию: False.

balanced_treebool, необязательно

Если True, медиана используется для разделения гиперпрямоугольников вместо середины. Обычно это дает более компактное дерево и более быстрые запросы за счет большего времени построения. По умолчанию: True.

boxsizearray_like или скаляр, опционально

Применить m-d тороидальную топологию к KDTree. Топология генерируется \(x_i + n_i L_i\) где \(n_i\) являются целыми числами и \(L_i\) является размером коробки вдоль i-го измерения. Входные данные должны быть обёрнуты в \([0, L_i)\). ValueError возникает, если какие-либо данные выходят за эти границы.

Атрибуты:

данныеndarray, форма (n,m)

n точек данных размерности m для индексирования. Этот массив не копируется, если это не необходимо для создания непрерывного массива double. Данные также копируются, если kd-дерево построено с copy_data=True.

leafsizeположительное целое число

Количество точек, при котором алгоритм переключается на метод грубой силы.

mint

Размерность одной точки данных.

nint

Количество точек данных.

maxesndarray, форма (m,)

Максимальное значение в каждом измерении n точек данных.

минутыndarray, форма (m,)

Минимальное значение в каждом измерении для n точек данных.

размерint

Количество узлов в дереве.

Методы

count_neighbors(other, r[, p, weights, ...])	Подсчитать, сколько пар можно образовать из близлежащих элементов.
query(x[, k, eps, p, distance_upper_bound, ...])	Запросите kd-дерево для поиска ближайших соседей.
query_ball_point(x, r[, p, eps, workers, ...])	Найти все точки в пределах расстояния r от точки(точек) x.
query_ball_tree(other, r[, p, eps])	Найти все пары точек между self и other расстояние до которого не превышает r.
query_pairs(r[, p, eps, output_type])	Найти все пары точек в self расстояние до которого не превышает r.
sparse_distance_matrix(other, max_distance)	Вычислить разреженную матрицу расстояний.

innernode
листовой узел
узел

Примечания

Используемый алгоритм описан в Maneewongvatana and Mount 1999. Общая идея заключается в том, что kd-дерево — это бинарное дерево, каждый узел которого представляет собой выровненный по осям гиперпрямоугольник. Каждый узел задаёт ось и разделяет набор точек на основе того, больше или меньше их координата вдоль этой оси определённого значения.

Во время построения ось и точка разделения выбираются по правилу "скользящей середины", что гарантирует, что ячейки не становятся все длинными и тонкими.

Дерево может быть запрошено на r ближайших соседей любой заданной точки (опционально возвращая только тех, кто находится в пределах некоторого максимального расстояния от точки). Также можно запросить, с существенным выигрышем в эффективности, r приближенных ближайших соседей.

Для больших размерностей (20 уже считается большим) не ожидайте, что это будет работать значительно быстрее, чем метод грубой силы. Запросы ближайшего соседа в высоких размерностях — это существенная открытая проблема в информатике.