scipy.spatial.KDTreeの `leafsize`を理解する
問題文：
3D空間に150kの点があり、それらの座標はmm単位の次元[150k、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パラメータは、結果の唯一のパフォーマンスをクエリの結果に影響を与えません。
以下に示す2つのツリーで、同じデータ（ただし、リーフサイズパラメーターが異なる）と、赤い円内のすべてのポイントを検索するクエリを想像してみてください。
どちらの場合も、コードは赤い円の内側にある2つのポイントのみを返します。これは、円と交差するツリーのすべてのボックス内のすべてのポイントをチェックすることによって行われます。これにより、それぞれの場合で作業量が異なります（つまり、パフォーマンスが異なります）。左側のツリー（より大きなリーフサイズに対応）の場合、アルゴリズムは13個のポイントが円の内側にあるかどうかをチェックする必要があります（上部の交差ボックスに6個、下部の交差ボックスに7個）。右側のツリー（葉のサイズが小さい）では、3つのポイントのみが処理されます（1つは上部の交差ボックスに、2つは下部の交差ボックスにあります）。
このロジックに従うと、常に小さいリーフサイズを使用することが理にかなっていると思うかもしれません。これにより、アルゴリズムの最後で実際の比較の数が最小限に抑えられます（ポイントが実際にクエリ領域にあるかどうかを判断してください）。しかし、それはそれほど単純ではありません。葉のサイズが小さいほど、木が深くなり、建設時間と木の横断時間にコストがかかります。ツリートラバーサルパフォーマンスとリーフレベルの比較の適切なバランスをとることは、実際には、ツリーに入力されるデータのタイプと、実行している特定のリーフレベルの比較によって異なります。そのため、scipyはleafsizeパラメーターを引数として提供するため、特定のアルゴリズムで最高のパフォーマンスを発揮するように調整できます。