室内用户语义位置预测研究
|
摘要
位置预测技术可以提前预知用户下一时刻的位置,在基于位置的服务(Location-based Service,LBS)领域中发挥着极其重要的作用。现有的位置预测技术大多仅使用用户的地理轨迹,仅使用地理轨迹挖掘出来的用户移动模式易受地理特性的限制缺乏深层次的语义信息。本文基于某商场群体用户的室内轨迹数据和语义信息预测用户下一个时刻语义位置。语义位置预测包括停留区域识别、停留区域语义匹配、语义位置建模。在停留区域识别阶段,为减少室内停留时间不固定对停留区域识别的影响,本研究提出了一种新型的时空凝聚层次聚类算法(Spatial-Temporal Agglomerative Nesting,ST-AGNES),该算法具有思想简单、超参数少、自动生成聚类个数等优点。在语义匹配阶段,引入了吸引度规则,充分利用停留区域所有轨迹点与室内高密度的商铺名称信息做匹配。最后,采用长短型记忆神经网络模型(Long Short-Term Memory,LSTM)挖掘群体用户的语义位置模式并预测用户未来的语义位置,实验预测正确率达到61.3%。
The location prediction technology can predict the location of the user at the next moment in advance,and plays an extremely important role in the field of Location-based Service(LBS).Most of the existing location prediction techniques only use the geographical location information and time information of the user's historical trajectory. The geographic trajectory is composed of a series of geographically-pointed time-stamped latitude and longitude points, and the geographic trajectory only mines users. Mobile mode is limited by geographic features.In this paper, we propose a novel approach for predicting the next semantic location of a user's movement based on the geographic and semantic characteristics of the group user trajectory. The semantic location prediction based on group users generally consists of three steps: Firstly, the specific algorithm is used to identify the staying area in the user's trajectory; Next, the semantic matching algorithm is used to associate the user's staying area with the semantic information; Finally, Mining the semantic location pattern of group users, using this pattern to predict the semantic location of the user at the next moment. In the stage of staying area identification,in order to reduce the influence of indoor stay time unfixed on the recognition of stay area, this paper proposes a new type of spatial-temporal agglomerative nesting(ST-AGNES), which can automatically identify the number of staying areas in the user's trajectory using only the distance threshold. In the semantic matching stage, this paper proposes a semantic matching method based on attractance rules, which makes uses all trajectory points in the stay area to be associated with indoor high-density semantic information. In the final forecasting stage, this paper uses Long Short-Term Memory(LSTM) to mine the semantic location patterns of group users and predict the future semantic location of users. The experimental results have achieved a prediction accuracy rate of 61.3%.
The location prediction technology can predict the location of the user at the next moment in advance,and plays an extremely important role in the field of Location-based Service(LBS).Most of the existing location prediction techniques only use the geographical location information and time information of the user's historical trajectory. The geographic trajectory is composed of a series of geographically-pointed time-stamped latitude and longitude points, and the geographic trajectory only mines users. Mobile mode is limited by geographic features.In this paper, we propose a novel approach for predicting the next semantic location of a user's movement based on the geographic and semantic characteristics of the group user trajectory. The semantic location prediction based on group users generally consists of three steps: Firstly, the specific algorithm is used to identify the staying area in the user's trajectory; Next, the semantic matching algorithm is used to associate the user's staying area with the semantic information; Finally, Mining the semantic location pattern of group users, using this pattern to predict the semantic location of the user at the next moment. In the stage of staying area identification,in order to reduce the influence of indoor stay time unfixed on the recognition of stay area, this paper proposes a new type of spatial-temporal agglomerative nesting(ST-AGNES), which can automatically identify the number of staying areas in the user's trajectory using only the distance threshold. In the semantic matching stage, this paper proposes a semantic matching method based on attractance rules, which makes uses all trajectory points in the stay area to be associated with indoor high-density semantic information. In the final forecasting stage, this paper uses Long Short-Term Memory(LSTM) to mine the semantic location patterns of group users and predict the future semantic location of users. The experimental results have achieved a prediction accuracy rate of 61.3%.
引文
[1]Wu F,Fu K,Wang Y,et al.A spatial-temporal-semantic neural network algorithm for location prediction on moving objects[J].Algorithms,2017,10(2):37.
[2]谭娟,王胜春.基于深度学习的交通拥堵预测模型研究[J].计算机应用研究,2015,32(10):2951-2954.[Tan J,Wang S C.Research on prediction model for traffic congestion based on deep learning[J].Application Research of Computers,2015,32(10):2951-2954.]
[3]Ying J C,Lee W C,Weng T C,et al.Semantic trajectory mining for location prediction[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems,2011:34-43.
[4]Sabarish B A,Karthi R,Gireeshkumar T.A survey of location prediction using trajectory mining[M].Springer India,2015:119-127.
[5]Liu J,Wolfson O,Yin H.Extracting semantic location from outdoor positioning systems[C].MDM2006 workshop MCISME,2006.
[6]Jeung H,Liu Q,Shen H T,et al.A hybrid prediction model for moving objects[C].IEEE International Conference on Data Engineering,2008:70-79.
[7]Ye Y,Zheng Y,Chen Y,et al.Mining individual life pattern based on location history[C].Tenth International Conference on Mobile Data Management:Systems,Services and MIDDLEWARE,2009:1-10.
[8]Morzy M.Mining frequent trajectories of moving objects for location prediction[C].International Conference on Machine Learning and Data Mining in Pattern Recognition,2007:667-680.
[9]Zheng Y,Zhang L,Ma Z,et al.Recommending friends and locations based on individual location history[J].Acm Transactions on the Web,2011,5(1):5.
[10]Alvares L O,Bogorny V,Kuijpers B,et al.A model for enriching trajectories with semantic geographical information[C].ACM International Symposium on Advances in Geographic Information Systems,2007:22.
[11]窦丽莎,曹凯.出行者子停留语义推断模型框架[J].山东理工大学学报(自然科学版),2012,26(6):17-22.[Dou L S,Cao K.A model framework for inferring sub-stays semantics of traveler[J].Journal of Shandong University of Technology(Natural Science Edition),2012,26(6):17-22.]
[12]齐凌艳,陈荣国,温馨.基于语义轨迹停留点的位置服务匹配与应用研究[J].地球信息科学学报,2014,16(5):720-726.[Qi L Y,Chen R G,Wen X.Research on the LBSmatching based on stay point of the semantic trajectory[J].Journal of Geo-information Science,2014,16(5):720-726.]
[13]Li Q,Zheng Y,Xie X,et al.Mining user similarity based on location history[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems,2008:34.
[14]宋路杰,孟凡荣,袁冠.基于Markov模型与轨迹相似度的移动对象位置预测算法[J].计算机应用,2016,36(1):39-43.[Song L J,Meng F R,Yuan G.Moving object location prediction algorithm based on markov model and trajectory similarity[J].Journal of Computer Applications,2016,36(1):39-43.]
[15]彭曲,丁治明,郭黎敏.基于马尔可夫链的轨迹预测[J].计算机科学,2010,37(8):189-193.[Peng Q,Ding Z M,Guo L M.Prediction of trajectory based on markov chains[J].Computer Science,2010,37(8):189-193.]
[16]林树宽,李昇智,乔建忠,等.基于用户移动行为相似性聚类的Markov位置预测[J].东北大学学报(自然科学版),2016,37(3):323-326.[Lin S K,Li S Z,Qiao J Z,et al.Markov location prediction based on user mobile behavior similarity clustering[J].Journal of Northeastern University(Natural Science),2016,37(3):323-326.]
[17]张心悦,王光霞,吴月,等.室内用户语义位置模式挖掘研究--以商场为例[J].测绘与空间地理信息,2016,39(2):12-16.[Zhang X Y,Wang G X,Wu Y,et al.Research on semantic location pattern mining of indoor users:Take shopping malls as an example[J].Geomatics&Spatial Information Technology,2016,39(2):12-16.]
[18]Ester M,Kriegel H P,Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C].International Conference on Knowledge Discovery and Data Mining,1996:226-231.
[19]Zheng Y,Zhang L,Xie X,et al.Mining interesting locations and travel sequences from GPS trajectories[C].International Conference on World Wide Web,2009:791-800.
[20]Birant D,Kut A.ST-DBSCAN:An algorithm for clustering spatial-temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.
[21]Leiva L A.Vidal E.Warped K-Means:An algorithm to cluster sequentially-distributed data[M].Elsevier Science Inc.,2013:196-210.
[22]唐建波,邓敏,刘启亮.时空事件聚类分析方法研究[J].地理信息世界,2013(1):38-45.[Tang J B,Deng M,Liu Q L.On spatio-temporal events clustering methods[J].Geomatics World,2013(1):38-45.]
[23]马春来,单洪,李志,等.移动用户下一地点预测新方法[J].浙江大学学报(工学版),2016,50(12):2371-2379.[Ma CL,Shan H,Li Z,et al.New next place prediction method for mobile users[J].Journal of ZheJiang University(Engineering Science),2016,50(12):2371-2379.]
[2]谭娟,王胜春.基于深度学习的交通拥堵预测模型研究[J].计算机应用研究,2015,32(10):2951-2954.[Tan J,Wang S C.Research on prediction model for traffic congestion based on deep learning[J].Application Research of Computers,2015,32(10):2951-2954.]
[3]Ying J C,Lee W C,Weng T C,et al.Semantic trajectory mining for location prediction[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems,2011:34-43.
[4]Sabarish B A,Karthi R,Gireeshkumar T.A survey of location prediction using trajectory mining[M].Springer India,2015:119-127.
[5]Liu J,Wolfson O,Yin H.Extracting semantic location from outdoor positioning systems[C].MDM2006 workshop MCISME,2006.
[6]Jeung H,Liu Q,Shen H T,et al.A hybrid prediction model for moving objects[C].IEEE International Conference on Data Engineering,2008:70-79.
[7]Ye Y,Zheng Y,Chen Y,et al.Mining individual life pattern based on location history[C].Tenth International Conference on Mobile Data Management:Systems,Services and MIDDLEWARE,2009:1-10.
[8]Morzy M.Mining frequent trajectories of moving objects for location prediction[C].International Conference on Machine Learning and Data Mining in Pattern Recognition,2007:667-680.
[9]Zheng Y,Zhang L,Ma Z,et al.Recommending friends and locations based on individual location history[J].Acm Transactions on the Web,2011,5(1):5.
[10]Alvares L O,Bogorny V,Kuijpers B,et al.A model for enriching trajectories with semantic geographical information[C].ACM International Symposium on Advances in Geographic Information Systems,2007:22.
[11]窦丽莎,曹凯.出行者子停留语义推断模型框架[J].山东理工大学学报(自然科学版),2012,26(6):17-22.[Dou L S,Cao K.A model framework for inferring sub-stays semantics of traveler[J].Journal of Shandong University of Technology(Natural Science Edition),2012,26(6):17-22.]
[12]齐凌艳,陈荣国,温馨.基于语义轨迹停留点的位置服务匹配与应用研究[J].地球信息科学学报,2014,16(5):720-726.[Qi L Y,Chen R G,Wen X.Research on the LBSmatching based on stay point of the semantic trajectory[J].Journal of Geo-information Science,2014,16(5):720-726.]
[13]Li Q,Zheng Y,Xie X,et al.Mining user similarity based on location history[C].ACM Sigspatial International Conference on Advances in Geographic Information Systems,2008:34.
[14]宋路杰,孟凡荣,袁冠.基于Markov模型与轨迹相似度的移动对象位置预测算法[J].计算机应用,2016,36(1):39-43.[Song L J,Meng F R,Yuan G.Moving object location prediction algorithm based on markov model and trajectory similarity[J].Journal of Computer Applications,2016,36(1):39-43.]
[15]彭曲,丁治明,郭黎敏.基于马尔可夫链的轨迹预测[J].计算机科学,2010,37(8):189-193.[Peng Q,Ding Z M,Guo L M.Prediction of trajectory based on markov chains[J].Computer Science,2010,37(8):189-193.]
[16]林树宽,李昇智,乔建忠,等.基于用户移动行为相似性聚类的Markov位置预测[J].东北大学学报(自然科学版),2016,37(3):323-326.[Lin S K,Li S Z,Qiao J Z,et al.Markov location prediction based on user mobile behavior similarity clustering[J].Journal of Northeastern University(Natural Science),2016,37(3):323-326.]
[17]张心悦,王光霞,吴月,等.室内用户语义位置模式挖掘研究--以商场为例[J].测绘与空间地理信息,2016,39(2):12-16.[Zhang X Y,Wang G X,Wu Y,et al.Research on semantic location pattern mining of indoor users:Take shopping malls as an example[J].Geomatics&Spatial Information Technology,2016,39(2):12-16.]
[18]Ester M,Kriegel H P,Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C].International Conference on Knowledge Discovery and Data Mining,1996:226-231.
[19]Zheng Y,Zhang L,Xie X,et al.Mining interesting locations and travel sequences from GPS trajectories[C].International Conference on World Wide Web,2009:791-800.
[20]Birant D,Kut A.ST-DBSCAN:An algorithm for clustering spatial-temporal data[J].Data&Knowledge Engineering,2007,60(1):208-221.
[21]Leiva L A.Vidal E.Warped K-Means:An algorithm to cluster sequentially-distributed data[M].Elsevier Science Inc.,2013:196-210.
[22]唐建波,邓敏,刘启亮.时空事件聚类分析方法研究[J].地理信息世界,2013(1):38-45.[Tang J B,Deng M,Liu Q L.On spatio-temporal events clustering methods[J].Geomatics World,2013(1):38-45.]
[23]马春来,单洪,李志,等.移动用户下一地点预测新方法[J].浙江大学学报(工学版),2016,50(12):2371-2379.[Ma CL,Shan H,Li Z,et al.New next place prediction method for mobile users[J].Journal of ZheJiang University(Engineering Science),2016,50(12):2371-2379.]