KD Tree: arti parameter `ukuran daun`

Question

Saya melihat implementasi KD Tree dari SciPy . Saya bingung dengan leafsizeparameter yang dikatakan

Jumlah titik di mana algoritme beralih ke gaya brute force. Default: 16.

Apakah ini jumlah daun di BST? Jika demikian, itu berarti secara default, pohon KD akan berisi tidak lebih dari 32 poin. Ini tampaknya terlalu kecil, terutama untuk kasus penggunaan k = 2 saya. Apakah saya salah menafsirkan parameter?

Answer 1

Parameter leafsizetidak mengontrol jumlah maksimum daun di pohon (yang tidak dibatasi), melainkan jumlah titik masukan yang terkait dengan satu daun di pohon. Pertimbangkan 64 poin yang ditambahkan ke pohon. Jika setiap titik dikaitkan dengan satu daun, Anda akan mendapatkan pohon penuh dengan kedalaman tujuh tingkat dan setiap pemrosesan yang memerlukan titik akan turun ke tujuh tingkat ini untuk menemukannya. Sebagai alternatif, jika ukuran daunnya 16, Anda akan mendapatkan pohon yang hanya sedalam 3 tingkat dan setiap daun di pohon dikaitkan dengan 16 titik. Pemrosesan titik melibatkan penurunan tiga tingkat pohon dan kemudian menguji masing-masing dari 16 titik di daun (karena tidak berurutan). Nilai ini dapat disetel untuk kinerja, dan secara empiris, nilai terbaik bergantung pada bagaimana tepatnya pohon itu digunakan.

Secara konseptual, berikut adalah contoh pohon yang akan dibangun untuk leafsizenilai yang berbeda .

Anda dapat melihat bagaimana leafsizeparameter melakukan short-circuit proses pembangunan pohon di kode sumber scipy . Ini akan meninggalkan titik di antara leafsize/2dan leafsizetidak teratur di daun pohon.