У меня 25 миллионов точек данных GPS, которые представляют местоположения многих поездов в секунду в течение одной секунды, и каждая точка помечается поездкой, частью которой она была.У меня также есть местоположения GPS 65 железнодорожных станций.Задача состоит в том, чтобы определить среднее время в пути между любыми двумя соседними станциями.
Поскольку точки могут быть сгруппированы в поездки, я могу легко определить время в пути между двумя станциями, но только если я знаю, какие точки на каждойпоездка означает остановку или прохождение мимо станции.
Таким образом, проблема сводится к .... Как определить (для каждой поездки) самую близкую точку к каждой станции, на которой поезд шел / до.
Мой план состоит из двухэтапной атаки:
1) Для каждой из 25M точек определите станцию, к которой она ближе всего, при условии, что она находится в пределах 250 м от станции.Станции находятся на расстоянии многих километров друг от друга, поэтому каждая точка будет близка максимум к 1 станции.Большинство точек не будет близко к какой-либо станции.
Теперь, концептуально, если вы рассматриваете весь набор точек как список поездок, то у нас есть списки точек (поездки) с несколькими сегментамипоследовательные точки, идентифицированные как находящиеся рядом с разными станциями.Например, первые 10 точек могут быть близки к начальной станции A, некоторые средние 8 точек могут быть близки к станции B, а последние 15 точек могут быть близки к конечной станции C.
2)На втором этапе группирование точек по поездкам для всех станций, некоторые из которых находятся рядом, определяют точку, ближайшую к каждой станции.
После завершения шага 2 из 25M точек должны быть помечены только те точки каждой поездки, которые представляют местоположение станции.Таким образом, выбор любой поездки должен обеспечить серию точек, соединяющих несколько станций.
Использование фреймов данных Python Шаги 1 и 2, моя первая попытка была очень беспочвенной.Просматривая каждую поездку, я использовал петли python, чтобы определить, где может подходить каждая станция.Пробег занял 29 часов.Неприменимо.
Моя вторая попытка состояла в том, чтобы использовать df.apply на всем наборе точек с лямбда-выражением для вызова функции python, чтобы очень эффективно найти ближайшую из 65 станций (если они были в пределах 250 м).Это заняло 100 минут, лучше, но все еще невозможно.
Следующее, что я рассматриваю, - это попытаться смоделировать все точки поезда как sklearn.neighbors.BallTree и запросить BallTree один раз для каждой станции, чтобы получить / пометить все точки в пределах 250 от каждой станции.Это осуществило бы шаг 1, описанный выше.
Затем, выбирая только отмеченные точки, для каждой поездки я бы отмечал ближайшую точку для каждой станции.Это осуществило бы Шаг 2, описанный выше, но я обеспокоен тем, что, хотя количество точек значительно уменьшилось, использование двух петель питона, одного для поездок, а другого для станций, снова сделает это слишком медленным.
Так что ты думаешь.Мой двухступенчатый план хорош?
Предполагая, что план надежный, я почти уверен, что смогу выяснить, как создавать и запрашивать BallTree, но мне бы хотелось посоветовать, как сделать Шаг 2 с помощью Python .... .... 1027 *
То есть заданы наборы точек, которые помечены их расстоянием ровно до одной из набора контрольных точек, как найти / пометить ближайшую отдельную точку для каждой контрольной точки?