Unsupervised User Similarity Mining in GSM Sensor Networks

Shafqat Ali Shad, Enhong ChenThe Scientific World JOURNAL 2013 · DOI

TL;DR

This paper introduces a novel unsupervised approach to build user mobility profiles and identify similar users by leveraging low-level GSM cell ID data combined with semantic tags. By effectively handling data challenges like missing values and cell oscillation, their method extracts meaningful spatiotemporal patterns, outperforming existing techniques in user similarity measurement.

What Problem Does This Paper Address?

The increasing availability of mobility data from sources like mobile phones presents a rich opportunity for various applications, including route prediction, social networking, and community finding. However, effectively utilizing this raw, low-level data to build meaningful "mobility profiles" for users is a significant challenge. Key hurdles include:

  • Data Granularity: Raw GSM cell ID data is imprecise and lacks inherent semantic meaning.
  • Data Quality Issues: GSM data is prone to missing values (due to network changes or user behavior) and "cell oscillation" (where a user is assigned multiple cell IDs while stationary, creating false mobility signals).
  • Extracting Meaningful Information: Converting these raw signals into high-level insights about a user's habits and significant locations is non-trivial.
  • User Similarity: Accurately determining how similar two users' mobility patterns are is crucial for many applications but is complicated by the aforementioned data challenges and variations in how users tag locations.

Existing methods often rely on more precise location data (like GPS) or struggle to robustly handle the inherent noise and ambiguity in GSM data. This paper aims to bridge this gap by developing a method that works effectively with readily available GSM data.

Methods

The proposed methodology is an unsupervised, two-phase approach:

Phase 1: Mobility Profile Building

  1. Location Information Retrieval and Outlier Removal: The process begins by retrieving raw cell ID data. This is then processed to remove spatial outliers and consolidate location information, often by mapping cell IDs to approximate geographic coordinates using external APIs.
  2. Cell Oscillation Resolution and Semantic Tagging: A core contribution is the resolution of cell oscillation. This is achieved by analyzing time spent at locations and using semantic tags (e.g., "home," "work") provided by users. Overlapping cell IDs that represent a single "stay point" are identified, effectively filtering out false mobility signals.
  3. Stay Point and Pattern Extraction: Identified stay points are time-stamped to create "fingerprints" that capture the user's presence at a location, the duration, and any associated semantic tag. These fingerprints are then grouped into clusters representing significant places. Frequent mobility patterns (sequences of stay points) are extracted using algorithms like prefix-span.
  4. Mobility Pattern Representation: Maximal trajectory patterns are used to represent user mobility, focusing on the most frequent and representative sequences of stay points.

Phase 2: User Similarity Mining

  1. Spatiotemporal Similarity Calculation: User similarity is determined by comparing their extracted mobility patterns. This involves calculating:
  2. Longest Common Subsequence (LnCSS): Measures the similarity of semantic patterns.
  3. Colocation Property (CoL): Accounts for both spatial proximity and temporal overlap of user visits to locations. This is crucial because semantic tags can be inconsistent.
  4. Similarity Matrix Construction: A similarity matrix is built based on these spatiotemporal and semantic comparisons.
  5. Overall User Similarity: The final user similarity is derived from this matrix, providing a quantitative measure of how alike two users' mobility behaviors are.

The approach emphasizes using both the raw GSM network properties (like cell IDs) and the user-provided semantic information in an integrated, unsupervised manner.

Datasets

The primary dataset used for evaluation is the MIT reality mining dataset. This dataset was collected from 100 individuals over a 9-month period using Nokia 6600 mobile phones, which lack GPS capabilities. Location information is derived solely from cell IDs. The dataset also includes user-provided semantic tags for important locations. The authors note that this dataset is from 2008 and that GSM networks have evolved since then.

Key Insights and Ideas

  • Leveraging GSM Data: The paper demonstrates that valuable insights into user mobility can be extracted even from low-precision GSM cell ID data, which is widely available.
  • Handling "Cell Oscillation": Effectively resolving cell oscillation is critical for accurate mobility profiling. Their method combines temporal analysis and semantic tags to distinguish true movement from network artifacts.
  • Semantic Tags are Imperfect: The authors acknowledge that semantic tags can be inconsistent and subjective. Their approach mitigates this by integrating them with spatiotemporal analysis, making the similarity measure more robust.
  • Unsupervised Approach: The methodology is unsupervised, meaning it doesn't require pre-labeled data for training similarity models, making it more broadly applicable.
  • Combined Spatiotemporal and Semantic Analysis: The core idea is that combining these two types of information provides a more accurate and comprehensive understanding of user behavior than either alone.

Key Results

The paper presents experimental results demonstrating the effectiveness of their proposed methodology.

  • Outperformance: Their proposed "Hybrid Approach" (HA) consistently outperforms baseline methods like Spatial Cosine Similarity (SCS) and Extra-Role Colocation Rate (ERCR) in user similarity measurement, as evaluated by Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (NDCG) metrics.
  • Data Cleaning Effectiveness: Figures and tables show the successful retrieval of location information and the consolidation of data after outlier removal and spatial clustering.
  • Pattern Analysis: Analysis of mobility pattern length (Figure 7) suggests that most significant patterns are of length 3, indicating a common transition phase.
  • User Trend Visualization: Visualizations (Figure 8) show that users tend to spend most of their time at known, often semantically tagged, locations.

Limitations and Future Work

Limitations:

  • Dataset Age: The MIT reality mining dataset is from 2008, and GSM networks have evolved significantly since then. This might affect the direct applicability of findings to current network conditions.
  • Partial Cell ID Information: The dataset only provides partial cell global identity (CGI) information (LAC and Cell ID), making precise location determination challenging.
  • Semantic Tag Inconsistency: While addressed, the inherent inconsistency of user-provided semantic tags remains a challenge.

Future Work:

  • Transient Reactions: Investigating user behavior in response to transient events like road construction or special events.
  • Real-World Scenarios: Applying the methodology to real-world scenarios for location-based services.
  • Advanced Pattern Extraction: Exploring more sophisticated techniques for extracting and analyzing mobility patterns.

Summary updated

Abstract

Mobility data has attracted the researchers for the past few years because of its rich context and spatiotemporal nature, where this information can be used for potential applications like early warning system, route prediction, traffic management, advertisement, social networking, and community finding. All the mentioned applications are based on mobility profile building and user trend analysis, where mobility profile building is done through significant places extraction, user's actual movement prediction, and context awareness. However, significant places extraction and user's actual movement prediction for mobility profile building are a trivial task. In this paper, we present the user similarity mining-based methodology through user mobility profile building by using the semantic tagging information provided by user and basic GSM network architecture properties based on unsupervised clustering approach. As the mobility information is in low-level raw form, our proposed methodology successfully converts it to a high-level meaningful information by using the cell-Id location information rather than previously used location capturing methods like GPS, Infrared, and Wifi for profile mining and user similarity mining.
BibTeX
@article{shad2013unsupervised,
  author = {Shafqat Ali Shad and Enhong Chen},
  title = {{Unsupervised User Similarity Mining in GSM Sensor Networks}},
  journal = {The Scientific World JOURNAL},
  year = {2013},
  doi = {10.1155/2013/589610},
}
Figure