Кластеризация траекторий (данные GPS (x, y) точек) и добыча данных

14

Просто еще один день в офисе для человека пушечное ядро.

У меня есть 2 вопроса по анализу набора данных GPS.

1) Извлечение траекторий У меня есть огромная база данных записанных GPS-координат вида (latitude, longitude, date-time). Согласно значениям даты-времени последовательных записей, я пытаюсь извлечь все траектории / пути, по которым идет человек. Например; скажем от времени M, (x,y)пары постоянно меняются вплоть до времени N. После того N, как изменение в (x,y)парах уменьшается, в этот момент я заключаю, что путь, взятый от времени MкNможно назвать траекторией. Это достойный подход, чтобы следовать при извлечении траекторий? Есть ли какие-нибудь известные подходы / методы / алгоритмы, которые вы можете предложить? Есть ли какие-либо структуры данных или форматы, которые вы хотели бы предложить мне для эффективного поддержания этих точек? Возможно, для каждой траектории было бы полезно выяснить скорость и ускорение?

2) Разработка траекторий После того, как у меня пройдены все траектории / пройдены пути, как я могу сравнить / сгруппировать их? Я хотел бы знать, похожи ли начальная или конечная точки, тогда как сравниваются промежуточные пути?

Как мне сравнить 2 пути / маршруты и сделать вывод, похожи они или нет. Более того; как объединить похожие пути в кластеры?

Я был бы очень признателен, если бы вы указали мне на исследование или что-то подобное по этому вопросу.

Разработка будет на Python, но приветствуются всевозможные предложения библиотек.

Точно такой же вопрос я открываю /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data в StackOverflow. Думаю, я получу больше ответов здесь ...

Мурат
источник
1
Хороший ответ обратит внимание на то, почему вы делаете этот анализ. Какими действиями занимаются ваши "люди"? Что вы имеете в виду в этом контексте под «траекторией»? Почему вас интересуют траектории? Что значит для траекторий быть «похожими»? Ваши разъяснения предложат соответствующие ответы; без разъяснений получение подходящего ответа будет делом удачи и догадок.
whuber
Ну, я заинтересован в выяснении распорядка дня человека; куда она ходит ежедневно / еженедельно / ежемесячно и по каким путям / маршрутам она обычно следует, когда туда ходит? Какими путями она редко следует?
Мурат
База данных содержит записанные людьми точки GPS более месяца с периодичностью 1-2 секунды. Я не знаю, что они делают; на самом деле, это то, что мне интересно узнать.
Мурат
1
@ Мурат Хорошо, это хорошо. Давайте уточним. Когда человек перемещается по дому или офису, вы считаете это стационарным или вы тоже пытаетесь отслеживать эти траектории? Когда вы говорите, что две траектории "похожи", вы имеете в виду, что они, кажется, следуют по одному и тому же пути между точками A и B, или они оба идут из точки A в точку B (возможно, разными путями, но без остановки), или что-то еще? Кстати, ваши данные полны или - как и следовало ожидать - есть периоды, когда данные отсутствуют или известны как ошибочные?
whuber
1
@ user5013 - посмотрите, что опубликовало исследование Microsoft Research. Он «содержит 17 621 траекторию с общим расстоянием около 1,2 миллиона километров и общей продолжительностью более 48 000 часов». research.microsoft.com/en-us/downloads/…
Мурат

Ответы:

2

Две статьи, которые вас, вероятно, заинтересуют, поскольку они имеют аналогичные мотивы для вашей:

Пределы предсказуемости в человеческой мобильности : Chaoming Song, Zehui Qu, Николас Блумм, Альберт-Ласло Барабаси. Science , Vol. 327, № 5968. (19 февраля 2010 г.), стр. 1018-1021.

Понимание индивидуальных моделей мобильности человека : Марта С. Гонсалес, Сезар А. Идальго, Альберт-Ласло Барабаси. Nature , Vol. 453, № 7196. (05 июня 2008 г.), с. 779-782.

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

Энди У
источник
2

PySAL - библиотека пространственного анализа Python может быть хорошим началом - http://code.google.com/p/pysal/

В частности, автокорреляционная секция:

Пространственная автокорреляция относится к неслучайному шаблону значений атрибутов в наборе пространственных единиц. Это может принимать две основные формы: положительная автокорреляция, которая отражает сходство значений в пространстве, и отрицательная автокорреляция или различие значений в пространстве. В любом случае автокорреляция возникает, когда наблюдаемая пространственная картина отличается от того, что можно было бы ожидать при случайном процессе, работающем в космосе.

http://pysal.org/1.2/users/tutorials/autocorrelation.html

Вы также можете рассмотреть возможность использования библиотек R http://cran.r-project.org/web/views/Spatial.html для анализа точечных паттернов .

Другие пакеты R:

Функции для доступа и управления пространственными данными для отслеживания животных. Фильтрация скорости и создание графиков затраченного времени из данных треков животных.

Это также может упростить анализ, если привязать точки к существующим линейным транспортным сетям (автомобильным / железнодорожным), доступным в OSM. Затем вы можете символизировать на основе этих строк и сколько людей используют их в определенное время дня.

geographika
источник
Учитывая контекст вопроса, предлагать исследовать автокорреляцию не имеет никакого смысла. Автокорреляция каких атрибутов?
Энди Ш
Отметку времени для показаний GPS можно использовать, чтобы увидеть, какие районы города или города используются в разное время дня. Хотя неясно, будет ли первичное исследование выяснять, что люди делают, или как люди туда попадают.
География
Также можно проанализировать производный точечный набор данных с тесно связанными точками для людей, сгруппированных и получивших параметр «длительность»
geographika
Ваш первый комментарий меняет единицу анализа от людей к местам. Хотя я согласен с тем, что вопрос несколько двусмысленный, в нем нет ничего, что наводило бы на мысль, что ОП хочет сгруппировать места. Я вижу аргумент для второго комментария (точка имеет атрибут скорости). Хотя это интересное понятие, оно довольно абстрактное и новое, поэтому я не думаю, что имеет смысл предлагать изучение пространственной автокорреляции и, вероятно, сбивает с толку (вы можете кластеризовать точки в этой структуре, а не целые пути). Я согласен, что библиотеки pysal и R будут представлять интерес.
Энди W
2

Хотя я не могу комментировать траектории или пути ваших людей, я думаю, что вы находитесь на правильном пути с кластерным и временным подходом.

Я собрал демоверсию для Esri UC в прошлом году, работая с некоторыми людьми в Snow Leopard Conservancy, доступную по адресу: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418 -7FBC-C359E9644702

Он рассматривает «места кормления» (скопления) снежных барсов на основе заданных критериев:

  • насколько сгруппированы эти точки (расстояние друг от друга)
  • минимальный порог баллов (мой анализ требовал 4+ баллов, так как показания брались примерно каждые 12 часов)
  • точки должны быть последовательными (простая часть анализа, поскольку они должны быть собраны в линейном порядке)

Хотя для анализа расстояний используются инструменты Esri, сценарий python внутри может помочь вам с идеей кластеризации, если вы знаете, какие точки находятся рядом друг с другом. (используется теория графов: http://en.wikipedia.org/wiki/Graph_theory )

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

Анализ основывался в основном на концепциях: Кнопфа, К.Х., ARA Кноппа, М.Б. Уоррена и М.С. Бойса. 2009. Оценка методов телеметрии Глобальной системы определения местоположения для оценки параметров хищничества пумы. Журнал управления дикой природой73: 586-597.

KHibma
источник
2

Для запуска любого типа кластеризации на вашем наборе траекторий вам необходимо иметь способ вычисления сходства или расстояния между парами траекторий. Существует несколько существующих методов для этого, и новые разрабатываются для особых случаев или для устранения недостатка традиционных (я лично работаю над новым для моей кандидатской диссертации). Хорошо известными алгоритмами являются следующие:

  • Расстояние до ближайшей пары: просто определите расстояние между двумя траекториями на расстоянии пары точек, которая находится ближе всего друг к другу. Траектории должны состоять из одинакового количества точек.
  • Сумма парных расстояний: рассчитайте расстояния для каждой пары точек и сложите их. Также работает, только если траектории имеют одинаковую длину
  • Расстояние Dynamic Time Warping (DTW): Этот алгоритм был разработан для обработки траекторий различного количества измеренных точек. Он работает на парах точек и позволяет многократно использовать точку одной траектории в вычислениях парных расстояний, если другая движется «слишком быстро». DTW иллюстрация(Изображение из Википедии )
  • Самая длинная общая подпоследовательность: как следует из названия, она определяет сходство двух траекторий по длине самой длинной суб-траектории, где исходные пути проходят близко друг к другу.
  • Редактировать расстояние на реальной последовательности (EDR) и Редактировать расстояние с реальным штрафом (ERP) определяют сходство по количеству операций редактирования (добавления, удаления или замены), необходимых для преобразования одной из траекторий в другую.

Если вы знакомы с этой областью, я настоятельно рекомендую книгу «Вычисления с пространственными траекториями» от нескольких исследователей Microsoft Asia.

sw0rdf1sh
источник
0

Это может быть полезным для вас:

Орельяна Д., Вахович М. Исследование закономерностей приостановки движения в пешеходной мобильности. Geogr Anal. 2011; 43 (3): 241-60. PubMed PMID: 22073410.

Также взгляните на этот блог:

ideasonmovement.wordpress.com/

Дэвид
источник