R_Поиск ближайшего совпадения по количеству векторов

У меня есть следующие векторы

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

Я хочу сравнить каждый элемент X с соответствующими элементами a, b и c, и, наконец, мне нужен класс, назначенный каждой строке X. например.

  1. Первый элемент X равен 1, и он имеет совпадение в соответствующем векторе элементов a, тогда мне нужно назначить класс как '1-1' (независимо от того, из какого вектора он получил совпадение)

  2. Второй элемент X равен 1, и у него также есть совпадение (фактически 3), так что снова класс '1-1'

  3. Третий элемент X равен 3, и ему нет совпадения, тогда я должен искать следующее целочисленное значение, которое равно 4 и есть 4 (в b и c). Итак, класс должен быть «3-4».

  4. Четвертый элемент X равен 4, и ему нет совпадения. Также нет 5 (следующего целого числа), тогда он должен искать предыдущее целое число, которое равно 3 и есть 3. Таким образом, класс должен быть '4-3'

На самом деле у меня есть тысячи строк для каждого вектора, и я должен делать это для каждой строки. Любое предложение сделать это менее сложным способом. Я бы предпочел использовать базовые функции R.


person MaMu    schedule 08.05.2014    source источник
comment
Что было бы сделано на шаге 3, если бы не было 4 подходящих?   -  person alexis_laz    schedule 08.05.2014
comment
аналогично комментарию @alexis_laz на шаге 3, почему 3 не получает следующее самое близкое совпадение с 2 из вектора a? | 3-2 | = 1, | 4-2 | = 1, поэтому они кажутся мне одинаково далекими. Это просто правило тай-брейка? То есть, является ли правило, если более одного целочисленного значения одинаково хорошо совпадают, выбрать значение, которое больше ссылочного целого числа?   -  person rbatt    schedule 08.05.2014
comment
Да ... Вот что я хочу @rbatt   -  person MaMu    schedule 08.05.2014
comment
Ребят, а почему бы вам не выложить ответ, если есть решение? :)   -  person gagolews    schedule 08.05.2014
comment
Вы можете улучшить вопрос, включив ожидаемый результат.   -  person Thell    schedule 08.05.2014


Ответы (2)


Основываясь на комментарии и ответе rbatt, я понял, что моего первоначального ответа совершенно не хватало. Вот переделать ...

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"

По сравнению с исходным ответом и rbatt, мы обнаружили, что ни один из них не был правильным!

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"

и излишне медленно ...

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

Похоже, current_solution понимает это правильно; но без ожидаемого результата ...

Вот функции ...

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
}
person Thell    schedule 08.05.2014
comment
Это близко, но не совсем дает формат вывода 1-1, который запрашивал OP. - person rbatt; 09.05.2014
comment
@rbatt, спасибо, что указали на отсутствие данных "класса". Обновленный ответ. Похоже, у нас обоих были ошибки ... PS - Спасибо, что заставили меня подумать. :) - person Thell; 09.05.2014
comment
Я обновил свой ответ - у меня в конце было X, которое должно было быть X1. Хороший улов! Позже я еще разберусь с этим и посмотрю, согласен ли я с вашими сравнениями;) +1 - person rbatt; 09.05.2014

Это решение должно обеспечить желаемый результат. Кроме того, это примерно в 3 раза быстрее, чем решение Телла, потому что различия векторизованы и не вычисляются построчно с apply.

Я сравниваю время для двух подходов ниже. Обратите внимание: если вы хотите, чтобы «класс» был еще одним столбцом в data.frame, просто раскомментируйте последнюю строку моей функции. Я закомментировал это, чтобы время вычислений между двумя ответами было более сопоставимым (создание data.frame довольно медленное).

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

Мой ответ:

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

Весь ответ:

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

Тест на большой матрице (10 000 строк)

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

Тест на малой матрице (7 строк)

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

Пример вывода (малая матрица):

# > 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
person rbatt    schedule 08.05.2014