计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 23-27.doi: 10.11896/j.issn.1002-137X.2019.08.004

• 大数据与数据科学* • 上一篇    下一篇

基于轨迹划分与密度聚类的移动用户重要地点识别方法

杨震, 王红军   

  1. (国防科技大学电子对抗学院 合肥230037)
  • 收稿日期:2018-07-27 出版日期:2019-08-15 发布日期:2019-08-15
  • 通讯作者: 王红军(1968-),男,博士,教授,主要研究方向为移动通信网、认知电子战,E-mail:hongjun-wang@163.com
  • 作者简介:杨震(1994-),男,硕士生,主要研究方向为聚类分析、轨迹预测,E-mail:eei_yz@163.com
  • 基金资助:
    国家自然科学基金(61273302)

Important Location Identification of Mobile Users Based on Trajectory Division and Density Clustering Method

YANG Zhen, WANG Hong-jun   

  1. (Electronic Countermeasures College,National University of Defense Technology,Hefei 230037,China)
  • Received:2018-07-27 Online:2019-08-15 Published:2019-08-15

摘要: 移动用户轨迹数据作为新兴的空间轨迹数据,可用于分析个体或群体的行为特征、兴趣爱好,在智慧城市、交通规划和反恐维稳等领域应用广泛。为了从庞大的数据集中识别出移动用户的重要地点,提出了一种基于转角偏移度与距离偏移量的轨迹划分算法。该算法首先通过轨迹划分提取出用户的重要地点候选集,然后采用一种改进的密度聚类算法进一步对用户的候选重要地点实现聚类,从而识别出用户的最终重要地点。在Geolife轨迹数据集与Foursquare用户签到数据集上的实验表明,采用轨迹划分与密度聚类相结合的重要地点识别方法具有比现有的重要地点识别方法更高的准确率,证明了所提方法的可行性与优越性。

关键词: 轨迹划分, 密度聚类, 移动用户, 重要地点

Abstract: As emerging spatial trajectory data,mobile user trajectory data can be used to analyze individual or group behavioral characteristics,hobbies and interests,and are widely used in smart cities,transportation planning,and anti-terrorism maintenance.In order to identify the important locations of mobile user from a huge data set,this paper proposed a trajectory division method based on the angle and distance offset.The method firstly extracts the important locations candidate set by trajectory division,and then further clusters the important locations through an improved density clustering algorithm,extracting the final important location of user.The experiment on Geolife trajectory data set and Foursquare data set shows that the important location identification method combining trajectory division and density clustering has higher accuracy than other existing important location identification method,which proves the feasibility and superiority of the proposed method

Key words: Density clustering, Important locations, Mobile user, Trajectory division

中图分类号: 

  • TP181
[1]MENG X X.Research on Location based Mobile Information Service [D].Changsha:University of Defense Technology,2013.(in Chinese) 孟祥旭.基于位置的移动信息服务技术与应用研究[D].长沙:学技术大学,2013.
[2]YUAN J,ZHENG Y,XIE X,et al.T-Drive:Enhancing Driving Directions with Taxi Drivers’ Intelligence[J].IEEE Transactions on Knowledge & Data Engineering,2013,25(1):220-232.
[3]ZHENG Y,XIE X,MA W Y.GeoLife:A Collaborative Social Networking Service among User,Location and Trajectory[J].Bulletin of the Technical Committee on Data Engineering,2010,33(2):32-39.
[4]LU F,DUAN Y,ZHENG N.A Practical Route Guidance Approach Based on Historical and Real-time Traffic Effects[C]∥International Conference on Geoinformatics.IEEE,2009:1-6.
[5]YUAN J,ZHENG Y,XIE X.Discovering Regions of Different Functions in A City Using Human Mobility and POIs[C]∥ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.ACM,2012:186-194.
[6]SONG C,BARABASI A L.Limits of Predictability in Human Mobility[J].Science,2010,327(5968):1018-1021.
[7]ASHBROOK D,STARNER T.Using GPS to Learn Significant Locations and Predict Movement across Multiple Users[J].Personal & Ubiquitous Computing,2003,7(5):275-286.
[8]YANG P,ZHU T,WAN X,et al.Identifying Significant Places Using Multi-day Call Detail Records[C]∥2014 IEEE 26th International Conference on Tools with Artificial Intelligence (ICTAI).IEEE,2014:360-366.
[9]MONTOLIU R,BLOM J,GATICA-PEREZ D.Discovering Places of Interest in Everyday Life from Smartphone Data[J].Multimedia Tools and Applications,2013,62(1):179-207.
[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.ACM,2007:1-8.
[11]LIN K W,HSIEH M H,TSENG V S.A Novel Prediction-Based Strategy for Object Tracking in Sensor Networks by Mining Seamless Temporal Movement Patterns[J].Expert Systems with Applications,2010,37(4):2799-2807.
[12]WANG Z,BULUT E,SZYMANSKI B K.Distributed Energy-Efficient Target Tracking with Binary Sensor Networks[J].Acm Transactions on Sensor Networks,2010,6(4):1-32.
[13]KHALIL E A,ATTEA B A.Energy-Aware Evolutionary Routing Protocol for Dynamic Clustering of Wireless Sensor Networks[J].Swarm & Evolutionary Computation,2011,1(4):195-203.
[14]HE W,LI D Y,AN L F,et al.Regular Route Mining Algorithm Based on GPS Trajectories [J].Journal of Jilin University (Engineering and Technology Edition),2014,44(6):1764-1770.(in Chinese) 何雯,李德毅,安利峰,等.基于GPS轨迹的规律路径挖掘算法[J].吉林大学学报(工学版),2014,44(6):1764-1770.
[15]KREVELD M V,LUO J.The Definition and Computation of Trajectory and Sub-trajectory Similarity[C]∥ACM InternationalSymposium on Geographic Information Systems,Acm-Gis 2007.Seattle,Washington,Usa,DBLP,2007:1-4.
[16]YUAN G,XIA S X,ZHANG L,et al.Trajectory Clustering Algorithm Based on Structural Similarity [J].Journal on Communications,2011,32(9):103-110.(in Chinese) 袁冠,夏士雄,张磊,等.基于结构相似度的轨迹聚类算法[J].通信学报,2011,32(9):103-110.
[17]KHETARPAUL S,CHAUHAN R,GUPTA S K,et al.Mining GPS Data to Determine Interesting Locations[C]∥International Workshop on Information Integration on the Web:in Conjunction with WWW.ACM,2011:1-6.
[18]YANG Z,WANG H J,ZHOU Y.A Clustering Algorithm by Adaptive Cut-off Distance and Cluster Centers [J].Data Analysis and Knowledge Discovery,2018,2(3):39-48.(in Chinese) 杨震,王红军,周宇.一种截断距离和聚类中心自适应的聚类算法[J].数据分析与知识发现,2018,2(3):39-48.
[19]ALEX R,ALESSANDRO L.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[20]ZHENG Y,ZHANG L,XIE X,et al.Mining Interesting Locations and Travel Sequences from GPS Trajectories[C]∥International Conference on World Wide Web.ACM,2009:791-800.
[21]ZHENG Y,LI Q,CHEN Y,et al.Understanding mobility based on GPS data[C]∥International Conference on Ubiquitous Computing.ACM,2008:312-321.
[22]ZHENG Y,XIE X,MA W Y.GeoLife:A Collaborative Social Networking Service among User,Location and Trajectory[J].Bulletin of the Technical Committee on Data Engineering,2011,33(2):32-39.
[23]YUAN Q,CONG G,MA Z,et al.Time-aware Point-of-Interest Recommendation[C]∥International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM,2013:363-372.
[24]POWERS D M.Evaluation:From Precision,Recall and F-mea- sure to ROC,Informedness,Markedness and Correlation[J].Journal of Machine Learning,2011,1(2):37-63.
[1] 吴善杰, 王新.
基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法
Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks
计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[2] 贾琳, 杨超, 宋玲玲, 程镇, 李琲珺.
改进的否定选择算法及其在入侵检测中的应用
Improved Negative Selection Algorithm and Its Application in Intrusion Detection
计算机科学, 2021, 48(6): 324-331. https://doi.org/10.11896/jsjkx.200400033
[3] 贾伟, 华庆一, 张敏军, 陈锐, 姬翔, 王博.
基于冲突度和协同过滤的移动用户界面模式推荐
Mobile User Interface Pattern Recommendation Based on Conflict Degree and Collaborative Filtering
计算机科学, 2018, 45(10): 202-206. https://doi.org/10.11896/j.issn.1002-137X.2018.10.037
[4] 杨旭华,朱钦鹏,童长飞.
基于Laplacian中心性的密度聚类算法
Density Clustering Algorithm Based on Laplacian Centrality
计算机科学, 2018, 45(1): 292-296. https://doi.org/10.11896/j.issn.1002-137X.2018.01.051
[5] 瞿原,邓维斌,胡峰,张其龙,王鸿.
基于Spark的点排序识别聚类结构算法
Algorithm for Ordering Points to Identify Clustering Structure Based on Spark
计算机科学, 2018, 45(1): 97-102. https://doi.org/10.11896/j.issn.1002-137X.2018.01.015
[6] 陈德华,韩学士,乐嘉锦,朱立峰.
面向临床检验指标的非同步时间序列聚类算法研究
Efficient and Effective Clustering Algorithm for Asynchronous Time Series of Clinical Laboratory Indicators
计算机科学, 2016, 43(9): 120-123. https://doi.org/10.11896/j.issn.1002-137X.2016.09.023
[7] 胡志冬,任永功,杨雪.
基于滑动窗口密度聚类的数据流偏倚采样算法
Bias Sampling Data Stream Based on Sliding Window Density Clustering Algorithm Research
计算机科学, 2013, 40(9): 254-256.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!