Memahami `leafsize` di scipy.spatial.KDTree

Question

Pernyataan masalah:

Saya memiliki 150k titik dalam ruang 3D dengan koordinatnya disimpan dalam matriks dengan dimensi [150k, 3] dalam mm.

Saya ingin mencari semua tetangga dari titik tertentu pyang berada dalam radius r. Dan saya ingin melakukannya dengan cara yang paling akurat.

Bagaimana cara memilih leafsizeparameter saya ?

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

Fungsi ini query_ball_pointakan mengembalikan kumpulan titik yang benar untuk versi apapun dari pohon pencarian. The leafsizeparameter tidak mempengaruhi hasil query, hanya kinerja hasil.

Bayangkan dua pohon yang ditampilkan di bawah ini untuk data yang sama (tetapi parameter ukuran daun berbeda) dan kueri yang mencari semua titik di dalam lingkaran merah.

Dalam kedua kasus, kode hanya akan mengembalikan dua titik yang berada di dalam lingkaran merah. Ini dilakukan dengan mencentang semua titik di semua kotak pohon yang memotong lingkaran. Ini mengarah ke jumlah pekerjaan yang berbeda (yaitu, kinerja yang berbeda) dalam setiap kasus. Untuk pohon kiri (sesuai dengan ukuran daun yang lebih besar), algoritme harus memeriksa apakah 13 titik berada di dalam lingkaran (6 di kotak berpotongan atas dan 7 di kotak berpotongan bawah). Di pohon kanan (yang memiliki ukuran daun lebih kecil), hanya tiga titik yang diproses (satu di kotak berpotongan atas dan dua di kotak berpotongan bawah).

Mengikuti logika ini, Anda mungkin berpikir masuk akal untuk selalu menggunakan ukuran daun kecil: ini akan meminimalkan jumlah perbandingan aktual di akhir algoritme (putuskan apakah titik benar-benar terletak di wilayah kueri). Tetapi tidak sesederhana itu: ukuran daun yang lebih kecil akan menghasilkan biaya tambahan pohon yang lebih dalam pada waktu konstruksi dan waktu traversal pohon. Mendapatkan keseimbangan yang tepat antara kinerja penjelajahan pohon dengan perbandingan tingkat daun sangat bergantung pada jenis data yang masuk ke pohon dan perbandingan tingkat daun tertentu yang Anda lakukan. Itulah sebabnya scipy menyediakan parameter ukuran daun sebagai argumen sehingga Anda dapat menyetel hal-hal agar berkinerja terbaik pada algoritme tertentu.