Mehrer posts existiere zur effizienten Berechnung paarweiser Abstände in MATLAB. Bei diesen Beiträgen geht es in der Regel darum, den euklidischen Abstand zwischen einer großen Anzahl von Punkten schnell zu berechnen.

Ich muss eine Funktion erstellen, die die paarweisen Unterschiede zwischen kleineren Punktzahlen (normalerweise weniger als 1000 Paare) schnell berechnet. Innerhalb des größeren Schemas des Programms, das ich schreibe, wird diese Funktion viele tausend Male ausgeführt, so dass selbst kleine Effizienzgewinne wichtig sind. Die Funktion muss auf zwei Arten flexibel sein:

Bei jedem Anruf kann die Entfernungsmetrik euklidisch ODER im Stadtblock sein.Die Abmessungen der Daten werden gewichtet.

Soweit ich das beurteilen kann, wurde keine Lösung für dieses spezielle Problem veröffentlicht. Die statistische Toolbox bietet pdist und pdist2, die viele verschiedene Distanzfunktionen akzeptieren, aber keine Gewichtung. Ich habe Erweiterungen dieser Funktionen gesehen, die eine Gewichtung ermöglichen, aber diese Erweiterungen ermöglichen es Benutzern nicht, verschiedene Entfernungsfunktionen auszuwählen.

Ideally möchte ich die Verwendung von Funktionen aus der Statistik-Toolbox vermeiden (ich bin nicht sicher, ob der Benutzer der Funktion Zugriff auf diese Toolboxen hat).

ch habe zwei Funktionen geschrieben, um diese Aufgabe zu erfüllen. Der erste verwendet knifflige Aufrufe zum Repmatieren und Permutieren, und der zweite verwendet einfach for-Schleifen.

function [D] = pairdist1(A, B, wts, distancemetric)

% get some information about the data
    numA = size(A,1);
    numB = size(B,1);

    if strcmp(distancemetric,'cityblock')
        r=1;
    elseif strcmp(distancemetric,'euclidean')
        r=2;
    else error('Function only accepts "cityblock" and "euclidean" distance')
    end

%   format weights for multiplication
    wts = repmat(wts,[numA,1,numB]);

%   get featural differences between A and B pairs
    A = repmat(A,[1 1 numB]);
    B = repmat(permute(B,[3,2,1]),[numA,1,1]);
    differences = abs(A-B).^r;

%   weigh difference values before combining them
    differences = differences.*wts;
    differences = differences.^(1/r);

%   combine features to get distance
    D = permute(sum(differences,2),[1,3,2]);
end

UND

function [D] = pairdist2(A, B, wts, distancemetric)

% get some information about the data
    numA = size(A,1);
    numB = size(B,1);

    if strcmp(distancemetric,'cityblock')
        r=1;
    elseif strcmp(distancemetric,'euclidean')
        r=2;
    else error('Function only accepts "cityblock" and "euclidean" distance')
    end

%   use for-loops to generate differences
    D = zeros(numA,numB);
    for i=1:numA
        for j=1:numB
            differences = abs(A(i,:) - B(j,:)).^(1/r);
            differences = differences.*wts;
            differences = differences.^(1/r);    
            D(i,j) = sum(differences,2);
        end
    end
end

Hier sind die Leistungstests:

A = rand(10,3);
B = rand(80,3);
wts = [0.1 0.5 0.4];
distancemetric = 'cityblock';


tic
D1 = pairdist1(A,B,wts,distancemetric);
toc

tic
D2 = pairdist2(A,B,wts,distancemetric);
toc

Elapsed time is 0.000238 seconds.
Elapsed time is 0.005350 seconds.

Es ist klar, dass die Repmat-and-Permute-Version, zumindest für kleinere Datensätze, viel schneller als die Double-for-Loop-Version funktioniert. Aber ich weiß auch, dass Anrufe zum Repmatieren die Dinge oft verlangsamen. Ich frage mich also, ob jemand in der SO-Community Ratschläge zur Verbesserung der Effizienz einer der beiden Funktionen hat!

BEARBEITE

@ Luis Mendo bot eine schöne Bereinigung der Repmat-and-Permute-Funktion mit bsxfun. Ich habe seine Funktion mit meinem Original auf Datensätzen unterschiedlicher Größe verglichen:

Wenn die Daten größer werden, wird die bsxfun-Version zum klaren Gewinner!

EDIT # 2

Ich habe die Funktion fertig geschrieben und sie ist auf github verfügbar Verknüpfun]. Am Ende fand ich eine ziemlich gute vektorisierte Methode zur Berechnung der euklidischen Distanz Verknüpfun], also wende ich diese Methode im euklidischen Fall an und nehme @ DivakarsRa für Stadtblock. Es ist immer noch nicht so schnell wie pdist2, aber es muss schneller sein als einer der Ansätze, die ich zuvor in diesem Beitrag dargelegt habe, und akzeptiert leicht Gewichtungen.