Pourquoi l'exponentielle de voisin le plus proche basée sur KD-Tree est-elle dans K?

9

J'ai lu dans de nombreux articles sur la recherche du plus proche voisin de dimension supérieure que les arbres KD sont exponentiels en K, mais je n'arrive pas à déterminer pourquoi.

Ce que je recherche, c'est une solide analyse de complexité d'exécution qui explique cet aspect du problème.

akdom
la source
La pensée rapide est que kc'est effectivement la dimension du problème et qu'il souffre donc de la «malédiction de la dimensionnalité».
Michael Klein

Réponses:

1

kNN a tendance à être exponentiel car l'espace de recherche augmente avec 2k. Imaginez que vous partitionnez l'espace autour de votre point de recherche en quadrants. Pour k = 1, il suffit de rechercher deux «quadrants» (valeurs supérieures et inférieures), pour k = 2, c'est 4 quadrants, pour k = 3, c'est 8 quadrants, c'est-à-dire une croissance exponentielle de l'espace de recherche. C'est ce dont souffre l'arbre kD, car il doit chercher2k sous-branches.

D'autres arbres fonctionnent beaucoup mieux, par exemple le CoverTree . J'ai également constaté que le PH-Tree fonctionne assez bien, il semble toujours prendre deux fois plus de temps que le CoverTree pour les jeux de données entre k = 8 et k = 27 (je n'avais pas de jeux de données avec un k plus élevé).

TilmannZ
la source
Notez que vous pouvez utiliser LaTeX ici pour composer les mathématiques d'une manière plus lisible. Voir ici pour une courte introduction.
Raphael