Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (7): 155-163.doi: 10.11896/jsjkx.200800072

• Database & Big Data & Data Science • Previous Articles     Next Articles

Frequent Pattern Mining of Residents’ Travel Based on Multi-source Location Data

WU Cheng-feng, CAI Li, LI Jin, LIANG Yu   

  1. School of Software,Yunnan University,Kunming 650091,China
  • Received:2020-08-12 Revised:2020-09-19 Online:2021-07-15 Published:2021-07-02
  • About author:WU Cheng-feng,born in 1995,postgra-duate.Her main research interests include data mining and traffic big data analysis.(wuchengfeng@mail.ynu.edu.cn)
    CAI Li,born in 1975,Ph.D,associate professor,postgraduate supervisor.Her main research interests include data mining and data quality.
  • Supported by:
    National Natural Science Foundation of China(61663047).

PDF (PC)

819

Abstract: With the improvement of urbanization,the mining of frequent patterns for resident’s travel has become a hot topic.Most of existing studies have problems such as the lack of description of the purpose and significance for frequent travel patterns,and incomplete analysis for mining results.To address these issues,firstly,this paper proposes a novel mining method of residents’ frequent travel patterns (MMoRFTP).It divides the map into several different regions by using morphological image method,builds the travel model by using the fused multi-source location data,and identifies the city functions of each region by using topic model.Then,it transforms travel trajectories lacking semantic information into ones with regional and functional areas semantics,and constructs the travel pattern graph and label pattern graph with region as node and semantic trajectory as edge.Based on graph model construction,the MulEdge algorithm is proposed to mine the frequent association pattern of residents’ travel.In this paper,urban road network data,POI data,taxi GPS data and check-in data are used in the experiment.The results show that MMoRFTP has good performance,and the discovered frequent travel patterns can provide a decision-making basis for road planning,traffic management,commercial layout and so on.

Key words: City functional regions, Frequent pattern graph, Frequent pattern mining, Label graph, Multi-source location data

CLC Number: 

  • TP311.12
[1]MAO H H.Research on Person Trip Characteristics of Chinese Citizens [D].Beijing:Beijing University of Technology,2005.
[2]FENG T.Visual Analysis of Resident Trip Mode Based on Taxi OD Data[D].Wuhan:Wuhan university,2017.
[3]XIAO F,WANG Y,MEI Y N,et al.City Functional Region Discovery Algorithm Based on Travel Pattern Subgraph[J].Computer Science,2018,45(12):268-278.
[4]CHU D,SHEETS D,ZHAO Y,et al.Visualizing HiddenThemes of Taxi Movement with Semantic Transformation[C]//IEEE Pacific Visualization Symposium.2014:137-144.
[5]SUN G Z.Taxi Travel Demand Forecasting in Pick-up Hotspots Areas Based on GPS Trajectory Data[D].Beijing:Beijing Jiaotong University,2019.
[6]KOSTOV V,OZAWA J,YOSHIOKA M,et al.Travel Destination Prediction Using Frequent Crossing Pattern from Driving History[C]//Intelligent Transportation Systems.IEEE,2005:364-368.
[7]SAVAGE N S,NISHIMURA S,CHAVEA N E,et al.Frequent Trajectory Mining on GPS Data[C]//Proceedings of the Third International Workshop on Location & the Web.ACM,2010:3-7.
[8]COMITO C,FALCONE D,TALIA D,et al.Mining HumanMobility Patterns from Social Geo-Tagged Data[J].Pervasive and Mobile Computing,2016,33:91-107.
[9]YU W.Discovering Frequent Movement Paths from Taxi Tra-jectory Data Using Spatially Embedded Networks and Association Rules[J].IEEE Transactions on Intelligent Transportation Systems,2019,20(3):855-866.
[10]NIU X Z,NIU J J,SU D Z,et al.FP-Tree-Based Approach for Frequent Trajectory Pattern Mining[J].Journal of University of Electronic Science and Technology,2016(1):86-90,134.
[11]LEE I,CAI G,LEE K.Mining Points-of-Interest AssociationRules from Geo-tagged Photos[C]//Hawaii International Conference on System Sciences.IEEE,2013.
[12]ZHENG Y,LIU Y,YUAN J,et al.Urban Computing withTaxicabs[C]//International Conference on Ubiquitous Computing.ACM,2011:89.
[13]YAN X,HAN J.Discovery of Frequent Substructures[M]//Mining Graph Data.America:John Wiley & Sons,Inc.2006:97-115.
[14]HAN W S,LEE J,LEE J H.TurboISO:Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases[C]//ACM Sigmod International Conference on Management of Data.ACM,2013:337-348.
[15]YUAN N J,ZHENG Y,XIE X,et al.Discovering Urban Functional Zones Using Latent Activity Trajectories[J].IEEE Transactions on Knowledge and Data Engineering,2014,27(3):712-725.
[16]LI X F,MA D W,ZHAN Y J,et al.the Research on Algorithm of Image’s Erosion and Dilation[J].Imaging Techniques,2005(1):37-39.
[17]HAO Z B,HONG B R,HUANG Q C.Study of Coverage Path Planning Based on Grid-Map[J].Computer Application Research,2007,24(10):56-58.
[18]CAI L.Fusion and Mining of MULTI-Source Location Data[D].Shanghai:Fudan university,2020.
[19]BENTON A,DREDZE M.Deep Dirichlet Multinomial Regression[C]//Conference of the North American Chapter of the Association for Computational Linguistics:Human Language Technologies.2018:365-374.
[20]ULLMANN J R.An Algorithm for Subgraph Isomorphism [J].Journal of the ACM,1976,23(1):31-42.
[21]WENQ L.Efficient Techniques for Subgraph Mining and Query Processing[D].Singapore:Nanyang Technological University,2015.
[22]KURAMOCHI M,KARYPIS G.Finding Frequent Patterns in a Large Sparse Graph[J].Data Mining and Knowledge Discovery,2005,11(3):243-271.
[23]ZHOU L L,YE N.Digraph Frequent Subgraph Mining Based on gSpan[J].Journal of Nanjing University (Natural Science edition),2011,47(5):532-543.
[24]LEI K,HE W.Research on Software Defect Detection Method Based on Data Mining Technology[J].Electronic World,2012(15):112-114.
[25]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.
[26]YAN X,HAN J.Gspan:Graph-Based Substructure PatternMining[C]//2002 IEEE International Conference on Data Mi-ning,2002.IEEE,2002:721-724.
[27]HUAN J,WANG W,PRINS J.Efficient Mining of FrequentSubgraphs in the Presence of Isomorphism[C]//Third IEEE International Conference on Data Mining.IEEE,2003:549-552.
[28]YANG H G,SHEN D R,KOU Y,et al.Strongly Connected Components Based Efficient PPR Algorithms[J].Journal of Computer Science,2017,40(3):584-600.
[29]LI X T,LI J Z,GAO H.An Efficient Frequent Subgraph Mining Algorithm[J].Journal of software,2007(10):107-118.
[1] LEI Dong, WANG Tao and MA Yun-fei. Frequent Pattern Mining in Bit Stream Based on AC Algorithm [J]. Computer Science, 2017, 44(1): 128-133.
[2] DING Jian, HAN Meng and LI Juan. Review of Concept Drift Data Streams Mining Techniques [J]. Computer Science, 2016, 43(12): 24-29.
[3] GAO Ang,YANG Yang,WANG Yue-wei. New Algorithm Research for Mining Workflow Frequent Pattern [J]. Computer Science, 2009, 36(9): 231-233.
[4] HE Hai-Tao, ZHANG Shi-Ling （College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004）. [J]. Computer Science, 2008, 35(3): 200-202.
[5] . [J]. Computer Science, 2006, 33(9): 76-80.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.