# Clustering Trajectories (GPS data of (x,y) points) and Mining the data

I've got 2 questions on analyzing a GPS dataset.

1) Extracting trajectories I have a huge database of recorded GPS coordinates of the form (latitude, longitude, date-time). According to date-time values of consecutive records, I'm trying to extract all trajectories/paths followed by the person. For instance; say from time M, the (x,y) pairs are continuously changing up until time N. After N, the change in (x,y) pairs decrease, at which point I conclude that the path taken from time M to N can be called a trajectory. Is that a decent approach to follow when extracting trajectories? Are there any well-known approaches/methods/algorithms you can suggest? Are there any data structures or formats you would like to suggest me to maintain those points in an efficient manner? Perhaps, for each trajectory, figuring out the velocity and acceleration would be useful?

2) Mining the trajectories Once I have all the trajectories followed/paths taken, how can I compare/cluster them? I would like to know if the start or end points are similar, then how do the intermediate paths compare?

How do I compare the 2 paths/routes and conclude if they are similar or not. Furthermore; how do I cluster similar paths together?

I would highly appreciate it if you can point me to a research or something similar on this matter.

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

P.S: I'm opening the exact same question http://stackoverflow.com/questions/4910510/comparing-clustering-trajectories-gps-data-of-x-y-points-and-mining-the-data in StackOverflow. Thought I'd get more answers here...

-
A good answer will pay attention to why you are doing this analysis. What activities are your "persons" doing? What do you mean, in this context, by a "trajectory"? Why are you interested in the trajectories? What does it mean for trajectories to be "similar"? Your clarifications will suggest appropriate answers; without clarification, getting a suitable answer will be a matter of luck and guesswork. – whuber Feb 7 '11 at 15:16
Well, I'm interested in figuring out the daily routine of the person; where does she go on a daily/weekly/monthly basis and what paths/routes does she usually follow when going there? Which paths does she rarely follow? – Murat Feb 7 '11 at 15:43
The database contains people's recorded GPS points for over a month, with 1-2 seconds frequency. I don't know what they are doing; actually, that's what I'm interested in finding out. – Murat Feb 7 '11 at 15:44
@Murat OK, that's good. Let's get more precise. When a person moves around a home or office, would you consider that to be stationary or are you trying to track those trajectories too? When you say two trajectories are "similar" do you mean they seem to follow the same path between points A and B, or they both go from point A to point B (perhaps by different routes, but without stopping), or something else? BTW, are your data complete or--as one one would expect--are there periods when data are missing or known to be erroneous? – whuber Feb 7 '11 at 17:05
@user5013 - Take a look at what Microsoft Research has published. It "contains 17,621 trajectories with a total distance of about 1.2 million kilometers and a total duration of 48,000+ hours." research.microsoft.com/en-us/downloads/… – Murat Dec 3 '11 at 21:51

Two articles that you would likely be interested in, as they have similar motivations to yours:

Limits of Predictability in Human Mobility by: Chaoming Song, Zehui Qu, Nicholas Blumm, Albert-László Barabási. Science, Vol. 327, No. 5968. (19 February 2010), pp. 1018-1021.

Understanding individual human mobility patterns by: Marta C. Gonzalez, Cesar A. Hidalgo, Albert-Laszlo Barabasi. Nature, Vol. 453, No. 7196. (05 June 2008), pp. 779-782.

Note the two studies use the same data, which is similar to yours but not at the level of precision in space or time. I don't think what I would describe what you want to find as a trajectory, but I'm not sure what I would call it either. Why exactly do you want to cluster the beginning/end nodes of your "trajectories".

-

PySAL - the Python Spatial Analysis Library may be a good start - http://code.google.com/p/pysal/

Particulary the autocorrelation section:

Spatial autocorrelation pertains to the non-random pattern of attribute values over a set of spatial units. This can take two general forms: positive autocorrelation which reflects value similarity in space, and negative autocorrelation or value dissimilarity in space. In either case the autocorrelation arises when the observed spatial pattern is different from what would be expected under a random process operating in space.

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

You could also consider using R libraries http://cran.r-project.org/web/views/Spatial.html for Point Pattern Analysis.

Other R packages:

Functions for accessing and manipulating spatial data for animal tracking. Filter for speed and create time spent plots from animal track data.

It may also simplify the analysis if you snap the points to existing linear transport networks (roads/rail) available from OSM. Then you can symbolise based on these lines and how many people use them at particular times of day.

-
Given the context of the question suggesting to examine the autocorrelation does not make any sense. Auto-correlation of what attributes? – Andy W Feb 9 '11 at 4:54
The time stamp for the GPS readings can be used to see which areas of a town or city are used at different times of the day. Though its not clear if the primary research is to find what people do, or how people get there. – geographika Feb 9 '11 at 9:56
Also a derived point dataset with closely related points for individuals grouped and given a "duration" parameter could be analysed – geographika Feb 9 '11 at 11:50
Your first comment changes the unit of analysis from people to places. While I agree the question is somewhat ambiguous, there is nothing in it to insinuate the OP wants to cluster places. I can see an argument for the second comment (a point has an attribute of velocity). While an interesting notion, it is pretty abstract and novel, hence I don't think it makes much sense to suggest examining spatial auto-correlation and is likely to be confusing (you can cluster points in that framework, not entire paths). I agree though that pysal and R libraries will be of interest. – Andy W Feb 9 '11 at 16:15

While I can't comment much on the trajectories or paths of your people, I think you're on the right track with the cluster and time approach.

I put together a demo for the Esri UC last year while working with some people at the Snow Leopard Conservancy, available at: http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=1F9F376F-1422-2418-7FBC-C359E9644702

It looks at "feeding sites" (clusters) of Snow Leopards based on given criteria:

• how grouped those points were (distance from one another)
• a minimum threshold of points (my analysis required 4+ points as readings were taken about every 12hrs)
• points must be sequential (easy part of the analysis as they should be collected in a linear order)

While it uses Esri tools to do the distance analysis, the python script inside might help you with the clustering idea once you know what points are near each other. (it uses graph theory: http://en.wikipedia.org/wiki/Graph_theory)

As mentioned in the other answers, theres papers out there to determine attributes you'd need to make the decisions.

Analysis was based loosely on the concepts from: Knopff, K.H., A. R. A. Knopff, M. B. Warren, and M. S. Boyce. 2009. Evaluating Global Positioning System telemetry techniques for estimating cougar predation parameters. Journal of Wildlife Management73:586-597.

-

This may be of help too for you:

Orellana D, Wachowicz M. Exploring patterns of movement suspension in pedestrian mobility. Geogr Anal. 2011;43(3):241-60. PubMed PMID: 22073410.

Also have a look at this blog:

ideasonmovement.wordpress.com/

-