基于Period-Near算法的用户移动位置预测

doi:10.3969/j.issn.1006-2475.2017.06.003

计算机与现代化

基于Period-Near算法的用户移动位置预测

(山东大学计算机科学与技术学院，山东济南 250101)

收稿日期:2016-09-09 出版日期:2017-06-23 发布日期:2017-06-23
作者简介:高夏(1988-)，男，江苏镇江人，山东大学计算机科学与技术学院硕士研究生，研究方向：数据挖掘，大数据处理。

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

(School of Computer Science & Technology, Shandong University, Jinan 250101, China)

Received:2016-09-09 Online:2017-06-23 Published:2017-06-23

摘要/Abstract

摘要： 新浪微博是一种允许大量用户彼此分享包括位置在内的个人信息的电子媒介，它使得掌握用户的运动轨迹成为可能。尽管用户的运动和移动模式有着高度的自由性和多样性，但是周期性的运动是非常频繁的现象，因此寻找用户的周期行为对于了解用户的动作至关重要。在本文中将这个问题定义为“预测用户将要去哪里”，该问题涉及2个子问题：如何发现用户的历史行为以及如何应用用户的历史行为来预测其将来的行为。假设用户的行为是周期性的，并且如果用户在一个位置的时间足够长，那么他/她将会一直待在这个位置。基于这2个假设，提出一个4阶段算法Period-Near来解决这个问题。在算法的第1阶段挖掘用户的周期性行为，第2阶段发现其较为频繁的移动，第3阶段了解用户在最近一段时间所处的位置，第4阶段是根据前3个阶段来预测用户接下来将要去哪里。无论是在综合数据上还是实际数据上的实验研究均表明本文方法具有一定的有效性。

关键词: 行为预测, 频繁移动, 实际生活需求, 交叉定位

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

中图分类号:

TP391

高夏. 基于Period-Near算法的用户移动位置预测[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.06.003.

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.

参考文献

[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.

基于Period-Near算法的用户移动位置预测

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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价