R_Finding the closest match from number of vectors

Question

I have the following vectors

> X <- c(1,1,3,4)
> a <- c(1,1,2,2)
> b <- c(2,1,4,3)
> c <- c(2,1,4,6)

I want to compare each element of X with corresponding elements of a,b and c and finally I need a class assigned to each row of X. for eg.

1. The first element of X is 1 and it has a match in corresponding element vector a, then I need to assign a class as '1-1' (no matter from which vector it got the match)

2. The second element of X is 1 and it also has match (in fact 3) so, again the class is '1-1'

3. The third element of X is 3 and it doesn't have a match then I should look for next integer value, which is 4 and there is 4 (in b and c). So the class should be '3-4'

4. The fourth element of X is 4 and it doesn't have a match. Also there is no 5 (next integer) then it should look for the previous integer which is 3 and there is 3. So the class should be '4-3'

Actually I have thousand of rows for each vector and I have to do this for each row. Any suggestion to do it in a less complicated way. I would prefer to use base functions of R.

Answer 1

Based on rbatt's comment and answer I realized my original answer was quite lacking. Here's a redo...

match_nearest <- function( x, table )
{
  dist <- x - table
  tgt <- which( dist < 0, arr.ind=TRUE, useNames=F )
  dist[tgt] <- abs( dist[tgt] + .5 )
  table[ cbind( seq_along(x), max.col( -dist, ties.method="first" ) ) ]
}

X <- c(1,1,3,4)
a <- c(1,1,2,2)
b <- c(2,1,4,3)
c <- c(2,1,4,6)

paste(X, match_nearest(X, cbind(a,b,c) ), sep="-")

## [1] "1-1" "1-1" "3-4" "4-3"

Compared to the original answer and rbatt's we find neither was correct!

set.seed(1)
X <- rbinom(n=1E4, size=10, prob=0.5)
a <- rbinom(n=1E4, size=10, prob=0.5)
b <- rbinom(n=1E4, size=10, prob=0.5)
c <- rbinom(n=1E4, size=10, prob=0.5)

T <- current_solution(X,a,b,c)
R <- rbatt_solution(X,a,b,c)
all.equal( T, R )

## [1] "195 string mismatches"

# Look at mismatched rows...
mismatch <- head( which( T != R ) )
cbind(X,a,b,c)[mismatch,]

##      X a b c
## [1,] 4 6 3 3
## [2,] 5 7 4 7
## [3,] 5 8 3 9
## [4,] 5 7 7 4
## [5,] 4 6 3 7
## [6,] 5 7 4 2

T[mismatch]

## [1] "4-3" "5-4" "5-3" "5-4" "4-3" "5-4"

R[mismatch]

## [1] "4-6" "5-7" "5-8" "5-7" "4-6" "5-7"

and needlessly slow...

library(microbenchmark)
bm <- microbenchmark( current_solution(X,a,b,c),
                      previous_solution(X,a,b,c),
                      rbatt_solution(X,a,b,c) )
print(bm, order="median")

## Unit: milliseconds
##                           expr    min     lq  median      uq    max neval
##   current_solution(X, a, b, c)  7.088  7.298   7.996   8.268  38.25   100
##     rbatt_solution(X, a, b, c) 33.920 38.236  46.524  53.441  85.50   100
##  previous_solution(X, a, b, c) 83.082 93.869 101.997 115.961 135.98   100

Looks like the current_solution is getting it right; but without an expected output ...

Here's the functions...

current_solution <- function(X,a,b,c) {
  paste(X, match_nearest(X, cbind(a,b,c) ), sep="-")
}

# DO NOT USE... it is wrong!
previous_solution <- function(X,a,b,c) {
  dat <- rbind(X,a,b,c)
  v <- apply(dat,2, function(v) {
    v2 <- v[1] - v
    v2[v2<0] <- abs( v2[v2<0]) - 1
    v[ which.min( v2[-1] ) + 1 ]
  })
  paste("X", v, sep="-")
}

# DO NOT USE... it is wrong!
rbatt_solution <- function(X,a,b,c) {
    mat <- cbind(X,a,b,c)
    diff.signed <- mat[,"X"]-mat[,c("a","b","c")]
    diff.break <- abs(diff.signed) + sign(diff.signed)*0.5
    min.ind <- apply(diff.break, 1, which.min)
    ind.array <- matrix(c(1:nrow(mat),min.ind), ncol=2)
    match.value <- mat[,c("a","b","c")][ind.array]
    ref.class <- paste(X, match.value, sep="-")
    ref.class
}

Answer 2

This solution should provide the output you want. Also, it is ~ 3x faster than Thell's solution, because the differences are vectorized and are not calculated row-wise with apply.

I compare times for the two approaches below. Note that if you want the "class" as another column in a data.frame, just uncomment the last line of my function. I commented it out to make the calculation times between the two answers more comparable (creating a data.frame is quite slow).

# Example data from Thell, plus 1 more
X1 <- c(1,1,3,4,7,1, 5)
a1 <- c(1,1,2,2,2,2, 9)
b1 <- c(2,1,4,3,3,3, 3)
c1 <- c(2,1,4,6,6,6, 7)

# Random example data, much larger
# X1 <- rbinom(n=1E4, size=10, prob=0.5)
# a1 <- rbinom(n=1E4, size=10, prob=0.5)
# b1 <- rbinom(n=1E4, size=10, prob=0.5)
# c1 <- rbinom(n=1E4, size=10, prob=0.5)

My answer:

rbTest <- function(){
    mat <- cbind(X1,a1,b1,c1)

    diff.signed <- mat[,"X1"]-mat[,c("a1","b1","c1")] # differences (with sign)
    diff.break <- abs(diff.signed) + sign(diff.signed)*0.5 # penalize for differences that are negative by adding 0.5 to them (break ties by preferring higher integer)

    min.ind <- apply(diff.break, 1, which.min) # index of smallest difference (prefer larger integers when there is a tie)
    ind.array <- matrix(c(1:nrow(mat),min.ind), ncol=2) # array index format

    match.value <- mat[,c("a1","b1","c1")][ind.array] # value of the smallest difference (value of the match)
    ref.class <- paste(X1, match.value, sep="-") # the 'class' in the format 'ref-match'
    ref.class
    # data.frame(class=ref.class, mat)
}

Thell answer:

thTest <- function(){
    dat <- rbind(X1,a1,b1,c1)
    apply(dat,2, function(v) {
      # Get distance
      v2 <- v[1] - v
      # Prefer values >= v[1]
      v2[v2<0] <- abs( v2[v2<0]) - 1
      # Obtain and return nearest v excluding v[1]
      v[ which.min( v2[-1] ) + 1 ]
    })
}

Benchmark on large matrix (10,000 rows)

# > microbenchmark(rbTest(), thTest())
# Unit: milliseconds
#      expr       min        lq    median        uq      max neval
#  rbTest()  47.95451  52.01729  59.36161  71.94076 103.1314   100
#  thTest() 167.49798 180.69627 195.02828 204.19916 315.0610   100

Benchmark on small matrix (7 rows)

# > microbenchmark(rbTest(), thTest())
# Unit: microseconds
#      expr     min       lq   median       uq     max neval
#  rbTest() 108.299 112.3550 115.4225 119.4630 146.722   100
#  thTest() 147.727 152.2015 155.9005 159.3115 235.898   100

Example output (small matrix):

# > rbTest()
# [1] "1-1" "1-1" "3-4" "4-3" "7-6" "1-2" "5-7" "6-1"
# > thTest()
# [1] 1 1 4 3 6 2 7