Compreendendo `leafsize` em scipy.spatial.KDTree

Question

Declaração do problema:

Tenho 150k pontos em um espaço 3D com suas coordenadas armazenadas em uma matriz com dimensão [150k, 3] em mm.

Quero encontrar todos os vizinhos de um determinado ponto pque estão dentro de um raio r. E eu quero fazer isso da maneira mais precisa.

Como devo escolher meu 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

A função query_ball_pointretornará o conjunto correto de pontos para qualquer versão da árvore de pesquisa. O leafsizeparâmetro não afeta os resultados da consulta, apenas o desempenho dos resultados.

Imagine duas árvores mostradas abaixo para os mesmos dados (mas parâmetros de tamanho de folha diferentes) e uma consulta procurando por todos os pontos dentro do círculo vermelho.

Em ambos os casos, o código retornará apenas os dois pontos que estão dentro do círculo vermelho. Isso é feito marcando todos os pontos em todas as caixas da árvore que cruzam o círculo. Isso leva a uma quantidade diferente de trabalho (ou seja, desempenho diferente) em cada caso. Para a árvore da esquerda (correspondendo a um tamanho maior da folha), o algoritmo deve verificar se 13 pontos estão dentro do círculo (6 na caixa de intersecção superior e 7 na caixa de intersecção inferior). Na árvore certa (que tem um tamanho de folha menor), apenas três pontos são processados ​​(um na caixa de intersecção superior e dois na caixa de intersecção inferior).

Seguindo essa lógica, você pode pensar que faz sentido sempre usar um tamanho de folha pequeno: isso minimizará o número de comparações reais no final do algoritmo (decida se os pontos realmente estão na região de consulta). Mas não é tão simples: o tamanho menor da folha irá gerar uma árvore mais profunda, adicionando custo ao tempo de construção e ao tempo de travessia da árvore. Obter o equilíbrio certo de desempenho de travessia de árvore com as comparações de nível de folha realmente depende do tipo de dados que vai para a árvore e das comparações de nível de folha específicas que você está fazendo. É por isso que o scipy fornece o parâmetro leafsize como um argumento para que você possa ajustar as coisas para ter o melhor desempenho em um determinado algoritmo.