Clustering Trajectories: Detecting Patterns in Spatio-Temporal Data

Abstract

In this thesis, we study the detection of patterns in spatio-temporal data sets in the form of trajectory data. Many application areas collect unstructured trajectory data. Applications for the analysis of such data range from gait analysis of human movement to traffic-flow analysis, epidemiological hotspot detection, and Lagrangian analysis of particle simulations. Trajectory data is typically modeled as a sequence of points that defines a polygonal curve via linear interpolation between consecutive points. One of the most fundamental ways of detecting patterns in any kind of data is clustering, which aims to partition the data into groups where points from the same group are 'close' to one another and those from different groups are 'far apart'. The clustering of polygonal curves is the main focus of this thesis. <br/>

The first clustering problem we study is the (<em>k</em>, <em>l</em>)-median problem for polygonal curves, which asks for <em>k</em> center curves, each with at most <em>l</em> points, minimizing the sum of dynamic time warping (DTW) distances from each input curve to its closest center. Numerous classical results for clustering problems have been extended to many different settings. A common assumption made is that the distance function is a metric, which DTW is not. Despite this, we provide a polynomial-time approximation algorithm with an approximation factor of <em>O</em>(<em>m l</em>), where <em>m</em> is the maximum number of points in any input curve. This is achieved by extending known algorithms for coreset construction—i.e., problem-specific input condensations—from metric spaces to the non-metric space of polygonal curves under DTW. <br/>

The second clustering problem we consider is Subtrajectory Covering, motivated by the need to detect patterns <em>within</em> a single curve by segmenting it into its constituent semantic parts. This is formulated as a set cover problem based on the continuous Fréchet distance. Given a polygonal curve with <em>n</em> points, the goal is to compute the smallest set of center curves, each with at most <em>l</em> points, such that every point on the input curve is covered by some center. A point is considered covered if it lies on a subtrajectory of the input curve whose (continuous) Fréchet distance to some center curve is at most Δ. We provide bicriteria approximation algorithms for arbitrary curves as well as for a subclass of realistic curves. Both algorithms approximate the required number <em>k</em>_Δ of centers by a factor of <em>O</em>(log <em>n</em>) and the distance threshold Δ by a factor of <em>O</em>(1). For arbitrary curves, the algorithm runs in roughly <em>O</em>(√<em>k</em>_Δ<em>n</em>^5/2) time. For the subclass of realistic curves (or more formally, <em>c</em>-packed curves whose arc length inside any ball of radius <em>r</em> is bounded by <em>cr</em>), the algorithm runs in roughly <em>O</em>(<em>k</em>_Δ<em>cn</em>²) time. We demonstrate the viability of both the problem formulation and the algorithm on real-world data. <br/>

Additionally, we investigate two related questions. First, given a clustering of trajectory data, a natural question is how to classify a new trajectory which is not part of the input. To this end, we design a data structure that answers approximate nearest neighbor queries: Given <em>n</em> input curves of complexity <em>m</em> and a query curve <em>q</em>, compute the closest input curve to <em>q</em> w.r.t. the continuous Fréchet distance. Our data structure answers such queries in roughly <em>O</em>(<em>F</em>(<em>m</em>, Φ) log <em>n</em>) time, where <em>F</em>(<em>m</em>, Φ) depends only on <em>m</em> and the spread Φ of vertices and edges. Second, we analyze the detection of erroneous patterns within a curve: Given two curves, how can we optimally modify one curve by replacing pieces of the curve with line segments so as to minimize the continuous Fréchet distance to the other curve? We show that this problem is not fixed-parameter tractable in the number of modifications and give a polynomial-time <em>O</em>(1)-approximation algorithm for its decision variant.