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.
kc'est effectivement la dimension du problème et qu'il souffre donc de la «malédiction de la dimensionnalité».Réponses:
kNN a tendance à être exponentiel car l'espace de recherche augmente avec2k . 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é).
la source