KD Tree: значение параметра `leafsize`

Question

Я смотрю на реализацию SciPy KD Tree . Меня смущает leafsizeпараметр, который называется

Количество точек, в которых алгоритм переключается на брутфорс. По умолчанию: 16.

Это количество листьев в BST? Если это так, это означает, что по умолчанию дерево KD будет содержать не более 32 точек. Это кажется неоправданно маленьким, особенно для моего случая использования k = 2. Я неправильно интерпретирую параметр?

Answer 1

Параметр leafsizeне контролирует максимальное количество листьев в дереве (которое не ограничено), а скорее количество входных точек, связанных с одним листом в дереве. Представьте, что к дереву добавляются 64 точки. Если каждая точка будет связана с одним листом, вы получите полное дерево с семью уровнями глубины, и любая обработка, требующая точки, будет спускаться по этим семи уровням, чтобы найти ее. В качестве альтернативы, если размер листа равен 16, вы получите дерево глубиной всего 3 уровня, и каждый лист в дереве связан с 16 точками. Обработка точки включает спуск по трем уровням дерева и затем тестирование каждой из 16 точек в листе (поскольку они неупорядочены). Это значение можно настроить с учетом производительности, и эмпирически наилучшее значение зависит от того, как именно используется дерево.

По идее, вот пример деревьев, которые будут построены для разных leafsizeзначений.

Вы можете увидеть, как leafsizeпараметр сокращает процесс построения дерева в исходном коде scipy . Это оставит точки между leafsize/2и в leafsizeнеупорядоченном виде на листьях дерева.