SEGMENTATION TECHNIQUES BASED ON CLUSTERING FOR THE ANALYSIS OF MOBILITY DATA

The Thesis focuses on segmentation methods for the partitioning of spatial trajectories in semantically meaningful sub-trajectories and their application to the analysis of mobility behavior. Spatial trajectories are complex structured data consisting of sequences of temporally ordered spatio-temporal points sampling the continuous movement of an object in a reference space. Spatial trajectories can reveal behavioral information about individuals and groups of individuals, and that motivates the concern for data analysis techniques.
Segmentation techniques are key for the analysis of spatial trajectories. In general, the segmentation task partitions a sequence of data points in a series of disjoint sub-sequences based on some homogeneity criteria. The Thesis focuses, in particular, on the use of clustering methods for the segmentation of spatial trajectories. Unlike the traditional clustering task, which is applied to sets of data points, the goal of this class of techniques is to partition sequential data in temporally separated clusters. Such techniques can be utilized for example to detect the sequences of places or regions visited by moving objects. While a number of techniques for the cluster-based segmentation are proposed in literature, none of them is really robust again noise, while the methodologies put in place to validate those techniques suffer from severe limitations, e.g., simple datasets, no comparison with ground truth. This Thesis focuses on a recent cluster-based segmentation method, called SeqScan, proposed in previous work. This technique promises to be robust against noise, nonetheless the approach is empirical and lacks a formal and theoretical framework. The contribution of this research is twofold. First it provides analytical support to SeqScan, defining a rigorous framework for the analysis of the properties of the model. The method is validated through an extensive experimentation conducted in an interdisciplinary setting and contrasting the segmentation with ground truth. The second contribution is the proposal of a technique for the discovery of a collective pattern, called gathering. The gathering pattern describes a situation in which a significant number of moving objects share the same region, for enough time periods with possibility of occasional absences, e.g. a concert, an exhibition. The technique is built on SeqScan. A platform, called MigrO, has been finally developed, including not only the algorithms but also a variety of tools facilitating data analysis.