Calcolo della distanza di Hamming per due vettori in R?

Question

sto cercando solo di calcolare la distanza di Hamming tra due vettori a R. Attualmente sto tentando di usare il pacchetto "E1071", e la funzione hamming.distance, come segue:

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

Dove X è un data.frame con 2 file e (in particolare la mia dati) 667 colonne, ed ogni osservazione è 0 o 1.

Inizialmente ho ottenuto l'errore:

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

Dopo alcune ricerche, è emerso che una correzione potrebbe aumentare l'opzione di base in R. Questo l'ho fatto tramite opzioni (espressioni = 5000), e poi provato a valori variabili al posto del 5000. Ma questo prodotto solo l'errore:

Error: C stack usage is too close to the limit 

io non sono molto di un programmatore, e le correzioni per questo l'errore più recente sembra avere a che fare con qualcosa all'interno del pacchetto e1071 che potrebbe non essere chiamato correttamente (o al momento giusto).

Qualche idea su cosa sto facendo male? Alla fine voglio le distanze di Hamming tra un gran numero di vettori, e questo era solo un punto di partenza. Se questo ha a che fare con l'allocazione della memoria, qualche suggerimento su come affrontarlo?

Answer 1

io non so come funziona internamente hamming.distance, ma un modo semplice per calcolare la distanza per 2 vettori è solo

sum(x1 != x2) 

o, in questo caso,

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

Se il totale il numero di vettori non è troppo grande (fino a, per esempio qualche migliaio), è possibile implementarlo in un ciclo annidato:

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,]) 

Avvertenza: non testata.

Answer 2

hamming.distance prende due vettori o una matrice, ma non un frame di dati, in modo da ciò che si vuole è probabilmente uno

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

o

hamming.distance(as.matrix(X)) 

ma, come è stato sottolineato questo è in il tuo caso particolare è lo stesso di

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

(In generale, evitare data.frame s se quello che hai non è una struttura eterogenea dal momento che sono molto, molto più lento di matrici)

Answer 3

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

non so l'efficienza relativa delle 'XOR' a '! = '

Answer 4

AVVISO PER L'UTILIZZO DELLA MARTELLAZIONE. DISTANZA DAL PACCHETTO e1071!

L'implementazione di questo pacchetto obbliga gli oggetti confrontati ai booleani con as.logical. Ciò significa che i valori di 0 saranno FALSE e tutti i valori diversi da zero saranno VERO.Ciò significa che per la sequenza: 0 1 2 rispetto a 0 1 1 la distanza di hamming verrà riportata come 0 invece del valore corretto di 1 - questo pacchetto tratterà 1 e 2 come uguale poiché as.logical (1) == as.logical (2).

Ecco il guasto (a mio avviso) implementazione:

> 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> 

La mia raccomandazione: NON USARE. La distanza di Hamming è banale da implementare come notato più volte sopra.

Answer 5

Basta aggiungere al @HongOoi ci tengo a precisare che in R != e == ritorno NA quando uno dei valori manca, in modo che possa dare risultati fuorvianti

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

tuttavia %in% uscite FALSE per 1 %in% NA confronto. A causa di ciò, se quando si confrontano i vettori si desidera contare valori come "diverso" mancante, quindi è necessario utilizzare sum(!((x != y) %in% FALSE)) codice:

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

Si noti anche che potrebbe accadere che x e y vettori hanno lunghezza differente, quale sarebbe portare a valori mancanti nel vettore più breve - puoi fare due cose: troncare il vettore più lungo o affermare che i valori assenti nel vettore più breve sono "diversi". Questo potrebbe essere tradotto in funzione stand-alone con i parametri R familiari:

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)) 
} 

Questa funzione consente di scegliere se si desidera contare i valori mancanti come "diverso" (na.rm = FALSE) o ignorarli. Con na.rm = TRUE se i vettori differiscono nella loro lunghezza, il più lungo viene troncato.

Answer 6

Come aggiunta a tutto ciò che è stato menzionato sopra: sebbene la distanza di Hamming sia banale da implementare come un normale ciclo annidato, in termini di tempo di esecuzione le cose possono rapidamente sfuggire di mano a matrici più grandi. In R, è molto più efficiente utilizzare invece la moltiplicazione della matrice per calcolare la distanza di Hamming tra tutte le colonne di grandi matrici. Questo è estremamente veloce rispetto a un ciclo annidato a livello R. Un esempio di implementazione può essere trovato here.