TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering

Jae-Gil Lee, Jiawei Han, Xiaolei Li, Hector Gonzalez

TL;DR

This paper introduces TraClass, a novel framework for classifying trajectories by combining region-based and trajectory-based clustering. This hierarchical approach effectively captures both spatial regions and movement patterns within trajectories, leading to significantly improved classification accuracy and efficiency compared to existing methods.

What Problem Does This Paper Address?

Classifying trajectories – predicting the class labels of moving objects based on their paths – is crucial for many real-world applications, from vessel identification to tracking atmospheric phenomena. Existing methods often struggle because discriminative features might only appear in specific parts of a trajectory or are related to spatial regions rather than just the overall shape of movement. This is particularly true for long trajectories covering large geographic areas. The paper aims to address this limitation by developing a more comprehensive feature generation framework that can identify and leverage these localized and region-specific discriminative features.

Methods

TraClass employs a two-pronged hierarchical clustering approach after an initial trajectory partitioning step:

  • Trajectory Partitioning: Each trajectory is first broken down into smaller segments (partitions) based on rapid changes in movement direction. This is done using a Minimum Description Length (MDL) principle to find an optimal partitioning. A "class-conscious" partitioning step further refines these segments to ensure they don't span across class boundaries, making discriminative parts more identifiable.
  • Region-Based Clustering: This technique identifies spatial regions that are dominated by trajectories of a single class, regardless of their specific movement patterns within that region. It uses a multi-resolution grid structure and an MDL-based approach to find a balance between homogeneity (uniform class distribution within a region) and conciseness (minimizing the number of regions).
  • Trajectory-Based Clustering: This method focuses on discovering common movement patterns within sub-trajectories. It builds upon existing density-based clustering techniques, adapted to work with trajectory segments and incorporating class labels to ensure clusters are class-specific.
  • Hierarchical and Collaborative Approach: TraClass applies these two clustering methods hierarchically. Region-based clustering, which captures higher-level spatial features, is performed first. Trajectory-based clustering then operates on the remaining trajectory partitions, capturing lower-level movement patterns. The collaboration between these two types of clustering allows TraClass to discover a richer set of discriminative features.
  • Cluster Link Generation: To further enhance classification, TraClass generates "combined features" by linking connectable clusters, capturing sequential relationships between clusters.

Datasets

The paper evaluates TraClass on three real-world datasets:

  • Animal Movement Data: Collected by the Starkey project, this dataset contains animal movements categorized by species (elk, deer, cattle).
  • Vessel Navigation Data: From the MUSE project, this dataset includes vessel trajectories classified as Point Lobos or Point Sur. A larger version was created by perturbing the original data.
  • Hurricane Track Data: This dataset comprises Atlantic hurricane tracks from 1950-2006, classified by Saffir-Simpson scale intensity (categories 2 and 3).

The paper also mentions experiments with synthetic data to analyze the effect of region-based clustering and data size on performance.

Key Insights and Ideas

  • Discriminative features are often localized: The paper strongly emphasizes that important classification cues are frequently found in specific parts of trajectories or within particular geographic regions, not just in the overall trajectory shape.
  • Region and movement patterns are complementary: Combining region-based and trajectory-based clustering is crucial. Regions capture spatial context, while trajectory-based clustering captures dynamic movement. Together, they provide a more complete picture for classification.
  • Hierarchy matters: Performing region-based clustering first (higher-level, more general features) before trajectory-based clustering (lower-level, more specific features) leads to better efficiency and accuracy.
  • Class-conscious partitioning is key: Ensuring that trajectory partitions and clusters do not span across different class boundaries is vital for isolating discriminative information.
  • MDL principle for optimal partitioning/quantization: The paper effectively uses the Minimum Description Length (MDL) principle to guide both trajectory partitioning and region quantization, balancing descriptive power with conciseness.

Key Results

  • Significantly improved accuracy: TraClass consistently outperformed a trajectory-based-only approach (TB-ONLY) across all three real-world datasets. For example, accuracy reached 83.3% for animal data (vs. 50.0%), 98.2% for vessel data (vs. 84.4%), and 73.1% for hurricane data (vs. 65.4%).
  • Enhanced efficiency: The training time for TraClass (RB-TB) was often shorter than the TB-ONLY approach, especially on larger datasets. This is attributed to region-based clustering covering many trajectory partitions, reducing the workload for the more computationally intensive trajectory-based clustering.
  • Robustness to parameter tuning: The paper demonstrates that TraClass is less sensitive to parameter variations, particularly when region-based clustering plays a significant role, making it more practical to use.
  • Effective feature generation: Visualizations of generated features (region-based clusters as rectangles, trajectory-based clusters as colored lines) show their intuitive and meaningful nature.

Limitations and Future Work

  • Handling numerical attributes: The paper acknowledges that trajectories often have associated numerical attributes (e.g., speed, time-of-day) which are not directly handled by TraClass. The authors suggest that their framework can be integrated with existing methods for numerical feature generation.
  • Parameter selection heuristic: While the paper proposes a heuristic for parameter value selection, it notes that finding the optimal parameters can still be challenging.
  • Future work: The authors suggest investigating detailed issues such as integrating numerical features and exploring more advanced classification strategies.

Summary updated

Abstract

Trajectory classification, i.e. , model construction for predicting the class labels of moving objects based on their trajectories and other features, has many important, real-world applications. A number of methods have been reported in the literature, but due to using the shapes of whole trajectories for classification, they have limited classification capability when discriminative features appear at parts of trajectories or are not relevant to the shapes of trajectories. These situations are often observed in long trajectories spreading over large geographic areas. Since an essential task for effective classification is generating discriminative features, a feature generation framework TraClass for trajectory data is proposed in this paper, which generates a hierarchy of features by partitioning trajectories and exploring two types of clustering: (1) region-based and (2) trajectory-based. The former captures the higher-level region-based features without using movement patterns, whereas the latter captures the lower-level trajectory-based features using movement patterns. The proposed framework overcomes the limitations of the previous studies because trajectory partitioning makes discriminative parts of trajectories identifiable, and the two types of clustering collaborate to find features of both regions and sub-trajectories. Experimental results demonstrate that TraClass generates high-quality features and achieves high classification accuracy from real trajectory data.
BibTeX
@article{lee2008traclass,
  author = {Jae-Gil Lee and Jiawei Han and Xiaolei Li and Hector Gonzalez},
  title = {{TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  url = {https://openreview.net/forum?id=nYuF8u_AhsV},
}
Figure