基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘

王亮; 胡琨元; 库涛; 吴俊伟

doi:10.16383/j.aas.2015.c130804

基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘

doi: 10.16383/j.aas.2015.c130804

王亮^1,2,3, ,,
胡琨元¹,
库涛¹,
吴俊伟^1,3

1.
中国科学院沈阳自动化研究所信息服务与智能控制研究室沈阳 110016;
2.
西安科技大学电气与控制工程学院西安 710054;
3.
中国科学院大学北京 100049

基金项目:

国家自然科学基金(61003208, 61203161, 61174164, 61105067, 614 02360)资助

详细信息

作者简介:
胡琨元中国科学院沈阳自动化研究所研究员.1994年获西安电子科技大学检测技术与仪器专业工学学士学位,2003年获东北大学系统工程专业工学博士学位.主要研究方向为智能信息处理技术,移动商务与现代物流,企业信息化. E-mail:hukunyuan@sia.cn

通讯作者:
王亮西安科技大学讲师,博士.2009年获东北大学控制理论与控制工程专业工学硕士学位,2014年获中国科学院沈阳自动化研究所工学博士学位.主要研究方向为移动计算,智能信息处理,复杂系统建模与优化理论.本文通信作者. E-mail:liangwang0123@gmail.com

计量
- 文章访问数: 1724
- HTML全文浏览量: 103
- PDF下载量: 1099
- 被引次数: 0
出版历程
- 收稿日期: 2013-08-19
- 修回日期: 2014-03-25
- 刊出日期: 2015-01-20

Mining Urban Moving Trajectory Patterns Based on Multi-scale Space Partition and Road Network Modeling

WANG Liang^{1,2,3
, ,},
HU Kun-Yuan¹,
KU Tao¹,
WU Jun-Wei^1,3

1.
Laboratory of Information Service and Intelligent Control, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 1100116;
2.
College of Electrical and Control Engineering, Xi'an University of Science and Technology, Xi'an, 710054;
3.
University of Chinese Academy of Sciences, Beijing 100049

Funds:

Supported by National Natural Science Foundation of China (61003208, 61203161, 61174164, 61105067, 61402360)

摘要

摘要: 针对城市移动轨迹模式挖掘问题展开研究, 提出移动全局模式与移动过程模式相结合的挖掘方法, 即通过移动轨迹的起始位置点--终点位置点 (Origin-destination, OD点) 与移动过程序列分别进行移动全局模式与过程模式的发现. 在移动全局模式发现中, 提出了弹性多尺度空间划分方法, 避免了硬性等尺度网格划分对密集区域边缘的破坏, 同时增强了密集区域与稀疏区域的区分能力.在移动过程模式发现中, 提出了基于移动轨迹的路网拓扑关系模型构建方法, 通过路网关键位置点的探测抽取拓扑关系模型.最后基于空间划分集合与路网拓扑模型对原始移动轨迹数据进行序列数据转换与频繁模式挖掘. 通过深圳市出租车历史 GPS 轨迹数据的实验结果表明, 该方法与现有方法相比在区域划分、数据转换等方面具有更好的性能, 同时挖掘结果语义更为丰富, 可解释性更强.
- 数据挖掘 /
- 移动轨迹 /
- 多尺度划分 /
- 路网模型
Abstract: In this paper, the problem of discovering moving trajectory patterns in urban environment is studied and the method of integration of moving global pattern and moving local pattern is proposed. Through moving trajectory origin-destination (OD) and moving sequence features, the global patterns and local patterns are mined. In the process of moving global pattern mining, a flexible multi-scale space partition is devised to avoid damage of the dense region edges by hard regular grid division and enhance the ability to distinguish the dense regions and sparse regions. In the process of moving local pattern mining, the modeling method of road network based on moving trajectory is devised to extract the feature of topological relation by key road network nodes. Finally, the raw moving trajectory dataset is converted by partitioned discrete regions and road network model, and the frequent moving trajectory patterns are discovered by a modified sequence pattern mining algorithm. A comprehensive experimental evaluation on Shenzhen taxicabs GPS trajectory dataset is presented, and the evaluation shows that the proposed method outperforms the existing methods in space division, data transform, and interpretability of mined patterns.
- Data mining /
- moving trajectory /
- multi-scale partition /
- road network modeling

HTML全文

参考文献(32)

[1]	Liu Yu, Xiao Yu, Gao Song, Kang Chao-Gui, Wang Yao-Li. A review of human mobility research based on location aware devices. Geography and Geo-Information Science, 2011, 27(4): 8-13(刘瑜, 肖昱, 高松, 康朝贵, 王瑶莉. 基于位置感知设备的人类移动研究综述. 地理与地理信息科学, 2011, 27(4): 8-13)
[2]	Wang Ming-Sheng, Huang Lin, Yan Xiao-Yong. Exploring the mobility patterns of public transport passengers. Journal of University of Electronic Science and Technology of China, 2012, 41(1): 2-7 (王明生, 黄琳, 闫小勇. 探索城市公交客流移动模式. 电子科技大学学报, 2012, 41(1): 2-7)
[3]	Zou Yong-Gui, Wan Jian-Bin, Xia Ying. LBSN user movement trajectory clustering mining method based the road network. Application Research of Computers, 2013, 30(8): 2410-2414(邹永贵, 万建斌, 夏英. 基于路网的 LBSN 用户移动轨迹聚类挖掘方法. 计算机应用研究, 2013, 30(8): 2410-2414)
[4]	Castro P S, Zhang D Q, Li S J. Urban traffic modelling and prediction using large scale taxi GPS traces. In: Proceedings of the 2012 Pervasive Computing Lecture Notes in Computer Science. Berlin Heidelberg: Springer, 2012. 57-72
[5]	Gong H M, Chen C, Bialostozky E, Lawson C T. A GPS/ GIS method for travel mode detection in New York city. Computers, Environment, and Urban Systems, 2012, 36(2): 131-139
[6]	Yue Y, Wang H D, Hu B, Li Q Q, Li Y G, Yeh A G O. Exploratory calibration of a spatial interaction model using taxi GPS trajectories. Computers, Environment, and Urban Systems, 2012, 36(2): 140-153
[7]	Zhan X Y, Hasan S, Ukkusuri S V, Kamga C. Urban link travel time estimation using large-scale taxi data with partial information. Transportation Research Part C: Emerging Technologies, 2013, 33: 37-49
[8]	Brouwers N, Woehrle M. Dwelling in the canyons: dwelling detection in urban environments using GPS, Wi-Fi, and geolocation. Pervasive and Mobile Computing, 2013, 9(5): 665 -680
[9]	Yue Y, Zhuang Y, Li Q Q, Mao Q Z. Mining time-dependent attractive areas and movement patterns from taxi trajectory data. In: Proceedings of the 17th International Conference on Geoinformatics. Fairfax, USA: IEEE, 2009. 1-6
[10]	Zhang W S, Li S J, Pan G. Mining the semantics of origin-destination flows using taxi traces. In: Proceedings of the 2012 ACM Conference on Ubiquitous Computing. New York, USA: ACM, 2012. 943-949
[11]	Guo D S, Zhu X, Jin H, Gao P, Andris C. Discovering spatial patterns in origin-destination mobility data. Transactions in GIS, 2012, 16(3): 411-429
[12]	Pan G, Qi G D, Wu Z H, Zhang D Q, Li S J. Land-use classification using taxi GPS traces. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(1): 113-123
[13]	Veloso M, Phithakkitnukoon S, Bento C. Urban mobility study using taxi traces. In: Proceedings of the 2011 International Workshop on Trajectory Data Mining and Analysis. New York: ACM, 2011. 23-30
[14]	Veloso M, Phithakkitnukoon S, Bento C. Sensing urban mobility with taxi flow. In: Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Location-Based Social Networks. New York, USA: ACM, 2011. 41-44
[15]	Huang Jian-Bin, Zhang Pan-Pan, Huangfu Xue-Jun, Sun He-Li. A trajectory prediction approach for mobile objects by combining semantic features. Journal of Computer Research and Development, 2014, 51(1): 76-87(黄健斌, 张盼盼, 皇甫学军, 孙鹤立. 融合语义特征的移动对象轨迹预测方法. 计算机研究与发展, 2014, 51(1): 76-87)
[16]	Zhao Yue, Liu Yan-Heng, Yu Xue-Gang, Wei Da, Shan Chang-Wei, Zhao Yang. Method for mobile path prediction based on pattern mining and matching. Journal of Jilin University (Engineering and Technology Edition), 2008, 38(5): 1125-1130(赵越, 刘衍珩, 余雪岗, 魏达, 单长伟, 赵洋. 基于模式挖掘与匹配的移动轨迹预测方法. 吉林大学学报 (工学版), 2008, 38(5): 1125- 1130)
[17]	Gidófalvi G, Pedersen T B. Mining long, sharable patterns in trajectories of moving objects. GeoInformatica, 2009, 13(1): 27-55
[18]	Sohn K, Kim D. Dynamic origin-destination flow estimation using cellular communication system. IEEE Transactions on Vehicular Technology, 2008, 57(5): 2703-2713
[19]	Caceres N, Wideberg J P, Benitez F G. Deriving origin destination data from a mobile phone network. IET Intelligent Transport Systems, 2007, 1(1): 15-26
[20]	Won J I, Kim S W, Baek J H, Lee J. Trajectory clustering in road network environment. In: Proceedings of the 2009 Computational Intelligence and Data Mining. Nashville, USA: IEEE, 2009. 299-305
[21]	Li X L, Han J W, Lee J G, Gonzalez H. Traffic density-based discovery of hot routes in road networks. Advances in Spatial and Temporal Databases, Berlin Heidelberg: Springer, 2007. 441-459
[22]	Giannotti F, Nanni M, Pinelli F, Pedreschi D. Trajectory pattern mining. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2007. 330-339
[23]	Lee J G, Han J W, Li X L, Gonzalez H. TraClass: trajectory classification using hierarchical region based and trajectory based clustering. In: Proceedings of the 2008 VLDB Endowment. Auckland, New Zealand: VLDB, 2008. 1081-1094
[24]	Wang L, Hu K Y, Ku T, Yan X H. Mining frequent trajectory pattern based on vague space partition. Knowledge-Based Systems, 2013, 50: 100-111
[25]	Li H J, Tang C J, Qiao S J, Wang Y, Yang N, Li C. Hotspot district trajectory prediction. In: Proceedings of the 2010 Web-Age Information Management. Berlin Heidelberg: Springer, 2010. 74-84
[26]	Agrawal R, Imieliński T, Swami A. Mining association rules between sets of items in large databases. In: Proceedings of the 1993 ACM-SIGMOD International Conference on Management of Data. New York, USA: ACM, 1993. 207-216
[27]	Agrawal R, Srikant R. Fast algorithms for mining association rules. In: Proceedings of the 1994 International Conference on Very Large Data Bases. Santiago, Chile: VLDB, 1994. 487-499
[28]	Srikant R, Agrawal R. Mining sequential patterns: generalizations and performance improvements. In: Proceedings of the 5th International Conference on Extending Database Technology. Avignon, France: EDBT, 1996. 3-17
[29]	Pei J, Han J W, Mortazavi-Asl B, Wang J Y, Pinto H, Chen Q M. Mining sequential patterns by pattern-growth: the prefixspan approach. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 1424-1440
[30]	Han J W, Cheng H, Xin D, Yan X F. Frequent pattern mining: current status and future directions. Data Mining and Knowledge Discovery, 2007, 15(1): 55-86
[31]	Wu Feng, Zhong Yan, Wu Quan-Yuan. Mining frequent patterns over data stream under the time decaying model. Acta Automatica Sinica, 2010, 36(5): 674-684(吴枫, 仲妍, 吴泉源. 基于时间衰减模型的数据流频繁模式挖掘. 自动化学报, 2010, 36(5): 674-684)
[32]	Pan Yun-He, Wang Jin-Long, Xu Cong-Fu. State-of-the-art on frequent pattern mining in data streams. Acta Automatica Sinica, 2006, 32(4): 594-602(潘云鹤, 王金龙, 徐从富. 数据流频繁模式挖掘研究进展. 自动化学报, 2006, 32(4): 594-602)