У меня длинный набор данных со столбцами, представляющими время начала и окончания, и я хочу отбросить строку, если она перекрывается с другой и имеет более высокий приоритет (например, 1 - самый высокий приоритет). Мой пример данных
library(tidyverse)
library(lubridate)
times_df <- tibble(start = as_datetime(c("2019-10-05 14:05:25",
"2019-10-05 17:30:20",
"2019-10-05 17:37:00",
"2019-10-06 04:43:55",
"2019-10-06 04:53:45")),
stop = as_datetime(c("2019-10-05 14:19:20",
"2019-10-05 17:45:15",
"2019-10-05 17:50:45",
"2019-10-06 04:59:00",
"2019-10-06 05:07:10")), priority = c(5,3,4,3,4))Способ, которым я придумал, решает проблему задом наперед, находя перекрытия с более высоким значением приоритета, а затем используя их anti_joinдля удаления их из исходного кадра данных. Этот код не работает, если три периода перекрывают один и тот же момент времени, и я уверен, что есть более эффективный и функциональный способ сделать это.
dropOverlaps <- function(df) {
drops <- df %>%
filter(stop > lead(start) | lag(stop) > start) %>%
mutate(group = ({seq(1, nrow(.)/2)} %>%
rep(each=2))) %>%
group_by(group) %>%
filter(priority == max(priority))
anti_join(df, drops)
}
dropOverlaps(times_df)
#> Joining, by = c("start", "stop", "priority")
#> # A tibble: 3 x 3
#> start stop priority
#> <dttm> <dttm> <dbl>
#> 1 2019-10-05 14:05:25 2019-10-05 14:19:20 5
#> 2 2019-10-05 17:30:20 2019-10-05 17:45:15 3
#> 3 2019-10-06 04:43:55 2019-10-06 04:59:00 3Может ли кто-нибудь помочь мне получить тот же результат, но с более чистой функцией? Бонус, если он может обрабатывать вход с тремя или более периодами времени, которые все перекрываются.
combn, хотя это может дорого обойтись, если у вас много строк.times_df %>% mutate(interval = interval(start, stop)) %>% {combn(nrow(.), 2, function(x) if (int_overlaps(.$interval[x[1]], .$interval[x[2]])) x[which.min(.$priority[x])], simplify = FALSE)} %>% unlist() %>% {slice(times_df, -.)}plyrangesпоэкспериментировать с адаптацией IRanges / GRanges (используется для поиска перекрытий между геномами) для Tidyverse. Я думаю, что вы могли бы преобразовать свое время в «геномные» диапазоны, преобразовав свои дни + часы в целое число часов («хоромосома») и свои минуты + секунды в целое число секунд («нуклеотиды»). Если вы посмотрели на выводpair_overlaps(и использовали столбец ID, чтобы удалить их для самостоятельного перекрытия), вы могли бы сохранить свой приоритет и сделать хороший фильтр результатов + inner_join с вашей исходной таблицей. Это хакерский, но должен оптимизировать простоту кодирования + эффективность.Ответы:
Вот
data.tableрешение, которое используетсяfoverlapsдля обнаружения перекрывающихся записей (как уже упоминалось @GenesRus). Перекрывающиеся записи назначаются группам для фильтрации записей с макс. приоритет в группе. Я добавил еще две записи в данные вашего примера, чтобы показать, что эта процедура также работает для трех или более перекрывающихся записей:Редактировать: я изменил и перевел решение @ pgcudahy,
data.tableкоторое дает еще более быстрый код:Для получения дополнительной информации, пожалуйста, см.
?foverlaps- Есть несколько более полезных функций, реализованных для контроля того, что считается перекрытием, напримерmaxgap,minoverlapилиtype(любое, в пределах, начало, конец и равно).Обновление - новый тест
Код теста:
источник
У меня есть вспомогательная функция, которая группирует перекрывающиеся данные / время с помощью пакета igraph (он может включать буфер перекрытия, то есть конечные точки находятся в пределах 1 минуты ...)
Я использовал его, чтобы сгруппировать ваши данные на основе интервалов в lubridate, а затем немного обработать данные, чтобы получить только запись с самым высоким приоритетом из перекрывающихся времен.
Я не уверен, насколько хорошо это будет масштабироваться.
Который дает:
источник
Я спустился в кроличью нору, глядя на деревья интервалов (и R-реализации, такие как IRanges / plyranges), но я думаю, что для этой проблемы не нужна такая сложная структура данных, поскольку время начала может быть легко отсортировано. Я также расширил набор тестов, например @ismirsehregal, чтобы охватить больше потенциальных интервальных отношений, таких как интервал, который начинается до и заканчивается после его соседа, или когда три интервала перекрываются, но первый и последний не перекрывают друг друга, или два интервала, которые начинаются и остановиться в одно и то же время.
Затем я делаю два прохода через каждый интервал, чтобы увидеть, перекрывается ли он с предшественником или преемником.
stop >= lead(start, default=FALSE)а такжеstart <= lag(stop, default=FALSE))Во время каждого прохода выполняется вторая проверка, чтобы увидеть, имеет ли приоритет интервала более высокое числовое значение, чем предшественник или преемник
priority > lead(priority, default=(max(priority) + 1)). Во время каждого прохода, если оба условия выполняются, флаг «удалить» устанавливается в значение true в новом столбце с помощьюmutate. Любые строки с флагом удаления затем фильтруются.Это позволяет избежать проверки всех возможных комбинаций интервалов, таких как ответ @ Paul (2n против n! Сравнений), а также учитывает мое незнание теории графов :)
Точно так же ответ @ ismirsehregal имеет магию data.table, которая находится за пределами моего понимания.
Решение @ MKa не работает с> 2 перекрывающимися периодами
Тестирование решений дает
Из этого кода
источник
tibbleструктурой и, похоже,pull()был причиной проблемы. Ибоdataframe()он должен работать как есть. Только что обновил ответ.data.tableчто делает вещи еще быстрее (пожалуйста, проверьте мой новый тест).Также, используя
igraphдля идентификации любых перекрывающихся групп, вы можете попробовать:источник