Matlab: Hilfe bei der Suche nach Mindestabstand

Question

Ich versuche, den Punkt zu finden, der in einem minimalen Abstand von der Kandidatenmenge ist. Z ist eine Matrix, in der die Zeilen die Dimension und Spalten die Punkte darstellen. Berechnen der Zwischenpunktabstände und dann Aufnehmen des Punktes mit minimalem Abstand und dessen Entfernung. Unten ist das Code-Snippet. Der Code funktioniert gut für eine kleine Dimension und eine kleine Menge von Punkten. Es dauert jedoch lange Zeit für große Datenmengen (N = 1 Million Datenpunkte und Dimension ist ebenfalls hoch). Gibt es einen effizienten Weg?

Answer 1

Ich schlage vor, dass Sie pdist verwenden, um das schwere Heben für Sie zu tun. Diese Funktion berechnet die paarweise Entfernung zwischen zwei Punkten in Ihrem Array. Der resultierende Vektor ist zu Matrixform setzte in squareform, um mit dem Minimalwert für jedes Paar zu finden:

N = 100; 
Z = rand(2,N); % each column is a 2-dimensional point 

% pdist assumes that the second index corresponds to dimensions 
% so we need to transpose inside pdist() 
distmatrix = squareform(pdist(Z.','euclidean')); % output is [N, N] in size 
% set diagonal values to infinity to avoid getting 0 self-distance as minimum 
distmatrix = distmatrix + diag(inf(1,size(distmatrix,1))); 
mindists = min(distmatrix,[],2); % find the minimum for each row 
sum_dist = sum(mindists); % sum of minimal distance between each pair of points 

Dieser berechnet jedes Paar zweimal, aber ich denke, das für Ihre ursprüngliche Implementierung wahr ist.

Die Idee ist, dass pdist den paarweisen Abstand zwischen den Spalten seiner Eingabe berechnet. Also setzen wir die Transponierte von Z in pdist. Da die volle Ausgabe immer eine quadratische Matrix mit Nulldiagonale ist, wird pdist so implementiert, dass sie nur die Werte über der Diagonalen in einem Vektor zurückgibt. Daher wird ein Aufruf an squareform benötigt, um die richtige Abstandsmatrix zu erhalten. Dann muss das zeilenweise Minimum dieser Matrix gefunden werden, aber zuerst müssen wir die Null in den Diagonalen ausschließen. Ich war faul, also setze ich inf in die Diagonalen, um sicherzustellen, dass das Minimum woanders ist. Am Ende müssen wir nur die minimalen Entfernungen zusammenfassen.