Algorithm for Trajectory Movement Pattern Mining Based on Semantic Space Anonymity

doi:10.3969/j.issn.1671-1122.2018.08.005

Abstract

Abstract:

Aiming at the mining user movement patterns using trajectory data in offline scenario to leaks the privacy problems of the user sensitive location, using the geographic spatial distribution of points of interest, an anonymous trajectory-based moving pattern mining algorithm based on semantic space is proposed to defend against attacker map matching attacks or semantic inference attacks while implementing user mobility patterns mining. The algorithm first uses grid division technology to divide the urban area into uniform grids to generate grid areas. Then use the location distribution and semantic difference degree of the interest points in the grid area to spatially annotate the trajectory stay points to satisfy the (k,l) privacy model. Finally, the idea of mining PrefixSpan algorithm based on classical model mining is used to mine frequent moving patterns of anonymous trajectory datasets. Theoretical analysis and simulation experiments verify the security and effectiveness of the algorithm. Compared with MCSPP, an existing space-based anonymous trajectory moving pattern mining algorithm, this algorithm not only reduces the average information loss degree, but also has a higher spatial interpretation of the frequent movement patterns of mining.

Key words: trajectory, stay point, points of interest, (k, l) privacy model, movement pattern mining

CLC Number:

TP309

Kaizhong ZUO, Jian TAO, Haiyan ZENG, Liping SUN. Algorithm for Trajectory Movement Pattern Mining Based on Semantic Space Anonymity[J]. Netinfo Security, 2018, 18(8): 34-42.

Figures/Tables 14

References 21

[1]	FENG Zhenni, ZHU Yanmin. A Survey on Trajectory Data Mining: Techniques and Applications[EB/OL]. , 2016-4-13.
[2]	GUO Limin, HUANG Guangyan, GAO Xu, et al.DoSTra: Discovering Common Behaviors of Objects Using the Duration of Staying on Each Location of Trajectories[J]. Radiation Research, 2015, 161(2): 137-142.
[3]	HUANG Guangyan, HE Jing, ZHOU Wanlei, et al.Discovery of Stop Regions for Understanding Repeat Travel Behaviors of Moving Objects[J]. Journal of Computer & System Sciences, 2016, 82(4): 582-593.
[4]	SHEN Ying, ZHAO Ligang, FAN Jing.Analysis and Visualization for Hot Spot Based Route Recommendation Using Short-Dated Taxi GPS Traces[J]. Information, 2015, 6(2): 134-151.
[5]	MA Chunguang, ZHANG Lei, YANG Songtao.Review on Location Trajectory Privacy Protection[J]. Netinfo Security, 2015, 15(10): 24-31.
	马春光,张磊,杨松涛. 位置轨迹隐私保护综述[J]. 信息网络安全,2015,15(10):24-31.
[6]	KRUMM J.Inference Attacks on Location Tracks[C]//Springer. 5th International Conference on Pervasive computing, May 13-16, 2007, Toronto, Canada. Heidelberg: Springer, 2007: 127-143.
[7]	CHEN Hongsong, HAN Zhi, DENG Shuning.Analysis and Research on Big Data Security in Smart City[J]. Netinfo Security, 2015, 15(7): 1-6.
	陈红松,韩至,邓淑宁. 智慧城市中大数据安全分析与研究[J]. 信息网络安全,2015,15(7):1-6.
[8]	GIDOFALVI G, HUANG Xuegang, PEDERSEN T B. Probabilistic Grid-based Approaches for Privacy-preserving Data Mining on Moving Object Trajectories[EB/OL]. , 2017-11-10.
[9]	JURECZEK P L, KOZIERKIE A.A Privacy-preserving Framework for Mining Continuous Sequences in Trajectory Systems[C]//IEEE. 2014 European Network Intelligence Conference, September 29-30, 2014, Wroclaw, Poland. New Jersey: IEEE, 2014: 52-58.
[10]	ZHOU Changli, MA Chunguang, YANG Songtao, et al.A Location Privacy Preserving Method Based on Sensitive Diversity for LBS[C]//Springer. 11th IFIP International Conference on Network and Parallel Computing (NPC), September 18, 2014, Taiwan, China. Heidelberg: Springer, 2014: 409-422.
[11]	SHARMA P, BALAKRISHNA G.PrefixSpan: Mining Sequential Patterns by Prefix-projected Pattern[J]. International Journal of Computer Science & Engineering Survey, 2012, 2(4): 111-122.
[12]	GIANNOTTI F, NANNI M, PINELLI D, et al.Trajectory Pattern Mining[C]//ACM. 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 12-15, 2007, San Jose, California. New York: ACM, 2007: 330-339.
[13]	ZHANG Chao, HAN Jiawei, SHOU Llidan, et al.Splitter: Mining Fine-grained Sequential Patterns in Semantic Trajectories[J]. VLDB Endowment, 2014, 7(9):769-780.
[14]	CHEN C C, KUO C H, PENG W C.Mining Spatial-temporal Semantic Trajectory Patterns from Raw Trajectories[C]//IEEE. 2015 IEEE International Conference on Data Mining Workshop, November 14-17, 2015, Atlantic City, NJ, USA. New Jersey: IEEE, 2015: 1019-1024.
[15]	WANG Liang, HU Kunyuan, KU Tao, et al.Mining Urban Moving Trajectory Patterns Based on Multi-scale Space Partition and Road Network Modeling[J]. Acta Automatica Sinica, 2015, 41(1): 47-58.
	王亮,胡琨元,库涛,等. 基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘[J].自动化学报,2015,41(1):47-58.
[16]	HUO Zheng, MENG Xiaofeng, HU Haibo, et al.You Can Walk Alone: Trajectory Privacy-preserving through Significant Stays Protection[C]//Springer.17th International Conference on Database Systems for Advanced Applications, April 15-18, 2012, Busan, South Korea. Heidelberg: Springer, 2012: 351-366.
[17]	CHEN Rui, FUNG B C M, MOHAMMED N, et al. Privacy-preserving Trajectory Data Publishing by Local Suppression[EB/OL]. , 2017-10-11.
[18]	WANG Jiabo, ZHAO Zemao, LI Lin.A Method of Trajectory Privacy Protection in Location-based Service Based on Dummies[J]. Netinfo Security, 2014, 14(3): 62-67.
	王家波,赵泽茂,李林. 位置服务中一种基于假轨迹的轨迹隐私保护方法[J]. 信息网络安全,2014,14(3):62-67.
[19]	LV Mingqi, CHEN Ling, XU Zhenxing, et al. The Discovery of Personally Semantic Places Based on Trajectory Data Mining[EB/OL]. , 2017-10-11.
[20]	YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al.T-drive: Driving Directions Based on Taxi Trajectories[C]//ACM. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, November 2-5, 2010, San Jose, California. New York: ACM, 2010: 99-108.
[21]	Datatang. Avalible Online[EB/OL]. , 2016-1-13.