Finden der nächsten Elemente über zwei Listen/Arrays in Python

Question

Ich habe zwei Nummernfelder x und y enthält Float-Werte. Für jeden Wert in x möchte ich das nächste Element in y finden, ohne Elemente aus y wiederzuverwenden. Die Ausgabe sollte eine 1-1-Abbildung von Indizes von Elementen von x zu Indizes von Elementen von y sein. Hier ist ein schlechter Weg, dies zu tun, der auf Sortieren beruht. Es entfernt jedes Element, das gepaart wurde, aus der Liste. Ohne zu sortieren wäre dies schlecht, da die Paarung von der Reihenfolge der ursprünglichen Eingabearrays abhängen würde.

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] 

ziehe ich es zu tun, ohne die Elemente erste Sortierung, aber wenn sie sortiert werden dann will ich die Indizes in den ursprünglichen, unsortierten Listen unsorted_x, unsorted_y zu bekommen. Was ist der beste Weg dies in numpy/scipy/Python oder mit Pandas zu tun? Vielen Dank.

bearbeiten: um zu klären, ich versuche nicht, die beste Passform über alle Elemente zu finden (nicht Minimierung Summe der Abstände zum Beispiel), sondern die beste Passform für jedes Element, und es ist in Ordnung, wenn es manchmal auf Kosten anderer Elemente. Ich nehme an, dass y im Allgemeinen viel größer ist als x im Gegensatz zu oben genannten Beispiel und so gibt es in der Regel viele sehr gute passt für jeden Wert von x in y, und ich möchte nur, dass man effizient zu finden.

Kann jemand ein Beispiel von scipy kdtrees dafür zeigen? Die Dokumente sind recht spärlich

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

Answer 1

EDIT 2 Eine Lösung KDTree verwendet, kann sehr gut durchführen, wenn Sie eine Reihe von Nachbarn können wählen, die garantiert, dass Sie einen einzigartigen Nachbarn für jedes Element im Array haben. Mit dem folgenden Code:

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 

und eine Probe von n=1000 Punkte, die ich erhalten:

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 

So das Optimum ist k=13, und dann das Timing ist:

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

Aber in Im schlechtesten Fall könnten Sie k=1000 benötigen und dann:

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

, die langsamer als die anderen Optionen ist:

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 Sortieren der Array vor der Suche nach Gruppen von mehr als 1000 Produkte auszahlt:

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 

Mit einem 10000 Element langes 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 

Bei kleineren Arrays ist die Leistung etwas schlechter.

---

Sie werden in einer Schleife über alle Ihre Artikel, um Ihre greedy nächsten Nachbar-Algorithmus zu implementieren, wenn auch nur um Duplikate zu verwerfen. In diesem Sinne, ist dies die schnellste, die ich in der Lage gewesen, um mit:

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 

Und jetzt mit:

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

ich:

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

Answer 2

Diese stark vereinfachte Code hat sehr gut funktioniert.

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)