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


14

Kolejny dzień w biurze dla ludzkiej armaty.

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 ...


1
Dobra odpowiedź zwróci uwagę na to, dlaczego przeprowadzasz tę analizę. Jakie czynności wykonują twoje „osoby”? Co w tym kontekście rozumiesz przez „trajektorię”? Dlaczego interesują Cię trajektorie? Co to znaczy, że trajektorie są „podobne”? Twoje wyjaśnienia podpowiedzą odpowiednie odpowiedzi; bez wyjaśnienia uzyskanie odpowiedniej odpowiedzi będzie kwestią szczęścia i domysłów.
whuber

Cóż, jestem zainteresowany ustaleniem codziennej rutyny osoby; dokąd idzie codziennie / co tydzień / co miesiąc i jakie ścieżki / trasy zwykle podąża, gdy tam jedzie? Jakimi ścieżkami rzadko podąża?
Murat

Baza danych zawiera zarejestrowane punkty GPS przez ponad miesiąc, z częstotliwością 1-2 sekund. Nie wiem co robią; właściwie tego właśnie chcę się dowiedzieć.
Murat

1
@Murat OK, to dobrze. Bądźmy bardziej precyzyjni. Kiedy ktoś porusza się po domu lub biurze, czy uważasz, że to stacjonarne, czy też próbujesz śledzić te trajektorie? Kiedy mówisz, że dwie trajektorie są „podobne”, masz na myśli, że wydają się one podążać tą samą ścieżką między punktami A i B, czy oba biegną od punktu A do punktu B (być może różnymi drogami, ale bez zatrzymywania się), czy coś innego? BTW, czy twoje dane są kompletne lub - jak można się spodziewać - czy są okresy, w których danych brakuje lub wiadomo, że są błędne?
whuber

1
@ user5013 - Zobacz, co opublikował Microsoft Research. „Zawiera 17 621 trajektorii o łącznej odległości około 1,2 miliona kilometrów i łącznym czasie trwania ponad 48 000 godzin”. research.microsoft.com/en-us/downloads/…
Murat

Odpowiedzi:


2

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”.


2

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:

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.


Biorąc pod uwagę kontekst pytania sugerującego zbadanie autokorelacji, nie ma żadnego sensu. Automatyczna korelacja jakich atrybutów?
Andy W,

Znacznika czasu dla odczytów GPS można użyć, aby zobaczyć, które obszary miasta są używane o różnych porach dnia. Chociaż nie jest jasne, czy głównym badaniem jest ustalenie, co ludzie robią lub jak ludzie się tam dostają.
geografia

Można również przeanalizować zbiór danych punktowych z ściśle powiązanymi punktami dla osób zgrupowanych i otrzymujących parametr „czas trwania”
geographika

Twój pierwszy komentarz zmienia jednostkę analizy z ludzi na miejsca. Chociaż zgadzam się, że pytanie jest nieco dwuznaczne, nie ma w tym nic, co sugerowałoby, że OP chce skupić miejsca. Widzę argument za drugim komentarzem (punkt ma atrybut prędkości). Choć jest to interesujące pojęcie, jest dość abstrakcyjne i nowatorskie, dlatego nie wydaje mi się, aby sugerowanie badania autokorelacji przestrzennej miało sens i może być mylące (możesz skupiać punkty w tej strukturze, a nie całe ścieżki). Zgadzam się jednak, że biblioteki pysal i R będą interesujące.
Andy W

2

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.


2

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”. Ilustracja DTW(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.


0

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/

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.