Comparison / clustering of trajectories (GPS data of points (x, y)) and Mining data

Question

I have 2 questions on analyzing a GPS dataset.

1) Extracting the trajectories I have a huge database of recorded GPS coordinates of the form (latitude, longitude, date-time) . In accordance with the values ​​of the date and time of consecutive records, I try to extract all the trajectories / paths followed by the person. For example; say, from time M pairs (x,y) continuously change until time N After N change in the pairs (x,y) decreases, and at this moment I conclude that the path taken from time M to N can be called a trajectory. Is this a decent approach to follow when extracting paths? Are there any known approaches / methods / algorithms that you can offer? Are there any data structures or formats that you would like to offer me to effectively support these points? Perhaps for each trajectory it would be useful to find out the speed and acceleration?

2) Completion of the trajectories As soon as I go through all the trajectories or paths, how can I compare / group them? I would like to know if the starting or ending points are similar, but how to compare the intermediate paths?

How to compare 2 paths / routes and conclude whether they are similar or not. Moreover; How to group similar paths together?

I would really appreciate it if you could point me to a study or something similar on this subject.

Development will be in Python, but all kinds of library suggestions are welcome.

Thanks in advance.

Answer 1

Look at the work done in the geography department of the University of Zurich, especially Patrick Laube and Somayeh Dodge .

Take a look at the article

Individual movements and geographical data. Clustering Algorithms for highlighting hot spots in personal navigation routes

( link , presentation ). It demonstrates the use of DBSCAN core density estimation methods for GPS data.

Articles from the Nokia Mobile Data Challenge 2012 Workshop may also be useful here, especially:

MobReduce: Reducing State Complexity of Mobility Tracing ( link )

Fabian Hartmann, Christoph P. Mayer, Ingmar Baumgart and

Trajectory cleansing scheme for trajectory clustering ( link )

Agzam Idrissov, Mario A. Nascimento, University of Alberta

Answer 2

1) Extracting trajectories I think you're in the right direction. There will probably be some noise in the gps data and random walking, you should make some smooth splines to overcome this.

---

2) Extraction of trajectories Does it make sense in such trajectories? (This will help to build a distance metric, and then you can use some mahoot clustering algorithms) 1. I think the point where a person stops is more interesting, so you can generate statistics on the popularity of places. 2. If you need route similarity to find different paths to the same start end, you need to copy the first start end location and then simulate the curves (maximum distance between them, integral distance — some of the well-known functional indicators)