Вычисление расстояния Хэмминга для двух векторов в R?

Question

Я пытаюсь просто вычислить расстояние Хемминга между двумя векторами в R. В настоящее время я пытаюсь использовать пакет "e1071" и функцию hamming.distance следующим образом:

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

Где X - это data.frame с 2 строками и (в моих конкретных данных) 667 столбцами, а каждое наблюдение - 0 или 1.

Изначально я получил ошибку:

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

После некоторых исследований выяснилось, что одним исправлением может быть увеличение базовой опции в R. Это я сделал через опции (выражения = 5000), а затем попытался варьировать значения вместо 5000. Но это только вызвало ошибку:

Error: C stack usage is too close to the limit

Я не большой программист, и исправления этой самой последней ошибки, похоже, связаны с чем-то внутри пакета e1071, возможно, вызванным неправильно (или в нужное время).

Есть идеи, что я делаю не так? В конце концов я хочу расстояния Хэмминга между большим числом векторов, и это было только отправной точкой. Если это связано с распределением памяти, какие-либо предложения о том, как с этим бороться?

Answer 1

Я не знаю, как hamming.distance работает внутри, но простой способ рассчитать расстояние для 2 векторов это просто

sum(x1 != x2)

или, в данном случае,

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

Если общее число векторов не слишком велико (скажем, до нескольких тысяч), вы можете реализовать это во вложенном цикле:

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

Предупреждение: непроверено.

Answer 2

ПРЕДУПРЕЖДЕНИЕ О ИСПОЛЬЗОВАНИИ HAMMING.DISTANCE ИЗ ПАКЕТА e1071!

Реализация этого пакета принудительно сравнивает объекты с логическими значениями с помощью as.logical. Это означает, что значения 0 будут FALSE, а любые ненулевые значения будут TRUE. Это означает, что для последовательности: 0 1 2 по сравнению с 0 1 1 расстояние Хемминга будет отображаться как 0 вместо правильного значения 1 - этот пакет будет обрабатывать 1 и 2 как равные, поскольку as.logical (1) == as.logical (2).

Вот неправильная (на мой взгляд) реализация:

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

Моя рекомендация: НЕ ИСПОЛЬЗОВАТЬ. Расстояние Хэмминга тривиально для реализации, как отмечалось несколько раз выше.

Answer 3

hamming.distance занимает два вектора или матрицы, но не фрейм данных, так что вы, вероятно, хотите либо

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

или

hamming.distance(as.matrix(X))

но, как было указано, в вашем конкретном случае это то же самое, что и

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

(В общем, избегайте data.frame s, если то, что у вас есть, не является гетерогенной структурой, поскольку они намного, намного медленнее, чем матрицы)

Answer 4

Как дополнение ко всему, что было упомянуто выше: хотя расстояние Хэмминга тривиально для реализации в виде обычного вложенного цикла, с точки зрения времени выполнения вещи могут быстро выйти из-под контроля для больших матриц. В R гораздо эффективнее использовать матричное умножение для вычисления расстояния Хэмминга между всеми столбцами больших матриц. Это очень быстро по сравнению с вложенным циклом R-уровня. Пример реализации можно найти здесь .

Answer 5

Просто добавив к @ HongOoi Я хочу указать, что в R != и == возвращают NA, если одно из значений отсутствует, поэтому это может дать неверные результаты

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

однако %in% выводит FALSE для 1 %in% NA сравнения.Из-за этого, если при сравнении векторов вы хотите считать пропущенные значения как «разные», то вы должны использовать sum(!((x != y) %in% FALSE)) код:

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

Также обратите внимание, что может случиться так, что x и y векторы имеют разную длину, что может привести к отсутствию значений в более коротком векторе - вы можете сделать две вещи: усечь более длинный вектор или заявить, что значения, отсутствующие в более коротком векторе, «различны».Это можно перевести в автономную функцию со знакомыми параметрами R:

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

Эта функция позволяет вам выбрать, хотите ли вы считать пропущенные значения как «разные» (na.rm = FALSE) или игнорировать их.При na.rm = TRUE, если векторы различаются по длине, более длинный усекается.

Answer 6

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

Я не знаю относительную эффективность от 'xor' до '! ='