Capire "leafsize" in scipy.spatial.KDTree

Question

Dichiarazione problema:

Ho 150k punti in uno spazio 3D con le loro coordinate memorizzate in una matrice con dimensione [150k, 3] in mm.

Voglio trovare tutti i vicini di un dato punto pche si trovano entro un raggio r. E voglio farlo nel modo più accurato.

Come devo scegliere il mio leafsizeparametro?

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 funzione query_ball_pointrestituirà il set di punti corretto per qualsiasi versione dell'albero di ricerca. Il leafsizeparametro non influisce sui risultati della query, ma solo sulle prestazioni dei risultati.

Immagina due alberi mostrati di seguito per gli stessi dati (ma diversi parametri di dimensione foglia) e una query che cerca tutti i punti all'interno del cerchio rosso.

In entrambi i casi, il codice restituirà solo i due punti che si trovano all'interno del cerchio rosso. Questo viene fatto controllando tutti i punti in tutte le caselle dell'albero che intersecano il cerchio. Questo porta a una diversa quantità di lavoro (cioè, prestazioni diverse) in ogni caso. Per l'albero di sinistra (corrispondente a una dimensione foglia più grande), l'algoritmo deve controllare se 13 punti sono all'interno del cerchio (6 nel riquadro intersecante superiore e 7 nel riquadro intersecante inferiore). Nell'albero di destra (che ha una dimensione foglia più piccola), vengono elaborati solo tre punti (uno nel riquadro intersecante superiore e due nel riquadro intersecante inferiore).

Seguendo questa logica, potresti pensare che abbia senso usare sempre una dimensione foglia piccola: questo ridurrà al minimo il numero di confronti effettivi alla fine dell'algoritmo (decidi se i punti si trovano effettivamente nella regione della query). Ma non è così semplice: la dimensione della foglia più piccola genererà un albero più profondo, aggiungendo costi al tempo di costruzione e al tempo di attraversamento dell'albero. Ottenere il giusto equilibrio tra le prestazioni di attraversamento dell'albero con i confronti a livello foglia dipende in realtà dal tipo di dati che entrano nell'albero e dai confronti specifici a livello foglia che stai facendo. Questo è il motivo per cui scipy fornisce il parametro leafsize come argomento in modo da poter regolare le cose per funzionare al meglio su un particolare algoritmo.