Finde den nächsten Vektor aus einer Liste von Vektoren | Python

Question

Wenn Sie sagen, eine Liste von 10 Vektoren, genannt A, die verschiedene Gruppen darstellen. Dann haben Sie eine Zeitreihe von Vektoren v1, v2, ..., vn, von denen jeder auch ein Vektor ist. Ich habe mich gefragt, ob es einen Weg gibt, den "nächsten" Vektor in A für jede v1, v2, ..., vn zu finden, wenn Sie eine Entfernungsmetrik definieren?

Gibt es einen schnellen Weg dies zu tun, um alle Einträge zu durchlaufen und nur zu vergleichen?

Edit: Nein Ich frage nicht, wie man k-bedeutet oder so etwas.

Answer 1

Sie können die spatial KDtree in scipy verwenden. Es verwendet einen schnellen Baumalgorithmus, um nahe Punkte für Vektoren beliebiger Dimension zu identifizieren.

Bearbeiten: Entschuldigung, wenn Sie nach arbitrary distance metrics suchen, könnte eine baumähnliche Struktur immer noch eine Option sein. Hier

ein Beispiel:

>>> from scipy import spatial 
>>> A = [[0,1,2,3,4], [4,3,2,1,0], [2,5,3,7,1], [1,0,1,0,1]] 
>>> tree = spatial.KDTree(A) 

Dies stellt der KDTree mit allen Punkten in A, so dass Sie schnell räumliche Suche innerhalb es auszuführen. Eine solche Abfrage nimmt einen Vektor und gibt den nächsten Nachbarn in A für sie:

>>> tree.query([0.5,0.5,0.5,0.5,0.5]) 
(1.1180339887498949, 3) 

Der erste Rückgabewert ist der Abstand des nächsten Nachbarn und der zweite seine Position in A, so dass Sie es erhalten für Beispiel wie folgt aus:

>>> A[ tree.query([0.5,0.5,0.5,0.5,0.5])[1] ] 
[1, 0, 1, 0, 1] 

Answer 2

Wenn Sie eine Metrik definieren, können Sie es in der min Funktion:

closest = min(A, key=distance) 

Answer 3

So ein Beispielcode ist:

# build a KD-tree to compare to some array of vectors 'centall' 
tree = scipy.spatial.KDTree(centall) 
print 'shape of tree is ', tree.data.shape 

# loop through different regions and identify any clusters that belong to a different region 
[d1, i1] = tree.query(group1) 
[d2, i2] = tree.query(group2) 

Dies gibt Variablen d und i. d speichert die nächstliegende Entfernung ich gebe den Index zurück, bei dem dies geschieht

Hoffe, das hilft.