Calcul répété du plus proche voisin pour des millions de points de données trop lent

J'ai un ensemble de données fonctionnant sur des millions de points de données en 3D. Pour le calcul que je fais, je dois calculer le voisin (recherche de plage) de chaque point de données dans un rayon, essayer d'ajuster une fonction, calculer l'erreur pour l'ajustement, répéter cela pour le prochain point de données et ainsi de suite. Mon code fonctionne correctement mais son exécution prend très longtemps, environ 1 seconde par point de données! C'est probablement parce que pour chaque point, il doit rechercher dans l'ensemble de données. Existe-t-il un moyen de rendre le processus rapide. J'ai une idée que si je peux en quelque sorte établir une relation d'adjacence entre les premiers voisins, cela peut être moins lent. Si cela aide, j'essaie de trouver la largeur de fenêtre Parzen optimale en 3D.

Je suggérerais de googler pour les hiérarchies de volumes limites (arbre BSP en particulier). Compte tenu de votre nuage de points, vous pouvez trouver un avion qui le divise en deux sous-nuages ​​égaux. Ensuite, lorsque vous devez trouver la collection de points qui se trouvent dans un rayon R d'un point de test, vous pouvez d'abord comparer votre point de test à ce plan, et si sa hauteur au-dessus est supérieure à R, puis tout le sous-nuage en dessous du plan doit également être plus éloigné que R (vous n'avez donc pas besoin de vérifier l'un de ces points). Vous pouvez également appliquer cette idée de manière récursive, ce qui donne finalement des complexités de type n log n au lieu de n-carré. (Il s'agit de partitionnement BSP / espace binaire,

Il existe plusieurs structures de données pour stocker des données qui préservent les informations sur la position et la proximité; là en permettant la détermination rapide des voisins les plus proches.

En particulier R arbres (et les formes spécialisées comme R * -trees ) et X arbres . Beaucoup de choix optimisés pour des utilisations légèrement différentes.

Le choix d'un arbre R * plutôt que d'une recherche naïve de voisin le plus proche a été une grande partie de l'obtention d'un facteur d'accélération de 10000 dans un code particulier. (OK, peut - être quelques centaines de c'était le R * -tree, la plupart du reste était parce que le consultation naïve avait été mal codé de sorte qu'il a fracassé le cache. :: :: soupir )

$O(N \log N)$$N$$O(\log N)$

Ceci est très similaire à l'un des plus grands défis dans le domaine de la dynamique moléculaire - calculer toutes les interactions par paires entre les particules non liées.

Là, nous utilisons des listes de cellules (ou des listes de voisins ) pour nous aider à comprendre ce qui se trouve à proximité; pour cette application, la liste des cellules est probablement l'algorithme le plus facile à utiliser:

• Divisez la boîte en une série de cellules.
• Pour chaque particule, déterminez à quelle cellule elle doit être affectée (O (1) par particule).
• Ensuite, pour chaque particule, vérifiez la "propre" cellule plus les cellules voisines; si l'un d'eux est occupé, aucune autre recherche n'est nécessaire.
• Si tous les voisins les plus proches sont vides, développez-les jusqu'aux voisins les plus proches, et ainsi de suite, jusqu'à ce qu'une particule soit trouvée.

Si votre système a une distribution plus ou moins uniforme de particules, cela réduira considérablement le coût de votre algorithme, selon la grossièreté de la grille. Cependant, un réglage fin est nécessaire: une grille trop grossière et vous ne gagnerez pas beaucoup de temps; trop bien, et vous passerez beaucoup de temps à parcourir des cellules de grille vides!

Vous devriez certainement vérifier les arbres et octets KD qui sont les méthodes de choix pour les ensembles de points (tandis que les BSP sont pour les objets généraux et les grilles pour les densités plus ou moins uniformes). Ils peuvent être très compacts et rapides, minimisant la surcharge en mémoire et en calcul, et sont simples à implémenter.

Lorsque vos points sont plus ou moins uniformément répartis (même avec des zones vides, mais qu'il ne doit pas y avoir de singularité de densité ou d'autres concentrations élevées), vérifiez les emballages de sphères si vous souhaitez essayer une subdivision d'espace non hiérarchique de type grille.

Vous devriez probablement envisager de construire la triangulation de Delaunay (enfin, son analogue 3D). En 2D, c'est une triangulation spéciale des points de données qui contient toujours le plus proche voisin. La même chose vaut en 3D, mais avec des tétraèdres.

$n \log(n)$

J'espère que cela aide!