Finden Sie die geringsten Abstände zwischen den Zeilen einer großen Matrix: Allocation limit error

Question

Ich möchte die Abstände zwischen allen Zeilen einer großen Matrix berechnen. Für jede Zeile muss ich eine andere Zeile finden, die die geringste Entfernung hat. Die endgültige Ausgabe sollte eine Liste sein, die IDs der Zeilen mit den niedrigsten Abständen enthält (siehe Low_dis_ids im folgenden Beispiel).

Ich konnte eine Lösung für kleine Probengrößen finden (Beispiel unten). Allerdings kann ich diese Schritte nicht mit größeren Stichproben durchführen, da die Matrix mit den Abständen zu groß wird. Gibt es eine Möglichkeit, solch eine große Matrix wegzulassen? Ich brauche nur die Liste mit den IDs (wie low_dis_ids).

Reproduzierbare Beispiel:

set.seed(123) 

# Calculation of distances with small samplesize is working well 
N <- 100 
data_100 <- data.frame(x1 = rnorm(N, 5, 10), 
         x2 = rnorm(N, 5, 10), 
         x3 = rnorm(N, 5, 10), 
         x4 = rnorm(N, 5, 10), 
         x5 = rnorm(N, 5, 10)) 

# Matrix with all distances (no problem for the smaller samplesize) 
dist_100 <- as.matrix(dist(data_100)) 

# Find the row with the smallest distance 
for(i in 1:nrow(dist_100)) { 
    dist_100[i, i] <- Inf 
} 

low_dis <- numeric() 
for(i in 1:nrow(dist_100)) { 
    low_dis[i] <- as.numeric(sort(dist_100[ , i]))[1] 
} 

low_dis_ids <- list() 
for(i in 1:length(low_dis)) { 
    low_dis_ids[[i]] <- as.numeric(names(dist_100[ , i][dist_100[ , i] == low_dis[i]])) 
} 

# low_dis_ids is the desired output and stores the rows with the smallest distances 



# The same procedure is not working for larger samplesizes 
N <- 100000 
data_100000 <- data.frame(x1 = rnorm(N, 5, 10), 
          x2 = rnorm(N, 5, 10), 
          x3 = rnorm(N, 5, 10), 
          x4 = rnorm(N, 5, 10), 
          x5 = rnorm(N, 5, 10)) 
dist_100000 <- dist(data_100000) 

# Error: cannot allocate vector of size 37.3 Gb 

Answer 1

Sie können auf jeden Fall die Schaffung der großen Matrix vermeiden, die die Verwendung von dist als Ergebnis kommt. Eine solche Lösung besteht darin, die Abstände jeweils eine Zeile zu berechnen, wir könnten eine Funktion schreiben, die den gesamten Datenrahmen angibt, und eine Zeilen-ID findet heraus, welche Zeile der kleinsten Entfernung entspricht. Zum Beispiel:

f = function(rowid, whole){ 
    d = colSums((whole[rowid,] - t(whole))^2) # calculate distance 
    d[rowid] = Inf # replace the zero 
    which.min(d) 
} 

Die colSums Funktion optimiert ist ziemlich gut, so das relativ schnell. Ich vermute, which.min ist auch ein etwas schnellerer und möglicherweise sauberer Ansatz zum Durchlaufen der Vektoren von Entfernungen.

Um eine Lösung zu machen, die ich gilt dann für einen solchen Datenrahmen eine weitere kurze Funktion geschrieben, die diese jede Zeile bezieht und gibt Ihnen einen Vektor der Reihe ids

mindists = function(dat) do.call(c,lapply(1:nrow(dat),f,whole = as.matrix(dat))) 

Wenn Sie die Liste statt eines wollen Vektor, lassen Sie einfach die do.call Funktion weg. Ich hatte dies, um es einfacher zu machen, zu überprüfen, dass die Ausgabe das gab, was Sie erwartet hatten.

all(do.call(c,low_dis_ids) == mindists(data_100)) 
[1] TRUE 

Dies läuft auch für das größere Beispiel auf meinem Laptop. Es ist nicht schnell, weil Sie nrow(data) Aufrufe an f machen, aber es vermeidet die Erstellung eines großen Objekts. Es mag bessere Lösungen geben, aber das war die erste, die mir in den Sinn kam. Ich hoffe, das hilft.

EDIT:

Herausgegeben da es eine zusätzliche C++ Antwort von Roland ich auf dem kleineren Datensatz eine schnelle Benchmark tat. Die C++ Antwort ist in diesem Fall definitiv schneller. Einige zusätzliche Verkaufsargumente für diese Antwort ist es, ich denke, einfacher zu verstehen, wenn Sie nur ein R-Programmierer sind (keine Notwendigkeit, C++ und RCpp zu lernen). Die R-Version ist einfach zu parallelisieren mit einem parallelen Ersatz von lapply. Ich werde bemerken, dass das von Rolands Antwort nicht wegzunehmen ist, persönlich mag ich Rcpp, um nur Extra-Bits von Informationen für jeden zukünftigen Leser dieser Frage zu geben.

Answer 2

Verwendung RCPP da eine Basis R-Lösung wird zu langsam sein:

library(Rcpp) 
library(inline) 
cppFunction(
" IntegerVector findLowestDist(const NumericMatrix X) { 
    const int n = X.nrow(); 
    const int m = X.ncol(); 
    IntegerVector minind(n); 
    NumericVector minsqdist(n); 
    double d; 
    for (int i = 0; i < n; ++i) { 
     if (i == 0) { 
     d = 0; 
     for (int k = 0; k < m; ++k) { 
      d += pow(X(i, k) - X(1, k), 2.0); 

     } 
     minsqdist(i) = d; 
     minind(i) = 1; 
     } else { 
     d = 0; 
     for (int k = 0; k < m; ++k) { 
      d += pow(X(i, k) - X(0, k), 2.0); 

     } 
     minsqdist(i) = d; 
     minind(i) = 0; 
     } 

     for (int j = 1; j < n; ++j) { 
     if (i == j) continue; 
     d = 0; 
     for (int k = 0; k < m; ++k) { 
      d += pow(X(i, k) - X(j, k), 2.0); 

     } 
     if (d < minsqdist(i)) { 
      minsqdist(i) = d; 
      minind(i) = j; 
     } 
     } 
    } 
    return minind + 1; 
    }" 
) 

all.equal(findLowestDist(as.matrix(data_100)), 
      unlist(low_dis_ids)) 
#[1] TRUE 

findLowestDist(as.matrix(data_100000)) 
#works 

Der Algorithmus kann wahrscheinlich verbessert werden.