znajdowanie najbliższych pozycji na dwóch listach/tablicach w Pythonie

Question

Mam dwie niezliczone tablice x i y zawierające wartości zmiennoprzecinkowe. Dla każdej wartości w x, chcę znaleźć najbliższy element w y, bez ponownego użycia elementów z y. Wyjście powinno być 1-1 mapowaniem indeksów elementów od x do indeksów elementów od y. Oto zły sposób na to, który polega na sortowaniu. Usuwa każdy sparowany element z listy. Bez sortowania byłoby to złe, ponieważ parowanie zależałoby od kolejności oryginalnych tablic wejściowych.

def min_i(values): 
    min_index, min_value = min(enumerate(values), 
           key=operator.itemgetter(1)) 
    return min_index, min_value 

# unsorted elements 
unsorted_x = randn(10)*10 
unsorted_y = randn(10)*10 

# sort lists 
x = sort(unsorted_x) 
y = sort(unsorted_y) 

pairs = [] 
indx_to_search = range(len(y)) 

for x_indx, x_item in enumerate(x): 
    if len(indx_to_search) == 0: 
     print "ran out of items to match..." 
     break 
    # until match is found look for closest item 
    possible_values = y[indx_to_search] 
    nearest_indx, nearest_item = min_i(possible_values) 
    orig_indx = indx_to_search[nearest_indx] 
    # remove it 
    indx_to_search.remove(orig_indx) 
    pairs.append((x_indx, orig_indx)) 
print "paired items: " 
for k,v in pairs: 
    print x[k], " paired with ", y[v] 

wolę zrobić to bez sortowania elementów pierwszy, ale jeśli są one klasyfikowane następnie chcę uzyskać indeksy w oryginalnych, nieposortowane list unsorted_x, unsorted_y. jaki jest najlepszy sposób robienia tego w numpy/scipy/Python lub przy użyciu pand? dzięki.

edit: wyjaśnić, ja nie staram się znaleźć najlepsze dopasowanie we wszystkich elemets (nie minimalizuje sumę odległości, na przykład), ale raczej najlepsze dopasowanie do każdego elementu, i to jest w porządku, czy to czasem kosztem innych elementów. Zakładam, że y jest na ogół o wiele większy niż x w przeciwieństwie do powyższego przykładu, więc zazwyczaj istnieje wiele bardzo dobrych pasowań dla każdej wartości x w y, i chcę tylko znaleźć to wydajnie.

Czy ktoś może pokazać przykład scipy kdtrees do tego? Docs są dość skąpe

kdtree = scipy.spatial.cKDTree([x,y]) 
kdtree.query([-3]*10) # ?? unsure about what query takes as arg 

Answer 1

EDIT 2 Roztwór stosując KDTree można wykonać bardzo dobrze, jeśli można wybrać liczbę sąsiadów, który gwarantuje, że będziesz miał niepowtarzalną sąsiada dla każdego elementu w tablicy. Z następującego kodu:

def nearest_neighbors_kd_tree(x, y, k) : 
    x, y = map(np.asarray, (x, y)) 
    tree =scipy.spatial.cKDTree(y[:, None])  
    ordered_neighbors = tree.query(x[:, None], k)[1] 
    nearest_neighbor = np.empty((len(x),), dtype=np.intp) 
    nearest_neighbor.fill(-1) 
    used_y = set() 
    for j, neigh_j in enumerate(ordered_neighbors) : 
     for k in neigh_j : 
      if k not in used_y : 
       nearest_neighbor[j] = k 
       used_y.add(k) 
       break 
    return nearest_neighbor 

i próbki n=1000 punktów, otrzymuję:

In [9]: np.any(nearest_neighbors_kd_tree(x, y, 12) == -1) 
Out[9]: True 

In [10]: np.any(nearest_neighbors_kd_tree(x, y, 13) == -1) 
Out[10]: False 

więc optymalna jest k=13, a następnie czas jest:

In [11]: %timeit nearest_neighbors_kd_tree(x, y, 13) 
100 loops, best of 3: 9.26 ms per loop 

Ale w w najgorszym przypadku możesz potrzebować k=1000, a następnie:

In [12]: %timeit nearest_neighbors_kd_tree(x, y, 1000) 
1 loops, best of 3: 424 ms per loop 

który jest wolniejszy niż inne opcje:

In [13]: %timeit nearest_neighbors(x, y) 
10 loops, best of 3: 60 ms per loop 

In [14]: %timeit nearest_neighbors_sorted(x, y) 
10 loops, best of 3: 47.4 ms per loop 

---

EDIT Sortowanie tablicę przed wyszukiwaniem opłaca tablic ponad 1000 pozycji:

def nearest_neighbors_sorted(x, y) : 
    x, y = map(np.asarray, (x, y)) 
    y_idx = np.argsort(y) 
    y = y[y_idx] 
    nearest_neighbor = np.empty((len(x),), dtype=np.intp) 
    for j, xj in enumerate(x) : 
     idx = np.searchsorted(y, xj) 
     if idx == len(y) or idx != 0 and y[idx] - xj > xj - y[idx-1] : 
      idx -= 1 
     nearest_neighbor[j] = y_idx[idx] 
     y = np.delete(y, idx) 
     y_idx = np.delete(y_idx, idx) 
    return nearest_neighbor 

Z 10000 element long array:

In [2]: %timeit nearest_neighbors_sorted(x, y) 
1 loops, best of 3: 557 ms per loop 

In [3]: %timeit nearest_neighbors(x, y) 
1 loops, best of 3: 1.53 s per loop 

Dla mniejszych tablic działa nieco gorzej.

---

Będziesz mieć do pętli na wszystkich elementów, aby zaimplementować algorytm najbliższego sąsiada greedy, jeśli tylko usunąć duplikaty. Mając to na uwadze, jest to najszybciej udało mi się wymyślić:

def nearest_neighbors(x, y) : 
    x, y = map(np.asarray, (x, y)) 
    y = y.copy() 
    y_idx = np.arange(len(y)) 
    nearest_neighbor = np.empty((len(x),), dtype=np.intp) 
    for j, xj in enumerate(x) : 
     idx = np.argmin(np.abs(y - xj)) 
     nearest_neighbor[j] = y_idx[idx] 
     y = np.delete(y, idx) 
     y_idx = np.delete(y_idx, idx) 

    return nearest_neighbor 

A teraz z:

n = 1000 
x = np.random.rand(n) 
y = np.random.rand(2*n) 

uzyskać:

In [11]: %timeit nearest_neighbors(x, y) 
10 loops, best of 3: 52.4 ms per loop 

Answer 2

to znacznie uprościć kod działało idealnie.

N=12 
M=15 

X = [np.random.random() for i in range(N)] 
Y = [np.random.random() for i in range(M)] 

pair = [] 

for x in X: 
    t = [abs(x-y) for y in Y] 
    ind = t.index(min(t)) 
    pair.append((x,Y[ind])) 
    X.remove(x) 
    Y.remove(Y[ind]) 

print(pair)