Semantic-Geographic Trajectory Pattern Mining Based on a New Similarity Measurement

You Wan, Chenghu Zhou, Tao PeiISPRS Int. J. Geo Inf 2017 · DOI

TL;DR

This paper introduces a novel "semantic-geographic pattern" that combines both the meaning of activities and their spatial locations in trajectory data. They propose a new similarity metric, "semantic intensity," to effectively capture this combined similarity, leading to more interpretable and accurate movement patterns than purely semantic or geographic approaches.

What Problem Does This Paper Address?

Understanding human movement patterns is crucial for applications like recommendation systems, urban planning, and traffic monitoring. Trajectory data, which records sequences of locations over time, holds rich information about these patterns. However, existing methods often focus on either the geographic shape of trajectories or the semantic meaning of visited places, but not both simultaneously. This leads to patterns that are either geographically similar but semantically different, or semantically similar but geographically dispersed, making them less useful for real-world applications. The challenge lies in developing a unified approach that can effectively measure and mine patterns considering both the "what" (semantic activity) and the "where" (geographic location) of movement.

Methods

The core of this paper is the introduction of a new concept: the semantic-geographic pattern. This pattern requires trajectories to be both semantically similar (similar activities) and geographically close. To mine these patterns, the authors propose a novel similarity measurement called semantic intensity.

Here's a breakdown of their approach:

  • Data Preprocessing: Raw check-in data (event-triggered location records) is transformed into:
  • Semantic Traces (STrace): Sequences of POI (Point of Interest) category pairs with timestamps.
  • Semantic-Geographic Traces (SGTrace): Grouped POI locations by semantic category, including geographic information and timestamps.
  • Similarity Measurement:
    • Semantic Similarity: Calculated using cosine similarity on the semantic traces, leveraging TF-IDF weighting for POI category pairs.
  • Geographic Similarity: Calculated using a modified Hausdorff distance on the semantic-geographic traces, focusing on semantically related POI category pairs.
  • Semantic Intensity: This is the novel contribution. It combines semantic and geographic similarity into a single score, effectively measuring the average semantic similarity within a geographic unit distance. The formula is designed to keep the score between 0 and 1.
  • Pattern Mining: A density-based spatial clustering algorithm (DBSCAN) is employed to group trajectories based on the calculated semantic intensity similarity. DBSCAN is chosen for its ability to handle noise and outliers and its insensitivity to the number of clusters. Parameters for DBSCAN (epsilon and MinPts) are set based on the characteristics of the semantic and geographic similarities.

Datasets

The experiments were conducted on a dataset collected from the Chinese microblogging site Sina Weibo. This dataset comprised:

  • Over 238,000 users' check-in records in Beijing during 2013.
  • Approximately 54,000 POIs, which were classified into six categories (educational institution, hotel/restaurant, indoor entertainment, outdoor activity, transportation facility, and social institution/building).
  • After preprocessing, 14,729 check-in traces from 4340 users were selected for analysis.

The paper does not introduce a new benchmark dataset but uses a real-world dataset to evaluate their proposed method against existing ones.

Key Insights and Ideas

  • The Synergy of "What" and "Where": The most significant insight is that combining semantic and geographic information is crucial for truly understanding movement patterns. Purely geographic or semantic approaches miss valuable nuances.
  • Semantic Intensity as a Unified Metric: The proposed "semantic intensity" metric effectively bridges the gap between semantic and geographic similarities, providing a more holistic view of trajectory relationships.
  • DBSCAN's Suitability for Trajectory Clustering: The paper demonstrates that DBSCAN, a density-based clustering algorithm, is well-suited for mining trajectory patterns, especially when dealing with potentially noisy data and the need to identify dense regions of similar trajectories.
  • Interpretable Patterns: The semantic-geographic patterns generated by their method are more interpretable, allowing for better understanding of user activities and their spatial context, which is valuable for applications like recommendations and urban planning.

Key Results

The paper compares their semantic intensity approach against three other similarity measurements: semantic similarity, geographic similarity, and GTS similarity.

  • Effectiveness of Semantic Intensity: Experiments showed that semantic intensity effectively measures both semantic and geographic similarities among trajectories.
  • More Valuable Patterns: The patterns mined using semantic intensity were found to be more accurate and easier to interpret compared to those generated by the other methods.
  • Clustering Performance: Semantic intensity, along with GTS similarity, generated smaller and more focused clusters compared to purely semantic or geographic similarity. The analysis of user sets and POI sets within clusters indicated that semantic intensity identified patterns where users were both semantically and geographically similar, leading to more meaningful insights. For example, patterns related to the popular IT center Zhongguancun were identified, suggesting potential for targeted recommendations.
  • Limitations of Other Methods:
    • Pure semantic similarity resulted in many small clusters and a high overlap with geographically similar users, but without a strong combined semantic-geographic correlation.
  • Pure geographic similarity showed that many users were geographically close but engaged in different activities.
  • GTS similarity, while considering some temporal aspects, did not effectively integrate geographic similarity when distances were small, leading to broader and less specific patterns.

Limitations and Future Work

  • Data Quality Issues: The authors acknowledge that check-in data is a biased sample, representing only a fraction of a user's activities and locations. This limitation reduced the number of experimental users and patterns.
  • Representativeness of Users: The experimental users might not be representative of the entire population, making it difficult to generalize conclusions about specific user types (e.g., IT employees).
  • Parameter Sensitivity: The paper notes that setting fixed parameters for clustering algorithms can be challenging given the diversity of human movement behavior.
  • Future Work: The authors suggest the need for more flexible parameter-setting strategies and more stable clustering algorithms to identify more accurate and valuable patterns. They also highlight the ongoing challenge of addressing data quality issues in trajectory mining.

Summary updated

BibTeX
@article{wan2017semantic,
  author = {You Wan and Chenghu Zhou and Tao Pei},
  title = {{Semantic-Geographic Trajectory Pattern Mining Based on a New Similarity Measurement}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2017},
  doi = {10.3390/ijgi6070212},
}
Figure