J'ai une collection de points dimensionnels et je souhaite trouver ce que 2 sont les plus proches. Le mieux que je puisse arriver pour 2 dimensions est la suivante: qui donne mais c'est trop lent pour les grandes matrices. Quel type d'optimisation puis-je m'appliquer? lié: Euclidien distance entre les points de deux tableaux numpus différents, pas dans
7 Réponses :
Il y a toute une page Wikipedia sur juste ce problème, voir: http://en.wikipedia.org/ wiki / fermeest_pair_of_points
Résumé: vous pouvez obtenir O (N journal N) avec une division reconsive et une algorithme de conquérir (décrite sur la page Wiki ci-dessus).
Soigné! Je suis content d'avoir frappé l'actualisation avant d'écrire: "De toute évidence la complexité est O (n ^ 2)"; o)
Super. Si les points doivent être ajoutés successivement et que la paire de distance minimale doit être mise à jour, maintenir une structure de triangulation Delaunay est efficace.
À quelle vitesse est-il comparé à une boucle imbriquée et à garder une trace de la paire la plus courte? Je pense que la création d'un énorme réseau cross est ce qui pourrait vous faire mal. Même O (N ^ 2) est toujours assez rapide si vous ne faites que 2 points dimensionnels.
Ça aide, mais dégénère rapidement pour de grandes matrices
Il y a une fonction scipée http://docs.cipy.org/doc/scipy/ Référence / spatial.distance.html
qui génère les paires N * (N-1) / 2 (depuis R_IJ == R_JI). Vous pouvez ensuite rechercher sur la valeur minimale et éviter toute la gâche en boucle dans votre code. pdist qui vous obtiendra des distances paires entre les points d'une matrice de manière assez efficace:
Essayez scipy.spatial.distance.pdist (myarr) . Cela vous donnera une matrice de distance condensée. Vous pouvez utiliser argmin dessus et trouver l'index de la plus petite valeur. Cela peut être converti en informations sur la paire.
Quel est le moyen le plus simple d'obtenir ces coordonnées de cet entier unique?
@ Ηλίας Vous pouvez utiliser np.unravel_index (np.argmin (distances), distances.shape) si distances contient le résultat de l'appel pdist appel dessus.
Cela me donne un mal d'estomac à utiliser cette méthode pour trouver des paires les plus proches de O (n ^ 2), car la solution de division-and-conquérir O (N log n) était littéralement le premier algorithme que j'ai appris dans ma classe d'algorithmes à l'école. Mais c'est tellement plus facile à mettre en œuvre et cela fonctionne bien pour un petit ensemble suffisamment.
Peut-être que vous pourriez peut-être poursuivre ces lignes:
In []: from scipy.spatial.distance import pdist as pd, squareform as sf In []: m= 1234 In []: n= 123 In []: p= randn(m, n) In []: d= sf(pd(p)) In []: a= arange(m) In []: d[a, a]= d.max() In []: where(d< d.min()+ 1e-9) Out[]: (array([701, 730]), array([730, 701]))
Vous pouvez profiter de la dernière version des outils de triangulation Delaunay's (V0.9) de Scipy (V0.9). Vous pouvez être sûr que les deux points les plus proches seront un bord d'un Simplex dans la triangulation, qui est un sous-ensemble beaucoup plus petit de paires que chaque combinaison.
Voici le code (mis à jour pour le général ND): semble étroitement O (n): 
Peut réellement fonctionner en 2D. Avez-vous fait des horaires? Cependant, cette approche échoue malheureuse dans une dimension supérieure. Merci
@eat: Pourquoi dites-vous que cela "échoue misérablement"? 3D est de 4-5x plus lent que le même n en 2D. Mais toute approche (à l'exception de l'approche brute naïve) va voir les ralentissements avec D.
Eh bien, c'est une sorte d'inutile d'essayer de faire la triangulation de Delaunay en 123D! Cela ne résoudra donc pas la question de l'opération (à moins que son ND soit 2 ou 3). Ne vous méprenez pas, je suis vraiment très heureux que sciped est capable d'effectuer une triangulation Delaunay si rapidement. Veuillez faire des horaires avec pdist pour n = 2 ... 123, vous verrez. Merci
@eat: J'ai raté le fait que l'OP voulait une solution N-D générale, j'avais l'impression que c'était strictement 2D. Je suis un petit "tunnel de bridge" et je considère parfois 3D non seulement comme "haute dimension", mais le plus élevé!
La réponse acceptée est OK pour les petits ensembles de données, mais son temps d'exécution échoue comme Cette solution optiale peut être obtenue en utilisant sklearn.neighbors.balltree comme suit. Cette procédure échoue bien pour de très grands ensembles de valeurs une solution identique peut être obtenue en utilisant scipe.spatial.ckdtree , en remplaçant le n ** 2 . Toutefois, comme indiqué par @payne, une solution optimale peut atteindre n * journal (n) mise à l'échelle du temps de calcul. xy et même pour les grandes dimensions dim (alambule l'exemple illustre le cas dim = 2 ). La sortie résultante ressemble à ceci 
Sklearn Importer avec l'Egny One suivant. REMARQUE Toutefois que ckdtree , contrairement à Balltree , ne fonctionne pas bien pour les dimensions élevées
@ Ηλίας: environ combien de points avez-vous? Veuillez noter qu'il est possible d'avoir un ensemble de plus de 2 points (même tous les points) avec les mêmes distances (mais des calculs inexacts peuvent ne pas refléter cela, de sorte que vous devez donc pouvoir définir un seuil TRH où les différences de distance sont inférieures à la TRH. considéré égal). Vous n'êtes pas intéressé de trouver le point le plus proche d'une personne donnée?
@eat C'est un groupe de hiérarchies que je suis en construction et que j'ai besoin de trouver les deux centroïdes les plus proches. Normalement moins de mille points, mais j'ai besoin de voir à quel point il peut échoué. Les erreurs d'arrondi, ne seront pas aussi importantes dans mon cas.