Выберите уникальные пары x и y, чтобы минимизировать значение

Question

Мне нужно выбрать уникальный ID.x для каждого ID.y (формируя уникальные пары), который минимизирует значение расстояния, начиная с самых низких значений расстояния.Я чувствую, что это немного похоже на головоломку судоку, потому что каждый x и y может использоваться только один раз, поэтому информация из каждой пары позволяет сопоставлять другие пары.

В приведенном ниже примере лучше использовать ID.x 55соответствует для ID.y 1, чем для ID.x 56, потому что ID.x 56 лучше подходит для ID.y 2. Аналогично, ID.x 58 можно сопоставить с ID.y 4, потому что любой другой доступный параметр будетбольшее расстояние, и ID.y 5 может затем взять ID.x 59 на расстоянии 4. Однако ID.y 7 не может быть сопоставлен, поскольку ID.x 61 и ID.x 62 одинаково близки.

Пример:

DT = data.table(
  ID.x = c("55", "55", "55", "55", "55", "55", "55", "56", "56", "56", "56", "56", "56", "56", "57", "57", "57", "57", "57", "57", "57", "58", "58", "58", "58", "58", "58", "58", "59", "59", "59", "59", "59", "59", "59", "60", "60", "60", "60", "60", "60", "60", "61", "61", "61", "61", "61", "61", "61", "62", "62", "62", "62", "62", "62", "62"),
  ID.y = c("1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7", "1", "2", "3", "4", "5", "6", "7"),
  distance = c("2", "3", "3", "4", "6", "6", "7", "2", "1", "2", "5", "5", "5", "6", "4", "4", "3", "5", "5", "5", "6", "5", "5", "5", "4", "4", "5", "6", "7", "7", "7", "6", "4", "6", "7", "6", "6", "6", "6", "4", "2", "5", "7", "7", "7", "7", "5", "5", "5", "6", "6", "6", "6", "4", "4", "5")
  )

Цель:

   ID.x ID.y distance
1:   55    1        2
2:   56    2        1
3:   57    3        3
4:   58    4        4
5:   59    5        4
6:   60    6        2
7:   NA    7        NA

Эта первая попытка , вдохновленная этим вопросом , не работает:

DT[DT[, .I[distance == min(distance)], by=ID.x]$V1][DT[, .I[1], by = ID.y]$V1]

ОБНОВЛЕНИЕ: В ответ на ответы @ chinsoon12 и @ paweł-chabros, вот обновленный файл data.table, в котором исправлено несколько вещей.Он меняет местами x и y (мой первоначальный вопрос - сопоставление x с y, но более естественная интерпретация - y с x).В этом примере удаляется неоднозначное сопоставление для ID.y 7. В этом примере наименьшее расстояние соответствует ID.x 63. Отдельно я также добавил новый ID.y 8, чтобы уточнить, когда однозначное сопоставление невозможно (оно соответствует ID.х 64 и 65 одинаково хорошо).Ответ не должен выбирать совпадение произвольно.

DT = data.table(
  ID.y = c("55", "55", "55", "55", "55", "55", "55", "55", "56", "56", "56", "56", "56", "56", "56", "56", "57", "57", "57", "57", "57", "57", "57", "57", "58", "58", "58", "58", "58", "58", "58", "58", "59", "59", "59", "59", "59", "59", "59", "59", "60", "60", "60", "60", "60", "60", "60", "60", "61", "61", "61", "61", "61", "61", "61", "61", "62", "62", "62", "62", "62", "62", "62", "62", "63", "63", "63", "63", "63", "63", "63", "63", "64", "64", "64", "64", "64", "64", "64", "64", "65", "65", "65", "65", "65", "65", "65", "65"),
  ID.x = c("1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8", "1", "2", "3", "4", "5", "6", "7", "8"),
  distance = c(2, 3, 3, 4, 6, 6, 7, 15, 2, 1, 2, 5, 5, 5, 6, 15, 4, 4, 3, 5, 5, 5, 6, 15, 5, 5, 5, 4, 4, 5, 6, 15, 7, 7, 7, 6, 4, 6, 7, 15, 6, 6, 6, 6, 4, 2, 5, 15, 7, 7, 7, 7, 5, 5, 6, 15, 6, 6, 6, 6, 4, 4, 10, 15, 11, 11, 11, 11, 11, 11, 5, 12, 11, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 11, 11, 1)
  )

Ожидаемый результат:

   ID.y ID.x distance
1:   55    1        2
2:   56    2        1
3:   57    3        3
4:   58    4        4
5:   59    5        4
6:   60    6        2
7:   63    7        5
8:   NA    8        NA

Я использую этот код для завершения нечеткого соединения с использованием stringdist_join, как описано в этом вопросе. У меня естьдва набора данных, которые нуждаются в сопоставлении (отсюда ID.x и ID.y).В моем случае у меня есть оценки до и после теста, которые должны соответствовать нескольким ненадежным характеристикам.

Answer 1

Я не знаю data.table, так что я могу дать вам только tidyverse решение.Но, возможно, это поможет вам:)

library(tidyverse)

ID_y <- unique(DT$ID.y)

DT %>%
  as_tibble() %>%
  group_by(ID.x) %>%
  mutate(min_dist = min(distance)) %>%
  arrange(min_dist) %>%
  nest() %>%
  mutate(data = data %>% map(~ {
    min_row <- .x %>%
      filter(ID.y %in% ID_y) %>%
      filter(distance == min(distance)) %>%
      slice(1)
    ID_y <<- ID_y[ID_y != min_row$ID.y]
    min_row
  })) %>%
  unnest() %>%
  select(-min_dist) %>%
  arrange(ID.x)

Я сохраняю все уникальные значения ID.y.Затем я вычисляю минимальное расстояние для всех комбинаций и подстраиваюсь по этому минимальному расстоянию, чтобы сначала заняться этими в цикле map.После фильтрации минимального расстояния я удаляю ID.y из вектора, поэтому другие ID.x ищут только в оставшихся ID.y.

Answer 2

Мне непонятно, почему ID.x 62 и ID.y 7 расстояние 5 неосуществимо.

Предполагая, что ID.x 62, ID.y 7 и расстояние 5 приемлемо, возможный подходиспользуя data.table:

setorder(DT, distance)
choseny <- c()
ans <- DT[,
    {
        y <- setdiff(ID.y, choseny)[1L]
        choseny <- c(choseny, y)  
        .(ID.y=y, dist=.SD[ID.y==y, distance[1L]])
    },
    by=.(ID.x)]
setorder(ans, ID.x)[]

вывод:

   ID.x ID.y dist
1:   55    1    2
2:   56    2    1
3:   57    3    3
4:   58    4    4
5:   59    5    4
6:   60    6    2
7:   61 <NA> <NA>
8:   62    7    5

Answer 3

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

 DT[, .(ID.y
     , distance
     , Row.Num = rank(distance)
     , Row.Num.ID = rank(ID.y)), by = list(ID.x)][, .SD[Row.Num == min(Row.Num) ], by = ID.x][, .SD[Row.Num.ID == min(Row.Num.ID) ], by = ID.x] 
 >  ID.x ID.y distance Row.Num Row.Num.ID
1:   55    1        2     1.0          1
2:   56    2        1     1.0          2
3:   57    3        3     1.0          3
4:   58    4        4     1.5          4
5:   59    5        4     1.0          5
6:   60    6        2     1.0          6
7:   61    5        5     2.0          5
8:   62    5        4     1.5          5