Algorithmes pour trouver le vecteur le plus proche

Question

J'ai un ensemble de vecteurs. Pour un vecteur dans cet ensemble, j'aime trouver le sous-ensemble le plus proche de ce vecteur. Quel algorithme peut le faire.

Answer 1

utiliser la similitude de cosinus (http://en.wikipedia.org/wiki/Cosine_similarity) parmi les vecteurs, puis les trier.

Answer 2

Cette classe d'algorithmes est appelée Plus proche voisin ou K Plus proche voisin.

Le cosine similarity comme dit excepeiont fonctionnera si la direction du vecteur est importante. Si le vecteur représente une position dans un espace, alors n'importe quelle métrique pour représenter une distance dans l'espace fonctionnera.

Par exemple le Euclidean distance: prenez la racine carrée de la somme des carrés de différence dans chaque dimension. Cela vous donnera une distance pour chaque vecteur, puis triera votre ensemble de vecteurs croissant sur cette distance.

Ce processus sera O (N) dans le temps. Si cela est trop lent pour vous, vous pourriez vouloir regarder quelques algorithmes communs K Nearest Neighbour.

Answer 3

Si votre problème est lié à une grande quantité de données:

I a publié un algorithme connexe sur ddj.com, qui trouve la ligne la plus proche à un point donné :

Accelerated Search For the Nearest Line

Vous Il faudrait modifier cet algorithme, c'est-à-dire en convertissant le vecteur donné en un certain nombre de points. Cela permettra de réduire le nombre de possibles matchs de manière drastique. Le match exact doit alors être vérifiée pour chaque match possible par

• Trouver le point de coupe des deux vecteurs ou
• Get distance de début de vecteur et point final pour le match possible, comme décrit dans l'article