基于出行模式子图的城市功能区域发现方法

doi:10.11896／j.issn.1002-137X.2018.12.044

摘要/Abstract

摘要： 城市的功能区域是指在城市的发展过程中逐渐形成的功能(如工业、商业、居住、教育等)相对固定的地理区域。这些区域间的位置结构影响着城市中居民的出行模式,与此同时,城市居民的出行模式也客观地反映了城市不同区域的真实的功能定位。文中以出租车运行轨迹数据为基础,研究城市居民的出行模式,并根据所得模式实现城市功能区域的自动化发现。主要思路及贡献包括:1)使用车辆轨迹及路网结构数据构造区域模式图(region pattern graph)结构,并提出区域模式图构建算法,采用图结构将城市的不同地理区域连接起来;2)提出自底而上的功能区域发现算法(Bottom-Up Functional Region Discovering,BUFRD)框架及基本实现思路,包括提出频繁出行模式子图挖掘算法,发现区域模式图中频繁出现的出行模式;3)提出功能区域聚类算法,聚类已获取的出行模式子图集,并最终实现城市功能区域的发现。实验结果表明,通过所提方法发现的城市功能区域较传统方法所得结果的功能纯度更高,其熵值比传统方法降低了至少10%。

关键词: 城市大数据, 城市功能区域, 出行模式子图, 数据挖掘

Abstract: City’s functional regions refer to the geographical regions with relatively fixed functions(such as industry,commerce,housing,education,etc.) in the development of city.The position structure of these functional regionsaffect people’s travel patterns,and these travel patterns also objectively reflect the real function of regions.This paper focused on the travel patterns of urban residents by using the taxicabs’ trajectory data,and obtained functional regions accor-ding to these travel models.The main contributions of this paper are as follows.Firstly,this paper constructed the region pattern graph by using the taxicabs’ trajectories and the road network structures,and then connected different geographical regions via the graph structure created by region graph pattern construcing algorithm.Secondly,this paper proposed the framework and basic implementation idea of bottom-up functional region discovering algorithm,including mining the frequent travel pattern subgraphs and discovering frequent travel pattern from these subgraphs.Thirdly,this paper proposed a functional region cluster algorithm to cluster the obtained travel pattern graph set,thus discovering the functional regions according to the clustering results.The experimental results show that this method is effective and achieves higher purity of the function compared with traditional methods,and the entropy is decreased by 10%.

Key words: City big data, City functional region, Data mining, Travel pattern subgraph

中图分类号:

TP311

肖飞, 王悦, 梅逸男, 白璐, 崔丽欣. 基于出行模式子图的城市功能区域发现方法[J]. 计算机科学, 2018, 45(12): 268-278. https://doi.org/10.11896／j.issn.1002-137X.2018.12.044

XIAO Fei, WANG Yue, MEI Yi-nan, BAI Lu, CUI Li-xin. City Functional Region Discovery Algorithm Based on Travel Pattern Subgraph[J]. Computer Science, 2018, 45(12): 268-278. https://doi.org/10.11896／j.issn.1002-137X.2018.12.044

参考文献

[1]FURLETTI B,CINTIA P,RENSO C,et al.Inferring human ac-tivities from GPS tracks[C]∥Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing.ACM,2013.
[2]YUAN N J,ZHENG Y,XIE X,et al.Discovering urban func-tional zones using latent activitytrajectories[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(3):712-725.
[3]ZHENG Y,LIU Y,YUAN J,et al.Urban computing with taxicabs[C]∥Proceedings of the 13th International Conference on Ubiquitous Computing.ACM,2011:89-98.
[4]HUANG X,ZHAO Y,MA C,et al.TrajGraph:A graph-based visual analytics approach to studying urban network centralities using taxi trajectory data[J].IEEE Transactions on Visualization and Computer Graphics,2016,22(1):160-169.
[5]ZHENG Y,CAPRA L,WOLFSON O,et al.Urban computing:concepts,methodologies,and applications[J].ACM Transactions on Intelligent Systems and Technology (TIST),2014,5(3):38.
[6]YUAN J,ZHENG Y,XIE X.Discovering regions of differentfunctions in a city using human mobility and POIs[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2012:186-194.
[7]YAJING X,GONGFU L,CHAO X,et al.Affinity-based human mobility pattern for improved region function discovering[J].The Journal of China Universities of Posts and Telecommunications,2016,23(1):60-67.
[8]DEZANI H,BASSI R D S,MARRANGHELLO N,et al.Optimizing urban traffic flow using Genetic Algorithm with Petri net analysis as fitness function[J].Neurocomputing,2014,124:162-167.
[9]TANG J,LIU F,WANG Y,et al.Uncovering urban humanmobility from large scale taxi GPS data[J].Physica A:Statistical Mechanics and its Applications,2015,438:140-153.
[10]PAN G,QI G,WU Z,et al.Land-use classification using taxi GPS traces[J].IEEE Transactions on Intelligent Transportation Systems,2013,14(1):113-123.
[11]ZHENG Y.Trajectory data mining:an overview[J].ACMTransactions on Intelligent Systems and Technology (TIST),2015,6(3):1-41.
[12]YAN X,HAN J.gspan:Graph-based substructure pattern mi-ning[C]∥IEEE International Conference on Data Mining(ICDM 2003).IEEE,2002:721-724.
[13]ELSEIDY M,ABDELHAMID E,SKIADOPOULOS S,et al.Grami:Frequent subgraph and pattern mining in a single large graph[J].Proceedings of the VLDB Endowment,2014,7(7):517-528.
[14]HaN W S,LEE J,LEE J H.Turbo iso:towards ultrafast and robust subgraph isomorphism search in large graph databases[C]∥Proceedings of the 2013 ACM SIGMOD International Confe-rence on Management of Data.ACM,2013:337-348.
[15]VISHWANATHAN S V N,BORGWARDT K M,KONDORR,et al.Graph Kernels[J].Journal of Machine Learning,2008,11(2):1201-1242.
[16]FOUSS F,FRANCOISSE K,YEN L,et al.An experimental investigation ofkernels on graphs for collaborative recommendation and semisupervised classification[J].Neural Networks,2012,31(none):53-72.
[17]GAÜZERE B,BRUN L,VILLEMIN D.Two new graphs kernels in chemoinformatics[J].Pattern Recognition Letters,2012,33(15):2038-2047.
[18]BARRA V,BIASOTTI S.3D shape retrieval using kernels on extended Reeb graphs[J].Pattern Recognition,2013,46(11):2985-2999.
[19]HIDO S,KASHIMA H.A linear-time graph kernel[C]∥9th IEEE International Conference on Data Mining.2009:179-188.
[20]ZHANG T Y,SUEN C Y.A fast parallel algorithm for thinning digital patterns[J].Comm Acm,1984,27(3):236-239.
[21]FIORIO C,GUSTEDT J.Two linear time Union-Find strategies for image processing[J].Theoretical Computer Science,1996,154(2):165-181.
[22]WU K,OTDO E.Optimizing connected component labeling algorithms[C]∥Medical Imaging:Image Processing.International Society for Optics and Photonics.2005.
[23]OpenStreetMap Foundation.Beijing 3th ring osm data [DB/OL].[2016-06-23].http://www.openstreetmap.org.
[24]CASTRO P S,ZHANG D,CHEN C,et al.From taxi GPS traces to social and community dynamics:A survey[J].Acm Computing Surveys,2013,46(2):1-34.
[25]SNYDER,JOHN P.Map projections[M].Springer Nether-lands.1997.
[26]ROSENFELD A,DAVIS LS.A Note on Thinning.IEEE Transdactions on Systems,Man and Cybernetics,1976,SMC-6(3):226-228.
[27]YAN C,WANG P,SUN L.Sensing Urban with Wi-Fi and Sa-tellite:Functional Region Discovery across Cities[C]∥On Thematic Workshops of Acm Multimedia.ACM,2017:314-322.
[28]LIU X,GONG L,GONG Y,et al.Revealing travel patterns and city structure with taxi trip data[J].Journal of Transport Geography,2015,43:78-90.
[29]FENG Z,ZHU Y.A Survey on Trajectory Data Mining:Techniques and Applications[J].IEEE Access,2017,4:2056-2067.
[30]YU Y,CHEN X.A survey of point-of-interest recommendation in location-based social networks∥Twenty-Ninth AAAI Conference on Artificial Intelligence.2015.
[31]LIU X P,HE J L,YAO Y,et al.Classifying urban land use by integrating remote sensing and social media data[J].International Journal of Geographical Information Science,2017(1):1675-1696.

相关文章 15

[1]	黎嵘繁, 钟婷, 吴劲, 周帆, 匡平. 基于时空注意力克里金的边坡形变数据插值方法 Spatio-Temporal Attention-based Kriging for Land Deformation Data Interpolation 计算机科学, 2022, 49(8): 33-39. https://doi.org/10.11896/jsjkx.210600161
[2]	么晓明, 丁世昌, 赵涛, 黄宏, 罗家德, 傅晓明. 大数据驱动的社会经济地位分析研究综述 Big Data-driven Based Socioeconomic Status Analysis:A Survey 计算机科学, 2022, 49(4): 80-87. https://doi.org/10.11896/jsjkx.211100014
[3]	孔钰婷, 谭富祥, 赵鑫, 张正航, 白璐, 钱育蓉. 基于差分隐私的K-means算法优化研究综述 Review of K-means Algorithm Optimization Based on Differential Privacy 计算机科学, 2022, 49(2): 162-173. https://doi.org/10.11896/jsjkx.201200008
[4]	马董, 李新源, 陈红梅, 肖清. 星型高影响的空间co-location模式挖掘 Mining Spatial co-location Patterns with Star High Influence 计算机科学, 2022, 49(1): 166-174. https://doi.org/10.11896/jsjkx.201000186
[5]	张亚迪, 孙悦, 刘锋, 朱二周. 结合密度参数与中心替换的改进K-means算法及新聚类有效性指标研究 Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index 计算机科学, 2022, 49(1): 121-132. https://doi.org/10.11896/jsjkx.201100148
[6]	吴成凤, 蔡莉, 李劲, 梁宇. 基于多源位置数据的居民出行频繁模式挖掘 Frequent Pattern Mining of Residents’ Travel Based on Multi-source Location Data 计算机科学, 2021, 48(7): 155-163. https://doi.org/10.11896/jsjkx.200800072
[7]	徐慧慧, 晏华. 基于相对危险度的儿童先心病风险因素分析算法 Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children 计算机科学, 2021, 48(6): 210-214. https://doi.org/10.11896/jsjkx.200500082
[8]	张岩金, 白亮. 一种基于符号关系图的快速符号数据聚类算法 Fast Symbolic Data Clustering Algorithm Based on Symbolic Relation Graph 计算机科学, 2021, 48(4): 111-116. https://doi.org/10.11896/jsjkx.200800011
[9]	张寒烁, 杨冬菊. 基于关系图谱的科技数据分析算法 Technology Data Analysis Algorithm Based on Relational Graph 计算机科学, 2021, 48(3): 174-179. https://doi.org/10.11896/jsjkx.191200154
[10]	邹承明, 陈德. 高维大数据分析的无监督异常检测方法 Unsupervised Anomaly Detection Method for High-dimensional Big Data Analysis 计算机科学, 2021, 48(2): 121-127. https://doi.org/10.11896/jsjkx.191100141
[11]	刘新斌, 王丽珍, 周丽华. MLCPM-UC:一种基于模式实例分布均匀系数的多级co-location模式挖掘算法 MLCPM-UC:A Multi-level Co-location Pattern Mining Algorithm Based on Uniform Coefficient of Pattern Instance Distribution 计算机科学, 2021, 48(11): 208-218. https://doi.org/10.11896/jsjkx.201000097
[12]	刘晓楠, 宋慧超, 王洪, 江舵, 安家乐. Grover算法改进与应用综述 Survey on Improvement and Application of Grover Algorithm 计算机科学, 2021, 48(10): 315-323. https://doi.org/10.11896/jsjkx.201100141
[13]	张煜, 陆亿红, 黄德才. 基于密度峰值的加权犹豫模糊聚类算法 Weighted Hesitant Fuzzy Clustering Based on Density Peaks 计算机科学, 2021, 48(1): 145-151. https://doi.org/10.11896/jsjkx.200400043
[14]	游兰, 韩雪薇, 何正伟, 肖丝雨, 何渡, 潘筱萌. 基于改进Seq2Seq的短时AIS轨迹序列预测模型 Improved Sequence-to-Sequence Model for Short-term Vessel Trajectory Prediction Using AIS Data Streams 计算机科学, 2020, 47(9): 169-174. https://doi.org/10.11896/jsjkx.190800060
[15]	袁得嵛, 章逸钒, 高见, 孙海春. 基于用户特征提取的新浪微博异常用户检测方法 Abnormal User Detection Method in Sina Weibo Based on User Feature Extraction 计算机科学, 2020, 47(6A): 364-368. https://doi.org/10.11896/JsJkx.190700008

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed