Rechnen paarweise Hamming Abstand zwischen allen Reihen von zwei ganzzahligen Matrizen/Datenrahmen

Question

Ich habe zwei Datenrahmen, df1 mit Referenzdaten und df2 mit neuen Daten. Für jede Reihe in df2, muss ich die beste (und die zweitbeste) passende Zeile zu df1 in Bezug auf Hamming-Abstand finden.

Ich habe e1071 Paket verwendet, um Hamming-Abstand zu berechnen. Hamming-Distanz zwischen zwei Vektoren x und y können als beispielsweise berechnet werden:

x <- c(356739, 324074, 904133, 1025460, 433677, 110525, 576942, 526518, 299386, 
     92497, 977385, 27563, 429551, 307757, 267970, 181157, 3796, 679012, 711274, 
     24197, 610187, 402471, 157122, 866381, 582868, 878) 

y <- c(356739, 324042, 904133, 959893, 433677, 110269, 576942, 2230, 267130, 
     92496, 960747, 28587, 429551, 438825, 267970, 181157, 36564, 677220, 
     711274, 24485, 610187, 404519, 157122, 866413, 718036, 876) 

xm <- sapply(x, intToBits) 
ym <- sapply(y, intToBits) 

distance <- sum(sapply(1:ncol(xm), function(i) hamming.distance(xm[,i], ym[,i]))) 

und der resultierende Abstand ist 25. Dennoch muss ich tun dies für alle Reihen von df1 und df2. Eine triviale Methode benötigt ein doppeltes Loop-Nest und sieht schrecklich langsam aus.

Irgendwelche Ideen, wie man das effizienter macht? Am Ende muss ich df2 anfügen:

• eine Spalte mit der Reihe von ID df1, die den niedrigsten Abstand ergibt;
• eine Spalte mit dem niedrigsten Abstand;
• eine Spalte mit der Zeilen-ID von df1, die den zweitniedrigsten Abstand ergibt;
• eine Spalte mit dem zweitniedrigsten Abstand.

Danke.

Answer 1

schnelle Berechnung der Hamming-Distanz zwischen zwei ganzen Zahlen Vektoren gleicher Länge

Wie ich in meinem Kommentar gesagt, was wir tun können:

hmd0 <- function(x,y) sum(as.logical(xor(intToBits(x),intToBits(y)))) 

zu Hamming-Distanz zwischen zwei ganzen Zahlen Vektoren berechnen von gleiche Längex und y. Dies verwendet nur R-Basis, ist aber effizienter als e1071::hamming.distance, , weil es vektorisiert ist!

Für das Beispiel x und y in Ihrem Beitrag, gibt dieser 25. (Meine andere Antwort wird zeigen, was wir tun sollten, wenn wir paarweise Hammingabstands wollen.)

---

Schnell Hamming Abstand zwischen einer Matrix und einem Vektor

Wenn wir die Hamming-Distanz zwischen einem einzigen y und mehreren x s berechnen möchten, dh die Hamm Abstand zwischen einem Vektor und einer Matrix können wir die folgende Funktion verwenden.

hmd <- function(x,y) { 
    rawx <- intToBits(x) 
    rawy <- intToBits(y) 
    nx <- length(rawx) 
    ny <- length(rawy) 
    if (nx == ny) { 
    ## quick return 
    return (sum(as.logical(xor(rawx,rawy)))) 
    } else if (nx < ny) { 
    ## pivoting 
    tmp <- rawx; rawx <- rawy; rawy <- tmp 
    tmp <- nx; nx <- ny; ny <- tmp 
    } 
    if (nx %% ny) stop("unconformable length!") else { 
    nc <- nx/ny ## number of cycles 
    return(unname(tapply(as.logical(xor(rawx,rawy)), rep(1:nc, each=ny), sum))) 
    } 
    } 

Beachten Sie, dass:

1. hmd Berechnung führt spaltenweise. Es wurde entwickelt, um CPU-Cache-freundlich zu sein.Auf diese Weise sollten wir, wenn wir eine zeilenweise Berechnung durchführen wollen, zuerst die Matrix transponieren;
2. gibt es hier keine offensichtliche Schleife; Stattdessen verwenden wir tapply().

---

Schnelle Hamming-Distanz Berechnung zwischen zwei Matrizen/Datenrahmen

Dies ist, was Sie wollen. Die folgende Funktion foo benötigt zwei Datenrahmen oder Matrizen df1 und df2, wobei der Abstand zwischen df1 und jeder Zeile df2 berechnet wird. Das Argument ist eine Ganzzahl, die angibt, wie viele Ergebnisse Sie beibehalten möchten. p = 3 behält die kleinsten 3 Abstände mit ihren Zeilennummern in df1.

foo <- function(df1, df2, p) { 
    ## check p 
    if (p > nrow(df2)) p <- nrow(df2) 
    ## transpose for CPU cache friendly code 
    xt <- t(as.matrix(df1)) 
    yt <- t(as.matrix(df2)) 
    ## after transpose, we compute hamming distance column by column 
    ## a for loop is decent; no performance gain from apply family 
    n <- ncol(yt) 
    id <- integer(n * p) 
    d <- numeric(n * p) 
    k <- 1:p 
    for (i in 1:n) { 
    distance <- hmd(xt, yt[,i]) 
    minp <- order(distance)[1:p] 
    id[k] <- minp 
    d[k] <- distance[minp] 
    k <- k + p 
    } 
    ## recode "id" and "d" into data frame and return 
    id <- as.data.frame(matrix(id, ncol = p, byrow = TRUE)) 
    colnames(id) <- paste0("min.", 1:p) 
    d <- as.data.frame(matrix(d, ncol = p, byrow = TRUE)) 
    colnames(d) <- paste0("mindist.", 1:p) 
    list(id = id, d = d) 
    } 

Beachten Sie, dass:

1. Umsetzung am Anfang geschehen ist, nach zuvor Gründen;
2. Eine for Schleife wird hier verwendet. Dies ist jedoch tatsächlich effizient, da in jeder Iteration beträchtliche Berechnungen durchgeführt werden. Es ist auch eleganter als mit *apply Familie, da wir für mehrere Ausgabe (Zeile ID id und Abstand d) fragen.

---

Experiment

Dieser Teil verwendet kleine Dataset unsere Funktionen zu testen/demonstrieren.

Einige Spielzeug Daten:

set.seed(0) 
df1 <- as.data.frame(matrix(sample(1:10), ncol = 2)) ## 5 rows 2 cols 
df2 <- as.data.frame(matrix(sample(1:6), ncol = 2)) ## 3 rows 2 cols 

-Test hmd erste (benötigt Umsetzung):

hmd(t(as.matrix(df1)), df2[1, ]) ## df1 & first row of df2 
# [1] 2 4 6 2 4 

-Test foo:

foo(df1, df2, p = 2) 

# $id 
# min1 min2 
# 1 1 4 
# 2 2 3 
# 3 5 2 

# $d 
# mindist.1 mindist.2 
# 1   2   2 
# 2   1   3 
# 3   1   3 

Wenn Sie einige Spalten df2 anhängen möchten, Du weißt was zu tun ist, oder?

Answer 2

Bitte seien Sie nicht überrascht, warum ich einen anderen Abschnitt nehme. Dieser Teil gibt etwas Relevantes. Es ist nicht, was OP verlangt, aber kann jedem Leser helfen.

---

Allgemein Hammingdistanz Berechnungs

In der vorherige Antwort beginne ich aus einer Funktion hmd0 die Hamming-Distanz zwischen zwei ganzzahligen Vektoren derselben Länge berechnet.Dies bedeutet, wenn wir zwei Integer-Vektoren haben:

set.seed(0) 
x <- sample(1:100, 6) 
y <- sample(1:100, 6) 

wir mit einem Skalar am Ende:

hmd0(x,y) 
# 13 

Was passiert, wenn wir paarweise Hamming-Distanz von zwei Vektoren berechnen möchten?

In der Tat eine einfache Modifikation unserer Funktion hmd tun:

hamming.distance <- function(x, y, pairwise = TRUE) { 
    nx <- length(x) 
    ny <- length(y) 
    rawx <- intToBits(x) 
    rawy <- intToBits(y) 
    if (nx == 1 && ny == 1) return(sum(as.logical(xor(intToBits(x),intToBits(y))))) 
    if (nx < ny) { 
    ## pivoting 
    tmp <- rawx; rawx <- rawy; rawy <- tmp 
    tmp <- nx; nx <- ny; ny <- tmp 
    } 
    if (nx %% ny) stop("unconformable length!") else { 
    bits <- length(intToBits(0)) ## 32-bit or 64 bit? 
    result <- unname(tapply(as.logical(xor(rawx,rawy)), rep(1:ny, each = bits), sum)) 
    } 
    if (pairwise) result else sum(result) 
    } 

Jetzt

hamming.distance(x, y, pairwise = TRUE) 
# [1] 0 3 3 2 5 0 
hamming.distance(x, y, pairwise = FALSE) 
# [1] 13 

---

Hamming-Distanz Matrix

Wenn wir das berechnen wollen Hamming-Distanz-Matrix, zum Beispiel mple,

set.seed(1) 
x <- sample(1:100, 5) 
y <- sample(1:100, 7) 

Die Distanzmatrix zwischen x und y ist:

outer(x, y, hamming.distance) ## pairwise argument has no effect here 

#  [,1] [,2] [,3] [,4] [,5] [,6] [,7] 
# [1,] 2 3 4 3 4 4 2 
# [2,] 7 6 3 4 3 3 3 
# [3,] 4 5 4 3 6 4 2 
# [4,] 2 3 2 5 6 4 2 
# [5,] 4 3 4 3 2 0 2 

Wir können auch tun:

outer(x, x, hamming.distance) 

#  [,1] [,2] [,3] [,4] [,5] 
# [1,] 0 5 2 2 4 
# [2,] 5 0 3 5 3 
# [3,] 2 3 0 2 4 
# [4,] 2 5 2 0 4 
# [5,] 4 3 4 4 0 

Im letzteren Fall können wir mit einer symmetrischen Matrix am Ende mit 0 auf der Diagonale. Die Verwendung von outer ist hier ineffizient, aber es ist immer noch effizienter als das Schreiben von R-Schleifen. Da unsere hamming.distance in R-Code geschrieben ist, würde ich bei der Verwendung von outer bleiben. In my answer zu this question demonstriere ich die Idee, kompilierten Code zu verwenden. Dies erfordert natürlich das Schreiben einer C-Version von hamming.distance, aber ich werde es hier nicht zeigen.

Answer 3

Hier ist eine alternative Lösung, die nur Basis R verwendet, und sollte sehr schnell sein, besonders wenn Ihre df1 und df2 viele Zeilen haben. Der Hauptgrund hierfür ist, dass keine beliebige R-Level-Schleifen zur Berechnung der Hamming-Distanzen verwendet werden, wie zum Beispiel For-Schleifen, While-Schleifen oder * Funktionen anwenden. Stattdessen verwendet es matrix multiplication for computing the Hamming distance. In R ist dies viel schneller als bei jedem Ansatz mit R-Level-Looping. Beachten Sie auch, dass die Verwendung einer * apply-Funktion Ihren Code nicht unbedingt schneller macht als die Verwendung einer for-Schleife. Zwei weitere effizienzbezogene Merkmale dieses Ansatzes sind: (1) Er verwendet partial sorting zum Finden der besten zwei Übereinstimmungen für jede Zeile in df2 und (2) Er speichert die gesamte bitweise Darstellung von df1 in einer Matrix (dasselbe für df2). und dies in einem einzigen Schritt, ohne irgendwelche R-Pegel-Schleifen zu verwenden.

Die Funktion, die die ganze Arbeit:

# INPUT:  
# X corresponds to your entire df1, but is a matrix 
# Y corresponds to your entire df2, but is a matrix 
# OUTPUT: 
# Matrix with four columns corresponding to the values 
# that you specified in your question 
fun <- function(X, Y) { 

    # Convert integers to bits 
    X <- intToBits(t(X)) 
    # Reshape into matrix 
    dim(X) <- c(ncols * 32, nrows) 

    # Convert integers to bits 
    Y <- intToBits(t(Y)) 
    # Reshape into matrix 
    dim(Y) <- c(ncols * 32, nrows) 

    # Calculate pairwise hamming distances using matrix 
    # multiplication. 
    # Columns of H index into Y; rows index into X. 
    # The code for the hamming() function was retrieved 
    # from this page: 
    # https://johanndejong.wordpress.com/2015/10/02/faster-hamming-distance-in-r-2/ 
    H <- hamming(X, Y) 

    # Now, for each row in Y, find the two best matches 
    # in X. In other words: for each column in H, find 
    # the two smallest values and their row indices. 
    t(apply(H, 2, function(h) { 
    mindists <- sort(h, partial = 1:2) 
    c(
     ind1 = which(h == mindists[1])[1], 
     val1 = mindists[1], 
     hmd2 = which(h == mindists[2])[1], 
     val2 = mindists[2] 
    ) 
    })) 
} 

die Funktion auf einige zufällige Daten abzurufen:

# Generate some random test data with no. of columns 
# corresponding to your data 
nrows <- 1000 
ncols <- 26 

# X corresponds to your df1 
X <- matrix(
    sample(1e6, nrows * ncols, replace = TRUE), 
    nrow = nrows, 
    ncol = ncols 
) 

# Y corresponds to your df2 
Y <- matrix(
    sample(1e6, nrows * ncols, replace = TRUE), 
    nrow = nrows, 
    ncol = ncols 
) 

res <- fun(X, Y) 

Das obige Beispiel mit 1000 Zeilen in sowohl X (df1) und Y (df2) brauchte ca. 1,1 - 1,2 Sekunden um auf meinem Laptop zu laufen.