Grupowanie trajektorii (dane GPS punktów (x, y)) i wyszukiwanie danych

Mam 2 pytania na temat analizy zestawu danych GPS.

1) Wyodrębnianie trajektorii Mam ogromną bazę danych zarejestrowanych współrzędnych GPS formularza (latitude, longitude, date-time). Zgodnie z wartościami daty i godziny kolejnych rekordów próbuję wyodrębnić wszystkie trajektorie / ścieżki, po których następuje osoba. Na przykład; powiedzmy od czasu M, (x,y)pary ciągle się zmieniają aż do czasu N. Potem Nzmiana (x,y)par maleje, w którym momencie dochodzę do wniosku, że ścieżka od czasu Mdo czasuNmożna nazwać trajektorią. Czy jest to przyzwoite podejście do wyciągania trajektorii? Czy są jakieś znane podejścia / metody / algorytmy, które możesz zasugerować? Czy są jakieś struktury lub formaty danych, które chciałbyś zasugerować, żebym utrzymał te punkty w wydajny sposób? Być może przy każdej trajektorii przydatne byłoby ustalenie prędkości i przyspieszenia?

2) Wydobywanie trajektorii Kiedy mogę śledzić wszystkie trajektorie / podążać ścieżkami, jak mogę je porównywać / grupować? Chciałbym wiedzieć, czy punkty początkowy lub końcowy są podobne, a jak się różnią ścieżki pośrednie?

Jak porównać 2 ścieżki / trasy i stwierdzić, czy są one podobne, czy nie. Ponadto; jak mogę grupować podobne ścieżki razem?

Byłbym bardzo wdzięczny, jeśli możesz wskazać mi badania lub coś podobnego w tej sprawie.

Rozwój będzie w języku Python, ale mile widziane są wszelkie sugestie dotyczące bibliotek.

Otwieram dokładnie to samo pytanie /programming/4910510/comparing-clustering-trajectories-gps-data-of-xy-points-and-mining-the-data w StackOverflow. Myślałem, że otrzymam więcej odpowiedzi tutaj ...

Dwa artykuły, które prawdopodobnie Cię zainteresują, ponieważ mają podobne motywacje do twojego:

Granice przewidywalności w mobilności człowieka przez: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Science , Vol. 327, nr 5968. (19 lutego 2010 r.), S. 1018–1021.

Zrozumienie indywidualnych wzorców mobilności człowieka : Marta C. Gonzalez, Cesar A. Hidalgo, Albert-Laszlo Barabasi. Nature , Vol. 453, nr 7196. (05 czerwca 2008 r.), S. 779–782.

Pamiętaj, że dwa badania wykorzystują te same dane, które są podobne do twoich, ale nie na poziomie precyzji w przestrzeni lub czasie. Nie sądzę, bym opisał to, co chciałbyś znaleźć jako trajektorię, ale nie jestem pewien, jak nazwałbym to. Dlaczego dokładnie chcesz klastować początkowe / końcowe węzły „trajektorii”.

PySAL - biblioteka analizy przestrzennej Python może być dobrym początkiem - http://code.google.com/p/pysal/

W szczególności sekcja autokorelacji:

Przestrzenna autokorelacja dotyczy nieprzypadkowego wzorca wartości atrybutów w zbiorze jednostek przestrzennych. Może to przybierać dwie ogólne formy: pozytywna autokorelacja odzwierciedlająca podobieństwo wartości w przestrzeni oraz negatywna autokorelacja lub odmienna wartość w przestrzeni. W obu przypadkach autokorelacja powstaje, gdy obserwowany wzór przestrzenny różni się od tego, czego można by oczekiwać w przypadku losowego procesu działającego w przestrzeni.

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

Możesz również rozważyć użycie bibliotek R http://cran.r-project.org/web/views/Spatial.html do analizy wzorca punktowego .

Inne pakiety R:

• klasy i metody dla danych czasoprzestrzennych
• Analiza przestrzenna danych dotyczących śladów zwierząt :

Funkcje dostępu do danych przestrzennych i manipulowania nimi w celu śledzenia zwierząt. Filtruj według prędkości i twórz wykresy czasu spędzonego na podstawie danych dotyczących śladów zwierząt.

Może to również uprościć analizę, jeśli przyciągniesz punkty do istniejących liniowych sieci transportowych (drogi / kolej) dostępnych z OSM. Następnie możesz symbolizować na podstawie tych linii i ilu osób korzysta z nich w określonych porach dnia.

Chociaż nie mogę komentować trajektorii ani ścieżek waszych ludzi, myślę, że podążacie właściwą ścieżką i czasem.

W zeszłym roku przygotowałem wersję demo dla Esri UC podczas pracy z niektórymi osobami w Snow Leopard Conservancy, dostępnej pod adresem : http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418 -7FBC-C359E9644702

Patrzy na „miejsca żerowania” (skupiska) lampartów śnieżnych na podstawie podanych kryteriów:

• jak pogrupowane były te punkty (odległość od siebie)
• minimalny próg punktów (moja analiza wymagała 4+ punktów, ponieważ odczyty dokonywane były co 12 godzin)
• punkty muszą być sekwencyjne (łatwa część analizy, ponieważ należy je zbierać w kolejności liniowej)

Chociaż do analizy odległości używa narzędzi Esri, skrypt Pythona wewnątrz może ci pomóc w tworzeniu klastrów, gdy tylko dowiesz się, które punkty są blisko siebie. (wykorzystuje teorię grafów: http://en.wikipedia.org/wiki/Graph_theory )

Jak wspomniano w innych odpowiedziach, tam są dokumenty, aby określić atrybuty potrzebne do podjęcia decyzji.

Analiza została luźno oparta na koncepcjach: Knopff, KH, ARA Knopff, MB Warren i MS Boyce. 2009. Ocena technik telemetrycznych globalnego systemu pozycjonowania do szacowania parametrów drapieżnictwa kuguara. Journal of Wildlife Management73: 586-597.

Aby uruchomić dowolny rodzaj grupowania na zestawie trajektorii, musisz mieć sposób na obliczenie podobieństwa lub odległości par trajektorii. Istnieje kilka istniejących metod, a nowe są opracowywane dla specjalnych przypadków lub w celu naprawy wad tradycyjnych (osobiście pracuję nad nową dla mojej pracy doktorskiej). Dobrze znane algorytmy są następujące:

• Odległość najbliższej pary: po prostu określ odległość 2 trajektorii przez odległość pary punktów, które są najbliżej siebie. Trajektorie muszą składać się z takiej samej liczby punktów.
• Suma odległości par: Oblicz odległości dla każdej pary punktów i dodaj je. Działa również tylko wtedy, gdy trajektorie mają tę samą długość
• Odległość dynamicznego dopasowania czasowego (DTW): ten algorytm został opracowany do obsługi trajektorii o różnej ilości mierzonych punktów. Działa na parach punktów i umożliwia wielokrotne użycie punktu jednej trajektorii w obliczeniach odległości pary, jeśli drugi porusza się „za szybko”. (Zdjęcie z Wikipedii )
• Najdłuższa wspólna kolejność: jak sama nazwa wskazuje, określa podobieństwo dwóch trajektorii przez długość najdłuższej pod trajektorii, w której oryginalne ścieżki poruszają się blisko siebie.
• Edycja odległości w rzeczywistej sekwencji (EDR) i Edycja odległości z rzeczywistą karą (ERP) określają podobieństwo na podstawie liczby operacji edycji (dodawania, usuwania lub zastępowania), które są potrzebne do przekształcenia jednej trajektorii w drugą.

Jeśli zajmujesz się tą dziedziną, gorąco polecam książkę „Computing with Spatial Trajectories” autorstwa wielu ekspertów Microsoft Asia.

Może ci to również pomóc:

Orellana D, Wachowicz M. Badanie modeli zawieszenia ruchowego w ruchu pieszym. Geogr Anal. 2011; 43 (3): 241–60. PubMed PMID: 22073410.

Zobacz także tego bloga:

ideasonmovement.wordpress.com/