Самый быстрый способ ранжировать поездки между двумя координатами на основе возможных возможностей?

Question

У меня есть фрейм данных с более чем 5000 мест с координатами широты и долготы, и у меня есть еще один фрейм данных с более чем 23000 поездок с исходными координатами широты и долготы и координатами широты и долготы назначения.

Все места и поездки находятся в областиof Prague, CZE.

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

Я попробовал вложенный цикл, чтобы создать список всех расстояний между местами, но он медленный, как ад.(добрался до 80-го места за 10 часов)

for (row in 73:nrow(dataset_2015_POI_prg)) {
    print(row)
    id <- toString(dataset_2015_POI_prg[row, "venue_id"])
    lat <- dataset_2015_POI_prg[row, "venue_lat"]
    lon <- dataset_2015_POI_prg[row, "venue_lon"]

    for (innerrow in 1:nrow(dataset_2015_POI_prg)) {
        innerid <- toString(dataset_2015_POI_prg[innerrow, "venue_id"])
        if (id != innerid && length(which(dataset_2015_POI_mix$from_venue_id == innerid & dataset_2015_POI_mix$to_venue_id == id)) == 0) {
            print(innerrow)
            innerlat <- dataset_2015_POI_prg[innerrow, "venue_lat"]
            innerlon <- dataset_2015_POI_prg[innerrow, "venue_lon"]   
            dist <- distm(c(lon, lat), c(innerlon, innerlat), fun = distHaversine)
            dataset_2015_POI_mix[nrow(dataset_2015_POI_mix) + 1,] = list(id, lat, lon, innerid, innerlat, innerlon, as.numeric(dist))
        }
    }
}

Поездки на фрейме данных

user_id from_lat    from_lon    to_lat      to_lon      distance
159493  50.08017    14.50109    50.09171    14.54276    3241.884096
159493  50.09171    14.54276    50.09076    14.54271    106.390784
159493  50.09076    14.54271    50.11302    14.61078    5456.33700
...

Размещение фрейма данных

venue_id    venue_lat   venue_lon
4adcda9     50.08096    14.42810
...

Какой правильный и самый быстрый способ сделать это?Ожидаемый результат - новый кадр данных с новым рангом столбца, который представляет собой общее количество всех мест ближе к исходному месту, чем описание.

Спасибо большое, я новичок в R:)

РЕДАКТИРОВАТЬ:исходные файлы слишком велики для вставки или около того, вот они: трипс: http://data.krysp.in/trips.txt мест http://data.krysp.in/pois.txt

РЕДАКТИРОВАТЬ2: dput() небольших примеров данных мест:

structure(list(venue_lat = c(50.09171, 50.090755, 50.113024, 
50.113251, 50.103708, 50.080167, 50.108774, 50.113106, 50.081854, 
50.104832, 50.090597, 50.113026, 50.068476, 50.113124, 50.10815, 
50.060503), venue_lon = c(14.542765, 14.542707, 14.610781, 14.611714, 
14.490623, 14.501095, 14.577527, 14.611648, 14.500505, 14.476009, 
14.541811, 14.611271, 14.404627, 14.611779, 14.583479, 14.506008
)), row.names = c(NA, 16L), class = "data.frame")

поездки

structure(list(user_id = c(159493, 159493, 159493, 159493, 159493, 
159493, 159493, 159493, 159493, 159493, 159493, 159493, 159493, 
159493, 159493, 159493, 159493, 159493, 159493, 159493, 159493, 
159493, 159493, 159493, 159493, 159493, 159493, 159493, 159493, 
159493), from_lat = c(50.080167, 50.09171, 50.090755, 50.113024, 
50.113251, 50.113024, 50.103708, 50.080167, 50.108774, 50.113024, 
50.113106, 50.09171, 50.080167, 50.081854, 50.113106, 50.113024, 
50.104832, 50.09171, 50.090597, 50.113024, 50.09171, 50.113026, 
50.113024, 50.068476, 50.113124, 50.113024, 50.09171, 50.113024, 
50.10815, 50.09171), from_lon = c(14.501095, 14.542765, 14.542707, 
14.610781, 14.611714, 14.610781, 14.490623, 14.501095, 14.577527, 
14.610781, 14.611648, 14.542765, 14.501095, 14.500505, 14.611648, 
14.610781, 14.476009, 14.542765, 14.541811, 14.610781, 14.542765, 
14.611271, 14.610781, 14.404627, 14.611779, 14.610781, 14.542765, 
14.610781, 14.583479, 14.542765), from_timestamp = c(10284, 58919, 
58960, 82576, 197020, 1520404, 1539221, 1581079, 1585186, 1586688, 
1586730, 1615656, 1637753, 1640134, 1643362, 1643399, 1659750, 
1756952, 1765592, 1870541, 2000993, 2008701, 2008728, 2541997, 
2653448, 2659355, 2682234, 2727528, 2822921, 2852025), to_lat = c(50.09171, 
50.090755, 50.113024, 50.113251, 50.113024, 50.103708, 50.080167, 
50.108774, 50.113024, 50.113106, 50.09171, 50.080167, 50.081854, 
50.113106, 50.113024, 50.104832, 50.09171, 50.090597, 50.113024, 
50.09171, 50.113026, 50.113024, 50.068476, 50.113124, 50.113024, 
50.09171, 50.113024, 50.10815, 50.09171, 50.060503), to_lon = c(14.542765, 
14.542707, 14.610781, 14.611714, 14.610781, 14.490623, 14.501095, 
14.577527, 14.610781, 14.611648, 14.542765, 14.501095, 14.500505, 
14.611648, 14.610781, 14.476009, 14.542765, 14.541811, 14.610781, 
14.542765, 14.611271, 14.610781, 14.404627, 14.611779, 14.610781, 
14.542765, 14.610781, 14.583479, 14.542765, 14.506008), to_timestamp = c(58919, 
58960, 82576, 197020, 1520404, 1539221, 1581079, 1585186, 1586688, 
1586730, 1615656, 1637753, 1640134, 1643362, 1643399, 1659750, 
1756952, 1765592, 1870541, 2000993, 2008701, 2008728, 2541997, 
2653448, 2659355, 2682234, 2727528, 2822921, 2852025, 3185844
), distance = c(3241.88409599252, 106.39078390924, 5456.33700758756, 
71.2359425785903, 71.2359425785903, 8640.94151730882, 2725.20357275113, 
6319.36823149692, 2420.67310365364, 62.5615027825454, 5464.76021027322, 
3241.88409599252, 192.467213137768, 8665.6776299234, 62.5615027825454, 
9664.83271725758, 4985.72628636199, 141.396853243087, 5521.3444368517, 
5405.101536154, 5436.65634829112, 34.9800594737613, 15536.1468890647, 
15607.2384436169, 72.1080346201786, 5405.101536154, 5405.101536154, 
2023.20076623555, 3435.28409601096, 4354.77279195115)), row.names = c("2", 
"3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", 
"15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", 
"26", "27", "28", "29", "30", "31"), class = "data.frame")

Answer 1

Я не уверен, понял ли я, что вы имеете в виду под "ранжированием назначений на основе возможных возможностей". Это, конечно, означает, что один и тот же пункт назначения может иметь разные ранги в зависимости от разного происхождения пользователей. Также я не уверен, должно ли «вмешательство» подразумевать направление между пунктом отправления и пунктом назначения.

В любом случае это то, что у меня есть:

Предложение 1 (с учетом направления)

Подготовка trips df

library(sf)

buffers <- list()

for(i in 1:nrow(trips)) {
buffers[[i]] <- st_buffer(st_linestring(matrix(as.numeric(trips[i, c(3,2,6,5)]), ncol = 2, byrow = T)), dist = 0.01)
}

buffer_sfc <- st_sfc(buffers, crs = 4326)

sf_trips <- st_sf(trips, geometry = buffer_sfc)

Подготовка dest DF

sf_dest <- st_as_sf(x = dest, coords = c("venue_lon", "venue_lat"), crs = 4326)

Создание званий

res <- st_contains(sf_trips, sf_dest)

trips$rank <- sapply(res, length)

И это то, что он делает: соедините пункт отправления и пункт назначения с прямой линией и создайте вокруг нее многоугольник. Тогда все остальные точки назначения, которые лежат в этом многоугольнике, «вмешиваются». Вы можете настроить размер многоугольника с помощью аргумента dist = в st_buffer в зависимости от того, какое отклонение от прямого соединения по-прежнему квалифицируется как «промежуточное».

Я вполне уверен, что это будет работать быстрее, чем ваш код. Если, однако, под «вмешательством» вы подразумеваете любое место ближе к источнику, независимо от направления, которое вы можете сделать:

Предложение 2

library(RANN)


intv_ops <- list()

for(i in 1:nrow(trips)) {
  intv_ops[[i]] <- nn2(dest, trips[i, 2:3], searchtype = "radius", radius = (trips$distance[i]/1.11) * 0.00001)$nn.idx
}

trips$rank <- sapply(intv_ops, function(x) sum(x != 0))

nn2 - это оболочка для алгоритма knn, написанного на C ++, поэтому он довольно быстрый.