¿Por qué el vecino más cercano basado en KD-Tree es exponencial en K?

9

He leído en muchos artículos sobre búsqueda de vecinos más cercanos en dimensiones superiores que los árboles KD son exponenciales en K, pero parece que no puedo determinar por qué.

Lo que estoy buscando es un análisis sólido de complejidad de tiempo de ejecución que explique este aspecto del problema.

akdom
fuente
Pensar rápidamente es que kefectivamente es la dimensión del problema y por eso sufre la "maldición de la dimensionalidad".
Michael Klein

Respuestas:

1

kNN tiende a ser exponencial porque el espacio de búsqueda aumenta con . Imagine que divide el espacio alrededor de su punto de búsqueda en cuadrantes. Para k = 1 solo tiene que buscar dos 'cuadrantes' (valores más altos y más bajos), para k = 2 son 4 cuadrantes, para k = 3 son 8 cuadrantes, es decir, crecimiento exponencial del espacio de búsqueda. De eso sufre el árbol kD, porque tiene que buscar sub-ramas.2k2k

Otros árboles funcionan mucho mejor, por ejemplo el CoverTree . También descubrí que el PH-Tree funciona bastante bien, parece que siempre toma el doble de tiempo que el CoverTree para conjuntos de datos entre k = 8 yk = 27 (no tenía conjuntos de datos con k más alto).

TilmannZ
fuente
Tenga en cuenta que puede usar LaTeX aquí para componer las matemáticas de una manera más legible. Vea aquí para una breve introducción.
Raphael