Как за короткое время рассчитать кратчайшее расстояние между точками долготы и широты в одном наборе данных с точками в другом

У меня есть два набора данных, один с 488 286 строками и координатами долготы и широты, а второй с 245 077 строками и координатами долготы и широты. Второй также содержит дополнительные данные, касающиеся координат. Я хочу найти самые близкие точки во втором наборе данных ко всем точкам в первом. Я не могу поделиться необработанными данными, поэтому для простоты я сгенерирую здесь несколько случайных точек:

df1<-cbind(runif(488286,min=-180, max=-120), runif(488286, min=50, max=85))
df2<-cbind(runif(245077,min=-180, max=-120), runif(245077, min=50, max=85))

Я попытался просто использовать функцию distm, но данные были слишком большими, поэтому я попытался разбить их следующим образом:

library(geosphere)

closest<-apply(df1, 1, function(x){
    mat<-distm(x, df2, fun=distVincentyEllipsoid)
    return(which.min(mat))
})

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

Заранее спасибо!


r distance latitude-longitude geosphere
person user5481267    schedule 01.04.2019    source источник
comment
Да, @Parfait, это быстро. Я буду запускать это в очереди с высокой памятью на сервере, поэтому теоретически должно быть доступно много оперативной памяти.   -  person user5481267    schedule 01.04.2019
comment
Во-первых, включите все library строки для небазовых функций R. Любопытно, работает ли distHaversine быстрее, чем distVincentyEllipsoid? Как видите, последний работает с вложенными циклами for и while.   -  person Parfait    schedule 01.04.2019
comment
@Parfait ах, извините, теперь добавлена ​​соответствующая библиотека. Я думаю, что да, я не понимал, что это будет иметь большое значение. Но только для одного из моих местоположений в df 1 для Haversine требуется 0,180 секунды, а для distVincentyEllipsoid - 53,989 секунды, так что это довольно большая разница. Так что, возможно, ответ так же прост, как изменить аргумент   -  person user5481267    schedule 01.04.2019

Ответы (1)


arrow_upward
1
arrow_downward

Возможно, это сработает для вас:

library(sf)
library(RANN)


df1<-data.frame("lon" = runif(2000,min=-180, max=-120), "lat" = runif(2000, min=50, max=85))
df2<-data.frame("lon" = runif(1430,min=-180, max=-120), "lat" = runif(1430, min=50, max=85))



df1_sf <- st_as_sf(df1, coords = c("lon", "lat"), 
         crs = 4326, agr = "constant")

df2_sf <- st_as_sf(df2, coords = c("lon", "lat"), 
                   crs = 4326, agr = "constant")

nearest <- nn2(df2_sf, df1_sf, k = 1, treetype = 'bd', searchtype = 'priority')

df2_sf[nearest$nn.idx,]

RANN - это оболочка для nn-библиотеки из C ++, так что это должно быть довольно быстро. Тем не менее я уменьшил количество баллов за этот ответ.

Сначала я преобразовал df1и df2 в sf-объекты. Затем я передал их алгоритму nn2, который является алгоритмом knn и возвращает список. Вектор nn.idx внутри списка содержит индекс ближайшей точки в df2 для каждой точки в df1.

ОБНОВЛЕНИЕ: вы также можете распараллелить

library(parallel)

c4 <- parallel::makeCluster(4)

df1_split <- split(df1_sf, cut(1:nrow(df1_sf), 4, labels = FALSE))

clusterExport(c2, "df2_sf")
clusterEvalQ(c2, library(RANN))


system.time(
  idxlist_parallel <- clusterApply(c2, df1_split, 
                                   function(x) nn2(df2_sf, x, k = 1, treetype = 'bd', searchtype = 'priority'))
)
person Humpelstielzchen    schedule 01.04.2019
comment
Спасибо @Humpelstielzchen. Кажется, это работает, но на это уходит много времени. Я только что пробовал использовать одно место в первом наборе данных, и пока это занимает более 20 минут (все еще выполняется). Я просто подумал, есть ли что-нибудь, что могло бы быть намного быстрее, так как я должен сделать это для более чем 400 000 баллов? - person user5481267; 01.04.2019
comment
конечно, это требует времени. Может быть, вам удастся упростить процесс распараллеливания. Я сделал и обновил в связи с этим. - person Humpelstielzchen; 01.04.2019
comment
Не знаю, почему, но исходное задание, которое у меня было, было убито, и даже когда я пытаюсь запустить код в R, он прерывает сеанс. Другой метод с distm не имеет этой проблемы и работает быстрее для небольшого подмножества данных. - person user5481267; 01.04.2019
comment
distm() быстрее, чем nn2()? Не для меня. nn2() работа на двух ядрах уже в 30 раз быстрее, а ваша функция все еще работает. Распараллеливание полезно только для больших наборов данных. Небольшим наборам данных требуется больше времени при распараллеливании из-за накладных расходов, связанных с методом. - person Humpelstielzchen; 01.04.2019
comment
А, я вижу, что я не проводил параллелизм, так что да, это, наверное, будет быстрее. Мне нужно выяснить, как это сделать с системой, и понять вышесказанное, поскольку я не привык делать это таким образом! Спасибо - person user5481267; 01.04.2019