2
$\begingroup$

The kd-tree implementation proposed by the scipy python libray asks for the value of the leafsize parameter that is to say the maximum number of points a node can hold. It is by default set to 10.

Are there methods or ways to estimate the value of the leafsize parameter to better distribute the data and avoid having leaves nodes with a single point?

https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html

scipy.spatial.KDTree(data, leafsize=10)
#The number of points at which the algorithm switches over to brute-force. Has to be positive.
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

With this setting of 10, you should never have a leaf with a single point, unless your data set consists of exactly one point.

Because the splits are balanced in size, the previous level must have at more than 10 points. So the minimum size is 5, if you set the maximum to 10 (except if there are less than 5 data points total).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I experienced the scipy kd-tree with leafsize set to 10 but it contains leaves with one point. The dataset contains 10000 points generated with make_blobs (function implemenetd in sklearn.datasets.samples_generator) $\endgroup$
    – curiosus
    Commented Feb 10, 2019 at 14:29
  • $\begingroup$ Then it wasn't split at a midpoint? $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Feb 11, 2019 at 1:56
  • $\begingroup$ Yes it uses the midpoint. Maybe it is faster than median. $\endgroup$
    – curiosus
    Commented Mar 22, 2019 at 16:52
  • $\begingroup$ Well, with midpoint split the tree depth is O(n) in the worst case (unbalanced, degenerated to a linear chain), so it certainly can't have a better complexity guarantee. On such data, you'll have plenty of leaves with just 1 point. So you can't estimate this value either. Consider the data set of powers of 2: 2^i for i integer. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Mar 22, 2019 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.