[GIS] Clustering trajectories (GPS data of (x,y) points) and mining the data

algorithmclusteringgpspython

Just another day at the office for the human cannonball.

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…

Best Answer

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

Related Solutions

[GIS] Creating polyline-based “heatmap” from GPS tracks

I've done a bit of work on this in GeoTools/GeoServer by extending the Heatmap Rendering Transformation to support geometries other than points.

Pizza deliveries heatmap

It's not finished yet, but you can get the feature branch from my repository on GitHub.

The screenshot is of GPS tracks from when I worked as a pizza delivery driver.

Detecting and Fixing Outliers in GPS Trajectory Data

Algorithm I use.

Calculate Euclidean minimum spanning tree of points:

Find 2 points most far apart from each other on this network

Find shortest route between them:

As one can see it might cut corner on a sharp turn.

I have ArcGIS python implementation of above algorithm, it uses networkx module. Let me know if this is of interest and I'll update my answer with the script

UPDATE:

# Connects points to make polyline. Makes 1 line at a time
# Tool assumes that 1st layer in Table of Conternt is TARGET polyline feature class,
# second layer in TOC is SOURCE point fc.
# If no selection found in SOURCE layer, works on entire dataset

import arcpy, traceback, os, sys
import itertools as itt
from math import sqrt
sys.path.append(r'C:\Users\felix_pertziger\AppData\Roaming\Python\Python27\site-packages')
import networkx as nx
from networkx import dijkstra_path_length

try:
    def showPyMessage():
        arcpy.AddMessage(str(time.ctime()) + " - " + message)
    def CheckLayerLine(infc):
        d=arcpy.Describe(infc)
        theType=d.shapeType
        if theType!="Polyline":
            arcpy.AddWarning("\nTool designed to work with polylines as TARGET!")
            raise NameError, "Wrong input\n"
        return d
    def CheckLayerPoint(infc):
        d=arcpy.Describe(infc)
        theType=d.shapeType
        if theType!="Point":
            arcpy.AddWarning("\nTool designed to work with points as SOURCE!")
            raise NameError, "Wrong input\n"
        return d
    mxd = arcpy.mapping.MapDocument("CURRENT")
    layers = arcpy.mapping.ListLayers(mxd)
    if len(layers)<=1:
        arcpy.AddWarning("\nNot enough layers in the view!")
        raise NameError, "Wrong input\n"
    destLR, sourceLR=layers[0],layers[1]
    a = CheckLayerPoint(sourceLR);d = CheckLayerLine(destLR)

#  copy all points to manageable list
    g=arcpy.Geometry()
    geometryList=arcpy.CopyFeatures_management(sourceLR,g)
    nPoints=len(geometryList)
    arcpy.AddMessage('Computing minimum spanning tree')
    list2connect=[p.firstPoint for p in geometryList]
#  create network    
    p=list(itt.combinations(range(nPoints), 2))
    arcpy.SetProgressor("step", "", 0, len(p),1)
    G=nx.Graph()
    for f,t in p:
        p1=list2connect[f]
        p2=list2connect[t]
        dX=p2.X-p1.X;dY=p2.Y-p1.Y
        lenV=sqrt(dX*dX+dY*dY)
        G.add_edge(f,t,weight=lenV)
        arcpy.SetProgressorPosition()
    arcpy.AddMessage(len(G.edges()))
    mst=nx.minimum_spanning_tree(G)
    del G

#  find remotest pair
    arcpy.AddMessage(len(mst.edges()))
    length0=nx.all_pairs_dijkstra_path_length(mst)
    lMax=0
    for f,t in p:
        lCur=length0[f][t]
        if lCur>lMax:
            lMax=lCur
            best=(f,t)
    gL=nx.dijkstra_path(mst,best[0],best[1])
    del mst
    nPoints=len(gL)
    ordArray=arcpy.Array()
    for i in gL: ordArray.add(list2connect[i])

#  append line to TARGET
    curT = arcpy.da.InsertCursor(destLR,"SHAPE@")
    curT.insertRow((arcpy.Polyline(ordArray),))
    arcpy.RefreshActiveView()
    del curT

except:
    message = "\n*** PYTHON ERRORS *** "; showPyMessage()
    message = "Python Traceback Info: " + traceback.format_tb(sys.exc_info()[2])[0]; showPyMessage()
    message = "Python Error Info: " +  str(sys.exc_type)+ ": " + str(sys.exc_value) + "\n"; showPyMessage()

Best Answer

Related Solutions

[GIS] Creating polyline-based “heatmap” from GPS tracks

Detecting and Fixing Outliers in GPS Trajectory Data

Related Question