derekwtian/mostpopularroute

Algorithms for discovering popular routes from trajectories

Discovering Popular Routes from Trajectories

Implementation of an algorithm for discovering popular routes from trajectories based on the paper published by IEEE

Abstract The booming industry of location-based services has accumulated a huge collection of users' location trajectories of driving, cycling, hiking, etc. In this work, we investigate the problem of discovering the Most Popular Route (MPR) between two locations by observing the traveling behaviors of many previous users. This new query is beneficial to travelers who are asking directions or planning a trip in an unfamiliar city/area, as historical traveling experiences can reveal how people usually choose routes between locations. To achieve this goal, we firstly develop a Coherence Expanding algorithm to retrieve a transfer network from raw trajectories, for indicating all the possible movements between locations. After that, the Absorbing Markov Chain model is applied to derive a reasonable transfer probability for each transfer node in the network, which is subsequently used as the popularity indicator in the search phase. Finally, we propose a Maximum Probability Product algorithm to discover the MPR from a transfer network based on the popularity indicators in a breadth-first manner, and we illustrate the results and performance of the algorithm by extensive experiments.

Data Preparation

The dataset we used in our experiments is downloaded from here

The script takes *.plt files as input. The dataset path and some other variables have to be set with the following format :

Starting at line 24 in config.py:

DATASET_ROOT_DIR = '../data/test2/Data'   # The data set root directory
DATASET_SCALE    = 3                    # How many users' trajectory data are choosed
TRAJACTORY_SCALE = 4                    # How many trajectories are choosed per user
RANGE = {                               # To pick trajectory points within the range
    'status': True,
    'longitude_upper_bound': 116.32,
    'longitude_lower_bound': 116.304,
    'latitude_upper_bound': 40.018,
    'latitude_lower_bound': 40.004,
}

Mining Transfer Network

Coherence expanding algorithms are used to construct the trasfer network from a set of raw trajectory points.

Step 1

Set parameters for Coherence Expanding Algorithm. These variables have to be carefully adjusted according to different dataset.

Starting at line 35 in config.py:

GROUP_SIZE_THRESHOLD    = 3         # group size threshold φ
COHERENCE_THRESHOLD     = 0.99      # coherence threshold τ
SCALING_FACTOR          = 15e-4     # scaling factor δ
TURNING_ALPHA           = 5         # tuning parameter α
TURNING_BETA            = 2         # tuning parameter β

Step 2

Initialize the program by running

python adjust_params.py

Analysis graph and reports are generated to help adjust the parameters

Figure 1 experiment on simulated dataset with 192 points, 16 clusters are found

Figure 2 experiment on real dataset with 1154 points, 60 clusters are found

Deriving Transfer Probability

Through the Coherence Expanding Algorithm, we can retrieve a transfer network G(N,E) from raw trajectories. For each transfer node n_i , we calculate the vector V assuming it as the destination.

We draw transfer nodes by rectangles with the size propotional to their transfer probabilities. The destination is shown as a red rectangle.

Figure 3 Distribution of transfer probability

Searching the Most Popular Route

Through mining transfer network and the derivation of transfer probabilities, we acquire a directional transfer network G(N,E) with a set of transfer probability vectors(V).

Through the Maximum Probability Algorithm, we can discover the most popular route from the given start node A to end node B.

Figure 4 MPR from node A to node B

Figure 5 MPR from node A to node B