scipy.spatial.

cKDTree

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

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

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

Примечание

cKDTree функционально идентичен KDTree. До SciPy v1.6.0, cKDTree имел лучшую производительность и немного отличающуюся функциональность, но теперь оба имени существуют только для обратной совместимости. Если совместимость с SciPy < 1.6 не важна, предпочтительнее KDTree.

Параметры:

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

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

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

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

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 точек данных.

деревообъект, класс cKDTreeNode

Этот атрибут предоставляет Python-представление корневого узла в объекте cKDTree. Полное Python-представление kd-дерева создаётся динамически при первом обращении. Этот атрибут позволяет создавать собственные функции запросов на Python.

размерint

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

Методы

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

Примечания

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

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

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

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