J'ai Y a-t-il un moyen de résoudre ce problème plus rapidement que n = 10000 vecteurs 10 dimensions.
Pour chaque vecteur v1 je veux connaître le vecteur v2 qui minimise l'angle entre v1 et v2 .
O (n ^ 2) ?
4 Réponses :
Que diriez-vous de vous calculer des angles pour chaque vecteur (O (n)) puis triez la matrice en fonction des angles (O (NLogn)), puis de marcher sur le tableau (O (N)) Le vecteur le plus proche est soit i + 1 ou I-1.
EDIT: Comme indiqué dans des commentaires, cela ne fonctionne que dans 2 dimensions.
Pas du tout; Dans> 2 dimensions, l'équivalent consiste à remplacer les choses par des vecteurs unitaires, ce qui abaisse la dimensionnalité par une mais la laisse toujours trop haute pour être bien ordonnée.
Ce que vous avez est essentiellement le problème de la sphère de points le plus proche (puisque l'angle entre les vecteurs est à peu près la distance entre les points de la sphère que leur unité-vecteurs se trouvent), donc vous pourriez probablement faire une sorte de binaire (peut-être que le ternaire serait plus facile d'éviter trop de problèmes frontaliers) la décomposition de partitionnement de l'espace.
Mais cela serait désagréable de coder et probablement pas beaucoup plus vite que la méthode naïve de 10 000 points (en particulier, vous commencez par diviser les points parmi 3 ^ 10 = 59049 boîtes, bien que la plupart de ceux-ci puissent être vide). Cent millions de produits DOT à dix éléments doivent être bien inférieurs à une seconde.
Vous pouvez normaliser tous les vecteurs dans O (n) temps et trouver un paramétrage d'entre eux sur l'hypersphère à 9 dimensions résultant. Vous pouvez ensuite utiliser une structure de recherche spatiale dans l'espace dimensionnel N-1, comme un kd-arbre pour accélérer la requête voisine la plus proche. Il existe des méthodes bien connues ( Ann ) pour le faire.
wow. Vecteurs dix dimensions? Que faites-vous avec ceux?
Je suppose que je devrais commencer par la réduction de chaque vecteur à une longueur unitaire - c'est-à-dire aux points d'une hypersphère - utilisez ensuite un algorithme "Recherche voisine de voisin la plus proche" (NNS), tel que l'arborescence KD (arbre binaire K-dimensionnel), R-Tree, meilleure corbeille d'abord, etc.
Il est probablement impossible de résoudre ce problème plus rapidement que O (n log n), car si vous pouviez résoudre ce problème plus rapidement que cela, vous pouvez résoudre plus rapidement le «problème de paire de points» plus simple plus rapidement que la limite inférieure actuelle de O (N journal n).
Comme Tom Womack, souligné, l'algorithme de la force brute-force O (N ^ 2) prendra moins de temps d'horloge murale réelle que ces algorithmes plus sophistiqués pour "petites" quantités de données, et on dirait "n = 10000" est relativement petit pour 10 dimensions.
J'espère que "10" est en binaire ...