Prediction of User’s Moving Location Based on Period-Near Algorithm

doi:10.3969/j.issn.1006-2475.2017.06.003

Abstract

Abstract: Sina Weibo is an electronic medium that allows a large number of users to share personal information with each other including location information, which makes it possible to know users’ movement. Even though users’ movement and mobility patterns have a high degree of freedom and variation, periodicity is a frequently happening phenomenon for users. Finding periodic behaviors is essential for understanding user movements. In this paper, we address the problem as to predict where a user will go. It involves two sub-problems: how to detect users’ historical behavior, and how to use historical behaviors to predict the behavior in the future. Our main assumptions are that users’ behaviors are periodic and a user will stay in one location if he or she stays in this location for a long time. Based on these assumptions, we propose a 4-stage algorithm, Period-Near, to solve the problem. At the first stage, we mine the periodic behaviors of a user, then, find frequent transfers. At the third stage, we aim to know where the user is in the nearest time. At last, we consider the three stages together to predict where the user will go in the next time. Empirical studies on both synthetic and real data sets demonstrate the effectiveness of our method.

Key words: behavior prediction, frequent movement, real-life needs, cross location

CLC Number:

TP391

GAO Xia. Prediction of User’s Moving Location Based on Period-Near Algorithm[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.06.003.

References

[1] Gonzalez M C, Hidalgo C A, Barabasi A-L. Understanding individual human mobility patterns[J]. Nature, 2008,453(7196):779-782.

[2] Kapoor A, Eagle N, Horvitz E. People, quakes, and communications: Inferences from call dynamics about a seismic event and its influences on a population[C]// Proceedings of the 2010 AAAI Spring Symposium on Artificial Intelligence for Development. 2010.

[3] Song Chaoming, Qu Zehui, Blumm N, et al. Limits of predictability in human mobility[J]. Science, 2010,327(5968):1018-1021.

[4] Humphreys L. Mobile social networks and social practice: A case study of Dodgeball[J]. Journal of Computer-Mediated Communication, 2007,13(1):341-360.

[5] Scellato S, Noulas A, Lambiotte R, et al. Socio-spatial properties of online location-based social networks[C]// Proceedings of the 5th International AAAI Conference on Weblogs and Social Media. 2011:329-336.

[6] Noulas A, Scellato S, Mascolo C, et al. An empirical study of geographic user activity patterns in foursquare[C]// Proceedings of the 5th International AAAI Conference on Weblogs and Social Media. 2011:570-573.

[7] Sui Xueqin, Chen Zhumin, Wu Kai, et al. Social media as sensor in real world: Geolocate user with microblog[C]// Proceedings of the 3rd CCF Conference on Natural Language Processing and Chinese Computing. 2014:229-237.

[8] Cheng Zhiyuan, Caverlee J, Lee K. You are where you tweet: A content-based approach to geo-locating Twitter users[C]// Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010:759-768.

[9] Sadilek A, Kautz H, Bigham J P. Finding your friends and following them to where you are[C]// Proceedings of the 5th ACM International Conference on Web Search and Data Mining. 2012:723-732.

[10] Cho E, Myers S A, Leskovec J. Friendship and mobility: User movement in location-based social networks[C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011:1082-1090.

[11] Li Zhenhui, Ding Bolin, Han Jiawei, et al. Mining periodic behaviors for moving objects[C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010:1099-1108.

[12] Leighton T. Improving performance on the Internet[J]. Communications of the ACM, 2009,52(2):44-51.

[13] Hao Qiang, Cai Rui, Wang Changhu, et al. Equip tourists with knowledge mined from travelogues[C]// Proceedings of the 19th International Conference on World Wide Web. 2010:401-410.

[14] Zheng V W, Zheng Yu, Xie Xing, et al. Collaborative location and activity recommendations with GPS history data[C]// Proceedings of the 19th International Conference on World Wide Web. 2010:1029-1038.

[15] Zheng Yu, Zhang Lizhu, Xie Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C]// Proceedings of the 18th International Conference on World Wide Web. 2009:791-800.

[16] Glaeser E L, Kahn M E. Sprawl and urban growth[M]// Handbook of Regional and Urban Economics. Elsevier, 2004,4:2481-2527.

[17] Eubank S, Guclu H, Kumar V S A, et al. Modelling disease outbreaks in realistic urban social networks[J]. Nature, 2004,429(6988):180-184.

[18] Hatton T J, Williamson J G. Global Migration and the World Economy: Two Centuries of Policy and Performance[M]. The MIT Press, 2006.

[19] Amitay E, Har’El N, Sivan R, et al. Web-a-where: Geotagging Web content[C]// Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2004:273-280.