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.


Published in:
Proc. IEEE International Conference on Data Mining
Presented at:
2015 IEEE International Conference on Data Mining, Atlantic City, NJ, USA, November 14-17, 2015
Year:
2015
Publisher:
IEEE
ISBN:
978-1-4673-9504-5
Keywords:
Laboratories:




 Record created 2016-12-14, last modified 2018-03-18

Publisher's version:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)