meaning of 'leaf_size', 'n_leaves' and 'n_calls'?

[pixar0407]

Hello, I have a question about hi-dimension dataset on KDTree.

I am using 'KDTree' from sklearn.neighbors.
After i build the tree and i give query to this tree.
It works fine.

But, I am confused with the parameters.
here is the code for my experiment.

import numpy as np
from sklearn.neighbors import KDTree
from sklearn.metrics.pairwise import euclidean_distances as pd

rng = np.random.RandomState(0)
X = rng.random_sample((1024, 128)) # 1024 points in 32 dimensions

n = 100 # query's the 100th point.
query = X[n-1:n]

tree = KDTree(X, leaf_size=1)
dist, ind = tree.query(query, k=1)

print('Kd answer :',ind) # indices of 1 closest neighbors
print(dist) # distances to 1 closest neighbors

ans=tree.getstate()
print('neighbors',neighbor)
print('leaf size',ans[4])
print('n_levels',ans[5])
print('n_nodes',ans[6])
print('n_trims',ans[7])
print('n_leaves',ans[8])
print('n_splits',ans[9])
print('n_calls',ans[10])

This gives below.

leaf size 1
...
n_trims 9
n_leaves 1
n_splits 9
n_calls 2

In the 'https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/neighbors/_binary_tree.pxi', there is '_query_single_depthfirst'. This says that if the tree hits the leaf node, it does 'n_leaves += 1' and does the 'self.rdist'. And whenever the tree does the 'self.rdist', it does 'n_calls += 1'.

So, i thought that each leaf node has leaf_size numbers of points(i.e, if leaf_size is 128, then each leaf node has 128 points). So, n_calls = leaf_size * n_leaves. But it is not.

It seems that n_calls is 2 * leaf_size * n_leaves. This means that each leaf node has 2 * leaf_size numbers of points. This makes me confused.

Do i mis-understand the meaning of leaf_size in kd_tree?

[i-aki-y]

Although I am not familiar with kdtree, I will try to answer your question from the source code.

In the 'https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/neighbors/_binary_tree.pxi', there is '_query_single_depthfirst'. This says that if the tree hits the leaf node, it does 'n_leaves += 1' and does the 'self.rdist'. And whenever the tree does the 'self.rdist', it does 'n_calls += 1'.

This self.rdist() is located inside a for-loop.

for i in range(node_info.idx_start, node_info.idx_end):
    dist_pt = self.rdist(pt,
                            &self.data[self.idx_array[i], 0],
                            self.data.shape[1])

In this case, each leaf node has two points (idx_end - idx_start == 2).
This means the rdist() is called twice per leaf node and you get n_calls = 2 * n_leaves here.

you can see node info by following way:

for i in range(tree.node_data.shape[0]):
    info = tree.node_data[i]
    if info["is_leaf"] == 1:
        print(info)
        break

> {'idx_start': 0, 'idx_end': 2, 'is_leaf': 1, 'radius': 2.432875397014594}

So, i thought that each leaf node has leaf_size numbers of points(i.e, if leaf_size is 128, then each leaf node has 128 points). So, n_calls = leaf_size * n_leaves. But it is not.
It seems that n_calls is 2 * leaf_size * n_leaves. This means that each leaf node has 2 * leaf_size numbers of points. This makes me confused.

The leaf_size is used to estimate the number of levels in the tree, not used to determine the number of points of the leaf nodes directly.
You can see this in the __init__() of _binary_tree.pxi:

    # determine number of levels in the tree, and from this
    # the number of nodes in the tree.  This results in leaf nodes
    # with numbers of points between leaf_size and 2 * leaf_size
    self.n_levels = int(
        np.log2(fmax(1, (n_samples - 1) / self.leaf_size)) + 1)
    self.n_nodes = (2 ** self.n_levels) - 1

From the number of levels, we can estimate the number of the leaf node.
And the number of points for each leaf node is roughly estimated by {number of samples} / {number of leaf nodes}.
Of course, there are cases where the sample number is not divisible, in which case the number of points will vary over the leaf nodes.
Actually, the number of points is determined in _recursive_build() function.