Berechnung aller Entfernungen zwischen einem Punkt und einer Gruppe von Punkten effizient in R

Question

Zunächst einmal bin ich neu in R (ich begann gestern).

I haben zwei Gruppen von Punkten, data und centers, wobei die erste Größe n und die zweite Größe K (zum Beispiel n = 3823 und K = 10) und für jeden i in dem ersten Satz, ich brauche j zu finden in der Sekunde mit dem Mindestabstand.

Meine Idee ist einfach: für jeden i, lassen dist[j] der Abstand zwischen i und j, ich brauche nur which.min(dist) zu verwenden, um zu finden, was ich suche.

Jeder Punkt ist ein Array von 64 verdoppelt, so

> dim(data) 
[1] 3823 64 
> dim(centers) 
[1] 10 64 

ich mit

for (i in 1:n) { 
    for (j in 1:K) { 
    d[j] <- sqrt(sum((centers[j,] - data[i,])^2)) 
    } 
    S[i] <- which.min(d) 
} 

versucht haben, die extrem langsam (mit n = 200, es mehr als 40s dauert !!). Die schnellste Lösung, die ich geschrieben habe, ist

distance <- function(point, group) { 
    return(dist(t(array(c(point, t(group)), dim=c(ncol(group), 1+nrow(group)))))[1:nrow(group)]) 
} 

for (i in 1:n) { 
    d <- distance(data[i,], centers) 
    which.min(d) 
} 

Auch wenn es eine Menge Rechen tut, die ich nicht verwenden (da dist(m) den Abstand zwischen allen Zeilen von m berechnet), es ist viel schneller als die andere (Kann jemand erklären warum?), aber es ist nicht schnell genug für das, was ich brauche, weil es nicht nur einmal verwendet wird. Und auch der distance Code ist sehr hässlich. Ich habe versucht, es durch

zu ersetzen, aber das scheint zweimal langsamer zu sein. Ich habe auch versucht, dist für jedes Paar zu verwenden, aber es ist auch langsamer.

Ich weiß nicht, was ich jetzt tun soll. Es scheint, als würde ich etwas sehr falsch machen. Irgendeine Idee, wie man das effizienter macht?

ps: Ich brauche dies, um k-means von Hand zu implementieren (und ich muss es tun, es ist Teil einer Aufgabe). Ich glaube, ich brauche nur Euklidische Distanz, aber ich bin mir noch nicht sicher, also werde ich lieber einen Code haben, wo die Entfernungsberechnung leicht ersetzt werden kann. stats::kmeans alle Berechnungen in weniger als einer Sekunde durchführen.

Answer 1

Anstatt über Datenpunkte zu iterieren, können Sie dies einfach zu einer Matrixoperation zusammenfassen, was bedeutet, dass Sie nur über K iterieren müssen.

# Generate some fake data. 
n <- 3823 
K <- 10 
d <- 64 
x <- matrix(rnorm(n * d), ncol = n) 
centers <- matrix(rnorm(K * d), ncol = K) 

system.time(
    dists <- apply(centers, 2, function(center) { 
    colSums((x - center)^2) 
}) 
) 

Läuft in:

utilisateur  système  écoulé 
     0.100  0.008  0.108 

auf meinem Laptop.

Answer 2

Vielleicht möchten Sie einen Blick in die apply Funktionen werfen.

Zum Beispiel dieser Code

for (j in 1:K) 
    { 
    d[j] <- sqrt(sum((centers[j,] - data[i,])^2)) 
    } 

leicht durch so etwas wie

dt <- data[i,] 
d <- apply(centers, 1, function(x){ sqrt(sum(x-dt)^2)}) 

Sie können es auf jeden Fall ersetzt werden kann optimieren mehr, aber Sie erhalten den Punkt Ich hoffe

Answer 3

dist Werke schnell weil is't vektorisiert ist und interne C-Funktionen aufruft.
Sie Code-in-Schleife könnte in vielerlei Hinsicht vektorisiert werden.

Zum Beispiel berechnen Abstand zwischen data und centers könnten Sie outer verwenden:

Dies gibt Ihnen n x K Matrix von Entfernungen. Und sollte viel schneller als Loop sein.

Dann könnten Sie max.col verwenden, um das Maximum in jeder Zeile zu finden (siehe Hilfe, es gibt einige Nuancen, wenn viele Maxima sind). X muss negiert werden, weil wir nach dem Minimum suchen.

CL <- max.col(-X) 

Um in R effizient zu sein, sollten Sie so vektorisiert wie möglich. Loops könnten in vielen Fällen durch vektorisierten Ersatz ersetzt werden. Überprüfen Sie die Hilfe für rowSums (die auch rowMeans, colSums, rowSums), pmax, cumsum beschreiben. Sie könnten SO suchen, z.B. https://stackoverflow.com/search?q=[r]+avoid+loop (kopieren & fügen Sie diesen Link, ich nicht, wie es klickbar machen) für einige Beispiele.

Answer 4

Meine Lösung:

# data is a matrix where each row is a point 
# point is a vector of values 
euc.dist <- function(data, point) { 
    apply(data, 1, function (row) sqrt(sum((point - row)^2))) 
} 

Sie es versuchen können, wie:

x <- matrix(rnorm(25), ncol=5) 
euc.dist(x, x[1,]) 

Answer 5

rdist() ist eine R-Funktion von {Felder} Paket, das von Abständen zwischen zwei Sätzen zu berechnen Lage ist, Punkte im Matrixformat schnell.

https://www.image.ucar.edu/~nychka/Fields/Help/rdist.html

Verbrauch:

library(fields) 
#generating fake data 
n <- 5 
m <- 10 
d <- 3 

x <- matrix(rnorm(n * d), ncol = d) 
y <- matrix(rnorm(m * d), ncol = d) 

rdist(x, y) 
      [,1]  [,2]  [,3]  [,4]  [,5] 
[1,] 1.512383 3.053084 3.1420322 4.942360 3.345619 
[2,] 3.531150 4.593120 1.9895867 4.212358 2.868283 
[3,] 1.925701 2.217248 2.4232672 4.529040 2.243467 
[4,] 2.751179 2.260113 2.2469334 3.674180 1.701388 
[5,] 3.303224 3.888610 0.5091929 4.563767 1.661411 
[6,] 3.188290 3.304657 3.6668867 3.599771 3.453358 
[7,] 2.891969 2.823296 1.6926825 4.845681 1.544732 
[8,] 2.987394 1.553104 2.8849988 4.683407 2.000689 
[9,] 3.199353 2.822421 1.5221291 4.414465 1.078257 
[10,] 2.492993 2.994359 3.3573190 6.498129 3.337441