KD Tree: significado del parámetro `leafsize`
Estoy viendo la implementación de KD Tree de SciPy . Estoy confundido por el leafsizeparámetro, que se dice que es
El número de puntos en los que el algoritmo cambia a fuerza bruta. Predeterminado: 16.
¿Es este el número de hojas en el BST? Si es así, eso significa que, por defecto, el árbol KD no contendrá más de 32 puntos. Esto parece irracionalmente pequeño, especialmente para mi caso de uso de k = 2. ¿Estoy interpretando el parámetro incorrectamente?
Respuestas
El parámetro leafsizeno controla el número máximo de hojas en el árbol (que no está acotado), sino más bien el número de puntos de entrada asociados con una sola hoja en el árbol. Considere la posibilidad de agregar 64 puntos a un árbol. Si cada punto se asocia con una sola hoja, obtendrá un árbol completo que tiene siete niveles de profundidad y cualquier procesamiento que requiera un punto descenderá por estos siete niveles para encontrarlo. Alternativamente, si el tamaño de la hoja es 16, obtendrá un árbol que tiene solo 3 niveles de profundidad y cada hoja del árbol está asociada con 16 puntos. Procesar un punto implica descender tres niveles del árbol y luego probar cada uno de los 16 puntos de la hoja (ya que están desordenados). Este valor se puede ajustar para el rendimiento y, empíricamente, el mejor valor depende de cómo se utilice exactamente el árbol.
Conceptualmente, aquí hay un ejemplo de los árboles que se construirían para diferentes leafsizevalores.
Puede ver cómo el leafsizeparámetro cortocircuita el proceso de construcción del árbol en el código fuente de scipy . Esto dejará entre leafsize/2y leafsizepuntos desordenados en las hojas del árbol.