Using asymmetry in the spectral clustering of trajectories.

Abstract

Spatial trajectories, for example those of vehicles passing through a traffic intersection, are of interest in many data collection applications since they capture a lot of semantic information in a fairly compact representation. Data mining, or unsupervised learning from sets of trajectories can be challenging since intuitive notions of trajectory similarity are hard to encode rigorously. Many similarity measures for trajectories that are needed for tasks such as clustering fail to satisfy basic metric properties like the triangle inequality, or even symmetry. While in some simple practical applications such measures have been quite successful, the violation of basic properties poses unique challenges for more advanced methods such as spectral clustering. We show how the asymmetry of a trajectory similarity measure can be exploited when clustering a set of trajectories. The asymmetry is used both indirectly, in a traditional spectral clustering method, and directly, by developing a spectral clustering method that can handle asymmetric affinity matrices natively without requiring an artificial symmetrization step to be performed, thus avoiding the attendant loss of information entailed by that process. We propose a modification of the Hausdorff distance for comparing trajectories, which we first symmetrize in a non-standard fashion inspired by a local scaling approach, and then further show that the distance can be used directly without prior symmetrization. We perform a variety of experiments, with a focus on vehicle trajectories. A novel automated tracking method is developed to provide experimental data.