В этом уроке Python мы узнаем о «Scipy Kdtree», где научимся находить ближайшие точки к определенной точке.
- Что такое Kdtree
- Метод KDTree.query()
- Метод KDTree.query_ball_point()
- Метод KDTree.query_pairs()
- Класс KDTree()
- Метод query_ball_tree()
- Метод count_neighbors()
- Метод count_neighbors()
- Сравнение Kdtree и ckdtree
- Параметры
- Производительность
Что такое Kdtree
Структура данных с разделением пространства, известная как kd-дерево(сокращение от k-мерного дерева), используется в информатике для организации точек в k-мерном пространстве.
Деревья Kd представляют собой полезную структуру данных для многих приложений, включая создание облаков точек и выполнение поиска с использованием многомерного ключа поиска (например, поиск по диапазону и поиск ближайших соседей). Особым типом дерева разбиения двоичного пространства является дерево kd.
Метод KDTree.query()
Метод KDTree.query() существует в модуле scipy.spatial, который находит ближайших соседей.
Синтаксис:
KDTree.query(x, eps=0, k=1, p=2, workers=1, distance_upper_bound=inf,)
Где параметры:
- x(array_data, последнее измерение): массив точек, подлежащих запросу.
- eps(nonnegative float): гарантированно, что k-й сообщаемый результат будет не более чем в(1+eps) раз больше расстояния до фактического k-го ближайшего соседа. Возвращает приблизительных ближайших соседей.
- k(int, последовательность int): список k-х ближайших соседей, которые нужно вернуть, начиная с 1, или количество ближайших соседей, которые нужно вернуть.
- p(float): использование p-нормы Минковского. Расстояние суммы абсолютных значений(или «Манхэттенское») равно 1. Типичное евклидово расстояние равно двум. Расстояние с наибольшей разницей координат равно бесконечности. Если переполнение возможно при большом конечном p, может возникнуть ошибка ValueError.
- workers(int): используется для параллельной обработки с точки зрения рабочих. Каждый поток ЦП используется, если указано -1. По умолчанию: 1.
- distance_upper_bound(неотрицательное число с плавающей запятой): будут возвращены только те, кто находится рядом. Может быть полезно указать расстояние до ближайшего соседа самой последней точки, если вы выполняете серию запросов ближайших соседей, поскольку это используется для сокращения поиска по дереву.
Метод KDTree() возвращает d (расстояние между ближайшими соседями) и i(индекс соседа в self.data.i по форме напоминает d. Self.n используется для обозначения отсутствующих соседей) типа float и целых чисел соответственно.
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
from scipy import spatial import numpy as np
Создайте многомерный массив и передайте его в KDTree, используя приведенный ниже код.
x_data, y_data = np.mgrid[0:6, 2:7] kd_tree = spatial.KDTree(np.c_[x_data.ravel(), y_data.ravel()])
Используйте следующий код, чтобы выполнить поиск сжатого соседа и получить результаты:
d, i = kd_tree.query([[0, 0], [1.1, 1.9]], k=1) print(d, i, sep='\n')
Метод KDTree.query_ball_point()
Метод KDTree.query_ball_point() существует в модуле scipy.spatial, который находит все точки, которые находятся ближе к точке(ям) x, чем r.
Синтаксис:
KDTree.query_ball_point(x, r, p=2.0, eps=0, workers=1, return_sorted=None, return_length=False)
Где параметры:
- x(array_data): какую точку или точки следует использовать для поиска близлежащих точек.
- r(array_data): длина x должна передаваться по радиусу возвращаемых точек.
- p(float): какую p-норму Минковского следует применять. Должно находиться в диапазоне [1, инф]. Если переполнение возможно для конечного большого p, может возникнуть ошибка ValueError.
- eps(неотрицательное число с плавающей запятой): предполагаемый поиск. Ветви дерева не проверяются, если их ближайшие точки находятся на расстоянии более чем r/(1 + eps), и добавляются массово, если они находятся ближе, чем r *(1 + eps).
- workers(int): используется для параллельной обработки с точки зрения рабочих. Каждый поток ЦП используется, если указано -1. По умолчанию: 1.
- return_sorted(boolean): если True, возвращаемые индексы сортируются; если значение равно False, они не сортируются. Если «Нет», сортируются многоточечные запросы вместо одноточечного поиска, что было поведением по умолчанию до добавления этой опции.
- return_length(boolean): вместо списка индексов возвращает общее количество точек в радиусе.
Метод query_ball_point() возвращает результат, который представляет собой список индексов соседей x, который возвращается, если x представляет собой одну точку. Возвращает массив объектов кортежа формы со списками соседей, если x — массив точек.
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
from scipy import spatial import numpy as np
Создайте многомерный массив и передайте его в KDTree, используя приведенный ниже код.
x_data, y_data = np.mgrid[0:7, 0:7] kd_tree = spatial.KDTree(np.c_[x_data.ravel(), y_data.ravel()])
Передайте приведенные выше данные в метод query_ball_point(), чтобы найти все точки, которые находятся ближе к точке(точкам) x, чем r, используя приведенный ниже код.
sorted(kd_tree.query_ball_point([3, 1],2))
Метод KDTree.query_pairs()
Метод KDTree.query_pairs() существует в модуле scipy.spatial. Найдите внутри себя все пары точек, расстояния которых равны r или меньше.
Синтаксис:
KDTree.query_pairs(r, p=2.0, eps=0, output_type='set')
Где параметры:
- r(положительное плавающее значение): это максимальное расстояние.
- p(float): какой стандарт Минковского применить. Ограничение 1 = p <= бесконечность должно удовлетворяться p.
- eps(неотрицательное число с плавающей запятой): предполагаемый поиск. Ветви дерева не проверяются, если их ближайшие точки находятся на расстоянии более чем r/(1 + eps), и добавляются массово, если они находятся ближе, чем r *(1 + eps).
- output_type(string): выберите «set» или «ndarray» в качестве выходного контейнера. По умолчанию: «установить»
Метод query_pairs() возвращает результат типа set или ndarray, который представляет собой группу пар(i,j), где I > j и соответствующие места находятся рядом друг с другом. Возвращается ndarry, а не набор, если тип вывода — «ndarray».
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
import numpy as np import matplotlib.pyplot as plt from scipy import spatial
Сгенерируйте точки данных, используя генератор случайных чисел, как показано в приведенном ниже коде.
rnd_gen = np.random.default_rng() pts = rnd_gen.random((30, 3))
Передайте точки в kdtree и найдите все пары точек на расстоянии ar в kd-дереве, используя приведенный ниже код.
kdtree = spatial.KDTree(pts) prs = kdtree.query_pairs(r=0.3)
Постройте пары, используя приведенный ниже код.
plt.figure(figsize=(5, 5))
plt.plot(pts[:, 0], pts[:, 1], "xk", markersize=14)
for(i, j) in prs:
plt.plot([pts[i, 0], pts[j, 0]],
[pts[i, 1], pts[j, 1]], "-r")
plt.show()
Класс KDTree()
Модуль Python scipy.spatial содержит класс KDTree() для быстрого поиска ближайшего соседа.
- Манивонгватана и Маунт 1999 подробно описывают алгоритм. Kd-дерево представляет собой бинарное дерево, каждый узел которого обозначает гиперпрямоугольник, выровненный по оси. Каждый узел обозначает ось и делит набор точек в зависимости от того, превышает или падает их координата вдоль этой оси определенное значение.
Синтаксис:
scipy.spatial.KDTree(data, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)
Где параметры:
- data(array): n точек измерения размера m, которые будут проиндексированы. Поскольку этот массив не копируется, если не требуется создать непрерывный массив двойных значений, изменение этих данных приведет к ложным результатам. Если при построении kd-дерева указано copy data=True, данные также копируются.
- Leafsize(positive int): Сколько раз алгоритм обращается к методам грубой силы. Стандарт: 10.
- Compact_nodes(boolean): в этом случае гиперпрямоугольники сжимаются, чтобы соответствовать диапазону данных kd-дерева. За счет более длительного времени сборки обычно получается более компактное дерево, устойчивое к повреждению входных данных и обеспечивающее более быстрые запросы. Как правило, да.
- copy_data(boolean): если True, данные всегда реплицируются для защиты от повреждения данных и защиты дерева kd. Ложь по умолчанию.
- Balance_tree(boolean): в этом случае гиперпрямоугольники делятся по медиане, а не по средней точке. Обычно компромиссом в пользу более длительного времени сборки является более компактное дерево и более быстрые запросы. Как правило, да.
- boxsize(scalar, array_data): придайте KDTree тороидальную топологию md. Топология создается по формуле, где L i — размер коробки по i-му измерению, а ni — целые числа. Входные данные должны быть заключены в [0, Li]. Если какие-либо данные выходят за пределы этой границы, возникает ошибка ValueError.
Метод query_ball_tree()
Python Scipy содержит метод query_ball_tree() в модуле scipy.spatial..KDTree, который находит каждую пару точек между собой и другим объектом, расстояние между которыми не превышает r.
Синтаксис:
KDTree.query_ball_tree(other, r, p=1.0, eps=1)
Где параметры:
- other(экземпляр KDTree): дерево, содержащее точки поиска.
- r(float): максимальное расстояние должно быть положительным.
- p(float): какую норму Минковского использовать. Ограничению 1 = p < бесконечность должно соответствовать p.
- eps(неотрицательное число с плавающей запятой): предполагаемый поиск. Ветви дерева не проверяются, если их ближайшие точки находятся на расстоянии более чем r/(1 + eps), и добавляются массово, если они находятся ближе, чем r *(1 + eps).
Метод query_ball_tree() возвращает результат типа list of list, где возвращает results[i] — список индексов соседей в Other.data для каждого элемента этого дерева с префиксом self.data[i].
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
import numpy as np import matplotlib.pyplot as plt from scipy import spatial
Сгенерируйте точки данных, используя генератор случайных чисел, как показано в приведенном ниже коде.
rnd_gen = np.random.default_rng() pts = rnd_gen.random((20, 3)) pts2 = rnd_gen.random((20,3))
Передайте точки в kdtrees и найдите все пары точек на расстоянии r в kd-дереве, используя приведенный ниже код.
kdtree = spatial.KDTree(pts) kdtree2 = spatial.KDTree(pts2) idx = kdtree.query_ball_tree(kdtree2, r=0.3)
Постройте пары, используя приведенный ниже код.
plt.figure(figsize=(5, 5))
plt.plot(pts[:, 0], pts[:, 1], "xk", markersize=14)
plt.plot(pts2[:, 0], pts2[:, 1], "og", markersize=14)
for i in range(len(idx)):
for j in idx[i]:
plt.plot([pts[i, 0], pts2[j, 0]],
[pts[i, 1], pts2[j, 1]], "-r")
plt.show()
Метод count_neighbors()
Метод count_neighbors() Python Scipy, который существует в модуле scipy.spatial, подсчитывает количество пар, которые могут образоваться поблизости.
Подсчитайте количество пар(x1, x2), которые можно составить, где расстояние(x1, x2, p) = r и где x1 взят из себя, а x2 взят из другого.
Синтаксис:
KDTree.count_neighbors(other, r, p=1.0, weights=None, cumulative=False)
Где параметры:
- other(KDTree): второе дерево, из которого должны быть получены точки, может быть само первым деревом.
- r(float, 1d float): радиус, в пределах которого вычисляется счетчик. Один обход дерева используется для поиска по многим радиусам. R определяет границы интервалов и не должен уменьшаться, если счетчик не является накопительным(кумулятивный = False).
- p(с плавающей запятой): 1<=p<=бесконечность. используя какую p-норму Минковского. Стандарт 2.0. Если переполнение возможно, конечное большое значение p может привести к ошибке ValueError.
- Weights(array_data, tuple array): подсчет пар не имеет веса, если None. Веса точек в одном и веса точек в другом, если они представлены в виде кортежа, равны весам[0] и весам[1 соответственно].
- cumulative(boolean): являются ли возвращаемые значения накопительными. Процедура оптимизирована для работы с большим количеством интервалов(>10), обозначенных r, когда для кумулятивного параметра установлено значение False. Метод настроен для работы с ограниченным числом r, когда для параметра cumulative установлено значение True. По умолчанию: Истина
Метод count_neighbors() возвращает результат скалярного типа или одномерный массив, который представляет собой количество пар. Результатом невзвешенного подсчета является целое число. Результатом взвешенного подсчета является число с плавающей запятой. Result[i] содержит числа с(-inf if I == 0 else r[i-1]), если совокупное значение равно False. < R <= r[i].
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
import numpy as np import matplotlib.pyplot as plt from scipy import spatial
Сгенерируйте точки данных, используя генератор случайных чисел, как показано в приведенном ниже коде.
rnd_gen = np.random.default_rng() pts = rnd_gen.random((10, 2)) pts2 = rnd_gen.random((10,2))
Передайте точки в kdtrees и между двумя kd-деревьями рассчитайте количество соседних соседей, используя приведенный ниже код.
kdtree = spatial.KDTree(pts) kdtree2 = spatial.KDTree(pts2) kdtree.count_neighbors(kdtree2, r=0.3)
Метод count_neighbors()
Метод sparse_distance_matrix модуля scipy.spatial.KDTree в Python Scipy вычисляет матрицу расстояний между двумя KDTrees, оставляя любые расстояния, превышающие максимальное расстояние, равными 0.
Синтаксис:
KDTree.sparse_distance_matrix(other, max_distance, p=1.0, output_type='coo_matrix')
Где параметры:
- other: это KDTree.
- max_distance(положительное число с плавающей запятой): используется для указания максимального расстояния.
- p(с плавающей запятой): 1<=p<=бесконечность. используя какую p-норму Минковского. Если переполнение возможно, конечное большое значение p может привести к ошибке ValueError.
- output_type(string): какой контейнер выходных данных использовать. Возможные варианты: «ndarray», «dict», «cooматрица». и «матрица документа», по умолчанию используется «матрица документа».
Метод sparse_distance_matrix() возвращает результат, который представляет собой разреженную матрицу, отображающую результаты в виде «словаря ключей». Ключами возвращаемого словаря являются(i,j) кортежи индексов. Массив записей с полями I «j» и «v» возвращается, если тип вывода — «ndarray».
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
import numpy as np import matplotlib.pyplot as plt from scipy import spatial
Сгенерируйте точки данных, используя генератор случайных чисел, как показано в приведенном ниже коде.
rnd_gen = np.random.default_rng() pts = rnd_gen.random((10, 4)) pts2 = rnd_gen.random((10,4))
Передайте точки в kdtrees и между двумя kd-деревьями вычислите разреженную матрицу расстояний. используя приведенный ниже код.
kdtree = spatial.KDTree(pts) kdtree2 = spatial.KDTree(pts2) kdtree.sparse_distance_matrix(kdtree2,0.4).toarray()
Сравнение Kdtree и ckdtree
Согласно самой последней (v1.8) документации SciPy, функционально эквивалентный scipy.spatial.KDTree занял место устаревшего scipy.spatial.cKDTree.
cKDTree по сути эквивалентен KDTree. До SciPy v1.6.0 cKDTree предлагал превосходную производительность и слегка отличающуюся функциональность, но сегодня эти два названия существуют в первую очередь из соображений обратной совместимости. Если совместимость с SciPy < 1.6 не является проблемой, отдайте предпочтение KDTree.
Параметры
Метод KDTree принимает параметр Leafsize, который определяет, сколько раз алгоритм обращается к методам грубой силы, по умолчанию это 10. В зависимости от Leafsize метод возвращает разные результаты.
Импортируйте необходимые библиотеки, используя приведенный ниже код.
from scipy import spatial import numpy as np
Сгенерируйте точки данных с помощью метода np.random.rand() и передайте точки данных в два kdtree с размером листьев для одного дерева, равным 20, а для другого — 10.
points = np.random.rand(20,3) Tree1 = spatial.KDTree(points, leafsize=20) Tree2 = spatial.KDTree(points, leafsize=10)
Найдите все точки на расстоянии 0,2 от точки 0,4 для обоих деревьев, используя приведенный ниже код.
neighbors_1= Tree1.query_ball_point((0.4,0.3,0.2), r=2.0) neighbors_2= Tree2.query_ball_point((0.4,0.3,0.2), r=2.0)
Проверьте результат, используя приведенный ниже код.
print(neighbors_1) print(neighbors_2)
Производительность
Импортируйте необходимые библиотеки, используя приведенный ниже код Python.
from scipy.spatial import KDTree, cKDTree from itertools import combinations from scipy.spatial.distance import cdist import time import numpy
Создайте точки данных, используя приведенный ниже код.
points = [numpy.random.randn(100,2) for x in range(100)]
Используйте ckdtree, чтобы найти все точки, используя метод query_ball_points, а также время, затрачиваемое этим методом, с использованием приведенного ниже кода.
start = time.time()
c_trees = [cKDTree(x) for x in points]
for c_p1, c_p2 in combinations(c_trees,2):
c_p1.query_ball_tree(c_p2,0.5,eps=1)
print("Time taken by ckdtree",time.time() - start)
Снова тот же код с kdtree, используя приведенный ниже код.
start = time.time()
kd_trees = [KDTree(x) for x in points]
for k_p1, k_p2 in combinations(kd_trees,2):
k_p1.query_ball_tree(k_p2,0.5,eps=1)
print("Time taken by kdtree",time.time() - start)
