A Constraint-Based Clustering Algorithm for Detection of Meaningful Places

Abstract

GPS devices generate a large amount of trajectory data. However these data do not contain the user-level notion of "place". A location is a pair of coordinates without any significance to the user whereas a place represents a meaningful location, such as “home , “work , based on the observation of routines and their embedded semantic meaning. One of the available mechanisms to extract knowledge from these data is through the application of clustering techniques. Clustering is a process to group objects based on their similarity, which in our case will allow us to detect intentional stops. Detecting intentional stops allows us to understand where the user spends most of his time, and, thus, to model mobility patterns. Recent clustering algorithms integrate both trajectory sample points and background geographic information. The main drawbacks of the existing approaches are: the user has to specify which physical spaces (places) he considers relevant to its trajectories; and geographic information is used to constrain the clustering algorithm and not to create a physical representation of a place. Location-based Social Networks (LBSN), like Foursquare and Twitter, support hundreds of millions of user-driven footprints. Those global-scale footprints provide a unique opportunity to model human activity - understand how social aspects can affect human mobility patterns - and geographical areas by means of place categories. The aim of our proposal is the creation of a robust spatio-temporal, i.e. density and time based, clustering algorithm for discovering intentional stops from the trajectories of users, in presence of noisy data. We also incorporate background geographic information - enriched with semantic labels gathered from Foursquare - to create a physical representation for the discovered intentional stops. Finally, we characterize aggregate activity patterns by finding the distributions of different activity categories over a city geography and study how social aspects can affect human mobility patterns.