基于出行模式子图的城市功能区域发现方法
|
摘要
城市的功能区域是指在城市的发展过程中逐渐形成的功能(如工业、商业、居住、教育等)相对固定的地理区域。这些区域间的位置结构影响着城市中居民的出行模式,与此同时,城市居民的出行模式也客观地反映了城市不同区域的真实的功能定位。文中以出租车运行轨迹数据为基础,研究城市居民的出行模式,并根据所得模式实现城市功能区域的自动化发现。主要思路及贡献包括:1)使用车辆轨迹及路网结构数据构造区域模式图(region pattern graph)结构,并提出区域模式图构建算法,采用图结构将城市的不同地理区域连接起来;2)提出自底而上的功能区域发现算法(Bottom-Up Functional Region Discovering,BUFRD)框架及基本实现思路,包括提出频繁出行模式子图挖掘算法,发现区域模式图中频繁出现的出行模式;3)提出功能区域聚类算法,聚类已获取的出行模式子图集,并最终实现城市功能区域的发现。实验结果表明,通过所提方法发现的城市功能区域较传统方法所得结果的功能纯度更高,其熵值比传统方法降低了至少10%。
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 regions affect 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 according 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%.
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 regions affect 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 according 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%.
引文
[1] FURLETTI B,CINTIA P,RENSO C,et al.Inferring human activities 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 functional 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 different functions 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 human mobility 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].ACM Transactions on Intelligent Systems and Technology(TIST),2015,6(3):1-41.
[12]YAN X,HAN J.gspan:Graph-based substructure pattern mining[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 Conference on Management of Data.ACM,2013:337-348.
[15]VISHWANATHAN S V N,BORGWARDT K M,KONDOR R,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]GAZERE 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.3Dshape 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 Netherlands.1997.
[26]ROSENFELD A,DAVIS LS.A Note on Thinning[J].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 Satellite: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[C]∥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.
[2] YUAN N J,ZHENG Y,XIE X,et al.Discovering urban functional 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 different functions 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 human mobility 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].ACM Transactions on Intelligent Systems and Technology(TIST),2015,6(3):1-41.
[12]YAN X,HAN J.gspan:Graph-based substructure pattern mining[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 Conference on Management of Data.ACM,2013:337-348.
[15]VISHWANATHAN S V N,BORGWARDT K M,KONDOR R,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]GAZERE 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.3Dshape 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 Netherlands.1997.
[26]ROSENFELD A,DAVIS LS.A Note on Thinning[J].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 Satellite: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[C]∥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.