Calculando la distancia de Hamming para dos vectores en R?

Question

estoy tratando sólo para calcular la distancia de Hamming entre dos vectores en R. Actualmente estoy tratando de utilizar el paquete "e1071", y la función hamming.distance, de la siguiente manera:

library(e1071) 
H <- hamming.distance(X) 

Donde X es un hoja.de.datos con 2 filas y (en mi particular de datos) 667 columnas, y cada observación es 0 ó 1.

Inicialmente consiguieron el error:

Error: evaluation nested too deeply: infinite recursion/options(expressions=)? 

Después de algunas investigaciones, parece que una solución podría estar aumentando la opción básica en R. Esto lo hice a través de Opciones (expresiones = 5000), y luego trató de variar los valores en lugar del 5000. Pero esto sólo se produjo el error:

Error: C stack usage is too close to the limit 

No soy mucho de un programador, y las correcciones para este el error más reciente parece tener que ver con algo dentro del paquete e1071 que posiblemente no se haya llamado correctamente (o en el momento correcto).

¿Alguna idea sobre lo que estoy haciendo mal? Finalmente quiero las distancias de Hamming entre una gran cantidad de vectores, y esto fue solo un punto de partida. Si esto tiene que ver con la asignación de memoria, ¿hay alguna sugerencia sobre cómo manejarla?

Answer 1

No sé cómo funciona internamente hamming.distance, pero una forma sencilla de calcular la distancia de 2 vectores es sólo

sum(x1 != x2) 

o, en este caso,

sum(X[1,] != X[2,]) 

Si el total número de vectores no es demasiado grande (hasta, por ejemplo, algunos miles), puede implementar esto en un bucle anidado:

n <- nrow(X) 
m <- matrix(nrow=n, ncol=n) 
for(i in seq_len(n - 1)) 
    for(j in seq(i, n)) 
     m[j, i] <- m[i, j] <- sum(X[i,] != X[j,]) 

Advertencia: no probado.

Answer 2

hamming.distance toma dos vectores o una matriz, pero no una trama de datos, por lo que lo que desea es probable que sea

m = as.matrix(X) 
hamming.distance(m[1,], m[2,]) 

o

hamming.distance(as.matrix(X)) 

pero como se ha señalado que esto es en su caso particular es el mismo que

sum(m[1,] != m[2,]) 

(En general, evite data.frame s si lo que tienes no es una estructura heterogénea, ya que son mucho, mucho más lento que las matrices)

Answer 3

sum(xor(x[1,],x[2,])) 

No sé la eficiencia relativa de 'XOR' a '! = '

Answer 4

ADVERTENCIA SOBRE EL USO DE HAMMING.DISTANCE FROM PACKAGE e1071!

La implementación de este paquete obliga a los objetos que se comparan con booleanos con as.logical. Esto significa que los valores de 0 serán FALSOS y cualquier valor distinto de cero será VERDADERO.Esto significa que para la secuencia: 0 1 2 en comparación con 0 1 1, la distancia de hamming se informará como 0 en lugar del valor correcto de 1; este paquete tratará a 1 y 2 como iguales, ya que as.logical (1) == as.logical (2).

Aquí es el defectuoso (en mi opinión) aplicación:

> library("e1071", lib.loc="C:/Program Files/R/R-2.15.3/library") 
    Loading required package: class 
    > hamming.distance 
    function (x, y) 
    { 
     z <- NULL 
     if (is.vector(x) && is.vector(y)) { 
      z <- sum(as.logical(x) != as.logical(y)) 
     } 
     else { 
      z <- matrix(0, nrow = nrow(x), ncol = nrow(x)) 
      for (k in 1:(nrow(x) - 1)) { 
       for (l in (k + 1):nrow(x)) { 
        z[k, l] <- hamming.distance(x[k, ], x[l, ]) 
        z[l, k] <- z[k, l] 
       } 
      } 
      dimnames(z) <- list(dimnames(x)[[1]], dimnames(x)[[1]]) 
     } 
     z 
    } 
    <environment: namespace:e1071> 

Mi recomendación: NO USE. La distancia de Hamming es trivial de implementar como se señaló varias veces más arriba.

Answer 5

Simplemente añadiendo a @HongOoi quiero señalar que en I != y == retorno NA cuando uno de los valores no se encuentra, por lo que podría dar resultados engañosos

> c(1, NA) == 1:2 
[1] TRUE NA 

embargo %in% salidas FALSE para 1 %in% NA comparación. Debido a que si al comparar los vectores que desea contar valores como "diferente" encuentra, entonces usted tiene que utilizar sum(!((x != y) %in% FALSE)) código:

> x <- c(1, 8, 5, NA, 5) 
> y <- 1:5 
> sum(!((x != y) %in% FALSE)) 
[1] 3 

Nótese también que podría suceder que x y y vectores tienen diferente longitud, lo que haría conducir a valores perdidos en el vector más corto; puede hacer dos cosas: truncar el vector más largo o afirmar que los valores ausentes en el vector más corto son "diferentes". Esto podría traducirse en función independiente con parámetros R familiares:

hamming <- function(x, y, na.rm = TRUE) { 
    size <- 1:max(length(x) & length(y)) 
    x <- x[size] 
    y <- y[size] 
    if (na.rm) { 
    del <- is.na(x) & is.na(y) 
    x <- x[del] 
    y <- y[del] 
    } 
    sum(!((x != y) %in% FALSE)) 
} 

Esta función le permite elegir si desea contar con valores perdidos como "diferente" (na.rm = FALSE) o ignorarlas. Con na.rm = TRUE si los vectores difieren en su longitud, el más largo se trunca.

Answer 6

Como una adición a todo lo mencionado anteriormente: Aunque la distancia de Hamming es trivial de implementar como un bucle anidado ordinario, en términos de tiempo de ejecución las cosas pueden salirse de control rápidamente para matrices más grandes. En R, es mucho más eficiente utilizar la multiplicación de matrices para calcular la distancia de Hamming entre todas las columnas de matrices grandes. Esto es extremadamente rápido en comparación con un bucle anidado de nivel R. Se puede encontrar una implementación de ejemplo here.