Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
DECODING THE OPTIMAL ROUTE ON TRANSPORT GRAPH USING CELLULAR DATA
Vadim E. Uvarov, Tele2, Moscow, Russia; Novosibirsk State Technical University, Novosibirsk, Russia, uvarov.vadim42@gmail.com
Dmitry V. Kurgansky, Tele2, Moscow, Russia, dmitry.kurgansky@tele2.ru
Alexander A. Popov, Novosibirsk State Technical University, Novosibirsk, Russia, alex@fpm.ami.nstu.ru
Artem A. Klimov, Tele2, Moscow, Russia, artem.klimov@tele2.ru
Anton S. Merzlyakov, Tele2, Moscow, Russia, anton.merzlyakov@tele2.ru
Abstract
The article presents a novel algorithm for optimal route decoding on transport graph using cellular data which uses probabilistic approach based on hidden Markov model. The distinctive feature of the proposed algorithm is that it can process sequential cellular data that consists of highly sparse call data records (CDR) instead of far more accurate GPS-data. Another feature is that this algorithm is able to cope with incomplete data in case when no path on graph can be found between the consecutive CDRs thanks to the proposed modified Viterbi algorithm. The algorithm was evaluated using anonymized CDRs and corresponding test GPS-data. The evaluation showed that the presented method is 2.5 more accurate than the simple algorithm that connects the coordinates of cell towers in order of their appearance. Also, it was shown that modified Viterbi algorithm allows to cover 30% more of test GPS-data points in comparison with of the standard version. In addition, the experimental data was presented that confirms the choice of hyperparameters used for the algorithm and one of the optimal hyperparameters was calculated with the alternative formula which also agrees with the evaluation data. Further work includes adding signal strength, speed, time, route complexity, road priorities and other factors to probabilistic model which will not only improve the algorithm accuracy but will also allow the transport type classification. The preliminary tests of the new version of algorithm shows that the error can be lowered down to 100 meters.
Keywords: hidden Markov models, incomplete data, telecommunication, machine learning, data science.
References
1. Quddus M.A., Ochieng W.Y., Noland R.B. (2007). Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transportation Research Part C: Emerging Technologies, vol. 15, iss. 5, pp. 312-328.
2. Rabiner L.R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, vol. 77, pp. 257-285.
3. Newson P., Krumm J. (2009). Hidden Markov Map Matching Through Noise and Sparseness. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 336 343.
4. Algizawy E. and Ogawa T. and El-Mahdy A. (2017). Real-Time Large-Scale Map Matching Using Mobile Phone Data. ACM Trans. Knowl. Discov. Data, vol. 11, no. 4, pp. 52:1 52:38.
5. OpenStreetMap contributors (2019). Open Street Maps, [Online], available at: https://www.openstreetmap.org, (accessed 16 April 2019).
6. Uvarov V.E., Popov A.A., Gultyaeva T.A. (2018). User Identification from Incomplete Motion Data Using Hidden Markov Models. 14th International Conference on Actual Problems of Electronic Instrument Engineering Proceedings, vol. 1, pp. 327-329.
7. Viterbi A.J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, vol. 13, iss. 2, pp. 260-269.
8. Rousseeuw P.J., Croux C. (1993). Alternatives to the median absolute deviation. Journal of the American Statistical Association, vol. 88, no. 424, pp. 1273-1283.
9. Gather U., Schultze V. (1999). Robust estimation of scale of an exponential distribution. Statistica Neerlandica, vol. 53, iss. 3, pp. 327-341.
10. Eiter T., Mannila H. (1994)þ Computing discrete Frechet distance. Tech. Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems.
Information about authors:
Vadim E. Uvarov, data scientist, Tele2, Moscow, Russia; postgraduate studentb, Novosibirsk State Technical University, Novosibirsk, Russia
Dmitry V. Kurgansky, data scientist, Tele2, Moscow, Russia
Alexander A. Popov, PhD, professorb, Novosibirsk State Technical University, Novosibirsk, Russia
Artem A. Klimov, senior data scientista, Tele2, Moscow, Russia
Anton S. Merzlyakov, head of big data departmenta, Tele2, Moscow, Russia