Location Prediction Modeling based on Mining Movement Pattern from Mobile Phone Data

Jingwei WangHosei 2014

TL;DR

This paper proposes a location prediction model that leverages event sequence analysis on mobile phone movement data to forecast a user's next destination. By identifying recurring patterns in human mobility, the model aims to improve the accuracy of predicting future locations, with potential applications in personalized advertising and understanding human dynamics.

What Problem Does This Paper Address?

Predicting human movement and future locations is a challenging but increasingly relevant problem. While mobile phones generate vast amounts of data about our daily lives, extracting meaningful patterns from this data to accurately forecast where someone will go next is difficult. Existing methods often struggle to capture the sequential nature of human behavior and the influence of past locations on future ones. This paper aims to address this gap by developing a model that specifically mines "movement patterns" from mobile phone data to predict a user's next likely location. The potential benefits include personalized services and a deeper understanding of human dynamics.

Methods

The core of this research lies in event sequence analysis applied to mobile phone GPS data. The process involves several key steps:

  • Data Pre-processing: Raw GPS data is cleansed to remove noise. A crucial step is converting GPS coordinates into meaningful location names using Google's Location API. The data is then partitioned and organized, with a focus on weekly movement behavior, assuming a 7-day activity cycle.
  • Place Threshold Initialization: A method is introduced to assign a "support" value to each location. This value considers factors like the speed of movement (distinguishing between stationary and transit states) and the frequency of visits, aiming to identify significant locations.
  • Event Sequence Analysis: The paper adapts data mining techniques to identify sequential patterns. It first identifies frequent individual locations (length 1 sequences) and then iteratively combines these to discover longer frequent sequences (e.g., location A followed by location B).
  • PreFixSpan Algorithm: To address efficiency concerns with traditional sequence mining, the paper adopts the PreFixSpan algorithm. This algorithm projects the database based on frequent prefixes, which is more efficient than considering all possible occurrences of frequent subsequences. It uses a depth-first traversal approach to generate projected databases and identify sequential patterns.

Datasets

The paper utilizes one year of anonymous mobile phone user data for its experiments. This data consists of GPS information, which is then processed to obtain location names. The authors also mention using data from "user 02" from a specific date range (1 month, 15 days, 2012) for testing. No new benchmarks are introduced; the focus is on applying existing sequence mining techniques to this mobile phone data.

Key Insights and Ideas

  • Human mobility is surprisingly regular: Despite the perception of free will, human movement patterns exhibit significant regularity, which can be mined for prediction.
  • Sequential patterns are key: The order in which locations are visited is crucial for accurate prediction, going beyond simple frequency counts.
  • PreFixSpan for efficiency: Using algorithms like PreFixSpan is essential for handling the large volume of mobile phone data and efficiently discovering sequential patterns.
  • Location names are vital: Raw GPS coordinates are insufficient; converting them into human-readable location names is a necessary step for understanding and modeling movement.

Key Results

The paper reports that by using the developed sequence model on the latter half of a user's historical data, they achieve an accuracy of 60% in predicting the user's next moving behavior. While not explicitly stated as a quantitative result, the paper demonstrates the process of generating projected data bases and identifying frequent sequences, illustrating the model's operational flow.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Data Granularity: The current model separates data into "work day" and "weekday." Future work should involve more detailed data partitioning, such as extracting holidays and understanding how holiday travel patterns differ.
  • Integration with External Information: The model currently relies solely on historical location data. To improve accuracy, it should integrate with other information sources like user's Facebook activity or internet search history, which can reveal intentions before a trip.
  • Handling Unseen Locations: The current prediction model cannot handle situations where a user visits a location not present in their historical data.
  • Semantic and Emotion Analysis: Integrating with semantic analysis (e.g., from Twitter) and emotion models could further enhance prediction accuracy by understanding user context and sentiment.
  • Time-Series Autoregressive Models: The authors propose exploring threshold autoregressive models, inspired by H. Tong, to predict the next location based on speed and geographical (longitude/latitude) changes, leveraging the relationship between time and human behavior.

Summary updated

Abstract

This paper proposes a location prediction model\nthat can be used for predicting a moving route of any mobile\nphone user. It is said that one's moving route may reflect his/her\nhobby, regular moving pattern, or sociability. With the\nadvancing network and communication technologies, mobile\nphones have become an indispensable device in our daily life.\nData analysis from mobile phone users has become a hot topic.\nThis paper describes how a mobile phone user's one year data is\nused to build the location prediction model by data partition,\ncleansing, and event sequence analysis and pattern extraction.\nWith one's location prediction model, it is possible to predict a\nnext place he/she will likely visit. This may be beneficial to some\nenterprise businesses. For example, if a company can predict\nsomeone will go to a certain location, it is possible to push some\ncommercial advertisement related to sales in this location or near\naround to his/her mobile phone.
BibTeX
@inproceedings{wang2014location,
  author = {Jingwei Wang},
  title = {{Location Prediction Modeling based on Mining Movement Pattern from Mobile Phone Data}},
  booktitle = {Hosei},
  year = {2014},
}
Figure