Понимание `leafsize` в scipy.spatial.KDTree
Постановка задачи:
У меня есть 150 тыс. Точек в трехмерном пространстве, координаты которых хранятся в матрице с размером [150 тыс., 3] в мм.
Я хочу найти всех соседей данной точки p, находящихся в пределах радиуса r. И я хочу сделать это максимально аккуратно.
Как мне выбрать свой leafsizeпараметр?
from scipy.spatial import KDTree
import numpy as np
pts = np.random.rand(150000,3)
T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)
neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)
np.allclose(sorted(neighbors1), sorted(neighbors2))
True
Ответы
Функция query_ball_pointвернет правильный набор точек для любой версии дерева поиска. leafsizeПараметр не влияет на результаты запроса, только при выполнении результатов.
Представьте себе два дерева, показанных ниже, для одних и тех же данных (но с разными параметрами размера листа) и запрос, ищущий все точки внутри красного круга.
В обоих случаях код вернет только две точки, лежащие внутри красного круга. Это делается путем проверки всех точек во всех квадратах дерева, пересекающих круг. Это приводит к разному объему работы (т. Е. Разной производительности) в каждом случае. Для левого дерева (соответствующего большему размеру листа) алгоритм должен проверить, находятся ли 13 точек внутри круга (6 в верхнем поле пересечения и 7 в нижнем поле пересечения). В правом дереве (которое имеет меньший размер листа) обрабатываются только три точки (одна в верхнем поле пересечения и две в нижнем поле пересечения).
Следуя этой логике, вы можете подумать, что имеет смысл всегда использовать небольшой размер листа: это минимизирует количество фактических сравнений в конце алгоритма (решите, действительно ли точки лежат в области запроса). Но это не так просто: меньший размер листа приведет к созданию более глубокого дерева, увеличивая затраты на время построения и время обхода дерева. Получение правильного баланса между производительностью обхода дерева и сравнениями конечного уровня действительно зависит от типа данных, поступающих в дерево, и конкретных сравнений конечного уровня, которые вы выполняете. Вот почему scipy предоставляет параметр leafsize в качестве аргумента, чтобы вы могли настроить вещи так, чтобы они лучше работали на конкретном алгоритме.