Блог

Постановка задачи:

У меня есть 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 в качестве аргумента, чтобы вы могли настроить параметры для наилучшей работы в конкретном алгоритме.