J'ai un problème d'identification croisée sur des données avec 2 axes comme

A = array([['x0', 'y0', 'data0', 'data0'],
           ['x0', 'y0', 'data0', 'data0'],
           ['x0', 'y0', 'data0', 'data0']])

B = array([['x1', 'y1', 'data1', 'data1'],
           ['x1', 'y1', 'data1', 'data1'],
           ['x1', 'y1', 'data1', 'data1']])   

Ce dont j'ai besoin, c'est de trouver les rangées de 2 listes qui ont le même position. Le position doit être décrit car son distance est suffisamment proche, ce qui est:

distance = acos(cos(y0)*cos(y1)*cos(x0-x1)+sin(y0)*sin(y1))
if(distance < 0.001):
    position = True

Actuellement, j'utilise un code comme ci-dessous:

from math import *
def distance(x1,y1,x2,y2):
    a = acos(cos(y1)*cos(y2)*cos(x1-x2)+sin(y1)*sin(y2))
    if(a < 0.001):
        return True
    else:
        return False
f = open('cross-identification')
for i in range(len(A[0])):
    for j in range(len(B[0])):
        if(distance(A[0][i],A[1][i],B[0][j],B[1][j])==True):
            print(A[0][i],A[1][i],A[2][i],B[2][j],A[3][i],B[3][j],file=f)
        else:continue

C'est OK avec quelques lignes, mais le problème est que j'ai des données MASSIVES et la vitesse est extrêmement lente. Y a-t-il des moyens qui peuvent le rendre plus rapide?

BTW J'ai lu this, proche de ce que je veux mais je ne peux pas simplement le changer. Peut-être que je peux obtenir de l'aide de vous?

3
X.Yang 16 avril 2018 à 12:22

3 réponses

Meilleure réponse

Afin d'éviter non seulement la formule Haversine coûteuse, mais aussi d'ouvrir la possibilité d'utiliser KDTrees, je recommanderais de traduire en coordonnées et distances euclidiennes.

def to_eucl_coords(lat, lon):
    z = np.sin(lat)
    x = np.sin(lon)*np.cos(lat)
    y = np.cos(lon)*np.cos(lat)
    return x, y, z

def to_eucl_dist(sphdist):
    return 2*np.arcsin(sphdist/2)

Les KDTrees sont faciles à utiliser, voici un squelette qui devrait vous aider à démarrer.

from scipy.spatial import cKDTree as KDTree

eucl_1 = np.c_[to_eucl_coords(lat1, lon1)]
eucl_2 = np.c_[to_eucl_coords(lat2, lon2)]
t1, t2 = KDTree(eucl_1), KDTree(eucl2)
neighbors = t1.query_ball_tree(t2, threshold)
2
Paul Panzer 16 avril 2018 à 11:02

Il s'agit d'un problème de type de produit externe classique: comparez chaque combinaison de deux vecteurs.

La réponse précédente est correcte: votre double boucle tue l'efficacité. Une réponse possible est d'utiliser numpy

Selon la taille de vos entrées, vous pouvez utiliser un meshgrid approche ou (plus compliqué) les fonctions universelles numpy avec produit externe.

Pour les premiers, vous pouvez essayer quelque chose comme:

import numpy as np
A = [[1, 1],
     [1, 3],
     [3, 1],
     [3, 3]]

B = [[1, 1],
     [3, 1],
     [1, 2],
     [1, 3],
     [3, 3]]

a_array = np.array(A)
b_array = np.array(B)

x0, x1 = np.meshgrid(a_array[:, 0], b_array[:, 0])
y0, y1 = np.meshgrid(a_array[:, 1], b_array[:, 1])

distance = np.arccos(np.cos(y0)*np.cos(y1)*np.cos(x0-x1)+np.sin(y0)*np.sin(y1))
good_pairs = np.nonzero(distance < 0.001)

print(distance)
print(good_pairs)
for b_ind, a_ind in zip(*good_pairs):
    print('Entry {} of A ({}) matches entry {} of B ({})'.format(a_ind, A[a_ind], b_ind, B[b_ind]))
0
EdR 16 avril 2018 à 10:52

Il s'agit d'un problème de performances. Vous avez beaucoup de fruits bas pour une énorme amélioration de votre fonction de distance.

  1. au lieu de acos(x) < eps utiliser x > 1 - (eps**2)/2 qui vous fait économiser un acos() expansif (cela fonctionne grâce à l'expansion de Taylor), évidemment pré-calculer 1 - (eps**2)/2

  2. au lieu de calculer cos(y0) etc 4*len(A[0])*len(B[0]) fois, pré-calculez-les, ce qui ne prend que 2*(len(A[0])+len(B[0])) fois, ce qui vous évite de nombreux calculs de trig si A*B devient volumineux

  3. me semble que le précalcul cos(x1-x2) est aussi une victoire, mais je ne suis pas sûr à 100%

Cela optimise légèrement chaque évaluation de distance. Je pense qu'un problème plus important est que votre double boucle effectue des évaluations N * M. Idéalement, vous pouvez réduire cette boucle avec un algorithme géométrique intelligent. (voir par exemple la géométrie informatique par Mark de Berg et al, Springer 2008)

Mais votre fonction de distance (métrique) est trop bizarre! Je ne vois pas comment transformer votre (x,y) en un espace avec cette fonction métrique. Je suis très curieux d'où vient cette fonction de distance.

0
Doctor Core 16 avril 2018 à 10:26