Árvore KD: significado do parâmetro `leafsize`

Question

Estou olhando para a implementação da árvore KD do SciPy . Estou confuso com o leafsizeparâmetro, que se diz ser

O número de pontos em que o algoritmo muda para força bruta. Padrão: 16.

É esse o número de licenças no BST? Nesse caso, isso significa que, por padrão, a árvore KD não conterá mais do que 32 pontos. Isso parece excessivamente pequeno, especialmente para o meu caso de uso de k = 2. Estou interpretando o parâmetro incorretamente?

Answer 1

O parâmetro leafsizenão controla o número máximo de folhas na árvore (que não é limitado), mas sim o número de pontos de entrada associados a uma única folha na árvore. Considere 64 pontos sendo adicionados a uma árvore. Se cada ponto for associado a uma única folha, você obterá uma árvore completa com sete níveis de profundidade e qualquer processamento que requeira um ponto descerá esses sete níveis para encontrá-lo. Alternativamente, se o tamanho da folha for 16, você obterá uma árvore com apenas 3 níveis de profundidade e cada folha da árvore está associada a 16 pontos. O processamento de um ponto envolve descer três níveis da árvore e, em seguida, testar cada um dos 16 pontos na folha (uma vez que não estão ordenados). Esse valor pode ser ajustado para desempenho e, empiricamente, o melhor valor depende de como exatamente a árvore está sendo usada.

Conceitualmente, aqui está um exemplo das árvores que seriam construídas para leafsizevalores diferentes .

Você pode ver como o leafsizeparâmetro causa um curto-circuito no processo de construção da árvore no código-fonte do scipy . Isso deixará os pontos intermediários leafsize/2e leafsizedesordenados nas folhas da árvore.