Recently, clustering moving object trajectories kept gaining interest from both the data mining and machine learning communities. This problem, however, was studied mainly and extensively in the setting where moving objects can move freely on the euclidean space. In this paper, we study the problem of clustering trajectories of vehicles whose movement is restricted by the underlying road network. We model relations between these trajectories and road segments as a bipartite graph and we try to cluster its vertices. We demonstrate our approaches on synthetic data and show how it could be useful in inferring knowledge about the flow dynamics and the behavior of the drivers using the road network.
Our approaches differ from existing propositions on two key aspects. First, the majority of existing work use density-based algorithms that require fine-tuning of their parameter values and assume that trajectories in the same cluster have a rather homogeneous density (which is rarely the case as discussed in @cite_5 ). In contrast, we opt for non-parametric algorithms that rely on robust and well defined clustering quality criteria. Secondly, existing approaches often use flat clustering, thus producing a unique level of clusters that can be overwhelming to analyse in the case of large datasets. Our propositions produce hierarchies of nested clusters that are suitable for multi-level exploration: the user can start with a small number of clusters to quickly understand the macro-organization of flow dynamics in the road network, then proceed to refining clusters of interest to reveal more details.
@cite_5
1533876949
With the advent of ubiquitous computing, we can easily acquire the locations of moving objects. This paper studies clustering problems for trajectory data that is constrained by the road network. While many trajectory clustering algorithms have been proposed, they do not consider the spatial proximity of objects across the road network. For this kind of data, we propose a new distance measure that reflects the spatial proximity of vehicle trajectories on the road network, and an efficient clustering method that reduces the number of distance computations during the clustering process. Experimental results demonstrate that our proposed method correctly identifies clusters using real-life trajectory data yet reduces the distance computations by up to 80 against the baseline algorithm.