plus proche voisin - arbre k-d - preuve wikipedia

Question

Sur le entrée wikipédia pour les arbres k-d L'article présente un algorithme permettant d'effectuer une recherche du plus proche voisin dans un arbre k-d. Il s'agit d'un algorithme de recherche de l'arbre. Ce que je ne comprends pas, c'est l'explication de l'étape 3.2. Comment savez-vous qu'il n'y a pas un point plus proche simplement parce que la différence entre la coordonnée de division du point de recherche et le nœud actuel est plus grande que la différence entre la coordonnée de division du point de recherche et le meilleur actuel ?

Recherche du plus proche voisin Animation de recherche de NN avec un arbre KD en 2D

L'algorithme du plus proche voisin (NN) vise à trouver le point de l'arbre qui est le plus proche d'un point d'entrée d'entrée. Cette recherche peut être effectuée efficacement en utilisant les propriétés propriétés de l'arbre pour éliminer rapidement parties de l'espace de recherche. La recherche d'un plus proche voisin dans un kd-tree se déroule comme suit :

1. En commençant par le nœud racine, l'algorithme se déplace vers le bas de l'arbre. récursivement, de la même façon qu'il le ferait qu'il le ferait si le point de recherche était de recherche (c'est-à-dire qu'il va vers la droite ou la gauche selon que le point est supérieur ou inférieur au nœud actuel dans la dimension partagée).
2. Une fois que l'algorithme atteint un nœud feuille, il enregistre ce point de nœud en tant que le "meilleur moment".
3. L'algorithme déroule la récursion de l'arbre, en effectuant les opérations suivantes les étapes suivantes à chaque nœud : 1. Si le noeud actuel est plus proche que le meilleur noeud actuel, alors il devient le noeud actuel. devient le meilleur actuel. 2. L'algorithme vérifie s'il existe des points sur les l'autre côté du plan de division qui sont plus proches du point de recherche que le meilleur point actuel. En théorie, cela se fait en croisant l'hyperplan de hyperplan de séparation avec une hypersphère autour du point de recherche dont le rayon est égal à la distance la plus proche. Puisque les hyperplans sont tous alignés sur l'axe est implémentée comme une simple comparaison pour voir si la différence entre la coordonnée de division du point de recherche et le nœud actuel est inférieure à la distance (coordonnées globales) entre le point de recherche et le nœud actuel meilleur. 1. Si l'hypersphère traverse le plan, il pourrait y avoir points plus proches de l'autre côté du plan plan, l'algorithme doit donc descendre l'autre branche de l'arbre à partir du nœud nœud actuel, à la recherche de points points plus proches, en suivant le même processus récursif que l'ensemble de la recherche. 2. Si l'hypersphère ne coupe pas le plan de séparation, alors l'algorithme continue de marcher l'arbre, et la branche entière sur de l'autre côté de ce noeud est éliminée.
4. Lorsque l'algorithme termine ce processus pour le nœud racine, alors l'indice recherche est terminée.

En général, l'algorithme utilise les carrés pour la comparaison afin d'éviter de calculer des racines carrées. De plus, il peut économiser des calculs en conservant la meilleure distance actuelle au carré dans une variable pour la comparaison.

Answer 1

Regardez attentivement la 6ème image de la animation sur cette page .

Comme l'algorithme remonte la récursion, il est possible qu'il y ait un point plus proche de l'autre côté de l'hyperplan sur lequel il se trouve. Nous avons vérifié une moitié, mais il pourrait y avoir un point encore plus proche sur l'autre moitié.

Eh bien, il s'avère que nous pouvons parfois faire une simplification. Si c'est impossible pour qu'il y ait un point sur l'autre moitié plus proche que notre meilleur point (le plus proche) actuel, alors nous pouvons sauter entièrement cette moitié d'hyperplan. Cette simplification est celle qui est montrée sur la 6ème image.

Pour déterminer si cette simplification est possible, on compare la distance entre l'hyperplan et le lieu de notre recherche. Comme l'hyperplan est aligné sur les axes, la ligne la plus courte entre lui et tout autre point est une ligne qui suit une dimension. Nous pouvons donc comparer uniquement la coordonnée de la dimension que l'hyperplan divise.

Si la distance entre le point de recherche et l'hyperplan est plus grande que celle entre le point de recherche et le point le plus proche, il n'y a aucune raison de chercher au-delà de cette coordonnée de séparation.

Même si mon explication ne vous aide pas, le graphique le fera. Bonne chance dans votre projet !

Answer 2

Oui, la description de la recherche NN (Nearest Neighbour) dans un arbre KD sur Wikipedia est un peu difficile à suivre. Cela n'aide pas qu'un lot des premiers résultats de la recherche Google sur l'arbre NN KD sont tout simplement faux !

Voici un peu de code C++ pour vous montrer comment le faire correctement :

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
    const const KDNode<T,N> &node,
    const std::array<T, N> &point, // looking for closest node to this point
    const KDPoint<T,N> &closest,   // closest node (so far)
    double &minDist,
    const uint depth) const
{
    if (node->isLeaf()) {
        const double dist = distance(point, node->leaf->point);
        if (dist < minDist) {
            minDist = dist;
            closest = node->leaf;
        }
    } else {
        const T dim = depth % N;
        if (point[dim] < node->splitVal) {
            // search left first
            nearest(node->left, point, closest, minDist, depth + 1);
            if (point[dim] + minDist >= node->splitVal)
                nearest(node->right, point, closest, minDist, depth + 1);
        } else {
            // search right first
            nearest(node->right, point, closest, minDist, depth + 1);
            if (point[dim] - minDist <= node->splitVal)
                nearest(node->left, point, closest, minDist, depth + 1);
        }
    }
}

API pour la recherche de NN sur un arbre KD :

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
    const KDPoint<T,N> closest;
    double minDist = std::numeric_limits<double>::max();
    nearest(root, point, closest, minDist);
    return closest;
}

Fonction de distance par défaut :

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
    double d = 0.0;
    for (uint i = 0; i < N; ++i) {
        d += pow(p1[i] - p2[i], 2.0);
    }
    return sqrt(d);
}

Edit : certaines personnes demandent de l'aide pour les structures de données aussi (pas seulement l'algorithme NN), donc voici ce que j'ai utilisé. En fonction de votre objectif, vous pouvez souhaiter modifier légèrement les structures de données. (Note : mais vous le ferez certainement no veulent modifier l'algorithme NN).

Classe KDPoint :

template <class T, std::size_t N>
class KDPoint {
    public:
        KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
        virtual ~KDPoint<T,N> () = default;
        std::array<T, N> point;
};

Classe KDNode :

template <class T, std::size_t N>
class KDNode
{
    public:
        KDNode () = delete;
        KDNode (const KDNode &) = delete;
        KDNode & operator = (const KDNode &) = delete;
        ~KDNode () = default;

        // branch node
        KDNode (const T                       split,
                std::unique_ptr<const KDNode> &lhs,
                std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
        // leaf node
        KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

        bool isLeaf (void) const { return static_cast<bool>(leaf); }

        // data members
        const T                                   splitVal;
        const std::unique_ptr<const KDNode<T,N>>  left, right;
        const std::shared_ptr<const KDPoint<T,N>> leaf;
};

Classe KDTree : (Note : vous devrez ajouter une fonction membre pour construire/remplir votre arbre).

template <class T, std::size_t N>
class KDTree {
    public:
        KDTree () = delete;
        KDTree (const KDTree &) = delete;
        KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
        KDTree & operator = (const KDTree &) = delete;
        ~KDTree () = default;

        const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

        // Nearest neighbour search - runs in O(log n)
        void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
                      const std::array<T, N> &point,
                      std::shared_ptr<const KDPoint<T,N>> &closest,
                      double &minDist,
                      const uint depth = 0) const;

        // data members
        const std::unique_ptr<const KDNode<T,N>> root;
};