Traveling Salesman in Reverse: Conditional Markov Entropy for Trajectory Segmentation

We are interested in inferring the set of waypoints (or intermediate destinations) of a mobility trajectory in the absence of timing information. We find that, by mining a dataset of real mobility traces, computing the entropy of conditional Markov trajectory enables us to uncover waypoints, even though no timing information nor absolute geographic location is provided. We build on this observation and design an efficient algorithm for trajectory segmentation. Our empirical evaluation demonstrates that the entropy-based heuristic used by our segmentation algorithm outperforms alternative approaches as it is 43% more accurate than a geometric approach and 20% more accurate than path-stretch based approach. We further explore the link between trajectory entropy, mobility predictability and the nature of intermediate locations using a route choice model on real city maps.


Publié dans:
Proc. IEEE International Conference on Data Mining
Présenté à:
2015 IEEE International Conference on Data Mining, Atlantic City, NJ, USA, November 14-17, 2015
Année
2015
Publisher:
IEEE
ISBN:
978-1-4673-9504-5
Mots-clefs:
Laboratoires:


Note: Le statut de ce fichier est: Anyone


 Notice créée le 2016-12-14, modifiée le 2020-06-17

Publisher's version:
Télécharger le document
PDF

Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)