Est-il possible de trouver le KNN pour un nœud qui est * IN * l'arbre KD?

Question

Essayer de créer une recherche KNN à l'aide d'un arbre KD. Je peux former le KD-tree bien (ou du moins, je crois que je peux!). Mon problème est que je cherche à trouver les 2 voisins les plus proches de chaque point dans une liste de points. Donc, y at-il une méthode pour trouver les K voisins les plus proches d'un point en utilisant un arbre KD même si le point est réellement dans l'arbre, ou ai-je besoin de construire un arbre KD séparé pour chaque point, en laissant de côté point que je souhaite rechercher?

Mon langage d'implémentation est C++, mais je suis plus à la recherche d'un algorithme ou d'une aide générale, merci!

Merci, Stephen

Answer 1

Si vous voulez que les Kexactes plus proches voisins dans votre arbre, l'arbre juste requête pour K + 1 voisins (évidemment depuis le premier voisin le plus proche sera votre requête).

Answer 2

Ce n'est pas vraiment beaucoup d'une réponse, mais je ne peux pas répondre à ce que je veux coller dans un commentaire. De toute façon, voici le texte pertinent de Wikipedia:

L'algorithme peut être étendu en de plusieurs manières par de simples modifications. Il peut fournir les k-plus proches voisins à un point en maintenant k actuel meilleurs au lieu d'un seul. Les branches sont seulement éliminées lorsqu'elles ne peuvent pas avoir des points plus proches que n'importe lequel des k meilleurs résultats actuels.

Il peut également être converti en un algorithme d'approximation pour s'exécuter plus rapidement. Par exemple, la recherche du plus proche voisin approximative peut être atteint par simple réglage d'une limite supérieure sur les points de nombre d'examiner dans l'arbre, ou en interrompant le processus de recherche basé sur une horloge en temps réel (qui peut être plus approprié dans les implémentations matérielles ). Le plus proche voisin pour les points qui sont dans l'arbre peut déjà être atteint en ne mise à jour du raffinement des nœuds qui donnent zéro distance que le résultat, ce a l'inconvénient de points en rejetant qui ne sont pas uniques, mais sont co -localisé avec la recherche originale point.

voisin le plus proche approximatif est utile dans les applications en temps réel telles que la robotique en raison de la vitesse importante augmentation acquise par la recherche de ne pas le meilleur point de manière exhaustive. L'un des implémentations est Best Bin First.

Answer 3

je recommande de jeter un oeil à ANN pour les détails de mise en œuvre http://www.cs.umd.edu/~mount/ANN/

Il est conçu pour les recherches les plus proches voisins approximatives, mais peut également faire des recherches les plus proches voisins exacte. C'est aussi un des codes les plus clairs et les mieux écrits que j'ai jamais trouvé, et je vous donnerais un aperçu même si vous voulez votre propre implémentation.