Any easy way to cluster GPS trajectories? Can anyone recommend an easy way to cluster hundreds of GPS trajectories to find out their common paths? The GPS data is coming from different vehicles that have traveled thousands of miles.
 A: There is no easy way.


*

*there is no universally useful accepted definition of what is a cluster, so how could you do clustering?
Similarity is not objective. If you use e.g. DTW then you do assume the complete series is relevant, not e.g. only parts of it. It works on the technology part, but that doesn't mean the results are what you are looking for...

*Complexity and cost. In particular if you are interested in partial overlaps, cost rises drastically. Segmentation itself is surprisingly hard and needs to be solved first.
First figure out what you want. Don't start with the method, but with the exact objective: what is a good result (and how would you use it, what is its impact?)
A: It seems you just need to estimate the spatial distribution of "good" locations belonging to ordinary paths in order to detect outliers, which is a way nicer problem than path clustering. 
The naive but likely sufficient way is to convert the entire path bundle into a density raster with a resolution equal to your intended tolerance (~100m), and use it to rise alert whenever the vehicle detours onto an empty pixel (or below some threshold in case your data already has outliers).
A: Consider phrasing the problem as a graph of locations that make up a path and you want to find commonly occurring subgraphs. Try looking at frequent pattern mining approaches, specifically mining graphs, trees and structures.
I originally ran across this idea in the gSpan algorithm. It finds a hierarchy of subgraphs (from small to large) and does it efficiently by creating a lexigraphical order of nodes to traverse. The authors even have an implementation of gSpan to use. 
You may run into problems with graph based approaches since I assume it's very unlikely that two lat/longs are exactly the same and you may need to round things off.
A: There are many different forms to approach this problem. There are a lot of research works done in this field (I guess since 2000) and a hand full of algorithms are introduced. Recently I read a good comprehensive survey that I recommend you read it: "Trajectory data mining: an overview" by YU ZHENG, Microsoft Research. To find your answer easier, you can directly read "Sequential pattern mining", "Distance/Similarity of Trajectories" and "Trajectory Clustering" sections which are more informative considering your question.
