Calcule la matriz de distancia euclidiana usando un objeto big.matrix

bigdata sparse-matrix

Question

Tengo un objeto de clase big.matrix en R con dimensión 778844 x 2 . Los valores son todos enteros (kilómetros). Mi objetivo es calcular la matriz de distancia euclidiana usando big.matrix y tener como resultado un objeto de clase big.matrix . Me gustaría saber si hay una forma óptima de hacerlo.

La razón de mi elección para usar la clase big.matrix es la limitación de memoria. Podría transformar mi big.matrix en un objeto de matrix de clase y calcular la matriz de distancia euclidiana usando dist() . Sin embargo, dist() devolvería un objeto de tamaño que no se asignaría en la memoria.

Editar

La siguiente respuesta fue dada por John W. Emerson, autor y mantenedor del paquete bigmemory :

Podrías usar el álgebra grande que espero, pero este también sería un buen caso de uso para Rcpp a través de sourceCpp (), y muy corto y fácil. Pero, en resumen, ni siquiera intentamos proporcionar funciones de alto nivel (que no sean los conceptos básicos que implementamos como prueba de concepto). Ningún algoritmo único podría cubrir todos los casos de uso una vez que comience a hablar de falta de memoria grande.

Answer 1

Aquí hay una forma de usar RcppArmadillo . Gran parte de esto es muy similar al ejemplo de RcppGallery . Esto devolverá una big.matrix con las distancias big.matrix pairwise asociadas (por fila) asociadas. Me gusta ajustar mis funciones big.matrix en una función de contenedor para crear una sintaxis más limpia (es decir, evitar la @address y otras inicializaciones).

Nota: como usamos bigmemory (y, por lo tanto, preocupado por el uso de RAM), este ejemplo arrojó la matriz N-1 x N-1 de solo elementos triangulares inferiores. Podrías modificar esto pero esto es lo que lancé.

euc_dist.cpp

// To enable the functionality provided by Armadillo''s various macros,
// simply include them before you include the RcppArmadillo headers.
#define ARMA_NO_DEBUG

#include <RcppArmadillo.h>
// [[Rcpp::depends(RcppArmadillo, BH, bigmemory)]]

using namespace Rcpp;
using namespace arma;

// The following header file provides the definitions for the BigMatrix
// object
#include <bigmemory/BigMatrix.h>

// C++11 plugin
// [[Rcpp::plugins(cpp11)]]

template <typename T>
void BigArmaEuclidean(const Mat<T>& inBigMat, Mat<T> outBigMat) {

  int W = inBigMat.n_rows;

  for(int i = 0; i < W - 1; i++){
      for(int j=i+1; j < W; j++){
          outBigMat(j-1,i) = sqrt(sum(pow((inBigMat.row(i) - inBigMat.row(j)),2)));
      }
  }
}

// [[Rcpp::export]]
void BigArmaEuc(SEXP pInBigMat, SEXP pOutBigMat) {
  // First we tell Rcpp that the object we''ve been given is an external
  // pointer.
  XPtr<BigMatrix> xpMat(pInBigMat);
  XPtr<BigMatrix> xpOutMat(pOutBigMat);


  int type = xpMat->matrix_type();
  switch(type) {
      case 1:
        BigArmaEuclidean(
            arma::Mat<char>((char *)xpMat->matrix(), xpMat->nrow(), xpMat->ncol(), false),
            arma::Mat<char>((char *)xpOutMat->matrix(), xpOutMat->nrow(), xpOutMat->ncol(), false)
        );
        return;

      case 2:
        BigArmaEuclidean(
          arma::Mat<short>((short *)xpMat->matrix(), xpMat->nrow(), xpMat->ncol(), false),
          arma::Mat<short>((short *)xpOutMat->matrix(), xpOutMat->nrow(), xpOutMat->ncol(), false)
        );
        return;

      case 4:
        BigArmaEuclidean(
          arma::Mat<int>((int *)xpMat->matrix(), xpMat->nrow(), xpMat->ncol(), false),
          arma::Mat<int>((int *)xpOutMat->matrix(), xpOutMat->nrow(), xpOutMat->ncol(), false)
        );
        return;

      case 8:
        BigArmaEuclidean(
          arma::Mat<double>((double *)xpMat->matrix(), xpMat->nrow(), xpMat->ncol(), false),
          arma::Mat<double>((double *)xpOutMat->matrix(), xpOutMat->nrow(), xpOutMat->ncol(), false)
        );
        return;

      default:
        // We should never get here, but it resolves compiler warnings.
        throw Rcpp::exception("Undefined type for provided big.matrix");
  }

}

Mi pequeño envoltorio

bigMatrixEuc <- function(bigMat){
    zeros <- big.matrix(nrow = nrow(bigMat)-1,
                        ncol = nrow(bigMat)-1,
                        init = 0,
                        type = typeof(bigMat))
    BigArmaEuc(bigMat@address, zeros@address)
    return(zeros)
}

La prueba

library(Rcpp)
sourceCpp("euc_dist.cpp")

library(bigmemory)

set.seed(123)
mat <- matrix(rnorm(16), 4)
bm <- as.big.matrix(mat)

# Call new euclidean function
bm_out <- bigMatrixEuc(bm)[]

# pull out the matrix elements for out purposes
distMat <- as.matrix(dist(mat))
distMat[upper.tri(distMat, diag=TRUE)] <- 0
distMat <- distMat[2:4, 1:3]

# check if identical 
all.equal(bm_out, distMat, check.attributes = FALSE)
[1] TRUE