Entendiendo `leafsize` en scipy.spatial.KDTree

Question

Planteamiento del problema:

Tengo 150k puntos en un espacio 3D con sus coordenadas almacenadas en una matriz con dimensión [150k, 3] en mm.

Quiero encontrar todos los vecinos de un punto dado pque estén dentro de un radio r. Y quiero hacerlo de la manera más precisa.

¿Cómo debo elegir mi leafsizeparámetro?

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

Answer 1

La función query_ball_pointdevolverá el conjunto correcto de puntos para cualquier versión del árbol de búsqueda. El leafsizeparámetro no afecta los resultados de la consulta, solo el rendimiento de los resultados.

Imagine dos árboles que se muestran a continuación para los mismos datos (pero diferentes parámetros de tamaño de hoja) y una consulta que busca todos los puntos dentro del círculo rojo.

En ambos casos, el código solo devolverá los dos puntos que se encuentran dentro del círculo rojo. Esto se hace marcando todos los puntos en todas las casillas del árbol que se cruzan con el círculo. Esto conduce a una cantidad de trabajo diferente (es decir, un rendimiento diferente) en cada caso. Para el árbol de la izquierda (correspondiente a un tamaño de hoja más grande), el algoritmo tiene que comprobar si hay 13 puntos dentro del círculo (6 en el cuadro de intersección superior y 7 en el cuadro de intersección inferior). En el árbol de la derecha (que tiene un tamaño de hoja más pequeño), solo se procesan tres puntos (uno en el cuadro de intersección superior y dos en el cuadro de intersección inferior).

Siguiendo esta lógica, puede pensar que tiene sentido usar siempre un tamaño de hoja pequeño: esto minimizará el número de comparaciones reales al final del algoritmo (decida si los puntos realmente se encuentran en la región de consulta). Pero no es tan simple: el tamaño de hoja más pequeño generará un árbol más profundo, lo que aumentará el costo del tiempo de construcción y el tiempo de recorrido del árbol. Lograr el equilibrio adecuado entre el rendimiento transversal del árbol con las comparaciones a nivel de hoja realmente depende del tipo de datos que ingresan al árbol y las comparaciones específicas a nivel de hoja que está haciendo. Es por eso que scipy proporciona el parámetro leafsize como argumento para que pueda ajustar las cosas para que funcionen mejor en un algoritmo particular.