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

I'm opening the exact same question https://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. Feb 7, 2011 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? Feb 7, 2011 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. Feb 7, 2011 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? Feb 7, 2011 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/… Dec 3, 2011 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? Feb 9, 2011 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. Feb 9, 2011 at 9:56
• Also a derived point dataset with closely related points for individuals grouped and given a "duration" parameter could be analysed Feb 9, 2011 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. Feb 9, 2011 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.

To run any kind of clustering on your set of trajectories, you need to have a way of calculating similarity or distance of trajectory pairs. There are several existing methods for this, and new ones are being developed for special cases or to fix a shortcoming of the traditional ones (I'm personally working on a new one for my PhD thesis). The well known algorithms are the following:

• Closest pair distance: simply define the distance of 2 trajectories by the distance of the point pair that's closest to each other. The trajectories must consist of the same number of points.
• Sum of pairs distance: Calculate the distances for each point pair and add them up. Also works only if the trajectories are of the same length
• Dynamic Time Warping (DTW) distance: This algorithm was developed to handle trajectories of different amount of measured points. It works on point pairs, and allows a point of one trajectory to be used multiple times in the pair distance calculations, if the other one is moving "too fast". (Image from Wikipedia)
• Longest Common Subsequence: as the name suggests, it defines similarity of two trajectories by the length of the longest sub-trajectory where the original paths are travelling close to each other.
• Edit Distance on Real Sequence (EDR) and Edit Distance with Real Penalty (ERP) define similarity by the number of edit operations (add, remove or replace) that are needed to transform one of the trajectories into the other one.

If you are into this field, I highly recommend the book called "Computing with Spatial Trajectories" from a number of Microsoft Asia reserachers.

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/